프로그램 실행과 관련된 몇 가지 기계어 명령

1. CPU 내에서 수행되는 명령
   • ex. Add 명령
   • 수행속도가 매우 빠름
2. 메모리 접근을 필요로 하는 명령
   • ex. Load, Store 명령
   • CPU 내에서 수행되는 명령보다는 오래 걸리지만 비교적 짧은 시간에 수행할 수 있는 명령

   ⇒ 1,2는 사용자 프로그램이 직접 실행할 수 있는 일반명령에 해당

3. 입출력을 동반하는 명령
   • 오랜 시간 소요
   • 모두 특권명령으로 규정되어 있음

CPU 버스트와 I/O 버스트

• CPU 버스트 : 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계

• I/O 버스트 : I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계

• I/O 바운드 프로세스 : I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
  • 주로 사용자로부터 인터랙션을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램
• CPU 바운드 프로세스 : I/O 작업을 거의 하지 않아 CPU 버스트가 길게 나타나는 프로세스
  • 프로그램 수행의 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램

⇒ 이와 같이 상이한 CPU 사용패턴이 존재하기 때문에 CPU 스케줄링이 필요함!
⇒ CPU 스케줄링 시 I/O 바운드 프로세스 (CPU 버스트가 짧은 프로세스) 의 우선순위를 높여주는 것이 바람직함 (대화형 프로세스의 빠른 응답성 제공과 I/O 장치의 효율성을 높이기 위해)

CPU 스케줄러

• CPU 스케줄러 : 준비 큐의 프로세스들 중 누구에게 CPU를 할당할지 결정하는 운영체제 코드
• CPU 스케줄링이 필요한 경우
  1. ✅ 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
  2. 🚫 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
  3. 🚫 I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 끝나 인터럽트가 발생하고 그 결과 프로세스의 상태가 준비 상태로 바뀌는 경우
  4. ✅ CPU에서 실행상태에 있던 프로세스가 종료되는 경우

  ⇒ 1, 4는 비선점형 스케줄링✅ / 2, 3은 선점형 스케줄링🚫

• CPU 스케줄링 방식

1. ✅ 비선점형(nonpreemptive) 방식
   • CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 방법
2. 🚫 선점형(preemptive) 방식
   • 프로세스가 CPU를 계속 사용하기 원하더라도 강제로 빼앗을 수 있는 방법
   • CPU 할당시간을 부여한 후 타이머 인터럽트를 방생시키는 방법으로 CPU를 빼앗음

디스패처

• 디스패처 : 새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드
• 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 프로세스에게 CPU 넘기는 과정 수행
• 새로운 프로세스의 문맥을 복원시킨 후에는 시스템의 상태를 사용자모드로 전환해 사용자 프로그램에게 CPU의 제어권을 넘김
• 디스패치 지연시간 : 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간

스케줄링의 성능 평가

1. 시스템 관점의 지표

   • CPU 이용률 (CPU utilization) : 전체 시간 중에서 CPU가 일을 한 시간의 비율

     전체 시간 중 주방장이 일한 시간의 비율

   • 처리량 (throughput) : 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지 (CPU 버스트를 완료한 프로세스의 개수), CPU의 서비스를 원하는 프로세스 중 몇 개가 원하는 만큼 CPU를 사용하고 이번 CPU 버스트를 끝내어 준비 큐를 떠났는지 측정한 것 ⇒ 처리량을 높이기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리

     주방장이 주어진 시간 동안 몇 명의 손님에게 요리를 만들어주었는지

2. 사용자 관점의 지표

   • 소요시간 (turnaround time) : 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간, 준비큐에서 기다린 시간 + 실제로 CPU를 사용한 시간

     손님이 중국집에 들어와서 주문한 음식을 다 먹고 나가기까지 소요된 총 시간

   • 대기시간 (waiting time) : CPU 버스트 기간 중 준비 큐에서 CPU를 얻기 위해 기다린 시간, 이번 CPU 버스트가 끝나기까지 준비 큐에서 기다린 시간의 합

     음식을 먹은 시간을 제외한 순수하게 기다린 시간 음식이 조금씩 여러번 나왔다면 각각의 음식이 나오기까지 기다린 시간의 합

   • 응답시간 (response time) : 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간, 준비 큐에 들어온 직후부터 첫 번째 CPU를 얻기까지 걸린 시간 ⇒ 타이머 인터럽트가 빈번히 발생할수록 응답시간이 향상됨, 사용자 입장에서 가장 중요한 성능 척도

     최초의 음식이 나오기까지 기다린 시간

