2.2 CPU 排班演算法（FCFS、SJF、Round Robin 與理論分析）#

排班問題的本質#

當多個就緒行程搶一個（或少數幾個）CPU，排班器（scheduler）必須決定「下一個跑誰、跑多久」。這是作業系統中最接近數學最佳化的一部分，也是在互動性（回應時間）與吞吐量（效率）之間取捨的藝術。排班概念最早可追溯到 1950 年代監督程式的單一佇列，而真正的學術研究爆發於 1960 年代分時系統時期：Corbató 在 CTSS（1961）為了讓每個使用者在兩秒內得到回應，發展出最早的時間輪轉排班。

評估排班演算法的標準量測（設行程 \(i\) 的到達時間為 \(t_i\) 、完成時間為 \(c_i\) 、服務時間（所需 CPU 時間）為 \(\tau_i\) ）：

• 等待時間 \(W_i = c_i - t_i - \tau_i\) ：在就緒佇列中浪費的時間。
• 週轉時間 \(T_i = c_i - t_i\) ：從到達到完成的總時長。
• 回應時間：第一次得到 CPU 前的等待（互動系統最重視）。
• 公平性：資源分配是否無人長期飢餓（starvation）。

注意一個殘酷的現實：服務時間 \(\tau_i\) 事先不可知。這使得理論上最優的演算法在實務上永遠只能被「估計」——這是排班理論貫穿始終的主旋律。

FCFS：先到先服務#

FCFS（First-Come, First-Served）是最自然的演算法：單一 FIFO 佇列，先到的先跑、跑完為止（非搶佔式）。1950 年代所有批次系統都是 FCFS。

它的致命弱點是護航效應（convoy effect）：一個長工作會拖住後面所有短工作。

FCFS 平均等待時間 = \((0 + 20 + 22)/3 = 14\) 。若改跑順序為 B、C、A，則平均等待 = \((0+2+4)/3 = 2\) 。同樣的工作集，平均等待差了 7 倍！

FCFS 的優點是不飢餓、開銷極小（零 context switch 的浪費）。它至今仍存活在許多 I/O 排班與批次佇列中，特別適合服務時間相近的場景。

SJF：理論最優，但無法實作#

SJF（Shortest Job First，最短工作優先）的理論結果是排班論文的基石：在非搶佔式排班中，SJF 最小化平均等待時間。證明用交換論證（exchange argument）：考慮任何最優排班中相鄰兩個工作 \(a\) 、 \(b\) ， \(\tau_a > \tau_b\) 且 \(a\) 先跑，交換順序後所有其他工作的等待不變，而 \(b\) 的等待減少 \((\tau_a - \tau_b) > 0\) 、 \(a\) 的等待增加相同量但按長度加權後總和下降——因此任何非相鄰排序都可以被改進，直到短者在前。

SJF 有兩個實作障礙：

1. 不可知性： \(\tau_i\) 無法預知。實務上用指數移動平均估計： \(\tau_{n+1}^{est} = \alpha \cdot \tau_n + (1-\alpha) \cdot \tau_n^{est}\) ，以過去行為預測未來（CPU burst 有很強的時間局部性）。
2. 飢餓：源源不絕的短工作會讓長工作永遠排不到。

搶佔版 SJF 稱為 SRTF（Shortest Remaining Time First）：新到的工作若比目前行程的剩餘時間還短，立即搶佔。它進一步是「所有排班中平均等待時間最短者」，但搶佔開銷與估計誤差使理論光環打折。

Round Robin：分時系統的答案#

RR（Round Robin，時間輪轉）是 FCFS 加上搶佔：每個行程最多執行一個**時間片（time slice / quantum） \(q\) **，時間一到由計時器中斷強制切換，行程回佇列尾。這正是 CTSS（1961）與 UNIX（1969）的基礎。

\(q\) 的取捨是排班理論最重要的實務參數：

• \(q \to \infty\) ：RR 退化成 FCFS，互動性喪失。
• \(q \to 0\) ：像「處理器共享（processor sharing）」，公平但 context switch 開銷 \(\Theta(n)\) 支配一切，吞吐量崩潰。

設 context switch 成本為 \(s\) ，RR 在 \(n\) 個等長行程下的效率為 \(\frac{q}{q+s}\) 。經驗法則是讓 \(q\) 滿足：80% 的 CPU burst 能在一個時間片內完成（典型 \(q\) 約 10–100 ms）。

沿用前例（ \(q=4\) ，s=0）：順序為 A(4) B(2) C(2) A(4) A(4) A(4)，完成時間 A=22、B=6、C=8，平均等待 = \(\frac{18+4+6}{3} = 9.33\) ——比最優 SJF（ \((0+20+22)/3=14\) 順序下的 0/2/4? 讀者可自行驗證 SJF 為 \(4.67\) ）差，但回應時間極好：B 在 4ms 內就首次獲得 CPU。這正是分時系統選 RR 的原因：它犧牲平均週轉，買進了每一個人的即時回應。

進階：優先權、多級回饋佇列與公平共享#

純 RR 無法表達「這個工作更重要」。1962 年 Corbató 在 CTSS 中提出多級回饋佇列（MLFQ），後經 Corbato 等人於 1962 年 CACM 論文與 1968 年 MULTICS 詳細化，成為影響最深遠的排班架構：

• 多個 RR 佇列，優先權由高到低；新行程進最高級。
• 用完整時間片 → 降級（可能是 CPU 密集者）；提前讓出 CPU → 留在原地或升級（可能是互動者）。
• 效果：不需要預先知道服務時間，就從行為中「學」出它——把 SJF 的精神用啟發式實作出來。

MLFQ 的問題是飢餓與被遊戲（惡意行程故意在時間片快結束前睡一下以維持高優先權），解法是定期把所有行程提升回最高級（boost）。今日 Windows、macOS 與 Linux 的 CFS 之前的排班器，都屬於 MLFQ 家族。

公平共享方向上，1990 年代 Waldspurger 提出彩票排班（lottery scheduling，1994），Linux 自 2.6.23（2007，Ingo Molnár）改用 CFS（Completely Fair Scheduler）：以紅黑樹依「虛擬執行時間（vruntime）」排序，每次挑 vruntime 最小者，數學上讓每個行程的 CPU 份額收斂到其權重比例——公平性的正式化。近年（2023+）Linux 又引入 EEVDF（最早虛擬截止時間優先），在公平之外補回延遲保證。

各演算法對照#

小結與展望#

排班演算法的演進史，本質上是「無法預知的未來」一詞的各種對策史：FCFS 假裝未來不存在；SJF 假設未來可知；RR 放棄最佳化等待、直接保證回應；MLFQ 用過去預測未來；CFS 把問題改寫成「公平」這個可即時維護的不變式。同樣的思想在分散式系統（工作排程如 Kubernetes scheduler）、資料庫查詢排班、乃至 GPU 排班中不斷重演。下一節將深入排班的最低層成本：context switch 究竟在切換什麼。