Learning Objectives
- 說明 MLFQ 怎麼在不知道工作長度的情況下，同時照顧互動型與 CPU 型工作
- 親手鑽出 MLFQ 舊規則的漏洞，並說明加分機制與累積配額各解決什麼問題
- 用虛擬執行時間解釋 Linux 怎麼依權重分配 CPU，以及 nice 的作用
- 比較共用佇列與每核一條佇列的取捨，說明負載平衡與親和性的代價
排程器不知道工作要跑多久
上一課的 SJF 很漂亮，但它要先知道每個工作還要跑多久，而作業系統不知道。你打開的編輯器，可能接下來一小時都只處理按鍵；也可能你按下存檔之後，它開始跑五分鐘的格式檢查。
作業系統能看到的只有過去：這個工作上次用了多少 CPU？是不是常常主動去等 I/O？多層回饋佇列（Multi-Level Feedback Queue，MLFQ）就是用過去的行為猜未來：
- 常常主動放棄 CPU 的工作，大概是互動型的，讓它優先，回應才會快。
- 一直用滿 CPU 的工作，大概是長時間運算，讓它排後面，但一次給長一點的時間片。
這個想法可以追溯到 Corbató 等人 1962 年描述的 CTSS（相容分時系統），是分時系統很早就面對的問題。
規則
系統有好幾層佇列，每層有自己的時間片，越高層時間片越短：
| 編號 | 規則 |
|---|---|
| 1 | 優先權高的層先跑；高層有人時，低層的工作不會跑 |
| 2 | 同一層之內用 RR 輪流 |
| 3 | 新工作從最高層開始 |
| 4 | 工作在某一層累積用滿配額，就降一層 |
| 5 | 每隔一段時間，所有工作都回到最高層（加分，priority boost） |
規則 3 讓新工作先被當成短工作：真的很短就很快做完，不短就一層一層往下沉，所以等於用實際表現逼近 SJF，不需要事先知道長度。規則 4 和 5 換一種寫法就會出問題，下面親手試。
Linux 的做法：虛擬執行時間
Linux 的一般行程不是用 MLFQ，而是追求比例公平：每個行程應該分到多少 CPU，就讓它分到多少。
從 Linux 2.6.23 起的 CFS（Completely Fair Scheduler）替每個行程記一個虛擬執行時間（vruntime）。行程跑了多久，就加到 vruntime 上；排程器永遠挑 vruntime 最小的來跑，也就是到目前為止被虧待最多的那個。官方文件的描述是 CFS 把可執行的工作依 vruntime 排在一棵紅黑樹上，取最左邊的節點。
權重讓「公平」可以不是平分。行程跑一段實際時間，虛擬時間增加的量大約是：
vruntime 增加量 = 實際執行時間 × 1024 / 權重
權重越大，虛擬時間長得越慢，排程器就越常選它。權重來自 nice 值，範圍是 −20（最優先）到 +19（最不優先），數字越大越「客氣」。sched(7) 說 nice 差 1 大約差 1.25 倍；核心原始碼裡的對照表 nice 0 是 1024，nice 5 是 335。
nice -n 5 ./long_job # 用 nice 5 啟動
renice -n 10 -p 1234 # 調整執行中的行程
把 nice 調大誰都可以做；調小（要更多 CPU）傳統上需要特權，現在也可以用資源限制 RLIMIT_NICE 開放。
挑 vruntime 最小的工作
兩個一直要用 CPU 的工作，權重取自核心的對照表。注意看 nice 5 跑一次，虛擬時間跳多大，以及這讓 nice 0 連續跑了幾次。為了避免小數，程式裡把數字都放大了 100 倍。
6.6 之後：EEVDF
Linux 6.6（2023 年 10 月發布）把 CFS 換成了 EEVDF（Earliest Eligible Virtual Deadline First，最早合格虛擬截止時間優先）。演算法本身來自 1995 年的論文。它和 CFS 一樣用虛擬時間追求公平，只是多處理了「誰該先拿到反應」：
- 每個工作有一個 lag：應得的 CPU 減去實際拿到的。lag 大於等於 0 的工作被欠了 CPU，才算合格（eligible）。
- 排程器替合格的工作算虛擬截止時間，選最早的來跑。時間片要求越短，截止時間越早，所以對延遲敏感的工作可以比較快拿到 CPU，但一次跑得比較短。
它也要防短暫睡眠的漏洞：拿太多 CPU 的工作（lag 為負）如果睡一下就能重置 lag，等於作弊，所以官方文件說明它讓睡眠中的工作的 lag 隨虛擬時間慢慢衰減。和 MLFQ 補的洞是同一類：只要排程器對「放棄 CPU」有優待，就會有人想利用它。
手冊頁
sched(7)目前還寫著預設排程器是 CFS。排程細節變動快，要查現況請看 核心文件。
寫程式時不需要記這些細節，但兩個判斷會一直有用：單純用 CPU 的程式會被公平分配，要影響分配就用 nice；而程式的等待習慣會影響它得到的待遇。
多顆核心怎麼分工
核心變多之後多了一個問題：不只決定「下一個是誰」，還要決定「在哪一顆跑」。
共用一條佇列最直接：所有核心從同一條佇列拿工作，不可能有核心閒著而別人排隊。缺點有兩個：
- 佇列要用鎖保護，核心越多，等鎖越久。
- 工作每次可能換到不同核心。每顆核心有自己的快取，換核心之後，原本快取裡的資料都要重新載入，這段時間程式跑得比較慢。
每核一條佇列沒有這兩個問題：不用搶鎖，工作也一直留在原來的核心。但它會負載不平衡：這顆核心的佇列空了，那顆還排著好幾個。
解法是負載平衡（load balancing）：定期檢查，把工作從忙的核心移到閒的核心。Linux 的每顆核心有自己的執行佇列，並由週期性的負載平衡移動工作。移動一次就要付一次快取的代價，所以要看什麼時候值得。
親和性（CPU affinity）讓你指定行程只能在哪些核心上跑。sched_setaffinity(2) 的說明提到，把行程固定在一顆核心上，可以避免快取失效帶來的效能損失。代價是排程器失去了移動它的自由。
taskset -c 2 ./job # 只能在核心 2 上跑
確認一下
只有舊規則（用滿時間片才降級）時，惡意程式怎麼一直留在最高層？
MLFQ 少了加分（規則 5），一個原本 CPU 型、後來變成互動型的工作會怎樣？
只有 nice 0 的 P 和 nice 5 的 Q 在同一顆核心上競爭 CPU，兩者都一直要用 CPU。大約會怎麼分？
下面的程式模擬 CFS 的記帳。P 的權重是 Q 的兩倍，一開始虛擬時間都是 0，平手時 P 先。跑 6 個單位之後，P 和 Q 各用了幾個單位？
一台 64 核心的伺服器，所有執行緒都很短、而且資料彼此無關。為什麼通常不用單一共用佇列？
重點整理
- MLFQ 用過去的行為猜未來：新工作從最高層開始，用得多就往下沉，定期加分讓所有工作回到最高層。
- 舊規則只看單次有沒有用滿時間片，會被故意提早放棄 CPU 的程式鑽漏洞；累積配額才補起來。加分解決飢餓，也讓行為改變的工作有機會被重新判斷。
- Linux 用虛擬執行時間追求比例公平：權重越大，vruntime 長得越慢。nice 差 1 約差 1.25 倍。從 6.6 起改用 EEVDF，加入 lag 與虛擬截止時間。
- 多核心的取捨：共用佇列負載平衡但有鎖競爭與快取損失；每核一條反過來，要靠負載平衡補救。親和性能留住快取，用錯會浪費核心。
延伸閱讀：免費公開的 OSTEP 第 8 章（MLFQ）、第 10 章（多處理器排程）。
下一課看另一種讓程式同時做多件事的方法：同一個行程裡的多個執行緒。