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

目標設定

排程器 (scheduler) 是任何一個多工作業系統核心都具備的機制，但彼此落差極大，考量點不僅是演算法，還有當應用規模提升時 (所謂的 scalability) 和涉及即時處理之際，會招致不可預知的狀況 (non-determinism)，不僅即時系統在意，任何建構在 Linux 核心之上的大型服務都會深受衝擊。為此，Linux 核心的排程器經歷多次變革，已非僅是挑選下一個可執行的行程 (process)，而是顧及公平 (fairness)、交互反應 (interactiveness)、多核處理器的負載平衡、進階電源管理、即時處理能力等議題。

在本講座中，我們會探討 Completely Fair Scheduler (CFS) 前後的變化，並提及 SCHED_DEADLINE 和 Energy-Aware Scheduling 等等實作。預計涵蓋:

scheduling goal
context switch 實作機制
$O (n)$ 排程器 $\to$ $O (1)$ 排程器 $\to$ Completely Fair Scheduler (CFS) 的演化歷程
多核處理器的排程: load balancing 與 CPU isolation
CPU topologies 和 scheduling domain
排程相關系統呼叫
Real-time scheduling
Kernel preemption

重新認識 scheduling

Wikipedia 說:

In computing, scheduling is the method by which work specified by some means is assigned to resources that complete the work.

用數學觀念來思考: scheduling 是個函數，把一組任務的集合映射到一組資源。具體來說，Linux (CPU) 排程器就是把一系列 process (中譯「行程」，即一種 workload) 映射到一個個 CPU core:

主要的任務計有常駐系統的服務、各式 agent、initscripts、週期性任務
scheduling 作為一個特殊函數，承受著考驗，需要考慮到公平、優先權、搶佔 (preemption)、效率、可擴展能力 (scalability，從單核遷徙到多核，還要涵蓋 NUMA) 等等。

先不講 Linux 排程器，資訊系統其實也存在多種排程器，例如:

erlang scheduler: erlang processes 到 threads 間的映射;
nginx: HTTP/HTTPS 請求到 processes / application 間的映射;
Memory manager: virtual memory 到 physical memory 間的映射;
hypervisor: VM 到實體硬體間的映射;
Amazon Elastic Compute Cloud (EC2): VM 到 hypervisor 間的映射;
Apache Spark: map/reduce job 到計算節點間的映射;

經由上述映射，我們可得到額外的好處:

資源得到更高效的利用;
由於增加一層 indirection，任務和任務所需要的資源間的耦合度大幅下降;
更好的服務品質（quality of service, QoS);

"All problems in computer science can be solved by another level of indirection" (the "fundamental theorem of software engineering")
– David Wheeler

仔細觀察上述案例，不難發現，待處理任務的數量往往遠大於資源的數量，甚至，二者落差可達數個數量級。這種用少量的資源以「打腫臉充胖子」的姿態，嘗試完成大量的任務的行為，在電腦科學領域有個經典的描述，叫做 oversubscribed。其實很多商業領域尤其是網際網路，其營運的秘密就在於 oversubscription 這個概念中。例如，電信業者承諾給你每月 50MB 流量的網路、早期 GMail 提供不斷增長的 1GB 信件容量、AWS 總是拍胸脯說「只要你有錢，EC2 機器想開幾台就開幾台」。

反過來，我們若想支援 oversubscription，就可引入特製的排程器，降低資源的兩端耦合度，即可解決。

當然，你很快就會納悶：享受到排程器的好處，對應的代價是什麼？

CPU scheduling 對系統的影響

排程器本身的運作會消耗系統資源，是其最主要的代價。自然，我們希望這代價越小越好。於是，下一個問題是：當 Linux 做一次 reschedule 的動作時，究竟耗費多少資源 (CPU 時間)？

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

回答這個問題前，我們要思考另一個問題：「如何測量？」

要測量上圖中橘色的部分，有兩個直觀的方法。一種方法是在進入點和出口記錄時間，然後計算數值差距，最後求平均值 —— 然而 scheduling 的動作並不受你我掌控，使用者層級 (userspace) 下很難找到其進入點和出口。

