問題：可執行的工作比 CPU 多
到現在你已經知道，一個行程在核心裡有一個控制區塊，並在各狀態之間移動——執行中、可執行（已就緒但在等一顆 CPU）、以及被阻塞（在等 I/O 或一把鎖）。在任何一個瞬間，你的筆電也許只有四個 CPU 核心，卻有好幾百個行程，而其中相當一部分是可執行的——它們現在就有事要做，只是在等一個輪到自己的機會。排程器就是那個核心子系統，它一遍又一遍、一秒鐘上千次地決定：每顆 CPU 接下來該跑哪一個可執行的工作、跑多久。沒有人會直接呼叫它；它是在精心挑選的時機從核心內部被觸發的。
排程器兜售的幻覺是：那些行程全都同時在跑。它們並沒有。在單一核心上，任何一瞬間都恰好只有一個工作在執行；排程器靠著切換得夠快、快到你察覺不出空隙，製造出同時進行的假象——這就是沒有平行的並行。每一次從一個工作交棒給另一個工作，都是一次脈絡切換：核心把離開的工作的暫存器（rip、rsp、那組通用暫存器）存進它的控制區塊，載入進來的工作先前存好的暫存器，切換位址空間，然後繼續執行。這不是免費的——一次切換要花上數百奈秒，外加碰新記憶體對快取和 TLB 造成的損害。
所以排程器有兩件彼此拉扯的工作。它必須給每個可執行的工作一份公平的 CPU 時間，好讓沒有東西被餓死、好讓你的編輯器在一個編譯跑著的時候仍然靈敏。它也必須切換得夠不頻繁，好讓切換的開銷不會把工作本身吃掉。排得太少，一個貪心的工作就霸佔住核心；排得太多，你就把所有時間花在存回與還原暫存器、而不是做真正的事。接下來的一切，都是核心如何在這個張力中航行。
執行佇列：每顆 CPU 一個的「誰可以跑」名單
排程器到哪裡去找下一個工作？到一個執行佇列裡：一個只裝著「此刻可執行」的工作的資料結構。關鍵在於，被阻塞的工作不在裡面——一個正在等慢速磁碟的 read() 的行程，已經被完全移出執行佇列，停泊在那個磁碟對應的等待佇列上；它不花排程器一分一毫，因為排程器根本連看都不看它一眼。當磁碟資料抵達，中斷處理常式會把它移回某個執行佇列，在那裡它再次競爭 CPU。執行佇列是競爭者的名單，不是所有行程的名單。
在多核心機器上，並不是只有一個全域執行佇列，而是每顆 CPU 各有一個執行佇列。這是個刻意的設計選擇，背後的直覺與你下一篇會再遇到的每顆 CPU 私有資料一樣：一個單一共享的執行佇列會需要一把鎖，每顆核心在每次排程決策時都要搶它，而那把鎖會變成一個尖叫的瓶頸。每顆 CPU 各自的執行佇列，意味著每顆核心都從自己的名單排程，在常見路徑上沒有跨核心的鎖。代價是這些佇列可能失衡——一顆核心的名單越來越長，另一顆卻閒著——所以排程器會週期性地執行負載平衡（load balancing），把工作從忙碌的佇列遷移到空閒的佇列。遷移也不是免費的，因為一個搬到新核心的工作，會把它溫熱的快取留在原地。
把公平做對：完全公平排程器
在它歷史的絕大部分時間裡，Linux 的預設排程器是完全公平排程器（CFS），於 2007 年併入，而它的核心想法優雅到足以放在腦子裡。想像一台完美、理想化的機器，上面 N 個可執行的工作各以恰好 1/N 的 CPU 速度同時執行——天生就完美公平。真實硬體做不到這件事；它一次只能跑一個工作。於是 CFS 為每個工作追蹤一個叫虛擬執行時間（virtual runtime，vruntime）的數字：大致就是那個工作已經耗用的 CPU 時間量。規則接著簡單到令人屏息——永遠跑 vruntime 最小的那個工作，因為那正是落後公平理想最遠的工作。
想像三個工作 A、B、C。A 跑了一個時間片，它的 vruntime 往上爬，現在 A 不再是最小的了——所以排程器挑 B，然後 C，要等到大家都追上來，才會回到 A。效果是各個 vruntime 傾向於彼此靠近，而這恰恰就是公平：沒有人在「已耗用的 CPU」上遙遙領先。優先權的納入方式不是插隊，而是縮放 vruntime 增長的快慢。一個高優先權工作的 vruntime 以慢動作前進，所以它更快就沉回排序的底部、跑得更頻繁；一個低優先權工作的 vruntime 飛快往前衝，所以它在兩次輪到之間要等更久。優先權改變的是權重，不是規則。
idealized fair share: each of N tasks gets 1/N of the CPU
vruntime = real CPU time consumed, scaled by priority weight
(high priority -> vruntime grows SLOWER)
scheduler rule: always run the task with the SMALLEST vruntime
stored in a red-black tree keyed by vruntime:
pick-next = leftmost node (O(log n) to remove + reinsert)
[ A:50 ] A ran, vruntime 50 -> 70, reinsert:
/ \
[ -- ] [ B:60 ] ---> pick leftmost = B (smallest vruntime now)
\
[ C:90 ]「永遠挑最小的」在有數百個工作時怎麼還能便宜？CFS 把執行佇列維護成一棵以 vruntime 為鍵的紅黑樹——一種自我平衡的二元樹。下一個要跑的工作永遠是最左邊的節點，找到它所花的時間與樹的深度成正比；一個工作跑完後，你更新它的 vruntime 並重新插入，也是對數時間。每次決策都不需要掃過所有工作。這就是為什麼「執行佇列真的是一條佇列」是初學者的簡化：真正的結構是一棵樹，正是為了讓「誰的 vruntime 最小」即使在池子很大時也能被快速回答。
搶佔：用強制手段把 CPU 收回來
我們已經決定了誰跑。現在的問題是：一個正在執行的工作究竟怎麼停下來？有兩種哲學，你上一級已經見過。在協作式排程下，一個工作會一直佔著 CPU，直到它自願讓出——透過阻塞在 I/O 上、睡眠、或明確放棄。這很簡單，也是早期系統的做法，但它致命地脆弱：單單一個卡在無窮迴圈、永不讓出的工作，就會凍結整台機器，因為沒有東西能把 CPU 從它手裡奪走。一支有臭蟲的程式，整個系統就掛了。
每一個現代通用作業系統改用搶佔式（preemptive）排程，而這個機制直接建立在本級前幾篇的中斷機制之上。核心會設定一個硬體計時器（timer）週期性地發出中斷——歷史上大約每 10 毫秒一次，稱為一個時脈滴答（tick）。當計時器發火，它觸發一個中斷，強制把控制權從正在執行的工作裡轉移進核心的處理常式，正是你在系統呼叫看過的那套陷阱與模式切換，只不過這次工作並沒有要求它。在處理常式裡，核心更新正在執行的工作的 vruntime，並檢查：現在是否有一個 vruntime 更小的可執行工作？如果有，它就設一個意思是「需要重新排程」的旗標，而在返回的路上，核心會執行一次脈絡切換到那個更好的工作，而不是恢復被打斷的那一個。
這就是為什麼一個失控的無窮迴圈在 Linux 上不會凍結你的機器：計時器中斷不管那個迴圈中的工作想不想都會發火，核心在每個 tick 都重新取得控制權，它可以乾脆排別的東西去跑。那個迴圈霸佔的是它自己那份公平的份額，不會更多。注意這個優雅的重用——那個遞送一次按鍵、或一個磁碟完成訊號的同一套中斷機制，正是讓搶佔式多工得以成立的根本。沒有一個非同步的中斷，核心就永遠無法從拒絕合作的程式碼手裡把 CPU 搶回來。
搶佔核心本身，以及這一切通向何方
還有一個更微妙的層次。搶佔一個使用者工作這件事已經定案。但那些跑在核心內部的程式碼呢——比方說，一個發出了慢速系統呼叫、現在正代表它執行核心程式碼的行程？早期的 Linux 在核心模式下是不可搶佔的：一旦一個工作進入核心，它就在那裡不受排程器打斷地執行，直到它返回或阻塞為止，這讓核心的資料結構保持簡單，卻可能讓一個冗長的系統呼叫拖延一個高優先權工作的甦醒。現代 Linux 是一個可搶佔核心：排程器可以把一個工作切走，即使它正在核心程式碼裡執行系統呼叫到一半——除了那些明確標記為不可搶佔的區域，例如正持有一把自旋鎖或正執行一個中斷處理常式的時候。
退一步看它的形狀。排程器不是單一演算法，而是對一個問題——下一個誰跑？——的分層回答，由你現在認得出來的零件組成：每顆 CPU 各自的、裝著可執行工作的執行佇列，一個從一棵平衡樹中挑出最小 vruntime 的公平政策（CFS），以及一個建立在計時器中斷之上、讓核心能從任何人——不管它合作與否——手裡收回 CPU 的搶佔機制。每一次排程決策都以一次脈絡切換作結，那是把一個工作的暫存器與位址空間換成另一個工作的、具體的機器層級動作。
再注意我們剛剛扯出的那條未了的線：核心在持有一把自旋鎖時不可被搶佔，而執行佇列本身就是需要保護的共享資料。這絕非巧合——排程器是核心裡爭用最激烈的共享狀態之一，被中斷處理常式、被每一顆 CPU 並行地觸碰。核心如何保護這樣的資料、又不讓自己陷入死結——自旋鎖、RCU，以及我們這裡倚靠的每顆 CPU 私有資料技巧——正是本級最後一篇的主題。