스케줄링 알고리즘

1. 선입선출 스케줄링 (First Come First Served : FCFS)

• 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식
• 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않음
• ex. 은행, 공항, 화장실 등
• ❌ 콘보이 현상(Convoy effect) : 잠깐만 사용하면 되는 프로세스는 앞의 긴 작업을 계속 기다려야 하기 때문에 평균 대기시간은 물론 I/O 장치들의 이용률까지 동반 하락

2. 최단작업 우선 스케줄링 (Shortest Job First : SJF)

• CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
• 평균 대기시간을 가장 짧게 하는 최적 알고리즘
  1. 비선점형 방식 : 일단 CPU를 획득하면 자진반납할 때까지 빼앗지 않음
  2. 선점형 방식 (Shortest Remaining Time First : SRTF) : 할당받아도 더 짧은 프로세스가 도착할 경우 빼앗아 더 짧은 프로세스에게 부여, 일반적인 시분할 환경에서 평균 대기시간을 가장 많이 줄일 수 있는 방식
• ❌ 프로세스의 CPU 버스트 시간을 미리 알 수 없으므로 과거의 CPU 버스트 시간을 통해 CPU 버스트 시간을 예측한 뒤 예측치가 가장 짧은 프로세스에게 CPU 할당
• ❌ 기아 현상(starvation) : CPU 버스트가 긴 프로세스는 준비 큐에서 무한정 기다려야 하는 문제

3. 우선순위 스케줄링

• 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
• 우선순위는 우선순위값을 통해 표시, 작을수록 높은 우선순위
• 우선순위를 결정하는 지표로 CPU 버스트 시간을 사용하면 SJF 알고리즘과 동일한 의미
  1. 비선점형 방식 : 일단 CPU를 획득하면 자진반납할 때까지 빼앗지 않음
  2. 선점형 방식 : 할당받아도 우선순위가 더 높은 프로세스가 도착하면 CPU를 빼앗아 더 높은 프로세스에게 부여

• ❌ 기아 현상(starvation) : 우선순위가 낮은 프로세스는 CPU를 얻지 못한 채 계속 기다려야 함

  ⇒ 노화(aging) 기법 : 기다리는 시간이 길어지면 우선순위를 조금씩 높여 언젠가는 CPU를 할당받을 수 있게 해주는 방법

4. 라운드 로빈 스케줄링

• 시분할 시스템의 성질을 가장 잘 활용한 새로운 의미의 스케줄링 방식
• 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 특정 시간으로 제한하고 이 시간이 지나면 CPU를 빼앗음
• 할당 시간 : 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간
  • 할당시간 ⬆️ : FCFS와 같은 결과, CPU 버스트 시간이 매우 긴 프로세스가 모든 작업을 수행할 만큼 할당시간을 길게 설정하는 경우
  • 할당시간 ⬇️ : CPU를 사용하는 프로세스가 빈번하게 교체되어 문맥교환 오버헤드 발생
• 프로세스 n개, 할당시간 q인 경우, 모든 프로세스는 (n-1)q 시간 내에 적어도 한 번 CPU를 할당받을 수 있음
• ✅ 대화형 프로세스의 빠른 응답시간을 보장할 수 있음
• ✅ CPU 버스트 시간이 짧은 프로세스가 빨리 CPU를 얻을 수 있고, CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않도록 함 ⇒ 공정한 스케줄링 방식
• 일반적으로 SJF 방식보다 평균 대기시간을 길지만, 응답시간은 더 짧음
• 할당시간이 만료되면 타이머 인터럽트를 발생해 CPU 회수, CPU 버스트 시간이 할당시간보다 짧으면 사용완료 후 스스로 반납
• FCFS vs 라운드로빈
  • FCFS : 프로세스를 하나씩 끝내는 방식이므로, 평균 대기시간이나 평균 소요시간 측면에서 좋은 결과를 얻을 수 있지만 프로세스 간 대기시간이나 소요시간의 편차가 매우 크며, 평균 응답시간이 지나치게 길어지는 문제가 있음
  • 라운드로빈 : CPU를 조금씩 같이 쓰고 거의 동시에 끝나게 되어 대기시간이나 처리시간의 편차는 크지 않지만, 평균 대기시간과 평균 소요시간이 길어 비효율적

  ⇒ 동일한 CPU 버스트 시간을 가지는 프로세스들에 라운드 로빈 스케줄링을 적용하면 평균 대기시간과 평균 소요시간은 FCFS의 거의 두 배, 하지만 평균 응답시간은 더 짧음

5. 멀티레벨 큐

