作業系統範例 (Operating-System Examples)
本系列文章內容參考自經典教材 Operating System Concepts, 10th Edition (Silberschatz, Galvin, Gagne)。本文對應章節:Section 5.7 Operating-System Examples。
本節以 Linux、Windows、Solaris 三個主流 OS 為例,說明排程理論在實際系統中的具體落實方式。本節所稱的「排程」,在 Linux 中是針對 kernel task 的排程,在 Solaris 與 Windows 中則是針對 kernel thread 的排程。
5.7.1 Linux 排程
歷史演進
Linux 排程器歷經三個明顯世代:
- Linux 2.5 以前:沿用傳統 UNIX 排程演算法。因未針對 SMP(Symmetric Multiprocessing)設計,當 Runnable Process 數量增多時,效能明顯下降。
- Linux 2.5 — O(1) 排程器:以常數時間複雜度(Constant Time)運作,加強 SMP 支援,並引入 Processor Affinity 與 Load Balancing。然而在桌面系統常見的互動式程序(Interactive Process) 上,響應時間較差。
- Linux 2.6.23 起:引入 CFS(Completely Fair Scheduler,完全公平排程器),成為預設排程演算法,在互動性與公平性之間取得更好的平衡,延用至今。
排程類別(Scheduling Classes)
Linux 的排程架構建立在排程類別(Scheduling Class) 的概念上:每個類別有自己的優先層級與排程演算法,排程器每次選擇優先層級最高的類別中優先層級最高的 Task 來執行。標準 Linux Kernel 實作兩個排程類別:
- 預設類別(Default Class):使用 CFS 演算法,面向一般程序
- 即時類別(Real-Time Class):使用 POSIX 標準的
SCHED_FIFO或SCHED_RR
這個架構讓 Kernel 可以依系統需求(伺服器、桌面、嵌入式)替換或新增排程類別,具有良好的擴充性。
CFS 核心設計:比例式 CPU 時間
傳統排程器直接指定每個 Process 的 Time Quantum。CFS 採用完全不同的思路:不指定固定的 Time Quantum,而是將 CPU 時間以比例方式分配給每個 Task。
比例的計算依據是 Nice Value(友善值):
- Nice Value 的範圍是 −20 到 +19,數值越低表示優先層級越高
- 預設 Nice Value 為 0
- Nice Value 越高(越「nice」),表示主動讓出 CPU 給其他 Task,獲得較低比例的 CPU 時間
- Nice Value 越低,獲得越高比例的 CPU 時間
CFS 不以 Time Slice 作為分配單位,而是定義一個 Targeted Latency:在這段時間區間內,每個 Runnable Task 應至少執行一次。每個 Task 所獲得的 CPU 時間,就是從 Targeted Latency 中依比例切割出來的份額。
為什麼不乾脆把 Targeted Latency 設得超長,保證每個 Task 都跑得到?
如果 Targeted Latency 是 10 秒,系統裡有 100 個 Task,每個 Task 每 10 秒才輪到一次。對互動式程式(例如文字編輯器)來說,按下按鍵後要等到 10 秒後才能響應,使用體驗完全無法接受。Targeted Latency 本質上就是「每個 Task 最久等多久才能輪到 CPU」的上限承諾,設太長就等於放棄了響應性。
那 Targeted Latency 的預設值是怎麼訂出來的?它是根據「讓使用者感覺不到延遲」的經驗值決定的(Linux 預設約 6–8 ms),這是在「響應速度」與「Context Switch 開銷」之間取得平衡的結果:太短,CPU 大部分時間花在切換;太長,響應性變差。
為什麼 Task 變多時 Targeted Latency 要自動增加?
假設 Targeted Latency 固定為 6ms,系統裡有 1000 個 Task,每個 Task 只分到 6ms / 1000 = 6μs,比一次 Context Switch 本身的耗時還短,換來換去毫無意義。因此,當 Active Task 數量超過閾值時,Targeted Latency 自動拉長,確保每個 Task 至少能執行一個 Minimum Granularity(最小粒度) 的時間(Linux 預設約 0.75ms),讓實際工作時間佔 Context Switch 開銷的合理比例。
vruntime 機制:CFS 的決策核心
CFS 用一個 per-task 變數 vruntime(virtual runtime,虛擬執行時間) 來追蹤每個 Task 已獲得多少 CPU 時間。
在理解 vruntime 之前,先區分兩個概念:
- 實際執行時間(Physical Runtime):Task 真正在 CPU 上運作的掛鐘時間(wall-clock time)。 例如一個 Task 在 CPU 上跑了 200ms,它的實際執行時間就是 200ms,這是客觀的物理時間。
- 虛擬執行時間(Virtual Runtime / vruntime):CFS 內部維護的一個加權計數器,不等於實際執行時間,而是根據 Task 的優先層級(Nice Value)對實際執行時間進行縮放後的值。
vruntime 的關鍵規則:vruntime 的增長速率取決於 Nice Value。
- Nice Value = 0(Normal Priority):vruntime 以 1:1 比率增長,跑 100ms → vruntime 增加 100ms
- 優先層級較高(Nice Value 較低,如 −10):vruntime 增長較慢,跑 100ms → vruntime 只增加約 50ms
- 優先層級較低(Nice Value 較高,如 +10):vruntime 增長較快,跑 100ms → vruntime 增加約 200ms
增長速率的目的不是「給 Task 更多時間跑」,而是讓排程決策自動反映優先層級。排程器永遠選取 vruntime 最小的 Task 執行。由於高優先層級 Task 的 vruntime 增長慢,即使它已經跑了一段時間,vruntime 依然可能比其他 Task 低,因而持續獲得 CPU。
- 每次排程時,CFS 選擇 vruntime 最小的 Task 執行
- 若有更高優先層級的 Task 變為 Runnable,可以搶佔(Preempt)正在執行的較低優先層級 Task
下圖說明 CFS 排程器持續運作的循環:
vruntime 機制的核心洞察在於:它讓「公平」這個概念自動浮現,而非靠外部強制。只要每個 Task 的 vruntime 依優先層級以不同速率增長,高優先層級 Task 的 vruntime 自然長期偏低,排程器永遠優先選它,完全不需要任何「優先層級佇列」或「搜尋優先層級」的額外邏輯。
I/O 密集 vs. CPU 密集的自然平衡
以兩個 Nice Value 相同的 Task 為例(因此 vruntime 增長速率相同),一個 I/O 密集(I/O-bound),一個 CPU 密集(CPU-bound):
- I/O 密集 Task:每次獲得 CPU 後只跑幾毫秒(例如 5ms),就因等待鍵盤輸入或磁碟資料而主動進入 Blocking 狀態,讓出 CPU。在 Blocking 期間,它不在 CPU 上運作,vruntime 完全停止增長。 等 I/O 完成喚醒後,再跑幾毫秒,再次 Blocking。
- CPU 密集 Task:每次獲得 CPU 就一路跑到時間用完(例如 20ms)才被排程器強制切換,從不主動放棄 CPU。它在 CPU 上持續運作,vruntime 不停累積。
兩者的 vruntime 增長速率雖然相同(Nice Value 相同),但累積的實際 CPU 時間差距巨大:在同一段掛鐘時間內,I/O 密集 Task 可能只真正使用了 CPU 50ms,CPU 密集 Task 卻使用了 500ms。vruntime 直接反映這個差距。
隨著時間推移,I/O 密集 Task 的 vruntime 遠低於 CPU 密集 Task。當 I/O 密集 Task 等待的 I/O 資料到位、重新成為 Runnable 時,它的 vruntime 最小,立即搶佔 CPU 密集 Task。
結果:互動式程序自然浮升,獲得快速的 CPU 響應;CPU 密集程序則在背景利用閒置的 CPU。這不需要任何人工干預,純粹由 vruntime 的自然差異驅動。
即時排程
Linux 採用 POSIX 標準實作即時排程,提供兩種即時排程政策(Scheduling Policy)供 Task 選擇使用:
SCHED_FIFO(First-In, First-Out):即時 Task 依照先進先出順序排程。一旦取得 CPU,就持續執行直到主動 Blocking 或被更高優先層級的即時 Task 搶佔為止,同優先層級之間沒有 Time Slice,不會被強制切換。SCHED_RR(Round-Robin):與SCHED_FIFO相同,但在同優先層級的即時 Task 之間加入 Time Slicing,讓它們能輪流使用 CPU,而不是讓先到的那個一直跑。
「使用這些政策」的意思是:每個 Thread 可以在建立時(或事後)透過 POSIX API(例如 pthread_attr_setschedpolicy())指定自己的排程政策為 SCHED_FIFO 或 SCHED_RR,Linux Kernel 就會依照所選政策來排程該 Thread。
即時 Task 的優先層級永遠高於所有 Normal Task。Linux 使用兩套獨立的優先層級數值空間:
下圖顯示 Linux 系統中的優先層級範圍配置:
兩個區段的含義:
- real-time(0–99):即時 Task 使用
SCHED_FIFO或SCHED_RR,靜態分配優先層級(不隨執行動態改變) - normal(100–139):普通 Task 由 CFS 管理,優先層級由 Nice Value 決定。Nice Value −20 對應 priority 100,Nice Value +19 對應 priority 139
這兩個範圍在系統內部構成一套統一的全域優先層級(Global Priority),數值越低優先層級越高,即時 Task 的全域優先層級永遠高於 Normal Task。
CFS 效能:紅黑樹(Red-Black Tree)
CFS 需要非常頻繁地找到「下一個應執行的 Task」,對效率要求極高。它使用的資料結構是紅黑樹(Red-Black Tree),這是一棵以 vruntime 為 key 的平衡二元搜尋樹(Balanced Binary Search Tree):
圖中各節點位置的含義:
- 左側節點:vruntime 較小(等待 CPU 時間最久,優先層級最高)
- 右側節點:vruntime 較大(已獲得較多 CPU 時間)
- 最左節點(Leftmost Node):vruntime 最小,是下一個應執行的 Task
當 Task 進入 Runnable 狀態(例如 I/O 完成),就加入樹中;當 Task 進入等待(例如發出 I/O 請求),就從樹中移除。
理論上,找到最左節點需要 O(log N) 步(N 為節點數)。但 Linux 排程器直接快取最左節點的指標於變數 rb_leftmost 中,因此選取下一個 Task 實際上只需 O(1) 時間:直接讀取快取值即可。
負載平衡與排程域(Scheduling Domains)
CFS 支援多核心系統上的負載平衡。在討論負載平衡之前,先釐清「負載(Load)」的定義。
直觀的想法是:「一個 Thread 使用 CPU 越多,負載就越高。」但 CFS 採用更精確的定義:負載 = 優先層級(Priority)與平均 CPU 使用率(Average CPU Utilization)的綜合指標。
這個定義的意義在於:
- 一個高優先層級但以 I/O 為主的 Thread(例如優先 −10 的互動式程序,但它大部分時間在等待使用者輸入):雖然優先層級高,但平均 CPU 使用率低,整體負載其實不高。
- 一個低優先層級但 CPU 密集的 Thread(例如優先 +5 的背景計算任務,持續使用 CPU):雖然優先層級低,但 CPU 使用率高,整體負載相當可觀。
這兩個 Thread 在 CFS 的定義下可能有相似的「負載」,平衡系統不應只看優先層級或只看 CPU 使用率。一個 Run Queue 的總負載 = 隊列中所有 Thread 負載的總和,負載平衡的目標是讓所有 Core 的 Run Queue 總負載盡量相等。
然而,遷移 Thread 到不同 Core 上可能引入記憶體存取代價(Cache 失效,或 NUMA 系統的跨節點記憶體延遲)。為了在負載平衡與記憶體效能之間取得平衡,CFS 定義了排程域(Scheduling Domain) 的層次結構:
圖中的排程域層次結構說明:
- domain0 / domain1:分別代表共享同一個 L2 Cache 的 Core 群組(例如 core0 與 core1 共享一個 L2,構成 domain0;core2 與 core3 共享另一個 L2,構成 domain1)
- physical processor domain(NUMA node):domain0 與 domain1 共享 L3 Cache,構成一個 NUMA 節點。在更大的 NUMA 系統中,多個 NUMA 節點可以進一步組成系統層級的域(System-Level Domain)
CFS 的負載平衡策略是從最低層級的域開始,逐層向上:
- 優先在同一個 domain 內進行 Thread 遷移(例如只在 domain0 的 core0 與 core1 之間)
- 若 domain 內部已均衡,才考慮跨 domain 遷移(domain0 ↔ domain1)
- 跨 NUMA 節點的遷移只在負載嚴重失衡時才發生,以避免高昂的 NUMA 跨節點記憶體延遲
- 若整體系統處於繁忙狀態,CFS 甚至不跨 domain 進行平衡
這個設計體現了一個核心取捨:負載平衡可以提升吞吐量,但 Thread Affinity(讓 Thread 留在同一 Core)可以降低 Cache Miss 與 NUMA 記憶體延遲。排程域層次結構讓這兩個目標在不同粒度上分別優化,互不干擾。