CPU Scheduling

 

이 포스트는 서울대학교의 '운영체제의 기초' 강의를 개인 학습용으로 작성한 포스트입니다.

 

 

 

* Preemptible resource : 한 프로세스가 점유한 상태에서 다른 프로세스에 양보할 수 있는 자원

* Non-preemptible resource : 한 프로세스가 점유하면 다른 프로세스에게 양보할 수 없는 자원

    -> 상황에 따라 다름

 

* CPU burst : 연속적으로 CPU 사용하는 단절된 구간

* I/O burst : I/O 완료 기다리며 block되는 구간

 

Scheduling Policy

Optimization Metrics

1. Throughput : 단위 시간에 수행을 종료시키는 process 개수

2. Turnaround time : 특정 프로세스를 수행하는데 걸리는 시간 (프로세스 종료시간 - 도착시간)

3. Waiting time : Ready queue에 있는 시간

4. Response time : Requeset ~ Output 시간

 

 

FIFO (FCFS)

한 프로세스가 점유하고 있으면 다른 프로세스는 기다려야 함

길이가 긴 프로세스가 앞에 있으면 비효율적

 

 

SJF (Shortest Job First)

optimal함

소요 시간을 미리 알아야 하기 때문에 구현 어려움

- Nonpreemptive : 순서를 미리 정해서 끝날 때까지 쭉감

- Preemptive : 태스크 종료될 때, 새로운 태스크 생성되거나 깨어날 때 remaing time보다 작으면 교체

 

* Exponential moving average

$\tau_{n+1} = \alpha t_n + (1-n)\tau_n$

$\tau$: 예측 값, $t$: CPU burst 실제 길이

 

 

Round Robin

time slice 지나면 queue 맨 뒤로 이동

 

Time slice 길 때 : FIFO에 가까워짐, CPU burst가 균질하면 좋음

Time slice 작을 때 : 오버헤드 커짐, CPU burst차이가 크면 좋음

 

* Adaptive scheduling : Workload 특성에 따라 time slice의 크기를 동적으로 바꿔주는 스케쥴링

 

 

MLFQ (Multi-Level Feedback Queue)

TS안에 burst가 끝나면 그대로, TS가 끝나도 burst가 남아 있으면 한 단계 아래로 강등 (낮은 우선순위로)

아래로 갈수록 TS 커지고, CPU bound process라는 뜻

 

 

* Priority based scheduling : 우선순위 높은 프로세스 먼저 수행 (Starvation 위험)

* Fair share scheduling : 대기 중인 프로세스에게 정해진 비율에 따라 CPU bandwidth 분배

* Rotating staircase deadline scheduler : queue의 맨 뒤로 가는게 아니라 deadline에 따라 queue 중간에 들어감

 

 

Scheduling 발전 역사

Shortest Remaining Time First

Round Robin

Multi Level Feedbacck Queue

Rotating Staircase Deadline Scheduler

CFS (Completely Fair Scheduler)