另一種方法是我們讓青色的區域無限接近零，讓整個時間片都被橘色的區域佔滿，這樣，任務運行的時長便是 scheudling 花費的總時長。按照這個思路，使用者層級的程式碼需要被簡化到只做一件事情：一旦被執行就立刻阻塞 (block) 自己，讓排程器毫不猶疑地把 CPU 讓給其他工作。

GNU/Linux 下面的 perf 工具已提供對應的基礎建設，操作如下:

$ perf bench sched pipe
# Running 'sched/pipe' benchmark:
# Executed 1000000 pipe operations between two processes

     Total time: 21.159 [sec]

      21.159808 usecs/op
          47259 ops/sec

測試環境: Marvell® ThunderX2® CN9975 28-core Arm processors

原理是兩個行程相互 pipe，排程器夾在其間來回奔波。這裡有個問題，由於行程可能分佈在不同的 CPU 核裡頭，測出的數字會失真，所以我們應該用 taskset 工具將其 affinity 指派為某個 CPU core 下：

affinity KK:[əˋfɪnətɪ] DJ:[əˋfiniti] 有「吸引力」的意思，可類比婚姻關係
參照 CPU Topology

$ taskset -c 0 perf bench sched pipe
# Running 'sched/pipe' benchmark:
# Executed 1000000 pipe operations between two processes

     Total time: 11.586 [sec]

      11.586201 usecs/op
          86309 ops/sec

每個操作的時間成本從 $21.16 μ s$ 降到 $11.59 μ s$ , 為什麼呢？

經由上述效能評比，我們學到些什麼？

首先，這些測試都不算嚴謹。我們並未消除系統裡其它行程的影響，因而測量的結果並不精確。但是，我們大概可以瞭解其處理速度的數量級。知道這個數量級，非常重要，因為，排程器把 CPU 時間切出來的 timeslice 應該要高於這個數量級，否則，便沒有意義。

其次，與其說它是 scheduling 的效能，不如說是 context switch 的表現，不過這兩者在非專門對排程器演算法和內部實作分析的我們來說，可粗略地視作相等，因為此刻我們關心的是，scheduling 前前後後所處理的各種瑣事 (從上一個 task 結束執行，到下一個 task 開始執行)，擠佔多少 CPU 時間。

我們接著可推斷：Linux 排程器做了大量的工作，這其中耗費的絕大多數時間是在 context switch 上，其中也有切換 page table 的成本。

golang 內建的 goroutine 排程器延遲可比 Linux 排程器低很多，因為在使用者層級下的排程器沒有諸多紛繁複雜，效能自然是很好。golang 排程器設計單純，沒有優先權，也沒有搶佔，而且 Go 語言程式已經預先編譯為原生的機械碼，效能勝出無可厚非。

Patterns / Trade-offs

考慮一個排程器時，我們探討下述問題:

任務如何組織？是所有的資源共享一個任務的 runqueue，排程器排程時經由 locking 來保證互斥，還是針對每個資源，我們都為其設置一個 runqueue，以減少 lock 帶來的損耗？那麼問題又來了，如果某個資源上的任務列表空了，資源是就此閒置，還是可去別的資源的 runqueue 上「偷」任務給自己執行？
資源如何利用？是 run to completion，還是 time slicing？run to completion 對於計算密集，且在意 latency 的場景非常有價值，因而在網絡設備中，除 traffic shaping 的需求外，訊息的處理大多採用 run to completion。time slicing 則適用於 I/O 密集，或者在意系統總體的使用率的場景。
用什麼資料結構組織 runqueue？是 FIFO queue (linked list)，還是 rb tree，還是 bitmap + FIFO queue，各種結構的優劣如何？
使用什麼演算法？是迭代走訪以挑出最合適的任務 (其時間複雜度為 $O (N)$ )，還是對於任意任務 round robin（weighted round robin）？Linux 2.6.0 提出的 $O (1)$ 排程器使用什麼演算法？CFS (Completely Fair Scheduler) 為何又將其取而代之？對於目前大叢集下的 cluster scheduling，排程器如何處理？