• 준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법, 즉 프로세스들이 한줄이 아닌 여러줄로 기다리는 것
• 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 분리
  • ex. 빠른 응답을 필요로 하는 대화형 작업과 그렇지 않은 작업을 분리
• 하나뿐인 CPU를 어느 줄에 먼저 스케줄링할 것인가 + 프로세스가 도착했을 때 어느 줄에 세울 것인가

1. 전위큐 (foreground queue) : 대화형 작업
   • 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용
2. 후위큐 (background queue) : 계산 위주의 작업
   • 응답시간이 큰 의미를 가지지 않기 때문에 FCFS 사용해 문맥교환의 오버헤드 줄임

• 큐 자체의 스케줄링 (어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링)
  1. 고정 우선순위 방식(fixed priority scheduling) : 큐에 고정 우선순위를 부여해 우선순위가 높은 큐 먼저 서비스
  2. 타임 슬라이스 방식(time sclice) : 각 큐에 CPU 시간을 적절한 비율로 할당 (80:20), 큐에 대한 기아 현상을 해소할 수 있는 방식

6. 멀티레벨 피드백 큐

• 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동가능하다는 점이 추가됨
• 프로세스들의 다양한 성격을 반영해 구현가능, 에이징(aging)을 이와 같은 방식으로 구현가능
• 멀티레벨 피드백 큐를 정의하는 파라미터들
  1. 큐의 수
  2. 각 큐의 스케줄링 알고리즘
  3. 프로세스를 상위큐로 승격시키는 기준
  4. 프로세스를 하위큐로 강등시키는 기준
  5. 프로세스가 도착했을 때 들어갈 큐를 결정하는 기준

• 과정

  
  • CPU 버스트가 긴 프로세스들은 처음 8만큼 CPU를 사용하고도 작업이 완료되지 않으면 > 16인 하위큐로 내려가서 줄서고 본인 차례가 되어 16만큼을 추가로 사용하고도 작업이 완료되지 않으면 > CPU를 오래 사용하는 계산 위주의 프로세스로 간주되어 최하위 큐로 이동해 FCFS 스케줄링을 적용

⇒ 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하고 작업시간이 긴 프로세스에 대해서는 문맥교환 오버헤드를 줄임

7. 다중처리기 스케줄링

• CPU가 여러 개인 시스템
• 프로세스를 준비큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내어가도록 함
• ex. 은행창구, 공항 체크인
• BUT 특정 CPU에서만 수행되어야 하는 프로세스가 있는 경우 복잡 (ex. 미용실) ⇒ 한 줄이 아니라 각 CPU 별로 줄 세우기
• 여러 줄로 줄 세우기 하는 경우 CPU 작업이 편중될 수 있어 로드 밸런싱 필요

1. 대칭형 다중처리 (symmetric multi-processing) : 각 CPU가 알아서 스케줄링 결정
2. 비대칭형 다중처리 (asymmetric multiprogramming) : 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지는 거기에 따라 움직임

8. 실시간 스케줄링

• 실시간 시스템 (real-time system)에서는 각 작업마다 주어진 데드라인이 있음

1. 경성 실시간 시스템 (hard real-time system)
   • 데드라인을 반드시 지켜야 함
   • 정해진 시간 안에 반드시 작업이 완료되도록 스케줄링
2. 연성 실시간 시스템 (soft real-time system)
   • 데드라인이 존재하기는 하지만, 지키지 못했다고 위험한 상황이 발생하지는 않음

• 실시간 환경에서의 스케줄링은 빠른 서비스도 중요하지만 데드라인 지키기가 더 중요함
• EDF (Earlist Deadline First) 스케줄링 : 데드라인이 얼마 남지 않은 요청 먼저 처리

스케줄링 알고리즘의 평가

1. 큐잉 모델 (queueing model)
   • 주로 이론가들이 수행하는 방식
   • 확률분포를 통해 프로세스들의 도착률과 CPU의 처리율을 입력값으로 주면 CPU의 처리량, 프로세스의 평균 대기시간 등을 구함
2. 시뮬레이션 (simulation)
   • 실제 시스템이 아니라 가상으로 CPU 스케줄링 프로그램을 작성한 후 프로그램의 CPU 요청을 입력값으로 넣어 어떤 결과 나오는지 확인하는 방법
3. 구현 및 실측 (implementation & measurement)
   • 이론가와 정반대인 구현가들이 수행하는 방식
   • 동일한 프로그램을 원래 커널과 CPU 스케줄러를 수정한 커널에서 수행시켜보고 실행시간 측정하여 알고리즘 성능평가