萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 伺服器教學

Linux 核心進程調度器演進與策略深度解析:從 O(1) 到 CFS、實時調度與搶佔模型

調度器核心觀念

  • 僅調度 TASK_RUNNING 狀態進程;睡眠/等待進程不在調度隊列。
  • 系統負載低時調度壓力小;高負載時調度品質決定系統吞吐與延遲。
  • 分兩大類:實時進程 (優先級 1-99) 與 普通進程 (nice -20~19,映射優先級 100-139)。

實時進程調度策略

策略行為適用場景
SCHED_FIFO先進先出,同優先級搶佔只能靠主動 sched_yield() 或阻塞確定性高、執行時間短的控制迴路
SCHED_RR時間片輪轉,同優先級按時間片輪換需公平分時的實時任務
  • 實時進程優先級由用戶空間透過 sched_setscheduler()/sched_setparam() 設定 (需 CAP_SYS_NICE),核心不動態調整。
  • 只要有實時進程可執行,普通進程完全無法獲得 CPU。

普通進程調度演進

1. Linux 2.4:O(n) 線性掃描

可執行隊列為單鏈表,每次調度掃描全表尋找最高 goodness(),複雜度 O(n)。

2. Linux 2.6 早期:O(1) 調度器

  • 140 個優先級陣列 (active/expired 兩組),每優先級一個鏈表。
  • 調度直接取 active 最高非空鏈表頭,O(1)。
  • 時間片用盡移入 expired;active 為空時交換指標。
  • 優點:極快;缺點:優先級粒度固定 (140 級),難以精細實現公平性。

3. Linux 2.6 後期至今:CFS (Completely Fair Scheduler)

  • 紅黑樹按 vruntime (虛擬運行時間) 排序,最左節點為下一個調度目標。
  • 複雜度 O(log N),N 為可執行進程數。
  • 「公平性」即 vruntime 增長速度與 nice 值成反比 (nice -20 权重最高)。
  • 支援群組調度 (cgroup)、帶寬控制、NUMA 感知負載均衡。

調度觸發時機

  1. 主動放棄:sleep、exit、等待 I/O、鎖、信號 (SIGSTOP)。
  2. 搶佔:
    • 時間片耗盡 (時鐘中斷檢測)。
    • 更高優先級進程就緒 (中斷喚醒、鎖釋放、定時器到期)。

混合調度場景 (實時 + 普通)

  • 實時進程就緒 → 立即搶佔普通進程。
  • 實時進程間按優先級搶佔;同優先級按 FIFO/RR。
  • RR 是 FIFO 延伸,解決同優先級飢餓問題。

Ingo Molnar 實時補丁 (PREEMPT_RT) 四種搶佔模式

模式配置選項特性適用場景
No Forced Preemption (Server)CONFIG_PREEMPT_NONE標準核心,無核心搶佔科學計算、高吞吐伺服器
Voluntary Kernel Preemption (Desktop)CONFIG_PREEMPT_VOLUNTARY關鍵路徑加入 might_resched(),降低延遲桌面、一般嵌入式
Preemptible Kernel (Low-Latency Desktop)CONFIG_PREEMPT核心可搶佔 (除 critical section),軟實時音視頻、工控、嵌入式
Complete Preemption (Real-Time)CONFIG_PREEMPT_RT全核心可搶佔、中斷執行緒化、PI 鎖,硬實時級機器人、高頻交易、工業控制

實時性越強,吞吐率越低,需根據業務權衡。

總結

從 O(n) → O(1) → CFS 紅黑樹,Linux 調度器在效率與公平性間不斷演進。理解實時/普通雙軌制、CFS 虛擬時間機制、搶佔模型,是效能調優與延遲敏感應用部署的基石。

copyright © 萬盛學電腦網 all rights reserved