Image Not Showing Possible Reasons

The image was uploaded to a note which you don't have access to
The note which the image was originally uploaded to has been deleted

Learn More →

改寫自 scheduling

排程器主要功能是將系統中的任務分派給個別 CPU 之上執行，並要滿足以下效能要求:

對於 time-sharing 的行程，排程器必須公平;
快速的行程反應時間 (Response time);
高 throughput;
低功耗;

不同的應用場景就有不同的需求，因此我們需要對任務進行分類：

普通行程
即時行程

對於即時行程，毫無疑問地，快且精準的反應時間的需求最為關鍵，而對於普通行程來說，該兼顧前 3 點。不難發現，上述這些需求互相衝突，對於這些 time-sharing 的普通行程如何平衡設計呢？於是又需要將普通行程細分為:

交互式行程 (interactive processs)
批處理行程 (batch process)

交互式行程需要和使用者互動，因而對排程器的延遲較為敏感，相較之下，批處理行程屬於在背景默默做事的執行單元，因而更注重 throughput。在 Linux 廣泛在移動裝置上採用後，排程器也往能源效率進行調整，於是有了 Energy Aware Scheduling (EAS)

簡報: CPU Scheduling of the Linux Kernel

令人詬病的 Linux 2.4 排程器

回顧 Linux 2.4 排程器的設計，瞭解其傳承，同時以史為鏡。

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

Linux 2.4 排程器支持 SMP（Symmetric Multi-Processing），然而，由於只用一個 global runqueue，各個 core 需要競爭同一個 runqueue 裡面的任務，所以可延展性能力 (scalability) 不好。稍早提及的考量點:

任務如何組織？是所有的資源共享一個任務的 runqueue，排程器藉由 locking 來保證互斥，還是針對每個資源，都為其準備一個 runqueue，以減少 lock 帶來的損耗？那麼問題又來了，若某個資源上的任務列表空了，資源是就此閒置，還是可去別的資源的 runqueue 上「偷」任務給自己執行？

global runqueue 帶來的效能問題其實可忍受，畢竟只是在 dequeue 的過程需要 lock，但這個問題就很致命：Linux 2.4 排程器的時間複雜度是 $O (N)$ 。現代作業系統可運作成千上萬個行程， $O (N)$ 的時間複雜度意味著，每到排程之際，對於目前執行完的行程，需要將所有在 expired queue 中的行程存取過一遍，找到合適的位置插入。這不僅僅會帶來效能上的巨大損失，還使得系統的排程時間非常不確定 —— 根據系統的負載，可能有數倍甚至數百倍的差異。如此的不確定性 (non-determinism) 是資訊系統的障礙，尤其在即時處理的領域。

在 Linux v2.6.0 到 v2.6.22 之間，排程器維護兩個 queue:

runqueue
expired queue

這二者永遠保持有序，當一個行程耗盡時間片段 (timeslice) 之際，就會被插入 expired queue；當 runqueue 為空時，只需要把 runqueue 和 expired queue 對調即可。

值得注意的是，排程系統的難點不在於尋找下一個可執行的行程，這個操作往往可達到夠好的表現，因為只要妥善對 runqueue 排序，使其第一個行程永遠是下次需要排程的行程即可。難點在於執行完的行程該如何安插，才能確保 runqueue 的順序符合預期。

符合 $O (1)$ 操作的資料結構

很多資料結構的操作， $O (l o g N)$ 就是很好的表現，那 Linux 2.6 的 O(1) 排程器到底如何實作呢？

回答這個問題前，我們回顧以下資料結構的基本操作及其時間複雜度：

