Linux 核心設計: 不只挑選任務的排程器 閱讀筆記

CPU scheduling 對系統的影響

本節說明如何評估一個 scheduling 的效能：

原理是兩個行程相互 pipe，排程器夾在其間來回奔波。

想像兩個行程互相丟球(資源的轉移)，一旦排程器跟上球便拋給另一行程，而排程器追著球跑，如此我們就可以測量出排程器的速度(效能)。

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 或俗稱 ready queue，存有待執行的行程或線程供排程器決定下一個執行的任務；根據引文谈谈调度 - Linux O(1)，這句話的場景是指當多個 core (即資源)嘗試取得任務應該如何取得，如果只有一個 runqueue，每個 core 進入取得任務時區要 lock runqueue，這是 Linux 2.4 scheduler 的策略，僅使用一個 global runqueue；見下一節令人詬病的 Linux 2.4 排程器。

而在 Linux 2.6 使用了 per core runqueue，見下一節 Linux 2.6

$O(1)$ 排程器

資源如何利用？是 run to completion，還是 time slicing？
run to completion 係指任務將執行直到完成，為 nonpreemptive scheduling；而 time slicing 則是依照設定的時間限制回到待執行狀態，等待下次執行，為 preemptive scheduling，如 Round Robin。

令人詬病的 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)$

2. 融合多種資料結構，因 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 留待之後討論。