[OS] CPU Scheduling

1. CPU Scheduling Basics

Turnaround Time: 작업이 도착한 이후 끝나는데 까지 걸리는 평균 시간

Response Time: 작업이 처음으로 CPU를 할당받는데 까지 걸리는 평균 시간

 

A. FIFO (FCFS)

FIFO 방식으로 나이브하게 하는 스케쥴링.

 

B. SJF (Shortest Jobs First)

Non-preemptive 하게 현재 가장 짧은 job을 고른 후 실행.

C. STCF (Shortest Time-to-Completion First)

Preemptive 하게 현재 가장 짧게 남음 job을 고른 후 실행

D. RR (Round-Robin)

Time slice (이때, time slice (scheduling quantum) 는 timer interrupt period의 배수여야 한다. 당연하게도.) 마다 한번씩 프로세스를 스위칭해준다.

 

지금까지 위의 SJF, STCF 등은 job length를 미리 알고있다는 가정하에 있다. 이 가정은 비현실적이므로 현실적인 스케쥴러가 필요하다.

 

2. Multi-Level Feedback Queue (MLFQ)

MLFQ는 다음과 같이 정리할 수 있다.

1. 우선순위가 높은 큐에 있는 프로세스들을 round-robin식으로  처리한다. 큐에 해당하는 "time slice"으로 RR을 진행한다.
2. 그 큐에 해당하는 "time allotment"를 다쓰면 priority가 내려간다.
3. 새로운 job이 들어오는 경우 무조건 가장 우선순위가 높은 큐에 배치한다.
4. 특정 시간이 지날때 마다 모든 job을 가장 높은 우선순위를 가진 큐로 올려준다. (starvation 방지)

 

3. Proportional-Share Scheduling (Fair-Share Scheduling)

 

Proportional-share scheduling은 위의 스케쥴링 알고리즘들과 달리, turnaround time, response time을 최적화 하는 방식의 스케쥴링이 아니다. 대신, 모든 프로세스에 적당한 양의 CPU 사용 percentage를 배정하는 것을 목표로 하는 스케쥴링이다.

A. Lottery Scheduling

기본적으로 Lottery Scheduling은 tickets이라는 개념을 바탕으로 한다. 가지고 있는 ticket의 상대적인 양에 비례하는 확률로 CPU를 할당받는 것이다. 즉, 티켓을 많이 들고 있으면 상대적으로 당첨확률이 올라 CPU를 배정받을 확률이 높은 것이다.

 

Ticket Currency: User 별로 다른 ticket currency가 존재할 수 있음. 유저 A가 프로세스 a1, a2에게 500, 800 에 해당하는 티켓을 주면, 시스템은 이것을 User A에게 할당한 global ticket을 바탕으로 global currency에 맞게끔 변환하여 lottery scheduling을 진행

 

B. Linux Completely Fair Scheduler (CFS)

Fair-share scheduler의 일종으로 efficient, scalable 하다.

 

vruntime: process가 실행될때 마다 vruntime은 실행시간에 비례하게 증가한다. 스케쥴러는 vruntime이 가장 작은 프로세스를 스케쥴링한다.

sched_latency: scheduler가 이 시간만큼을 프로세스의 개수만큼으로 나눈 시간만큼마다 다른 프로세스를 스케쥴링 할지 고려하게된다. 물론 우선순위 (niceness 등)이 포함된 경우 가중치가 생길 것이다. 즉, 이 값은 time slice를 구하는데 사용된다.

niceness: 우선순위이다. -20 ~ +19의 값을 가지며, niceness가 작을수록 우선순위가 높아져 더 큰 time slice를 가지게 된다. niceness의 값에 해당되는 가중치에 따라 상대적으로 sched_latency로 time slice가 정해지고, vruntime 또한 실제 runtime에서 가중치의 역수에 해당하는 정도로 늘게 된다. 즉, 결과적으로 가중치에 비례하는 cpu time을 가지게 된다.

 

CFS Red-Black Tree

vruntime이 가장 작은 프로세스를 찾기위해 BBST인 레드-블랙 트리를 사용한다. runnable 한 프로세스들을 레드-블랙 트리에 넣어놓고 대부분의 연산을 logN의 시간으로 처리한다.