access (隨機存取)
- array 是唯一能夠達到，且平均情況和最壞情況均能達到 $O (1)$ 隨機存取的資料結構;
- 其它的資料結構，像是 linked list 是 $O (N)$ ，tree 一般是 $O (l o g N)$ ;
search (搜尋):
- 也許你會先想到 hash table 作為 $O (1)$ 時間複雜度的實作。然而，它在最壞情況下是 $O (N)$ ;
- 沒有任何演算法可確保在最壞情況下，search 依然是 $O (1)$ ;
- 大部分 tree（B-tree, red-black tree）平均和最壞情況都是 $O (l o g N)$ ;
insert/deletion (插入和刪除)
- 插入和刪除兩者是對等的操作，這裡一起探討。linked list, stack, queue 在平均和最壞情況下都是 $O (1)$ ，而上述 hash table 雖然平均是 $O (1)$ ，但最壞情況是 $O (N)$ ;
- 大部分 tree（b-tree, red-black tree）平均和最壞情況都是 $O (l o g N)$ ;

不難發現，若要達成 $O (1)$ 排程器所需，操作只能包含純粹的 access, insert 和 deletion，但不得有 search。Linux v2.6 排程器在將執行完的行程 insert 回 expired queue 之際使用 search 操作，就大幅增長時間複雜度。此外，對於排程器的設計來說，儘量要選擇平均情況和最壞情況表現一致的演算法。若平均情況是 $O (1)$ ，最壞情況是 $O (n)$ ，那麼這個排程器會給系統帶來很大的不確定性。

綜合考量下，我們可選擇的範圍就很有限:

access 只能用 array;
insert/deletion 只能用 linked list, queue, stack;

Linux 2.6 `O(1)` 排程器

我們思考以下排程場景:

假設系統中有 6 個行程;
具備 3 種優先權等級: high, medium, low
沒有 preemption，嚴格按照優先權的順序執行行程

那麼，我們怎麼組合上述的資料結構，讓排程的操作達到 $O (1)$ 呢？

Linux v2.6 中，共有 140 種優先級，所以我們就用長度為 140 的陣列去記錄優先權級別。每個優先權下面用一個 FIFO queue 管理這個優先權下的行程。新來的插到隊尾，先進先出。在這種情況下，insert / deletion 都是 $O (1)$ 。

Priority Array 根據目前 140 個優先權等級 (MAX_PRIO = 140)，為每個 Task Priority 配置對應的 queue head，並且用unsigned long 涵蓋這 140 個優先權等級，透過個別 bit 為 0 或 1，表示該 Task Priority 是否有需要被執行的任務在排程等待執行中

再來，怎麼找到目前最高優先級下面的可執行的行程呢？若從 0 開始存取每個單元，時間複雜度雖然不是 $O (N)$ ，但跟優先級多寡相關的 $O (M)$ ，也不能算作 $O (1)$ 。在 Linux 2.6 排程器中，開發者採用 bitarray，為每種優先權分配一個 bit，若這個優先權佇列 (priority queue) 下面有行程，那麼就對相應的 bit 染色，置為 1，否則置為 0。這樣，問題就簡化成從低位到高位，尋找指定 bitarray 第一個設定為 1 的位元 (注意: 秉持 UNIX 傳統的 nice 值，數值越低，優先權等級越高，這也是為何要從低到高的方向)，這在現代處理器中，就是一道 CPU 指令，即 Find first set/one。

Linux 核心 API: fls

大致的排程步驟如下:

在 active bitarray 裡，尋找 left-most bit 的位置 x;
在 active priority array（APA）中，找到對應 queue APA[x];
從 APA[x] 中 dequeue 一個 process，dequeue 後，如果 APA[x] 的 queue 為空，那麼將 active bitarray 裡第 x bit 設定為 0;
對於目前執行完的行程，重新計算其 priority，然後 enqueue 到 expired priority array（EPA）相應的 queue EPA[priority];
若 priority 在 expired bitarray 裡對應的 bit 為 0，將其設定 1;
如果 active bitarray 全為 0，將 active bitarray 和 expired bitarray 交換;

當然，這裡面還有一些細節。例如若是行程被搶佔，其時間片段沒用完，則第 4 步將改為 enqueue 回 active priority queue 中。

