Linux 進程排程算法深度解析：FCFS、RR、多級回饋佇列、實時排程與 CFS 完全公平排程器

Linux 核心排程器經歷 O(1) → CFS (Completely Fair Scheduler) 演進。本文系統梳理經典排程算法 (FCFS、RR、預測式、優先權、多級回饋)、實時排程 (FIFO/RR/Deadline)、CFS 紅黑樹虛擬運行時間機制、CGroup 頻寬控制，並對比 Windows 排程差異。

經典批次/分時排程算法

Linux 實時排程類別

SCHED_FIFO   先入先出，同優先權無時間片，搶佔低優先權
SCHED_RR     輪轉，同優先權有時間片
SCHED_DEADLINE  EDF (Earliest Deadline First)，保證截止時間
# 需 CAP_SYS_NICE 權限
chrt -f 99 ./realtime_app

CFS (完全公平排程器) 核心機制

• 紅黑樹：以 vruntime (虛擬運行時間) 為鍵，最左節點 = 最值得運行的進程。
• vruntime 計算：vruntime += 实际运行时间 * 1024 / 权重，權重由 nice 值決定。
• 時間片動態：sched_latency / 進程數，最小 sched_min_granularity。
• 負載均衡：定期跨 CPU 遷移任務，維持各 CPU load_avg 平衡。

CGroup v2 + CPU 控制器

# 限制容器 CPU 配額 (quota/period)
echo 50000 > /sys/fs/cgroup/container/cpu.max   # 50% CPU (period=100000)

從 FCFS 到 CFS，Linux 排程器始終在「公平性、回應性、吞吐量」三角中尋找最佳平衡點。