Linux 進程調度核心原理：從 O(1) 到 CFS 紅黑樹演進

前言

進程調度是作業系統核心中最頻繁執行、對效能影響最大的子系統。Linux 經歷了 O(n) 線性掃描 → O(1) 陣列佇列 → O(log N) CFS 紅黑樹 三代演進。本文深入剖析實時/普通進程調度策略、動態優先級計算、公平性實現、多核負載均衡、優先級繼承、中斷執行緒化等核心機制。

一、進程分類與調度策略

實時進程調度細節

• SCHED_FIFO：先進先出，無時間片，除非主動 sched_yield()、阻塞、或被更高優先級搶佔，否則獨佔 CPU。
• SCHED_RR：輪轉，每進程固定時間片（預設 100ms），時間片耗盡移至同優先級隊列尾部。
• 限制實時佔用：/proc/sys/kernel/sched_rt_runtime_us (預設 950ms) / sched_rt_period_us (1s)，保留 5% CPU 給普通進程防死鎖。
• 權限：需 CAP_SYS_NICE（通常 root）才能 sched_setscheduler 設為實時。

二、普通進程 CFS（Completely Fair Scheduler）核心

1. 虛擬運行時間

CFS 不直接用優先級決定誰跑，而是維護每個進程的 vruntime（虛擬運行時間）：

vruntime += 實際運行時間 * (NICE_0_LOAD / 權重)
權重 = 1024 / (1.25 ^ nice)   # nice -20 權重最高 ~88761，nice +19 最低 ~15

vruntime 越小 = 應該越早獲得 CPU。

2. 紅黑樹佇列

• 所有可執行進程（TASK_RUNNING）掛在 cfs_rq->tasks_timeline 紅黑樹上，鍵值為 vruntime。
• 調度器每次選擇 最左節點（vruntime 最小） 進程運行。
• 插入/刪除/查找最小值複雜度均為 O(log N)，N 為可執行進程數。

3. 時間片動態計算

目標延遲 = sched_latency_ns (預設 6ms * log2(CPU數))
最小粒度 = sched_min_granularity_ns (預設 0.75ms)
時間片 = max(目標延遲 / 可執行進程數, 最小粒度)

進程數少 → 時間片大；進程數多 → 時間片縮小至最小粒度。

4. 調度入口

• schedule()：主動放棄 CPU（睡眠、等待鎖、sched_yield）。
• preempt_schedule()：內核搶佔點（中斷返回、釋放鎖）。
• tick 周期性檢查：scheduler_tick() 更新 vruntime，判斷是否需要搶佔。

三、動態優先級與互動性判斷（CFS 前身 O(1) 遺留邏輯）

雖 CFS 主打 vruntime，但 nice 值仍影響權重。早期 O(1) 調度器透過 睡眠時間 vs 運行時間 判斷互動性：

• 睡眠久、運行短 → 互動進程（GUI、服務端） → 獎勵優先級（降低 nice）。
• 長期運行、不睡眠 → 批次進程（編譯、科學計算） → 懲罰優先級（升高 nice）。

CFS 以權重取代動態優先級調整，但 sched_autogroup、sched_child_runs_first 等參數仍影響公平性感知。

四、調度觸發時機

五、多核負載均衡

架構

• 每 CPU 一個 rq（運行佇列），掛載該 CPU 可執行進程的 CFS 紅黑樹。
• idle_balance()：CPU 閒置時主動從最忙 CPU 偷任務。
• load_balance()：定期（sched_balance_interval）檢查佇列負載差異，遷移任務。

負載追蹤

• PELT (Per-Entity Load Tracking)：指數加權移動平均 (EWMA) 追蹤任務/佇列負載，平滑短期波動。
• 負載單位：1024 = 100% CPU。

拓撲感知

• SMT（超執行緒）姊妹核心共享 L1/L2 → 遷移成本極低，優先均衡。
• NUMA 節點跨插槽 → 遷移成本高（記憶體遠端存取），謹慎遷移。
• sched_domain 階層建模：SMC → MC → NUMA → ALL。

六、優先級繼承與反轉

問題

高優先級進程 A 等待鎖 → 低優先級進程 B 持有鎖 → 中優先級進程 C 搶佔 B → B 無法釋放鎖 → A 無限期阻塞（優先級反轉）。

解決：PI Mutex (Priority Inheritance)

• 鎖定 pthread_mutexattr_setprotocol(PTHREAD_PRIO_INHERIT)。
• 內核 rtmutex 實現：B 臨時繼承 A 的優先級，直至釋放鎖。
• 適用於實時進程同步，普通進程預設不啟用（futex 無 PI）。

七、中斷執行緒化

• 傳統：硬中斷上下文不可搶佔、不可調度、無 task_struct。
• Threaded IRQ：request_threaded_irq() 將處理函數移至內核執行緒（irq/xx），擁有 task_struct、可調度、可設定優先級。
• 優點：實時進程可搶佔中斷處理、中斷處理可睡眠（申請鎖、分配記憶體）。
• 代價：上下文切換開銷、延遲增加微秒級。
• 現狀：CONFIG_IRQ_FORCED_THREADING 強制執行緒化，大多數驅動已遷移。

八、關鍵調優參數（/proc/sys/kernel/）

九、總結

Linux 調度器從 O(1) 固定時間片轉向 CFS 紅黑樹 + vruntime，本質是用 「公平性即服務」 取代 「優先級即特權」。理解 vruntime、紅黑樹、PELT 負載追蹤、PI Mutex、Threaded IRQ 等機制，能讓你在實時系統調優、容器 CPU 配額設計、高併發伺服器調試中精準定位根因。

• 上一篇文章： Shell 自動交互三大絕技：Here Document、Pipe 與 Expect 實戰比較
• 下一篇文章： Linux 讀寫鎖實現原理與核心程式碼詳解

Linux 教學

Linux LVM 邏輯卷管理完整指南：架構、操作與進階應用

CentOS VPS 搭建 IPSec + L2TP VPN 完整教程

Bash 是什麼？從 Shell 到 Shellshock 漏洞的完整解析