# [Linux 核心設計: 不只挑選任務的排程器](https://hackmd.io/@sysprog/linux-scheduler) 閱讀筆記

## CPU scheduling 對系統的影響

本節說明如何評估一個 scheduling 的效能：
> 原理是兩個行程相互 pipe，排程器夾在其間來回奔波。
>
想像兩個行程互相丟球(資源的轉移)，一旦排程器跟上球便拋給另一行程，而排程器追著球跑，如此我們就可以測量出排程器的速度(效能)。

:::info
>[name=Kuanch]
這就是為什麼任務的數量遠大於核心數，但我們感到他們同時在執行；當然有平行化的功勞，但並行
:::

核心 (core)
任務 (task)
行程 (process)
線程 (thread)

CPU affinity 在 []() 有被提及，用於限定該程式發起的所有行程(？)僅運作於某一個 CPU core。

>其次，與其說它是 scheduling 的效能，不如說是 context switch 的表現，不過這兩者在非專門對排程器演算法和內部實作分析的我們來說，可粗略地視作相等，因為此刻我們關心的是，scheduling 前前後後所處理的各種瑣事

除了 context switching，其他還有什麼花費？我認為大致可以公式化成以下
scheduling = context switching + task arrangement (scheduling) + load balance (rebalance_domains(), affinity) + synchronization (concurrency) + overhead

### Patterns / Trade-offs

> 是所有的資源共享一個任務的 runqueue，排程器排程時經由 locking 來保證互斥，還是針對每個資源，我們都為其設置一個 runqueue，以減少 lock 帶來的損耗？

[Run queue](https://en.wikipedia.org/wiki/Run_queue) 或俗稱 ready queue，存有待執行的行程或線程供排程器決定下一個執行的任務；根據引文[谈谈调度 - Linux O(1)](https://zhuanlan.zhihu.com/p/33461281)，這句話的場景是指當多個 core (即資源)嘗試取得任務應該如何取得，如果只有一個 runqueue，每個 core 進入取得任務時區要 lock runqueue，這是 Linux 2.4 scheduler 的策略，僅使用一個 global runqueue；見下一節[令人詬病的 Linux 2.4 排程器](https://hackmd.io/@sysprog/linux-scheduler#%E4%BB%A4%E4%BA%BA%E8%A9%AC%E7%97%85%E7%9A%84-Linux-24-%E6%8E%92%E7%A8%8B%E5%99%A8)。

而在 Linux 2.6 使用了 per core runqueue，見下一節 [Linux 2.6 $O(1)$ 排程器](https://hackmd.io/@sysprog/linux-scheduler#%E7%AC%A6%E5%90%88-O1-%E6%93%8D%E4%BD%9C%E7%9A%84%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B)

> 資源如何利用？是 run to completion，還是 time slicing？
[run to completion](https://en.wikipedia.org/wiki/Run_to_completion_scheduling) 係指任務將執行直到完成，為 nonpreemptive scheduling；而 [time slicing](https://en.wikipedia.org/wiki/Preemption_(computing)#Time_slice) 則是依照設定的時間限制回到待執行狀態，等待下次執行，為 preemptive scheduling，如 [Round Robin](https://en.wikipedia.org/wiki/Round-robin_scheduling)。

### 令人詬病的 Linux 2.4 排程器
Linux 2.4 排程器的設計導致的以下問題
1. 僅有一個 global runqueue 導致 core 競爭 (bad scalability)
2. 每次排程需要將任務插入 global runqueue，導致複雜度為 $O(N)$

### 符合 $O(1)$ 操作的資料結構
1. 存取、搜尋、插入、刪除皆能夠滿足 $O(1)$ 的資料結構並不存在；瓶頸是搜尋，使用 B-tree 也需要 $O(logN)$ (換句話說，使用 B-tree 進行搜尋是最快的方法之一，複雜度為 $O(logN)$

3. 融合多種資料結構，因 array 的存取可以達 $O(1)$ (indexing)，而 linked list, stack, queue 在插入刪除都能夠滿足 $O(1)$，後來我們知道 Linux 2.6 選擇了 FIFO queue

### Linux 2.6 O(1) 排程器
如何將 array 和 FIFO queue 組合起來呢？使用一個 bitmap 依照 priority 紀錄是否有任務存在，因我們可以透過現代 CPU 指令快速取得目前最高優先權的 FIFO queue；確定 FIFO queue 後也可以在 $O(1)$ 內取得下一個任務。

>但單一處理器在同一時間只能執行一個任務，換言之，不考慮觸發中斷與重新觸發排程機制的情況下，目前任務的時間片段在尚未執行完畢前，其他的任務沒有機會執行，這導致我們無法細緻地排程。

這邊提到一個問題，先前說當任務用盡 timeslice 後將放入 expired queue， runqueue (active priority array) 為空後將和 expired queue 對調，故即便是高優先權的任務被放入 expired queue 後也需要等待目前所有 active task 被執行完畢之後才會被執行。

那如何解決呢？Completely Fair Scheduler (CFS) ，它按照權重分配給低優先權的任務更多 CPU 使用時間，CFS 留待之後討論。