D-OS-Ch05ia-Completely_Fair_Scheduling

Completely Fair Scheduling (CFS)

Introduction

CFS 是 proportional share scheduling 的一種實作方式，其選擇新 task 的複雜度為 $O(1)$，加入新 task 的複雜度則為 $O(\log n)$

CFS 也是 Linux v2.5 後對 non-real-time scheduling 使用的 scheduling scheme

How it works?

Step 1: Choose which task to run next

選擇 vruntime 最小的 task 作為下一個要跑的 task

Step 2: Compute the next time slice for task chosen

利用後面會介紹的方法計算此 task 在這一輪可以在 CPU 上跑多久（time slice）

Step 3: Set timer

算好 time slice 後 kernel 會把 timer 設好

Step 4: Execute the current task

執行選中的 task

---

Implementation

Task Selection

CFS 維護一棵包含所有在 ready queue 的 task 的紅黑樹（red-black tree）作為 next task selection 的輔助資料結構，此樹以 virtual clock 做排列

每次選擇新的 task 就選紅黑樹最左下的 task 就好，而新的 task 進入 ready queue 就做一次紅黑樹的 insert

因為紅黑樹是 self-balance tree，所以拿極值的時間複雜度是 $O(1)$ 而 insert/remove 的時間複雜度是 $O(\log n)$

sched_latency

sched_latency 表明的是每個 task 每過多少時間至少會執行一次

Time Slice

$${\text{time slice}}_k=\frac{{\text{weight}}_k}{{\sum }_{i=0}^{n-1}{\text{weight}}_i}\cdot \text{sched\_latency}$$

每個 task 每次能執行的 time slice 是根據自己的權重比例做分配，並且因為每個 task 至少在 sched_latency 的時間內都要跑一次，所以所有 task 在一個循環中就一起分配一個 sched_latency

然而，如果 sched_latency = 48ms 而我們有 2000 個 task，那麼大部分的 task 執行時間都會小於 context switch latency，造成 CPU 大部分的時間都會因為 context switch 而閒置，所以我們引入了 min granularity 的概念來確保一個 time slice 的 lower bound

也就是如果 time slice 算出來時間小於 min granularity，那麼就會設為 min granulairty