2007 - CFS 排班與 2.6.23（紅黑樹取代啟發式）#

案件摘要#

2007 年 10 月，Linux 2.6.23 發布，帶入 Ingo Molnar 的 CFS（Completely Fair Scheduler，完全公平排班器）—— 用紅黑樹取代 O(1) 排班器的啟發式互動偵測：

理論純潔性戰勝啟發式——CFS 用「虛擬執行時間（vruntime）」把公平性變成數學問題。

前因 -- 為什麼會有這個案子#

• O(1) 排班器的缺陷：O(1) 用複雜的啟發式判斷「哪些行程是互動式」（要給高優先度）——啟發式在桌面遊戲、影音編碼混跑時猜錯，互動卡頓——彌補的缺陷：啟發式不可靠。
• Con Kolivas 的刺激：桌面玩家 Kolivas 的 RDSL/staircase 排班器（2006–07）在桌面互動上表現更好，但 Torvalds 不採用——Molnar 受刺激後一個週末寫出 CFS。
• 理論基礎：理想公平排班（ideal fair scheduling）——若有無限細的時間粒度，每個可執行行程應獲得 1/n 的 CPU。CFS 用 vruntime 追蹤「誰領得少」。

線索與推理 -- CFS 的數學#

第一條線索：vruntime——公平的會計#

• 每個行程有 vruntime（虛擬執行時間）；排班永遠選 vruntime 最小者——紅黑樹左下角 O(log n) 取得。
• 彌補的缺陷：啟發式「猜互動」→ 數學式「誰領得最少就給誰」——公平性從猜測變成計算。

第二條線索：紅黑樹——O(log n) 的排班#

• 彌補的缺陷：O(1) 用 140 個佇列（優先度陣列）——粒度固定且僵硬；紅黑樹允許任意權重的動態排班。

第三條線索：群組排班（group scheduling）#

CFS 支援按使用者/群組分配：使用者 A 的 100 個行程與使用者 B 的 1 個行程，各得 50%—— - 彌補的缺陷：一個使用者開 100 個行程霸佔 CPU——公平性推廣到「群組」層級（後來與 cgroups 整合）。

C 範例：CFS 的核心資料結構#

/* kernel/sched_fair.c (2007) 風格 */
struct sched_entity {
    struct rb_node run_node;     /* 紅黑樹節點 */
    u64 vruntime;                /* 虛擬執行時間——公平的會計 */
    u64 sum_exec_runtime;        /* 實際執行時間 */
};

static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq) {
    /* 紅黑樹最左節點 = vruntime 最小 = 下一個跑 */
    struct rb_node *left = cfs_rq->rb_leftmost;
    return rb_entry(left, struct sched_entity, run_node);
}

Python 範例：CFS 的模擬#

from sortedcontainers import SortedList

class CFS:
    def __init__(self):
        self.tree = SortedList(key=lambda e: e["vruntime"])

    def enqueue(self, pid, weight):
        self.tree.add({"pid": pid, "weight": weight, "vruntime": 0})

    def schedule(self, dt=1.0):
        ent = self.tree[0]                      # vruntime 最小者先跑
        ent["vruntime"] += dt * 1024 / ent["weight"]
        self.tree.remove(ent); self.tree.add(ent)  # 重新插入平衡樹
        return ent["pid"]

cfs = CFS()
cfs.enqueue("nice0", 1024); cfs.enqueue("nice-5", 3121)
for _ in range(6):
    print(cfs.schedule())
# nice-5（權重高）被排班的次數多——公平按權重分配

Shell 範例：nice 權重的實證#

# nice 值影響 CFS 權重：nice -5 ≈ 3 倍 CPU 份額
$ nice -n -5 ffmpeg -i video.avi out.mp4 &   # 高權重：編碼加速
$ nice -n 19 updatedb &                       # 低權重：背景雜務讓路
$ top -b -n1 | head -8                        # 觀察 %CPU 份額

結案 -- 後果與影響#

• 桌面互動的解決：CFS 讓「背景重負載 + 前景即時互動」共存——Linux 桌面可用性大躍進。
• 理論的勝利：CFS 證明「數學公平」比「啟發式猜測」更可靠——後續 EEVDF（2024，6.6 排班器）進一步加入延遲敏感度。
• Kolivas 的平行宇宙：他的 MuQSS（2016）持續服務桌面玩家社群——啟發式派與數學派的百年角力。
• 歷史教訓：當啟發式開始猜錯，就該回到數學——CFS 是排班理論（公平共享）在實戰的勝利。

關鍵人物與文獻#

• I. Molnar：CFS (2007, 2.6.23)。
• C. Kolivas：RDSL/staircase (2006–07)、MuQSS (2016)。
• C. A. Waldspurger：lottery/stride scheduling（1995，CFS 的理論先驅）。
• 相關案件：2003-2.6核心革命.md、2008-cgroups與LXC.md。