5. CPU Scheduling

CPU Scheduling

• 프로그램은 CPU burst와 I/O burst의 연속
• 혹은 프로그램의 특성상 CPU를 자주 사용하는 혹은 I/O를 많이 필요로 하는 프로그램이 있을 수 있음

• 여러 종류의 Job(=Process)이 섞여 있기 때문에 CPU 스케줄링이 필요
  • Interactive job에게 적절한 response 제공
  • CPU와 I/O 장치 등 시스템 자원을 효율적으로 사용

프로세스의 특성 분류

• I/O-bound process
  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
  • many short CPU bursts
• CPU-bound process
  • 계산 위주의 job
  • few very long CPU bursts

CPU Scheduler & Dispatcher

• CPU Scheduler
  • Ready 상태의 프로세스 중에서 어떤 프로세스에게 CPU를 줄지 고름
• Dispatcher
  • CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘김
  • 이 과정을 Context switch라고 함
• CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우
  1. Running -> Blocked(ex: I/O 요청 시스템 콜)
  2. Running -> Ready (ex: 할당 시간 만료로 timer interrupt)
  3. Blocked -> Ready (ex: I/O 완료 후의 Interrupt)
  4. Terminate
• 1, 4에서의 스케줄링은 non-preemptive(비선점)
• 다른 스케줄링은 preemptive(선점)

스케줄링 성능 척도

• 시스템 입장
  • CPU utilization(이용률)
    • keep the CPU as busy as possible
  • Throughput(처리량)
    • number of processes that complete their execution per time unit
• 프로세스 입장
  • Turnaround time(반환 시간)
    • amount of time to execute a particular process
  • Waiting time(대기 시간)
    • amount of time a process has been waiting in the ready queue
  • Response time(응답 시간)
    • amount of time it takes from when a request was submitted until the first response is produced(not output) for time-sharing env.
  • Waiting time은 프로세스가 대기했던 총 대기 시간, Response time은 프로세스가 최초로 CPU를 얻기까지의 시간

스케줄링 알고리즘

FCFS (First-Come First-Served)

• 현실 세계에서 보편적인 처리 과정
• 비선점(non-preemptive) 알고리즘이자, 효율적이지 않은 알고리즘
• Convoy effect: CPU를 짧게 쓰는 프로세스들이 CPU를 길게 쓰는 프로세스 뒤에 배치되는 것

SJF (Shortest Job First)

• 각 프로세스의 다음 번 CPU burst time을 가지고 스케줄링에 활용
• CPU burst time이 가장 짧은 프로세스를 가장 먼저 스케줄링
• Two schemes

• Non-preemptive: 일단 CPU를 잡으면 이번 CPU burst가 완료될 때 까지 CPU를 선점 당하지 않음

• Preemptive
  • 현재 수행 중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  • 이 방법을 Shortest-Remaining Time First(SRTF)라고도 부름
• Preemptive가 average waiting time이 더 짧음
• SJF is optimal
  • 주어진 프로세스들에 대해 Minimun average waiting time을 보장(가장 짧은 평균 대기 시간)
• SJF의 문제점
  • CPU 사용 시간이 긴 프로세스들에 대한 Starvation의 문제가 있음
  • 다음 CPU Burst time의 예측
    • 다음 번 프로세스의 CPU Burst time을 어떻게 예측할 것인가? (input data, branch ...)
      • 과거의 CPU Burst time을 이용해서 추정(exponential averaging)

Priority Scheduling

• A priority number is associated with each process
• highest priority를 가진 프로세스에게 CPU 할당
• SJF는 일종의 priority scheduling
• 문제
  • Starvation: low priority processes may never execute
• 해결 방안
  • Aging: as time progresses increase the priority of the process

Round-Robin

• 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
  • 일반적으로 10-100 milliseconds
• 할당 시간이 지나면 프로세스는 선점 당하고, ready queue의 제일 뒤에 가서 다시 줄을 섬
• n개의 프로세스가 ready queue에 있고, 할당 시간이 q time unit인 경우, 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻음
  • 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않음!
• Performance
  • q large -> FCFS
  • q small -> Context Switch 오버헤드가 커짐
• 극단적 예
  • 같은 수행 시간을 지닌 프로세스들을 짧은 Time quantum으로 쪼개면 긴 Waiting time, Turnaroun time을 지니게 되어 굉장히 비효율적이 될 수 있음
  • 어느 하나의 프로세스도 빨리 빠져나가지 못하고 계속 짧은 구간을 반복적으로 수행해야 하기 때문!

Multi-Level Queue

• Ready Queue를 여러 개로 분할
  • foreground(interactive)
  • background(batch - no human interaction)
• 각 Queue는 독립적인 스케줄링 알고리즘을 가짐
  • foreground - RR
  • background - FCFS
• Queue에 대한 스케줄링이 필요
  • Fixed priority scheduling
    • serve all from foreground then from background
    • possibility of Starvation
  • Time slice
    • 각 queue에 CPU time을 적절한 비율로 할당
    • 80% to foreground in RR, 20% to background in FCFS

Multi-Level Feedback Queue

• 프로세스가 다른 queue로 이동이 가능
• Aging을 이와 같은 방식으로 구현 가능
• Multilevel Feedback queue Scheduler를 정의하는 Parameters
  • Queue의 수
  • 각 Queue의 Scheduling Algorithm
  • 프로세스를 상위/하위 queue로 보내는 기준

Multiple-Processor Scheduling

• CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
• Homogeneous processor인 경우
  • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
• Load sharing
  • 일부 프로세서에 Job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 별개의 Queue를 두는 방법 vs. 공동 Queue를 사용하는 방법
• Symmetric Multiprocessing
  • 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric Multiprocessing
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고, 나머지 프로세서는 거기에 따름

Real-Time Scheduling

• Hard real-time systems
  • 정해진 시간 안에 반드시 끝내도록 스케줄링
• Soft real-time computing
  • 일반 프로세스에 비해 높은 우선순위를 갖도록 해야 함

Thread Scheduling

• Local Scheduling
  • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄링할지 결정
• Global Scheduling
  • Kernel level thread의 경우 일반 프로세스와 마찬가지로 Kernel의 단기 스케줄러가 어떤 thread를 스케줄링할지 결정

Algorithm Evaluation

• Queueing models
  • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산
• Implementation & Measurement
  • 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
• Simulation
  • 알고리즘을 모의 프로그램으로 작성 후, trace를 입력으로 하여 결과 비교
  • 다양한 Test case를 사용하여 돌려봐야 함