並非所有工作都生而平等
到目前為止，本階梯一直假設一種民主。先到先服務按抵達順序服務工作；最短工作優先偏愛短的；輪流排程把時間切成公平相等的回合。但在真實生活裡，有些工作就是比別的工作重要。讓你的音樂不卡頓的音訊執行緒，理當比背景備份先拿到 CPU。一個負責釋放記憶體的核心雜務，應該排在螢幕保護程式前面。我們需要一種方式來表達這件事——那個方式就是 優先權排程。
這個想法簡單得令人愉快。給每個行程一個數字——它的優先權——每當短期排程器必須抉擇時，就把 CPU 交給就緒行程中數字最急迫的那一個。（一個著名又惱人的陷阱：在許多系統上，數字越小代表優先權越高，所以優先權 0 勝過優先權 9。務必確認你的教科書或核心採用哪種慣例。）和其他演算法一樣，優先權排程也有兩種風味。非搶佔版讓執行中的行程一直握著 CPU，直到它阻塞或結束；搶佔版則在更高優先權的行程一就緒的當下，半途把 CPU 搶走，交給這位新來者。
每個優先權方案裡都藏著的陷阱：飢餓
優先權排程帶著一個安靜而危險的缺陷。想像一間忙碌的醫院，最危急的病人永遠先就診。對急診來說這完全正確——但如果危急的病例不斷湧入，一位只有輕微不適的病人可能永遠坐在候診室裡，理論上是他那個優先權層級的下一位，卻從來沒有真正被叫號。在電腦裡，這就是 飢餓（也叫無限期阻塞）：一個低優先權行程明明完全準備好可以執行，但源源不絕的高優先權工作意味著它永遠擠不到最前面。它沒有卡死、也沒有壞掉——它只是被無止盡地略過。
這有多真實？有一則美妙的傳說：當麻省理工的 IBM 7094 終於在 1973 年關機時，據說操作員找到一個 1967 年提交、卻從未執行過的低優先權工作——飢餓了六年。不論日期是否精確，這個教訓是鐵一般的：任何永遠偏好高優先權的方案，在足夠的負載下，都會讓某個倒楣的低優先權行程無界限地等待下去。飢餓是「在乎優先權」的代價，你無法靠小心安排數字就把它許願消除。
老化：溫柔的解藥
解法和問題一樣有人情味。如果危險在於永遠等待，那就讓「等待」本身為你掙得些什麼。老化這條規則是：一個行程在就緒佇列裡等得越久，它的優先權就慢慢往上升。想像一個熟食店櫃台，除了你手上的號碼牌之外，店員還會把站太久的人往上調——最終，連最不起眼的客人也會一路爬到最前面被服務。一個從優先權 9 起步的行程，可能每被晾著幾秒就升一級，直到有一天它的排名超越了那群忙碌的高優先權客人，終於得以執行。
老化之所以有效，是因為它保證了等待時間有上界：如果你的優先權一直往上爬，你最終一定會抵達頂端，所以沒有行程會永遠等待，飢餓就此打破。這值得停下來想一想，因為這正是你會在並行領域以有界等待之名再次遇到的同一種形狀的保證——也就是「每個人都會在別人有限次的回合之內輪到」的承諾。老化，就是排程器信守那個承諾的方式。
當優先權反過來咬自己：優先權反轉
這裡有一個真實系統會撞上的誠實轉折。假設一個低優先權行程正握著一把高優先權行程需要的鎖。高優先權行程被迫等待——這合情合理，鎖必須被尊重。但現在一連串中優先權行程不斷搶佔那個持鎖的低優先權行程，使它永遠跑不完、永遠不釋放那把鎖。結果就顛倒了：高優先權行程實際上被卡在中優先權工作的後面，全因為一個它幫不上忙的卑微持鎖者。這就是 優先權反轉，而它絕非假想——1997 年它就赫赫有名地凍住了 NASA 的火星拓荒者號探測車，使它不斷自我重設，直到工程師從數百萬英里之外把它診斷出來。
標準解法是優先權繼承：當低優先權行程握著一把高優先權行程在等的鎖時，它暫時借用那個高優先權、迅速做完工作、釋放鎖，再降回原本的層級。現在這個誠實的重點只有一個：優先權很強大，但它與加鎖的互動方式，可能悄悄擊敗你一手安排的那套排名。這個故事背後的鎖，你會在並行那一階梯真正搞懂——在這裡，只要先記下：優先權不是堅不可摧的堡壘，而優先權與共享資源的草率混用，可能把整個次序徹底反轉。
多層回饋佇列：一個會學習的排程器
現在我們可以組裝經典排程的傑作了。先從一個比較簡單的想法開始，多層佇列：不是只有一條就緒隊伍，而是維護好幾條，每條都有自己的優先權與自己的演算法。想像一座機場為頭等艙、商務艙、經濟艙各設一條隊伍——互動式工作在最上面那條、批次工作在最下面那條，而排程器永遠先服務較高的隊伍才輪到較低的。麻煩在於，一個行程一出生就被分到某一條隊伍、從此卡死在那裡。但一個工作的行為不是固定的：一個一秒前還在猛算數字的程式，現在可能開始等鍵盤了。何不讓它換隊伍呢？
就這一項添加——讓行程根據它實際的行為在佇列之間移動——給了我們 多層回饋佇列（MLFQ），堪稱史上最具影響力的排程器設計。「回饋」就是那道魔法：排程器觀察每個行程，再把它重新歸位。規則優美而直覺。每個行程都從最頂端、最高優先權的佇列開始，那一層用輪流排程配上一個小小的時間量子。如果一個行程用完整段量子卻沒有阻塞，它看起來就是 CPU 密集又貪心，於是被降級到一個量子較長的較低佇列。反之，如果它早早交出 CPU 去等待輸入輸出，它看起來就是互動式又乖巧，於是留在高層或被升級。
退一步，欣賞它在完全沒被告知行程類型的情況下達成了什麼。短而互動的工作自然浮到頂端、感覺靈敏（極佳的回應時間），因為它們總在用盡量子之前就阻塞。長而 CPU 密集的工作自然沉到底部，在那裡仍然執行——只是讓開了互動人群的路——而底部較長的量子意味著較少浪費的上下文切換。這個排程器只用過去的行為就逼近了最短工作優先的好處，不需要任何水晶球。而為了不讓沉底的工作飢餓，MLFQ 會定期把所有人拉回頂端——這正是老化，只是戴了另一頂帽子。
Q0 (quantum 8ms, round robin) <-- new jobs start here; interactive jobs stay
| used full quantum, didn't block? -> demote
v
Q1 (quantum 16ms, round robin)
| used full quantum again? -> demote
v
Q2 (quantum 32ms, FCFS) <-- long CPU-bound jobs settle here
Rule: always run a job from the highest non-empty queue.
Periodically: move EVERY job back up to Q0 (this is aging -> no starvation)從教科書到真實的機器
對這一切聰明的代價誠實以對：MLFQ 有一堆旋鈕，而調校它們是真的很難。要幾層佇列？每段量子該多長？該多久把所有人拉回頂端一次以防飢餓？提升做得太少，長工作就飢餓；做得太多，你又抹掉剛剛精心完成的分類，而會鑽漏洞的程式還能作弊——在量子快結束前發出一個微小無意義的輸入輸出，假裝互動以保住高層。沒有放諸四海皆準的完美設定——正確的數值取決於你的工作負載，這正是為什麼它是一個工程問題，而不是一道已解的方程式。
值得知道的是，地表部署最廣的排程器走了另一條路。多年來 Linux 跑的是 完全公平排程器（CFS），它徹底扔掉了固定的優先權層級與離散的佇列。取而代之，它追蹤每個可執行行程已經得到多少 CPU 時間，並永遠挑選拿得最少的那一個，彷彿每個行程都被欠了一份「理想化的完美共享 CPU」的等額切片。優先權仍然存在——一個「nice」值會傾斜一個行程累積其虛擬執行時間的快慢——但核心想法是「靠記帳達成公平」，而不是「靠佇列分排名」。CFS 的完整故事、即時排程，以及這一切如何延伸到多個核心，是本階梯最後一篇導覽的主題。