當「平均來說夠好」還不夠好
到目前為止，你學到的所有 CPU 排程都追逐著同一個目標：平均來說表現良好。輪流排程讓每個人「平均」都保有回應性；SJF 把平均等待時間壓到最低；多層回饋佇列去猜哪些工作是互動式的，並善待它們。對一台筆電或一台網頁伺服器來說，「平均」正是恰當的目標——如果你的音樂播放器偶爾多等了幾毫秒，沒有人會因此送命。
但現在請想像汽車安全氣囊控制器、心律調節器，或工廠機械手臂裡的軟體。在這裡，一個任務不只是「重要」——它有一個截止期限（deadline），一個它絕對必須在之前完成的實際時刻。一個晚了 50 毫秒才引爆的安全氣囊，比沒用還糟。這就是即時排程的領域，而它徹底改變了問題。我們不再問「我們要怎樣讓平均值開心？」我們問的是「我們能不能在系統還沒開始跑之前，就『證明』每一個截止期限都將永遠被滿足？」
兩種即時排程器：固定優先權對上最近的截止期限
大多數即時工作是週期性的：一個任務每隔一段時間就醒來、做固定份量的工作，並且必須在它下一次醒來之前完成。每 10 毫秒讀一次溫度；每 16 毫秒更新一次畫面。所以每個任務都有一個週期（多久跑一次）與一個執行時間（一次跑要花多久）。給定單一 CPU 上的一堆這種任務，兩個著名的演算法之間，只在於它們如何指派優先權。
速率單調排程是比較簡單的那個：它把最高優先權交給「週期最短」的任務，而且從不改變主意。跑得越頻繁，就被當成越緊急——這就是全部的規則。由於優先權一次定好、永不更動，速率單調排程容易實作、也容易推理。它的缺點是它無法總是用滿整顆 CPU：即使存在一份能尊重所有截止期限的排程，一旦 CPU 太擁擠，速率單調可能就是找不到它（最壞情況下大約超過 69% 使用率就會如此）。
最早截止期限優先是比較聰明的那個：在每一個瞬間，它都執行「截止期限最近」的那個就緒任務，並隨著截止期限逼近而即時重算優先權。其回報相當亮眼——EDF 在單一 CPU 上是最佳的：只要有任何排程器能滿足所有截止期限，EDF 也能，而且它能把 CPU 一路榨到 100% 使用率。代價是更多的記帳工作（它必須不斷依截止期限重新排序），以及一種更難看的失敗模式：當超載的速率單調系統崩潰時，是優先權最低的任務先錯過，可以預測；而當超載的 EDF 系統崩潰時，它可能連鎖反應、四處錯過截止期限。
T1: period 4 ms, run 1 ms T2: period 5 ms, run 2 ms Rate-monotonic (T1 shorter period => higher priority): | T1 | T2 | T2 | T1 | T2 | T2 | T1 | ... ^T1 always wins ties; fixed forever Earliest-deadline-first (run the nearest deadline): | T1 | T2 | T2 | ... whoever's deadline is closest right now ^priorities recomputed as deadlines move
不只一顆 CPU：在不亂套的前提下分攤工作
到目前為止，我們一直默默假設只有一顆 CPU，並只問「接下來誰執行？」。然而每一台現代機器都有好幾個 CPU 核心，於是真正的問題變成了「誰要在『哪裡』執行，在哪一個核心上？」這就是多處理器排程，它帶來了真正全新的問題。最乾淨的設計是給所有核心共用一條就緒佇列，讓任何閒置的核心去搶下一個行程——簡單，但現在每個核心都得爭奪那一條佇列的鎖，當你加入越多核心，它就越成為瓶頸。所以多數真實系統改成給每個核心它『自己的』執行佇列，而困難之處變成了：要怎麼讓那些佇列保持平衡。
如果每個核心都有自己的佇列，就可能出現一個核心被十個行程淹沒、隔壁卻閒著沒事——白白浪費了一整顆 CPU。解法是負載平衡：核心會週期性地檢查有沒有失衡的佇列，並把工作遷移過去。它有兩種風味——推送遷移（push），由忙碌核心的執行佇列主動把任務塞給閒置的那個；以及拉取遷移（pull），由閒置的核心伸手過去，從較忙的鄰居那兒偷一個任務過來。真實的核心兩者都做。想像超市的結帳通道：一名店員要嘛揮手請你去空著的櫃台（推），要嘛閒著的收銀員喊一聲「下一位請到這邊」（拉）。
但這裡藏著一股張力。把一個行程移到不同的核心並非免費，因為每個核心都有自己快速的本地快取，裡頭裝滿了那個行程最近用過的資料。一旦遷移行程，你就把它溫熱的快取留在原地了；在新核心上它從「冷」開始，必須把一切都從主記憶體重新載入，那慢得多。核心傾向把行程留在它上一次執行的『同一個』核心上，這就叫做處理器親和性——正是記憶體階梯裡那套關於 TLB 與快取的智慧，套用到排程上：在使用地點附近的溫熱資料，是黃金，所以別輕易把它丟掉。
一個真實的排程器：Linux 的完全公平排程器
該來看看這一切理論如何落地到一個真實、實際出貨的作業系統裡了。十多年來，Linux 對於一般任務的預設排程器一直是完全公平排程器（Completely Fair Scheduler），簡稱 CFS，而它的核心想法簡單得令人愉快。CFS 不用固定的時間片，而是追蹤每個可執行任務已經拿到了多少 CPU 時間——它把這個數字叫做虛擬執行時間（virtual runtime）——並且永遠去執行「目前為止拿得最少」的那個任務。被餓得最久的任務，下一個上。這就是輪流排程的那份公平，只是連續的，而不是被切成僵硬的時間量子。
那麼，「把 CPU 給目前跑得最少的人」要怎麼處理優先權？靠的是虛擬執行時間那只時鐘的『速度』。一個高優先權任務的虛擬執行時間走得很慢，於是即使它用掉了大量真實 CPU 時間，看起來仍像是「被虧待」而持續被挑中；一個低優先權任務的時鐘則飛快前進，於是它很快就看起來「滿足了」而讓到一旁。同一條公平規則，不同的時鐘速率——優雅，而且遠比上一篇那些層層疊疊的回饋佇列來得不繁瑣。為了能快速挑出被服務得最少的任務，CFS 把所有可執行任務存在一棵依虛擬執行時間排序的平衡樹裡，於是就算有上千個任務，找出下一個該跑的也很便宜。
- 三個任務變成可執行。CFS 記下每一個的虛擬執行時間；一個全新的任務從目前的最小值附近起步，於是它既不會被不公平地偏袒，也不會被餓著。
- 派工器挑出虛擬執行時間最小的任務——落後最多的那個——並執行它。（這正是派工器在做它的脈絡切換，和第一篇裡一模一樣。）
- 當那個任務執行時，它的虛擬執行時間爬升——若它是高優先權就爬得慢，若是低優先權就爬得快。跑了一小片之後，核心檢查現在是不是有別人落後得更多了。
- 如果現在出現了一個更被餓著的任務（或剛有人醒來），CFS 就搶占目前的任務，切換到那個新的、落後最多的。然後永遠重複——公平是被『連續地』維持著的，而不是在固定的量子邊界上才維持。
兩個誠實的但書，讓 CFS 不至於聽起來像魔法。第一，「完全公平」是個理想，而不是字面上的承諾——在有著有限計時器、快取與親和性成本的真實硬體上，CFS 只是『逼近』完美的公平，正如 LRU 只是逼近那個無法實現的最佳分頁置換。第二，CFS 是給一般任務用的；Linux 把真正的即時任務（你的 EDF 與固定優先權的截止期限工作）跑在完全『分離』的排程類別上，而那些類別永遠壓過 CFS。而事實上，Linux 此後已經逐步把預設換成一個叫 EEVDF 的更新排程器——這提醒我們，就算是已出貨的排程器，也仍在不斷演進。
整個階梯，濃縮成一張圖
退一步看，這五篇構成了一道完整的弧線。你從「我們究竟為什麼要排程」開始問起——因為一個行程在運算的爆發與等待 I/O 之間交替，所以 CPU 空閒的時候比你以為的多得多，而一個排程器決定由誰來填補那個空檔。接著來了那一整族演算法，每一個都修補著前一個的缺陷：FCFS 公平，卻苦於護衛隊效應；SJF 對等待時間是最佳的，卻需要一顆水晶球、還可能餓死大工作；輪流排程保證了回應性，但它的時間量子必須調得剛剛好；優先權則冒著飢餓的風險，直到老化來拯救那些被遺忘的。
這最後一篇把那一切都提升到了真實世界。經典演算法最佳化的是平均值；即時排程要的是一份關於最壞情況的證明；多核心排程奮力讓眾多核心保持忙碌、又不失去快取的溫熱；而一個像 Linux 這樣的真實核心，則把這些想法融在一起——用虛擬執行時間為一般工作帶來公平、用分離的嚴格類別處理截止期限、用尊重親和性的謹慎遷移。沒有單一演算法能處處勝出，而這正是整個階梯最深的一課：排程不在於找出那唯一最好的政策，而在於知道你『這台特定機器與這份特定工作負載』真正需要的是哪一種取捨。