CFS - Linux

CFS : Completely fair process scheduling in Linux

CFS는 매우 효율적인 방법으로, 모든 작업에 프로세서 자원을 공정하게 할당한다

---

A blocked process, A runnable process

• A blocked process : I/O event 등으로 작업이 중지됨, event가 완료될 때까지 기다림
• A runnable process : blocked 되지 않은 프로세스

Processor-bound, I/O bound process

• processor-bound는 cpu bound라고도 하고, compute bound라고도 한다.
• processor-bound process는 주로 runnable 하며 I/O bound는 주로 blocked 된다
• 스케줄러는, 이 두가지 유형의 프로세스의 요구를 균형 맞추어야 함

Classic Preemptive Scheduling (vs CFS)

• Unix
• fixed timeslice : 고정된 시간 할당, 특정 프로세스가 일을 다 못 끝내면 다시 스케줄됨.
• multitasking 지원
• multiple scheduling queue 포함, 프로세스 하나당 우선순위 존재

---

CFS

• fixed timeslices & explicit priorities
• target latency : 대기시간 같은 개념. 작을수록 좋음
  - target latency의 1/N slice를 각 task에 할당 (N은 task의 수)

ex) target latency = 20ms 일 때, task의 개수가 4개라면 각 task는 5ms의 timeslice를 얻음 

*timeslice : context switching 간격

• N은 가변적임. 몇몇 프로세스들은 block하거나, block되었던 프로세스들이 runnable하게 되기 때문 따라서 timeslice는 고정적이지 않다.

• minimum granularity란, process에 부과된 최소 timeslice이다. 따라서, minimum granularity가 timeslice보다 크면, 시스템은 과부화될 것

• context switch는 overhead를 불러일으킴 => CFS는 최소화하려고 함, virtual runtime(vruntime)을 추적해 먼저 실행시키도록 앞으로 가져옴

• CFS rescheduling 빈도 계산

target latency(TL)=  20ms
minimum granularity(MG) = 4ms

TL / MG = 20 / 4 = 5

=> 5개의 TASK 허용

만약 task가 5개라면 timeslice는 4ms
이것은 MG와 동일함. (task * MG) = 20ms마다 reschedule 될 것임

• interactive task : user input이 많음, I/O bound. 비교적 낮은 vruntime을 가짐 스케줄링 라인의 앞쪽으로 가게 될 것임

• SMP(Symmetrical multiprocessing) 지원
  - 같은 scheduling policy를 가진 processor가 아니면 따로 분리해서 생각
  

• scheduling group 형성 가능.
  - single vruntime을 가짐. (vruntime-sharing)
  

CFS Implementation

• O(log N) time (* N은 트리의 노드 수)
• runqueue
  전통적인 방법은 따르지 않음. (FIFO)
  time-ordered red-black tree
  모든 프로세서가 특정한 runqueue를 가짐
  vruntime 값에 의해 인덱싱
  왼쪽이 더 낮은 vruntime value
  먼저 실행된 task는 오른쪽으로 이동하여 트리의 왼쪽 구성 요소들에게 기회를 줌.

---

아래의 자료를 읽고 요약한 포스팅입니다

CFS: Completely fair process scheduling in Linux
By Marty Kalin
February 5, 2019.