[Week4] CPU Scheduling

CPU Scheduling

CPU Scheduling이 필요한 이유

• 여러 종류의 job(process)가 섞여 있기 때문에 Interactive job에게 적절한 response를 제공하고, 시스템 자원을 효율적으로 사용하기 위해 CPU Scheduling이 필요하다

 

프로세스의 특성 분류

• I/O-bound process: I/O에 많은 시간이 필요한 job, many short CPU bursts
• CPU-bound process: 게산 위주의 job, few very long CPU bursts

 

CPU Scheduler & Dispatcher

CPU Scheduler

• Ready 상태의 프로세스 중에서 CPU를 줄 프로세스를 고른다 (Short-term scheduler)

Dispatcher

• CPU 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다 (Context Switch)

CPU Scheduling이 필요한 경우

• Nonpreemptive (비선점형): 강제로 빼앗지 않고 자진 반납하는 경우
  • running -> blocked (ex. I/O 요청하는 시스템 콜), terminate
• Preemptive (선점형): 강제로 빼앗음
  • running -> ready (ex. 할당시간만료로 timer interrupt), blocked -> ready (ex. I/O 완료 후 interrupt)

 

CPU Scheduling Criteria (성능 척도)

System 측면

• CPU utilization: Keep the CPU as busy as possible
• Throughput: # of processes hat complete their execution per time unit

Process 측면

• Turnaround time: amount of time to execute a particular process
  • ATT (average Turnaround Time)
• 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 environment)
  
  

---

Scheduling Algorithm

FCFS (First-Come First-Service)

FCFS (First-Come First-Service)

• 프로세스가 도착한 순서대로 스케줄링

Convoy Effect

• short process behind long process

👉 프로세스의 도착 순서에 따라 편차가 너무 크다는 단점

 

SJF (Shortest-Job-First)

SJF (Shortest-Job-First)

• CPU burst time(CPU usage time)이 가장 짧은 프로세스를 먼저 스케줄
• 주어진 프로세스들에 대해 minimum average waiting time을 보장하지만 starvation 발생 가능
  • 계속해서 실행시간이 짧은 프로세스들이 들어온다면 상대적으로 실행시간이 긴 프로세스는 starvation 발생

Two Schemes

• Nonpreemptive: 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 않음
• Preemptive: 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
  • = SRTF: Shortest-Remaining-Time-First

다음 CPU Burst Time 예측

• 과거의 CPU burst time을 이용해서 추정 (estimate) 만 가능 👉 Exponential Averaging

 

Priority Scheduling

Priority Scheduling

• highest priority를 가진 프로세스에게 CPU 할당 (smallest integer == highest priority)
• priority number (integer) is associated with each process
• SJF는 일종의 priority scheduling이다
  • priority = predicted next CPU burst time

Priority Scheduling Problem

• starvation: low priority processes may never execute

Solution

• Aging: as time progresses increase the priority of the process

 

Round Robin (RR)

Roud Robin (RR)

• 각 프로세스는 동일한 크기의 할당 시간 (time quantum)을 가지고, 할당 시간이 지나면 프로세스는 선점 당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다. 👉 preemptive
• 어떤 프로세스도 $(n-1)q$ time unit이상 기다리지 않는다. ($n$개의 프로세스가 있고 할당 시간이 $q$ time unit인 경우
• 일반적으로 SJF 보다 average turnaround time이 길지만 response time은 더 짧다.

Performance

• $q$ large -> FIFO (First In First Out)
• $q$ small -> context switch 오버헤드가 커진다.

 

Multilevel Queue

Multilevel Queue

• ready queue를 여러개로 분할하고 각 큐는 독립적인 스케줄링 알고리즘을 가진다.
  • foreground (interactive) -> RR
  • background (batch - no human interaction) -> FCFS
• 큐에 대한 스케줄링이 필요하다
  • Fixed priority scheduling: foreground를 먼저 처리한 후에 background를 수행, starvation
  • Time slice: 각 큐에 CPU time을 적절한 비율로 할당

Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능
• Aging을 이와 같은 방식으로 구현할 수 있다.
• 필요한 파라미터
  • Queue의 수, 각 큐의 scheduling algorithm, process를 상위/하위 큐로 보내는 기준, 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

 

Multiple-Processor Scheduling

CPU가 여러개인 경우 스케줄링은 더욱 복잡해진다.

 

Homogeneous processor

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

Load sharing

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

Symmetric Multiprcessing (SMP)

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

Asymmetric multiprocessing

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

 

Real-Time Scheduling

Hard Real-time systems

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

Soft Real-time computing

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

 

Thread Scheduling

Local Scheduling

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

Global Scheduling

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

 

Algorithm Evaluation

Queueing models

• 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

Implementation & Mesaurement

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

Simulation

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