---
tags: LINUX KERNEL, LKI
---
# [Linux 核心設計](https://hackmd.io/@sysprog/linux-kernel-internal): 不只挑選任務的排程器
Copyright (慣C) 2019, 2022, 2026 [宅色夫](https://wiki.csie.ncku.edu.tw/User/jserv)
直播錄影: ==[Part 1](https://youtu.be/COnqlKFJ6iE)==, ==[Part 2](https://youtu.be/wKbxn6m5s9M)==
## 目標設定
排程器 (scheduler) 是任何一個多工作業系統核心都具備的機制，但彼此落差極大，考量點不僅是演算法，還有當應用規模提升時 (所謂的 scalability) 和涉及即時處理之際，會招致不可預知的狀況 (non-determinism)，不僅即時系統在意，任何建構在 Linux 核心之上的大型服務都會深受衝擊。為此，Linux 核心的排程器經歷多次變革，已非僅是挑選下一個可執行的行程 (process)，而是顧及公平 (fairness)、互動反應 (interactiveness)、多核處理器的負載平衡、進階電源管理、即時處理能力等議題。
在本講座中，我們探討 Linux 核心排程器從初期的 $O(n)$ 設計到 EEVDF 的演化歷程，並涵蓋 SCHED_DEADLINE、Energy-Aware Scheduling、sched_ext 等實作。預計涵蓋:
- scheduling goal
- context switch 實作機制
- $O(n)$ 排程器 $\to$ $O(1)$ 排程器 $\to$ CFS $\to$ EEVDF 的演化歷程
- sched_ext: 以 BPF 實作可抽換的排程策略
- 多核處理器的排程: load balancing 與 CPU isolation
- CPU topologies 和 scheduling domain
- 排程相關系統呼叫
- Real-time scheduling
- Kernel preemption
## 重新認識 scheduling
[Wikipedia](https://en.wikipedia.org/wiki/Scheduling_(computing)) 提到:
> 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](https://www.calculate-linux.org/main/en/initscripts)、週期性任務
* scheduling 作為一個特殊函數，承受著考驗，需要考慮到公平、優先權、搶佔 (preemption)、效率、可擴展能力 (scalability，從單核遷徙到多核，還要涵蓋 NUMA) 等等。
先不講 Linux 排程器，資訊系統其實也存在多種排程器，例如:
1. [erlang scheduler](http://erlang.org/doc/man/scheduler.html): erlang processes 到 threads 間的映射;
2. [nginx](https://nginx.org/en/): HTTP/HTTPS 請求到 processes / application 間的映射;
3. [Memory manager](https://www.kernel.org/doc/html/latest/admin-guide/mm/index.html): virtual memory 到 physical memory 間的映射;
4. [hypervisor](https://en.wikipedia.org/wiki/Hypervisor): VM 到實體硬體間的映射;
5. [Amazon Elastic Compute Cloud (EC2)](https://aws.amazon.com/ec2/): VM 到 hypervisor 間的映射;
6. [Apache Spark](https://spark.apache.org/): map/reduce job 到計算節點間的映射;
經由上述映射，我們可得到額外的好處:
* 資源得到更高效的利用;
* 由於增加一層 indirection，任務和任務所需要的資源間的耦合度大幅下降;
* 更好的服務品質 ([quality of service](https://en.wikipedia.org/wiki/Quality_of_service), QoS);
:::info
"All problems in computer science can be solved by another level of [indirection](https://en.wikipedia.org/wiki/Indirection)" (the "[fundamental theorem of software engineering](https://en.wikipedia.org/wiki/Fundamental_theorem_of_software_engineering)")
-- David Wheeler
:::
仔細觀察上述案例，不難發現，待處理任務的數量往往遠大於資源的數量，甚至，二者落差可達數個數量級。這種用少量的資源以「打腫臉充胖子」的姿態，嘗試完成大量的任務的行為，在電腦科學領域有個經典的描述，叫做 [oversubscribed](https://encyclopedia2.thefreedictionary.com/Oversubscribed)。其實很多商業領域尤其是網際網路，其營運的秘密就在於 oversubscription 這個概念中。例如，電信業者承諾給你每月 50MB 流量的網路、早期 GMail 提供不斷增長的 1GB 信件容量、AWS 總是拍胸脯說「只要你有錢，EC2 機器想開幾台就開幾台」。
反過來，我們若想支援 oversubscription，就可引入特製的排程器，降低資源的兩端耦合度，即可解決。
當然，你很快就會納悶：享受到排程器的好處，對應的代價是什麼？
## CPU scheduling 對系統的影響
排程器本身的運作會消耗系統資源，是其最主要的代價。自然，我們希望這代價越小越好。於是，下一個問題是：當 Linux 做一次 reschedule 的動作時，究竟耗費多少資源 (CPU 時間)？
回答這個問題前，我們要思考另一個問題：「如何測量？」
要測量上圖中橘色的部分，有二個直觀的方法。一種方法是在進入點和出口記錄時間，然後計算數值差距，最後求平均值 —— 然而 scheduling 的動作並不受你我掌控，使用者層級 (userspace) 下很難找到其進入點和出口。
另一種方法是我們讓青色的區域無限接近零，讓整個時間片都被橘色的區域佔滿，這樣，任務運行的時長便是 scheduling 花費的總時長。按照這個思路，使用者層級的程式碼需要被簡化到只做一件事情：一旦被執行就立刻阻塞 (block) 自己，讓排程器毫不猶疑地把 CPU 讓給其他工作。
GNU/Linux 下面的 [perf 工具](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial) 已提供對應的基礎建設 (更多排程器效能評比工具可見 [Scheduler(6): 排程器測試工具](https://hackmd.io/@sysprog/linux-scheduler-6))，操作如下:
```shell
$ 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
原理是二個行程相互 [pipe](https://man7.org/linux/man-pages/man2/pipe.2.html)，排程器夾在其間來回奔波。這裡有個問題，由於行程可能分佈在不同的 CPU 核裡頭，測出的數字會失真，所以我們應該用 [taskset](https://man7.org/linux/man-pages/man1/taskset.1.html) 工具將其 affinity 指派為某個 CPU core 下：
> affinity KK:[əˋfɪnətɪ] DJ:[əˋfiniti] 有「吸引力」的意思，可類比婚姻關係
> 參照 [CPU Topology](http://kodango.com/cpu-topology)
```shell
$ 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 \mu s$ 降到 $11.59 \mu s$, 為什麼呢？
經由上述效能評比，我們學到些什麼？
首先，這些測試都不算嚴謹。我們並未消除系統裡其它行程的影響，因而測量的結果並不精確。但是，我們大概可以瞭解其處理速度的數量級。知道這個數量級，非常重要，因為，排程器把 CPU 時間切出來的 timeslice 應該要高於這個數量級，否則，便沒有意義。
其次，與其說它是純粹 scheduling 演算法的效能，不如說它更接近「scheduler path + context switch + wake-up 協調」的綜合表現。不過這三者在未深入拆解核心 tracepoint 前，對一般教學用途可暫時視為同一類成本，因為此刻我們關心的是 scheduling 前前後後所處理的各種瑣事 (從上一個 task 結束執行，到下一個 task 開始執行)，究竟擠佔多少 CPU 時間。
因此，更保守的推論是：Linux 在一次任務切換前後做大量工作，而這些成本中相當大一部分來自 context switch 本身，以及 task 喚醒、runqueue 操作、快取與 TLB 行為變化等機制。若前後二個 task 分屬不同位址空間，還可能伴隨 page table 切換成本，但這不是單靠 `perf bench sched pipe` 就能獨立量出的數值。
golang 內建的 [goroutine](https://go.dev/tour/concurrency/1) 排程器延遲可比 Linux 排程器低很多，因為使用者層級的排程器不須處理核心層級的諸多瑣事。早期 Go 排程器沒有優先權，僅靠合作式排程; 自 Go 1.14 (2020 年) 起引入非同步搶佔，透過訊號中斷長時間執行的 goroutine。Go 語言程式預先編譯為原生機器碼，加上 goroutine context switch 僅需儲存少量暫存器和堆疊指標，成本遠低於核心的行程切換。
## 設計模式與取捨 (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，排程器如何處理？
> 改寫自 [scheduling](https://zhuanlan.zhihu.com/p/33389178)
排程器主要功能是將系統中的任務分派給個別 CPU 之上執行，並要滿足以下效能要求:
1. 對於 time-sharing 的行程，排程器必須公平;
2. 快速的行程反應時間 ([Response time](https://en.wikipedia.org/wiki/Response_time_(technology)));
3. 高 throughput;
4. 低功耗;
不同的應用場景就有不同的需求，因此我們需要對任務進行分類：
* 普通行程
* 即時行程
對於即時行程，毫無疑問地，快且精準的反應時間的需求最為關鍵，而對於普通行程來說，該兼顧前 3 點。不難發現，上述這些需求互相衝突，對於這些 time-sharing 的普通行程如何平衡設計呢？於是又需要將普通行程細分為:
* 互動式行程 (interactive process)
* 批次處理行程 (batch process)
互動式行程需要和使用者互動，因而對排程器的延遲較為敏感，相較之下，批次處理行程屬於在背景默默做事的執行單元，因而更注重 throughput。在 Linux 廣泛在移動裝置上採用後，排程器也往能源效率調整，於是有了 [Energy Aware Scheduling (EAS)](https://docs.kernel.org/scheduler/sched-energy.html)
:::info
簡報: ==[CPU Scheduling of the Linux Kernel](https://docs.google.com/presentation/d/1qDSFOfhGF-AX3O8CNzoAkQr_5ohr0nMVDlNfPnM9hOI/edit?usp=sharing)==
:::
## 初期的 Linux 排程器
Linux 0.01 (1991 年) 的排程器極為簡單: 走訪 task 陣列中的所有行程，依 `counter` (剩餘時間片段) 和 `priority` 計算加權分數，挑選最高者執行。當所有可執行行程的 `counter` 歸零，以 `counter = counter/2 + priority` 重新計算所有行程的 `counter`，讓休眠中的行程累積較高值，甦醒時得以優先執行。此 $O(n)$ 排程器的核心邏輯從 Linux 0.01 延續至 2.4 版，未有本質變化。隨著行程數量增長和 SMP 架構普及，$O(n)$ 走訪和單一 runqueue 的瓶頸越來越難以忍受。
## 令人詬病的 Linux 2.4 排程器
回顧 Linux 2.4 排程器的設計，瞭解其傳承，同時以史為鏡。
Linux 2.4 排程器支援 SMP (Symmetric Multi-Processing)，然而，由於只用一個 global runqueue，各個 CPU core 需要競爭同一個 runqueue 裡面的任務，所以可擴展能力 (scalability) 不好。稍早提及的考量點:
> 任務如何組織？是所有的資源共享一個任務的 runqueue，排程器藉由 locking 來保證互斥，還是針對每個資源，都為其準備一個 runqueue，以減少 lock 帶來的損耗？那麼問題又來了，若某個資源上的任務列表空了，資源是就此閒置，還是可去別的資源的 runqueue 上「偷」任務給自己執行？
Linux 2.4 排程器的另一個致命問題，在於挑選下一個 task 時常需走訪 runnable task 集合，其時間複雜度是 $O(N)$。現代作業系統可運作成千上萬個行程，$O(N)$ 的時間複雜度意味著，每逢排程點都可能需要重新掃描大量 task。這不僅會帶來效能上的損失，還使排程延遲隨系統負載劇烈波動。如此的不確定性 (non-determinism) 是資訊系統的障礙，尤其在即時處理與大型 SMP 系統中更為明顯。
值得注意的是，排程系統的難點不在於尋找下一個可執行的行程，這個操作往往可達到夠好的表現，因為只要妥善對 runqueue 排序，使其第一個行程永遠是下次需要排程的行程即可。難點在於執行完的行程該如何安插，才能確保 runqueue 的順序符合預期。
## Linux 2.6 `O(1)` 排程器的 active/expired 設計
Linux v2.6.0 到 v2.6.22 的 `O(1)` 排程器，正是為了解決前述二個問題而生。一方面，它不再讓所有 CPU 競爭單一全域 runqueue，而是改採 per-CPU runqueue，減輕鎖競爭; 另一方面，它將 task 依優先權分桶，避免每次挑選下一個 task 都重新線性掃描所有 runnable task。
其主體概念是維護二組 priority array:
* active array
* expired array
當 task 耗盡目前時間片段 (timeslice) 時，通常會被放入 expired array；當 active array 清空時，再將 active 和 expired 對調。如此一來，排程器不需重新排序整個 runnable task 集合，而是透過資料結構本身維持「下一個可執行 task 在哪裡」這件事。
## 符合 $O(1)$ 操作的資料結構
很多資料結構的操作，$O(log N)$ 就是很好的表現，那 Linux 2.6 的 O(1) 排程器到底如何實作呢？
回答這個問題前，我們回顧以下資料結構的基本操作及其時間複雜度：
* access (隨機存取)
* array 是唯一能夠達到，且平均情況和最壞情況均能達到 $O(1)$ 隨機存取的資料結構;
* 其它的資料結構，像是 linked list 是 $O(N)$，tree 一般是 $O(log N)$;
* search (搜尋):
* 也許你會先想到 hash table 作為 $O(1)$ 時間複雜度的實作。然而，它在最壞情況下是 $O(N)$;
* 沒有任何演算法可確保在最壞情況下，search 依然是 $O(1)$;
* 大部分 tree (B-tree, red-black tree) 平均和最壞情況都是 $O(log N)$;
* insert/deletion (插入和刪除)
* 插入和刪除兩者是對等的操作，這裡一起探討。linked list, stack, queue 在平均和最壞情況下都是 $O(1)$，而上述 hash table 雖然平均是 $O(1)$，但最壞情況是 $O(N)$;
* 大部分 tree (B-tree, red-black tree) 平均和最壞情況都是 $O(log N)$;
不難發現，若要達成 `O(1)` 排程器的目標，關鍵在於避免「為了找到下一個 task 而重新搜尋整體 runnable 集合」。Linux 2.6 `O(1)` 排程器的設計重點，正是將 search 的成本預先編碼進 priority array 和 bitmap。對於排程器的設計來說，也要儘量選擇平均情況和最壞情況表現一致的演算法。若平均情況是 $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)$。在 Linux 2.6 排程器中，開發者採用 bitmap，為每種優先權分配一個 bit。若該優先權佇列 ([priority queue](https://en.wikipedia.org/wiki/Priority_queue)) 下面有行程，就把相應 bit 設為 1，否則設為 0。這樣，問題就簡化成找出 bitmap 中對應「最小非空優先權索引」的那個位元。由於 UNIX 慣用的 `nice` 值越低代表優先權越高，因此實務上就是找出「數值最小、且非空」的優先權佇列。
大致的排程步驟如下:
1. 在 active bitarray 裡，找出對應最小非空優先權的 bit 位置 x;
2. 在 active priority array (APA) 中，找到對應 queue `APA[x]`;
3. 從 APA[x] 中 dequeue 一個 process，dequeue 後，如果 APA[x] 的 queue 為空，那麼將 active bitarray 裡第 x bit 設定為 0;
4. 對於目前執行完的行程，重新計算其 priority，然後 enqueue 到 expired priority array (EPA) 相應的 queue `EPA[priority]`;
5. 若 priority 在 expired bitarray 裡對應的 bit 為 0，將其設定 1;
6. 如果 active bitarray 全為 `0`，將 active bitarray 和 expired bitarray 交換;
當然，這裡面還有一些細節。例如若是行程被搶佔，其時間片段沒用完，則第 4 步將改為 enqueue 回 active priority queue 中。
儘管 `O(1)` 排程器大幅降低排程延遲的不確定性，但它仍偏向「離散優先權 + 時間片段」思維。這種設計對互動式 task 的延遲敏感度、不同 `nice` 值之間的比例公平性，以及大量 runnable task 下的體感反應，都很難做到細膩調整。因此，在 Linux v2.6.23 (2007 年)，Ingo Molnár 引入 CFS (Completely Fair Scheduler)，以 red-black tree 組織的虛擬執行時間取代 bitarray + priority queue。
$O(1)$ 排程器以獨特的設計將 bitarray + priority queue 組合達成常數時間排程，仍是核心演算法教學的經典範例。
> 延伸閱讀: [Scheduler(1): O(1) Scheduler](https://hackmd.io/@sysprog/linux-scheduler-1)
## Completely Fair Scheduler (CFS)
Linux 核心文件 [CFS Scheduler](https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt) 以一句話概括:
> 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.
所謂理想的多工處理器: 若系統有 $N$ 個同權重任務，每個任務在任意時間區間都能取得 $\frac{1}{N}$ 的 CPU 時間。例如處理器上有二個任務，隨機取 10 ms 的區間來觀察，二者各佔 50% 的執行時間。CFS 以 `vruntime` (virtual runtime) 追蹤每個任務已消耗的加權 CPU 時間，並以 [red-black tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree) 組織所有可執行的任務。排程決策取 `vruntime` 最小的節點 (透過快取 `rb_leftmost` 達成 $O(1)$ 挑選)，而 enqueue/dequeue 操作為 $O(\log N)$。關於 CFS 的設計原理和實作細節，可分別參見 [Scheduler(2): 概述 CFS](https://hackmd.io/@sysprog/linux-scheduler-2) 和 [Scheduler(3): 深入剖析 CFS](https://hackmd.io/@sysprog/linux-scheduler-3)。
`nice` 值對應不同的權重: `nice` 越低，權重越大，`vruntime` 增長越慢，因此取得更多 CPU 時間。相鄰 `nice` 值之間的 CPU 時間比約為 1.25:1，確保 `nice` 差距產生一致的相對效果，而非取決於絕對值。
CFS 在 Linux 核心服務長達 16 年 (v2.6.23 至 v6.5)，期間持續演進:
- 階層式群組排程 (group scheduling): `sched_entity` 搭配 cgroup，讓容器和使用者之間公平分配 CPU
- `SCHED_BATCH` 和 `SCHED_IDLE` 策略類別，適用於批次處理和背景任務
- bandwidth throttling 機制，限制群組在指定週期內的 CPU 使用量
- [Per-Entity Load Tracking (PELT)](https://hackmd.io/@sysprog/linux-scheduler-4): 以指數衰減追蹤每個 task 和群組的負載貢獻，為排程決策和負載平衡提供更準確的依據
然而 CFS 也存在已知缺陷:
- sleeper fairness 啟發式規則複雜且難以調校: 休眠後甦醒的任務應補償多少 `vruntime`？過多導致搶佔風暴，過少則互動反應遲鈍
- 對延遲敏感的互動式任務缺乏明確的延遲上界保證
- `latency_nice` 等延遲提示機制，反映出僅靠 `vruntime` 很難同時兼顧公平性與延遲敏感需求
## EEVDF 排程器
Linux v6.6 (2023 年 10 月)，Peter Zijlstra 以 EEVDF (Earliest Eligible Virtual Deadline First) 取代 CFS 的核心排程邏輯。這是自 CFS 問世以來，Linux 排程器最大的架構變革。
關於 EEVDF 的完整分析，可見 [Scheduler(5): EEVDF 排程器](https://hackmd.io/@sysprog/linux-scheduler-5)。
EEVDF 源自 Ion Stoica 和 Hussein Abdel-Wahab 於 1995 年發表的論文 "[Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation](https://citeseerx.ist.psu.edu/document?repid=rep1&type=pdf&doi=805acf7726282721504c8f00575d91ebfd750564)"。主體概念:
每個任務持有二個虛擬時間參數:
* virtual eligible time ($ve_i$): 任務有資格被排程的最早虛擬時間
* virtual deadline ($vd_i$): 任務本次時間片段的虛擬截止時間
排程規則:
1. 任務在 $ve_i \leq V$ (系統目前虛擬時間) 時為「合格」(eligible)
2. 排程器從所有合格任務中，挑選 $vd_i$ 最小者執行
3. 時間片段 (slice) 越短，$vd_i$ 越早，排程優先權越高
EEVDF 沿用 red-black tree 結構 (augmented with earliest deadline)，排程時間複雜度維持 $O(\log N)$，但相較 CFS 有幾項重要改善:
1. 以 `lag` 值 (任務應得時間與實際執行時間的差) 更直接描述公平性，讓 task 甦醒後的處理規則較不依賴歷史啟發式
2. 以 virtual deadline 表示「延遲偏好」，比單純比較 `vruntime` 更容易兼顧互動式 task
3. 與延遲提示機制較容易對接，但這部分仍持續演進，不宜視為最終定論
不過，EEVDF 不是「從此沒有調校問題」的萬靈丹。Linux 核心文件也明確指出，sleeping task 的 `lag` 如何保存、何時衰減，仍需在公平性與延遲之間持續折衷。因此，更準確的說法是：EEVDF 讓 Linux 預設排程器的模型更一致，也讓延遲控制的語義更清楚，但並未讓排程問題從此消失。
## sched_ext: 以 BPF 實作排程策略
Linux v6.12 (2024 年 11 月)，sched_ext 框架正式合併，主要由 Tejun Heo、David Vernet (Meta) 與 Josh Don (Google) 推動。sched_ext 允許以 [BPF](https://docs.kernel.org/bpf/) 程式實作 CPU 排程策略，在核心空間執行，卻以使用者空間的開發速度迭代。
設計原理:
- 排程器以 BPF 程式實作 `struct sched_ext_ops` 回呼，包含 `select_cpu()`、`enqueue()`、`dispatch()` 等關鍵路徑
- 若 BPF 排程器發生異常，核心自動回退至內建排程器，確保系統穩定
- 近日，Tejun Heo (Meta) 引入 sub-scheduler patchset，每個 cgroup 可以載入其 sched_ext 排程器，親代排程器透過 `scx_bpf_sub_dispatch()` 動態分配 when and how much CPU time each child receives，可以實現單一系統上有多個 sched_ext 同時排程器運作，不過目前僅完成 dispatch 路徑支援，還在開發中。
https://lore.kernel.org/all/20260304220119.4095551-1-tj@kernel.org/
應用場景:
- 工作負載特化: Meta 的 [`scx_rusty`](https://github.com/sched-ext/scx) 最佳化 NUMA 親和性; `scx_lavd` 針對延遲敏感場景
- 排程器研究: 無需重新編譯核心即可驗證排程假說
- 桌面體驗: [CachyOS](https://cachyos.org/) 等發行版已採用 sched_ext 排程器提升互動反應
sched_ext 不取代 EEVDF，而是與其共存: EEVDF 作為預設排程策略，sched_ext 提供安全的框架讓特化策略在生產環境中快速實驗與部署。關於 sched_ext 的完整分析，可見 [Scheduler(7): sched_ext](https://hackmd.io/@sysprog/linux-scheduler-7)。
## 前後文切換與核心搶佔 (context switch / kernel preemption)
前文以 `perf bench sched pipe` 粗略觀察 scheduling 成本時，其實已經碰到一個核心事實: 真正昂貴的，不只是「挑下一個 task」這個演算法決策，還包括前後文切換 (context switch) 與搶佔 (preemption) 所伴隨的一連串機制。
一次完整的排程切換，通常至少包含下列步驟:
1. 儲存目前 task 的 CPU 暫存器狀態
2. 更新 task 狀態與 runqueue 結構
3. 選出下一個 task
4. 切換記憶體位址空間與核心堆疊
5. 還原下一個 task 的執行狀態
在支援虛擬記憶體的系統中，若前後二個 task 屬於不同行程，還可能伴隨 page table 切換與 TLB 行為變化，這也是為何 context switch 的成本遠高於單純函式呼叫。
Linux 採用 preemptive multitasking (搶佔式多工)。搶佔可能發生於:
* timer interrupt 到來，迫使目前 task 交出 CPU
* task 主動阻塞，例如等待 I/O 或鎖
* 更高優先權 task 甦醒
* 核心在允許搶佔的區段重新檢查 `need_resched`
這裡要特別區分二個層次:
* user preemption: 核心準備返回使用者空間前，發現有更適合執行的 task
* kernel preemption: 核心仍在執行內部程式碼時，只要不在 critical section，也可能被更高優先權 task 打斷
Kernel preemption 能降低延遲，但也讓核心程式設計更困難。凡是持有 spinlock、關閉中斷，或使用 `preempt_disable()` 保護的區段，都必須明確界定不可被搶佔的範圍。對於需要 hard real-time 保證的場景，可見 [Linux 核心搶佔](https://hackmd.io/@sysprog/linux-preempt)和 [Scheduler(10): PREEMPT_RT](https://hackmd.io/@sysprog/linux-scheduler-10)。
## 多核處理器的排程: topology、domain 與 load balancing
進入 SMP 與 NUMA 時代後，Linux 排程器不再只是「從佇列挑下一個 task」而已，還要決定「這個 task 應該在哪個 CPU 上跑」。
最直覺的做法，是讓每個 CPU 各自維護 runqueue，平時在本地排程，只有在負載失衡時才跨 CPU 遷移 task。這也是現代 Linux 的基本策略，因為它兼顧兩件事:
* 減少 runqueue lock 的競爭
* 盡量維持 cache locality，避免 task 在 CPU 間來回遷移
但「哪個 CPU 比較近」不是單一答案。對排程器來說，CPU 之間存在 topology:
* 同一個 SMT sibling，分享部分執行資源
* 同一個 core cluster 或 LLC domain，快取距離較近
* 同一個 NUMA node，記憶體存取延遲較低
* 跨 NUMA node，遷移成本更高
Linux 以 scheduling domain 建模這些硬體層級。負載平衡時，排程器會先在較近的 domain 內尋找可遷移 task，必要時才往更遠的 domain 擴張。[Energy-Aware Scheduling (EAS)](https://hackmd.io/@sysprog/linux-scheduler-8) 也是建立在類似概念上: 在大小核架構中，不只看「哪個 CPU 有空」，還要看 task 的 util 與能源成本模型，決定放到大核還是小核更合理。
因此，現代 CPU scheduling 的本質是三重折衷:
* fairness: CPU 時間是否分得合理
* locality: 快取與記憶體親和性是否被破壞
* energy: 功耗與熱設計是否可接受
## SCHED_DEADLINE 與即時排程
前面討論的 `O(1)`、CFS、EEVDF，主要都屬於一般用途的 CPU 排程器。對於 hard real-time 或 strongly latency-sensitive workload，Linux 另外提供 real-time scheduling class，例如 `SCHED_FIFO`、`SCHED_RR` 與 `SCHED_DEADLINE`。
若從即時排程理論來看，最常見的二個基礎模型是:
* Rate Monotonic Scheduling (RMS): 週期越短者，固定優先權越高
* Earliest Deadline First (EDF): 動態挑選最早到期的 task
RMS 和 EDF 都是重要理論背景，但 Linux `SCHED_DEADLINE` 的實作不是 RMS，而是以 EDF 搭配 Constant Bandwidth Server (CBS) 機制。其目的不是只看「誰的 deadline 最近」，還要限制每個 task 在特定期間內可使用的 CPU 預算，避免單一即時 task 吃光整台機器。
在使用者空間，`SCHED_DEADLINE` 透過 `sched_attr` 設定三個核心參數:
* `sched_runtime`: 在一個 period 內允許執行多久
* `sched_deadline`: 這份執行預算必須在多久內完成
* `sched_period`: 以多久為一個週期重新補充預算
對應的系統呼叫為:
```c
sched_getattr(pid_t pid, struct sched_attr *attr, unsigned int size,
unsigned int flags);
sched_setattr(pid_t pid, struct sched_attr *attr, unsigned int flags);
```
若把 `runtime / period` 視為 CPU 使用率，Linux 會在 admission control 階段先檢查新 task 是否可能破壞既有 deadline 保證。這也是 `SCHED_DEADLINE` 與一般 fair scheduler 最大的差異: 它不是盡量公平，而是優先滿足可證明的時間約束。
然而，EDF 在多核心環境也不是萬無一失。教科書常提到的 Dhall's effect 說明: 即使每個 CPU 的平均使用率看起來都沒滿，全域 EDF 在多核心上仍可能出現不可排程的 workload。因此，真實系統裡往往還要搭配 CPU affinity、partitioned scheduling、負載隔離，或更保守的 admission policy，才可能得到穩定結果。
換言之，`SCHED_DEADLINE` 把 Linux 從「平均公平」推向「時間保證」，但代價是設定更敏感、分析更困難，對使用者也提出更高的工作負載建模要求。關於 deadline scheduling 的完整討論，可見 [Scheduler(9): Deadline Scheduling](https://hackmd.io/@sysprog/linux-scheduler-9)。
## 排程介面與 CPU 隔離 (scheduling APIs / CPU isolation)
若要從使用者空間直接影響 Linux 排程行為，最常見的介面大致有三類:
* scheduling policy / priority: `sched_setscheduler()`、`sched_setparam()`
* CPU affinity: `sched_setaffinity()`
* 進一步的資源隔離: cpuset cgroup、`isolcpus=`、`nohz_full=`
`sched_setscheduler()` 可指定 task 採用 `SCHED_OTHER`、`SCHED_BATCH`、`SCHED_IDLE`、`SCHED_FIFO`、`SCHED_RR` 或 `SCHED_DEADLINE` 等策略類別。對一般工作負載來說，最常接觸的是預設的 fair scheduler；對音訊處理、工控或低延遲服務，則可能改用 real-time class。
`sched_setaffinity()` 則回答另一個問題: task 可以在哪些 CPU 上執行？這在多核心系統中特別重要，因為 affinity 不只影響負載平衡，也直接影響 cache locality、NUMA 親和性與干擾程度。前面用 `taskset -c 0 perf bench sched pipe` 做測量，本質上就是透過 affinity 限縮 task 的可執行 CPU 集合。
若還要進一步追求低抖動 (low jitter) 或降低干擾，系統管理者往往會搭配 CPU isolation。常見做法包括:
* 使用 cpuset cgroup，將一組 CPU 保留給特定工作負載
* 開機參數 `isolcpus=`，避免一般 task 被自動放進特定 CPU
* 開機參數 `nohz_full=`，讓指定 CPU 盡量免於週期性 scheduler tick 干擾
不過，CPU isolation 從來不是「設一個旗標就完成」的功能。若核心工作執行緒、中斷、RCU callback 或 ksoftirqd 仍落在同一組 CPU 上，隔離效果就會被打折扣。因此，實務上必須連同 IRQ affinity、housekeeping CPU 與 cgroup 配置一起考慮。
也因此，現代 Linux 排程不只是挑 task，還包括回答三個問題:
1. 這個 task 採用哪一類排程政策？
2. 這個 task 可在哪些 CPU 上跑？
3. 哪些 CPU 應保留給延遲敏感或即時工作負載？
## 延伸閱讀
經典論文與歷史文獻:
* [Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation](https://people.eecs.berkeley.edu/~istoica/papers/eevdf-tr-95.pdf) : Ion Stoica, Hussein Abdel-Wahab, 1995. EEVDF 演算法原始論文
* [[Announce] Modular Scheduler Core and Completely Fair Scheduler](https://lkml.org/lkml/2007/4/13/180) : Ingo Molnár, 2007. CFS 在 LKML 的首次公告
Linux 核心文件:
* [CFS Scheduler](https://docs.kernel.org/scheduler/sched-design-CFS.html) : CFS 排程器設計文件
* [EEVDF Scheduler](https://docs.kernel.org/scheduler/sched-eevdf.html) : EEVDF 排程器核心文件
* [Extensible Scheduler Class](https://docs.kernel.org/scheduler/sched-ext.html) : sched_ext 架構與介面
LWN 深度報導:
* [An EEVDF CPU scheduler for Linux](https://lwn.net/Articles/925371/) : Jonathan Corbet, 2023. Peter Zijlstra 的 EEVDF patch series 分析
* [Completing the EEVDF scheduler](https://lwn.net/Articles/969062/) : Jonathan Corbet, 2024. EEVDF 後續補完與延遲敏感任務機制
* [The extensible scheduler class](https://lwn.net/Articles/922405/) : Jonathan Corbet, 2023. sched_ext 概念首次報導
* [Sched_ext at LPC 2024](https://lwn.net/Articles/991205/) : Jonathan Corbet, 2024. Linux Plumbers Conference sched_ext 微型研討會紀錄
* [CFS group scheduling](https://lwn.net/Articles/240474/) : LWN, 2007. CFS 群組排程機制
* [CFS bandwidth control](https://lwn.net/Articles/428230/) : LWN, 2011. `cfs_quota_us` / `cfs_period_us` 頻寬控制
系列講座:
* [Scheduler(1): O(1) Scheduler](https://hackmd.io/@sysprog/linux-scheduler-1) : O(1) 排程器設計與 bitmap + priority queue 原理
* [Scheduler(2): 概述 CFS](https://hackmd.io/@sysprog/linux-scheduler-2) : CFS 設計原理與公平性機制
* [Scheduler(3): 深入剖析 CFS](https://hackmd.io/@sysprog/linux-scheduler-3) : CFS 實作細節: enqueue/dequeue 與 pick-next-task
* [Scheduler(4): PELT](https://hackmd.io/@sysprog/linux-scheduler-4) : Per-Entity Load Tracking 與指數衰減負載追蹤
* [Scheduler(5): EEVDF 排程器](https://hackmd.io/@sysprog/linux-scheduler-5) : EEVDF 理論基礎、delayed-dequeue 機制與核心 patch 分析
* [Scheduler(6): 排程器測試工具](https://hackmd.io/@sysprog/linux-scheduler-6) : Hackbench、Schbench、Cyclictest 等效能評比工具
* [Scheduler(7): sched_ext](https://hackmd.io/@sysprog/linux-scheduler-7) : 以 eBPF 實作可抽換排程策略的框架
* [Scheduler(8): Energy Aware Scheduling](https://hackmd.io/@sysprog/linux-scheduler-8) : 大小核架構的能源感知排程機制
* [Scheduler(9): Deadline Scheduling](https://hackmd.io/@sysprog/linux-scheduler-9) : EDF 演算法、CBS 機制與 SCHED_DEADLINE 實作
* [Scheduler(10): PREEMPT_RT](https://hackmd.io/@sysprog/linux-scheduler-10) : PREEMPT_RT patch series 與 RTLA 延遲分析工具
版本紀錄:
* [Linux v6.6](https://kernelnewbies.org/Linux_6.6) : 2023 年 EEVDF 取代 CFS 的版本
* [Linux v6.12](https://kernelnewbies.org/Linux_6.12) : 2024 年 sched_ext 正式合併的版本
Sign in via Google
Sign in via Facebook
Sign in via X(Twitter)
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet
Connect another wallet