儘管 $O (1)$ 排程器確實可消弭排程機制的不確定性，但單一處理器在同一時間只能執行一個任務，換言之，不考慮觸發中斷與重新觸發排程機制的情況下，目前任務的時間片段在尚未執行完畢前，其他的任務沒有機會執行，這導致我們無法細緻地排程。因此，在 Linux v2.6.23 後，引入新的 CFS (Completely Fair Scheduler) 排程機制，盡可能讓每個不同等級的任務得以更公平分配到處理器的時間，利用 red-black tree，讓越少被執行到的任務，得以有更高的機率被處理器挑選出來，從而避免優先級較低的任務，被延遲較久的時間，才有被處理器執行的機會。

在 Linux 核心的文件 CFS Scheduler，嘗試以一句話說明原理:

80% of CFS's design can be summed up in a single sentence: CFS basically models an "ideal, precise multi-tasking CPU" on real hardware.

所謂理想的多工處理器，是當處理器有 100% 的能力，且系統中有兩個任務在運作，這兩個任務可各自取得處理器 50% 的執行能力，並被處理器平行執行。換言之，任意時間間隔來看 (例: 隨機取 10 ms 間隔)，這兩個任務都具備分配到處理器 50% 的執行能力。

Linux 2.6 $O (1)$ 排程器已被更加強調公平性的 CFS取代，但其以獨特的設計，簡單的演算法，將 bitarray + priority queue 的組合展現核心演算法之美。

改寫自 Linux O(1)

排程器設計

複習不僅是個執行單元的 Process

取自 Donald E. Porter 教授的 CSE 506: Operating Systems 教材

Scheduling

cooperative multitasking: 協同式多工
preemptive multitasking: 搶佔式多工
搶佔的機會
- System calls
  - Before, During, After
- Interrupts
  - Timer interrupt: ensures maximum time slice

Scheduling, Part 2

涉及即時處理能力

在 SCHED_DEADLINE 類別中，會遇到一個問題:該如何決定優先權，這部分主要有兩個演算法，分別是依據週期長短決定優先權的 Rate Monotonic Scheduling (RMS)，以及根據最靠近下一個最後期限的 Earliest Deadline First (EDF)。
Rate Monotonice 是以週期越短的行程，有越高的優先權，在 RMS 排程之前必須要先確認所有行程的執行時間與週期的比值相加(也就是下圖的 U )，是否比 1 大，如果比 1 大，代表這些行程的 CPU 使用率是不合理的，無法排程。

下面是 RMS 排程的例子， C 代表該行程的執行時間， T 代表該行程的週期，可檢查出 U < 1 是可排程的。

實際排程時，會由週期最短的洗衣機優先執行，但最後發現核電廠這個行程在第三次要執行的週期前沒辦法完成第二次的工作，因此排程失敗。

另一個即時排程的方法是 Earliest Deadline First (EDF)，同樣要檢查 U < 1 ，跟第一個方法不一樣的是 EDF 排程演算法是依照誰離死線比較近來決定哪個行程可以優先執行。
行程的資訊跟 RMS 的相同

最後的排程結果如下，這三個行程可以順利執行。

在 SCHED_DEADLINE 類中，新增兩個系統呼叫來操作 sched_attr 結構
c sched_getattr(pid_t pid, struct sched_attr *attr, unsigned int size, unsigned int flags) sched_stattr(pid_t pid, struct sched_attr *attr, unsigned int flags)

上述的 EDF 演算法在單核的時候可以順利運行，但是在多核心架構下，不一定能夠滿足這些行程的需求。 Dhall's effect 是在描述在多核心處理器下，即使每個核心的使用率都未達 100%，全域的EDF演算法也不能保證這些 Real-time 的任務能夠滿足需求。

以下的例子描述了 Dhall's effect

對於 Dhall's effect，有兩個方法可以改善，第一個是讓每個行程可以在不同的核心上隨意的遷移，第二個是將不同執行長度的行程分類，讓該分類綁定在某個固定的CPU上，如上述的例子，就可以將行程分為短的與長的類別，並且固定執行該類別的核心。

關於 SCHED_DEADLINE 類，有一些基本的限制。