[Scheduling in single CPU] FIFO, SJF, STCF, RR, MLFQ, Lottery, Stride, CFS

💡Scheduling이란?

멀티프로그래밍 시스템 (: 실행이 준비된 프로세스가 두 개 이상)에서, OS의 일부인 scheduler는 scheduling 알고리즘을 이용해 무엇을 실행할지 결정한다.

🚩

스케줄러는 아래와 같이 context switch가 일어나는 모든 순간 invoke되어 다음 실행할 프로세스를 결정한다.

   프로세스 생성/종료 후

   I/O에서 프로세스 block

   I/O 인터럽트 발생 

   timer 인터럽트 발생 (preemtive한 경우)  

 

✅스케줄링을 평가하는 metrics

turnaround time = 완수된 시점 - 도착한 시점 

response time = 처음으로 실행된 시점 - 도착한 시점 

fairness = first job이 완수되는 시간 / second job이 완수되는 시간

 

 

 

💡아주 기본적인 방식

 

✅FIFO(FCFS)

먼저 온 프로세스부터 실행한다. 

 

 

✅SJF: Shortest Job First

짧은 job부터 순서대로 실행한다.

 

- response time이 좋지 않음

 

 

✅STCF: Shortest Time-to-Completion First (= PSJF: Preemptive SJF)

SJF 방식에 preemption을 더한 방식이다.

preemption: 어떤 프로세스가 실행되는 도중 다른 새 프로세스가 도착했는데,

만약 새 프로세스가 기존 프로세스보다 remain time이 짧다면,

기존 프로세스를 중단하고 새 프로세스부터 실행함. 

 

 

- response time이 좋지 않음

- time slice의 길이에 따른 trade-off: time slice가 짧을수록 - response time은 좋지만, switching 비용이 커짐

 

 

✅RR: Round Robin

한 job을 time slice (= scheduling quantum)동안만 실행한 뒤 다음 job의 실행으로 넘어간다. 

이를 job들이 모두 완수될 때까지 한다.

 

 

- time slice는 timer interrupt period의 배수여야 한다.

- response time 좋음, fairness 좋음, turnaround time 나쁨

 

 

💡Multi-Level Feedback Queue

서로 다른 priority를 가진 여러 개의 queue가 있다.

 

- Optimize turnaround time → Run shorter jobs first

- Minimize response time

- 각 프로세스가 CPU를 점유하는 시간을 미리 알고 있을 필요가 없이, 현재의 프로세스들의 behavior만을 가지고 판단한다.

 

✅MLFQ의 Rules

▶Rule 1: If Priority(A) > Priority(B), A runs (B doesn’t).

▶Rule 2: If Priority(A) = Priority(B), A & B run in RR.

 

▶Rule 3: When a job enters the system (arrives), it is placed at the highest priority

 

▶Rule 4: Once a job uses up its time allotment at a given level (regardless of how many times it has given up the CPU), its priority is reduced(i.e., it moves down on queue).

- 시간 소진 시 priority가 낮은 queue로 내려가는것이, time slice가 아니라 own time allotment를 기준으로 함. → scheduler trickng 방지 

 

▶Rule 5: After some time period S, move all the jobs to the topmost queue. : Priority Boost

- 이게 없으면 Starvation 위험 발생

   : 만약 interactive job이 많은 경우, long running jobs들은 일반적으로 length가 짧은 interactive job에 치여 priority가 낮은 queue로 내려갈 수밖에 없어 결국 CPU를 거의 차지하지 못한다.

 

 

✅Examples

 

 

 

- Rule 4 없음 vs 있음

 

 

- Rule 5 없음 vs 있음

 

💡Proportional Share (Fair share)

 

Guarantee that each job obtain a certain percentage of CPU time.

※ ticket: 해당 프로세스에게 주어지는 리소스의 몫 (퍼센트)

- Not optimized for turnaround or response time

 

✅Lottery Scheduling: Randomized

winning ticket을 가진 프로세스를 실행한다.

 

- 프로세스 간 경쟁하는 기간이 길어질수록, 원하던 비율에 가까워진다.

- job의 길이가 길수록 fairness가 좋아짐

- 장점: no per-process state, effective(∵ randomized)

 

- example

Process A has 75 tickets: 0 ~ 74
Process B has 25 tickets: 75 ~ 99

 

 

 

✅Stride Scheduling: Deterministic

Stride = 어떤 큰 수 / 해당 프로세스가 가진 ticket의 개수

프로세스가 run할 때, 이 프로세스의 stride씩 pass값에 더한다.

그리고, 가장 작은 pass값을 가진 프로세스가 run하도록 선택받는다.

 

- 단점: 새 job이 들어오면 이것의 pass값은 0이므로 이것이 CPU를 독점하게 됨.

 

✅CFS: Completely Fair Scheduling (Linux Completely Fair Scheduling): Deterministic

Red-black tree 상의 가장 왼쪽 프로세스,

즉 가장 작은 vruntime을 가진 프로세스가 run하도록 선택되며,

이것은 dynamic timeslice동안 run한다.

 

- Linux의 현재 CPU 스케줄러 방식임.

 

 

nice value

-20 ~ +19 사이의 정수값

이를 통해 priority가 구현됨

 

 

weight

각각의 nice value는 각 weight에 매치된다.

 

 

vruntime

 

 

dynamic timeslice

 

sched_latency

일반적으로는 48ms로 설정됨

 

 

red-black tree

Balanced binary tree

실행 중인 & 실행 가능한 프로세스만 들어가있음

efficient structure.

안의 숫자는 vruntime임.