CPU 스케줄링

CPU 스케줄링의 기본개념#

CPU - I/O 버스트 사이클#

• 프로세스는 CPU - I/O Burst의 사이클로 구성된다.
• 일반적으로 짧은 CPU버스트를 가지고, I/O 중심의 프로그램들은 전형적으로 짧은 CPU버스트를 가진다.
• CPU 지향 프로그램은 다수의 긴 CPU버스트를 가질 수 잇다.
• 이러한 분포는 CPU 스케줄링을 구현할 때 매우 중요할 수 잇다.

선점(preemptive) 및 비선점(nonpreemptive) 스케줄링#

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (예를 들어 입출력 요청이 들어왔을 때)

   Running → Blocked

2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때 (예를 들어 인터럽트가 발생할 때)

   Running → Ready

3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때 (예를 들어 입출력 종료 시)

   Blocked → Ready

4. 프로세스가 종료할 때

   Terminate

디스패처#

• 문맥을 교환하는 일
• 사용자 모드로 전환하는 일
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일

스케줄링의 기준(= 성능척도)#

• CPU 이용률(utilization)

  • 우리는 가능한 한 CPU를 최대한 빠르게 유지하길 원한다.
  • CPU가 실제로 몇 퍼센트 이용되고 있는지를 판단하고, 이 이용률을 최대화 해야한다.
• 처리량(throughput)

  • CPU가 프로세스를 수행하느라 바쁘다면, 작업이 진행되고 있는 것이다.
  • 작업량 측정의 한 방법은 단위 시간당 완료된 프로세스의 개수로, 이를 처리량(throughput)이라 한다.
  • 주어진 시간동안 얼마나 많은 처리가 가능한것인가.
• 총 처리 시간(turnaround time)

  • 프로세스를 실행하는 데 소요된 시간
  • 프로세스의 제출 시간과 완료 시간의 간격을 총 처리 시간이라 한다.
  • 총처리 시간은 메모리에 들어가기 위해 기다리며 소비한 시간, Ready Queue에서 대기한 시간, CPU에서 실행하는 시간, 그리고 입출력 시간을 합한 시간
• 대기 시간(waiting time)

  • 대기 시간은 Ready Queue에서 대기하며 보낸 시간의 합
  • CPU 스케줄링 알고리즘은 프로세스가 실행하거나 입출력을 하는 시간의 양에 영향을 미치지 않는다.
• 응답 시간(response time)

  • 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간
  • 대화식 시스템에서, 총처리 시간은 최선의 기준이 아닐 수도 있습니다. 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간입니다. 응답 시간이라고 하는 이 기준은 응답이 시작되는 데까지 걸리는 시간이지, 그 응답을 출력하는 데 걸리는 시간이 아닙니다.

스케줄링 알고리즘#

선입 선출 스케줄링(First Come, First-Served Scheduling, FIFO)#

• 가장 간단한 스케줄링 알고리즘으로, 선입 선처리 스케줄링 방식이다.
• CPU를 먼저 요청하는 프로세스가 먼저 CPU를 할당받는다.
• 프로세스 처리 순서에 따라서 대기시간이 길어질 수도, 짧아질 수도있다.
• 때문에 비효율적인 대기가 계속될 수 있다.
• 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것을 호위 효과(Convoy Effect) 라고 한다.

최단 작업 우선 스케줄링(Shortest-Job-First Scheduling, SJF)#

• CPU 이용이 가능해지면 가장 작은 CPU 버스트를 가진 프로세스부터 할당한다.
• 평균 대기시간을 최소화하는 알고리즘으로 알려져 있음
• 비선점형 스케줄링 방식 - CPU를 잡으면 CPU 버스트가 완료될 때까지 선점 당하지 않음
• 선점형 스케줄링 방식 - 수행중인 프로세스의 남은 CPU 버스트 타임보다 짧은 프로세스가 도악하면 CPU를 빼앗긴다.
• SJF는 일종의 우선순위 스케줄링이다.

  • 문제점: 기아 상태(Starvation)가 발생할 수 있다.
  • 해결: 노화(Aging)을 이용해 오래된 프로세스는 우선순위를 높혀주어 해결한다.
• 다음번 CPU 버스트 시간을 어떻게 알 수 있는가?

  • 추정(Estimate)만이 가능하다.
  • 과거의 CPU 버스트 시간을 이용해서 추정한다. (Exponential Averaging)

우선순위 스케줄링(Priority Scheduling)#

• 특정 기준으로 프로세스에게 우선순위를 부여해 우선순위에 따라 프로세서에 할당한다.
• 프로세스를 에이징(Aging)해서 오래 대기한 프로세스의 우선순위를 높이는 방식으로 사용된다.
• SRF의 경우 남은 수행 시간을 기준으로 우선순위를 부여한다고 할 수 있다.
• 다른 스케줄링 알고리즘과 결합해 사용할 수 있으므로 선점, 비선점 모두 가능하다.
• 문제점: 기아 상태(Starvation)가 발생할 수 있다.
• 해결: 노화(Aging)을 이용해 오래된 프로세스는 우선순위를 높혀주어 해결한다.

라운드 로빈 스케줄링(Round-Robin Scheduling)#

• 일정 시간 할당량(Time quantum) 단위로 여러 프로세스를 번갈아가며 프로세서에 할당한다.
• 시스템의 time-sharing과 같은 방식이다.
• 반응성이 좋다.
• 시간 할당량에 따라 운영체제가 계속 개입하는 선점 스케줄링 방식이다.
• 다만 시간을 길게 준다면 FIFO와 다를것이 없고, 너무 짧게 준다면 문맥교환이 너무 자주 발생해 오버헤드가 커진다.

다단계 큐 스케줄링(Multilevel Queue Scheduling)#

• 우선순위 기준이 다른 분리된 큐들을 두어서, 그 우선순위에 맞게 스케쥴링을 하는 것이 훨씬 쉬울 것이다. 이러한 접근방법을 multilevel queue라 한다.
• 일반적으로 포그라운드(foreground, 대화형) 프로세스들과 백그라운드(background, 일괄처리) 프로세스들을 구분
• 포그라운드는 RR 알고리즘에 의해 스케줄링되고, 백그라운드는 FCFS 알고리즘에 의해 스케줄될 수 있다.

다단계 큐 피드백 스케줄링(Multilevel Feedback Queue Scheduling)#

• New Job이 Queue Q0으로 들어감
• CPU를 잡아서 할당시간 8ms 동안 수행됨
• 8ms 동안 다 끝내지 못하면 Q1으로 내려감
• Q1에서 기다리다가 CPU를 할당받아 16ms 동안 수행됨
• 그동안 끝내지 못할경우 Q2로 쫓겨남

멀티 프로세서 스케줄링#

• Homogeneouse Processor의 경우

  • Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
• Load Balancing

  • 일부 프로세서에 job이 물리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법
• Symmetric Multiprocessing (SMP)

  • 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric Multiprocessing

  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름

실시간 CPU 스케줄링#

• Hard real-time systems

  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
• Soft real-time computing

  • Soft real time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

스레드 스케줄링#

• Local Scheduling

  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
• Global Scheduling

  • Kernel level thread의 경우 일반 프로세스와 마찬 가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

알고리즘의 평가#

• Queueing models

  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
• Implementation(구현) & Measurement(성능 측정)

  • 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
• Simulation(모의 실험)

  • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교