輪詢排程生來要修的問題
在上一篇導覽裡，你認識了先到先服務，也看到了它那場安靜的災難——護衛效應：一個長工作先到，搶下 CPU，後面每個短工作就一直等、一直等，像一輛慢吞吞的卡車堵住整條車道。你也認識了最短工作優先，它對平均等待時間而言可以證明是最佳的，卻在作弊——它需要知道未來，需要知道每個工作下一段 CPU 執行區段的確切長度，而真實的作業系統根本沒有這種資訊。於是我們卡在兩者之間：一個排程器公平卻可能凍住所有人，另一個聰明卻得有未卜先知的本事。輪詢排程走的是一條完全不同的路。
整個點子用一句話講完：給每個就緒的工作一小段等長的 CPU 時間，一旦這段時間用完，就停下它、換到隊伍裡的下一個工作。想像一位老師手上只有一支麥克風，面前圍著一圈躍躍欲試的孩子。她不會讓第一個孩子一直講到完全講完（那是先到先服務），而是把麥克風交給每個孩子三十秒，然後溫和地收回、傳給下一個——就這樣繞著圈子一圈又一圈。沒有人能霸占麥克風，而一個只有一個小問題的孩子幾乎馬上就被聽見，不必為了一位長篇大論的同學苦等一小時。
那句「溫和地收回」是關鍵的一步。輪詢排程是搶占式（preemptive）排程器的教科書範例——見搶占式與非搶占式。它不會等一個工作做完、也不等它自願交還 CPU；它在那段時間一到期，就強制中斷正在執行的工作。這正是讓分時系統得以成立的同一套機制，也是那個讓數十位使用者（或你那數十個瀏覽器分頁）都覺得自己獨占整台機器的小把戲。它發出去的那一小段時間有個名字，我們會在本篇導覽往後一直與它相伴：時間量子。
認識時間量子
時間量子（也叫時間片）是每個工作在排程器介入之前，被允許執行的那段固定 CPU 時間長度。真實系統裡的典型值落在小小的毫秒範圍——常常是大約 10 毫秒到 100 毫秒之間——不過確切的數字因系統而天差地別，我們也會看到為什麼這個選擇如此要緊。輪詢排程的整套行為，都活在這一個數字裡。把旋鈕轉得太大，輪詢排程就悄悄又變回先到先服務。把它轉得太小，機器就把所有力氣都花在切換上，幾乎沒有力氣做真正的工作。把這個數字調對，就是這門藝術的全部。
作業系統實際上是怎麼把麥克風收回來的？它不會（也不能）相信一個正在執行的工作會禮貌地自己停下。核心反而會設定一個硬體計時器，在剛好一個量子之後觸發一個中斷——也就是門鈴。當那聲門鈴響起，CPU 就跳出正在執行的工作、進入核心，核心接著執行排程器。這就是為什麼搶占需要硬體幫忙：少了計時器中斷，一個從不發出系統呼叫的工作可能永遠執行下去，任何軟體都攔不住它。計時器就是大樓管理員的鬧鐘，按固定的時刻響起，不管哪個住戶正在做什麼。
親手追一遍：三個行程，量子為 4
用數字才會讓這件事變得真實。假設三個行程都在時間 0 抵達，需要這些 CPU 執行區段：P1 需要 10、P2 需要 4、P3 需要 5。我們把量子設為 4 個時間單位。排程器維護一條就緒佇列——一條等著用 CPU 的工作排成的簡單先進先出隊伍。它取出最前面的工作，讓它最多執行一個量子，如果計時器響起時這個工作還有事沒做完，它就回到隊伍的最後面。我們就一格一格走過去，就像你真的在紙上一步步追蹤那樣。
- 時間 0–4：P1 跑滿一個量子。它原本需要 10，所以還剩 6。計時器響起，P1 回到隊伍最後面。現在的順序：P2、P3、P1。
- 時間 4–8：P2 跑。它剛好需要 4，所以在量子結束的那一刻正好做完，從此離開。現在的順序：P3、P1。
- 時間 8–12：P3 跑滿一個量子。它需要 5，所以還剩 1。P3 回到最後面。現在的順序：P1、P3。
- 時間 12–16：P1 跑滿一個量子。它原本還剩 6，所以還剩 2。P1 回到最後面。現在的順序：P3、P1。
- 時間 16–17：P3 跑完它最後的 1 個單位，做完了。現在的順序：P1。
- 時間 17–19：P1 跑完它最後的 2 個單位，做完了。佇列空了；所有人都完成了。
quantum = 4 bursts: P1=10 P2=4 P3=5 | P1 | P2 | P3 | P1 |P3| P1 | 0 4 8 12 16 17 19 finishes: P2 @ 8 P3 @ 17 P1 @ 19 turnaround (arrived @0): P1=19 P2=8 P3=17 avg = 14.7 response (first run): P1=0 P2=4 P3=8
好好看看這替我們換來了什麼、又付出了什麼。贏的是回應時間：每個行程都早早嚐到了 CPU，所以一個互動式工作幾乎立刻就有了活力——這正是你在打字、期待游標移動時想要的。代價顯現在周轉時間上：長工作 P1 直到時間 19 才完成，比在單純先到先服務下還晚，在那種情況它本可在 0–10 跑完、在時間 10 結束。輪詢排程刻意用一點點周轉時間，去換來大量的反應靈敏。那筆交易，正是你用過的每一個互動式系統的靈魂。
那個旋鈕：為什麼量子大小就是一切
現在來到問題的核心。每當計時器響起、我們從一個工作切換到另一個工作，就得付一次上下文切換的代價：核心必須存下換出工作的暫存器與 CPU 狀態、載入換入工作的狀態，而換進來的工作接下來還會碰上冰冷的快取。那次切換要花真實的時間——就叫它額外開銷吧——在那段時間裡，CPU 做的有用工作是零。量子決定了我們多常付這筆過路費。如果量子是 q、一次切換要花 s，那麼真正被浪費掉的時間比例大約是 s / (q + s)。
把旋鈕推到一個極端。把量子設得非常大——大過每個工作的執行區段——那就沒有任何工作會被搶占，因為每一個都在它那段時間用完之前就做完了。輪詢排程已經悄悄變回先到先服務，連同護衛效應一起回來。現在推到另一個極端。把量子設得極小，比方說 1 毫秒，而一次切換也要花大約 1 毫秒；現在幾乎一半的 CPU 時間都燒在切換上，機器慢得像在爬。更糟的是，這是個真有其事、值得記住名字的病症：當量子變得太小，系統會在上下文切換上疲於奔命，做的記帳比做的工作還多。
有一個誠實的微妙之處，可以送走一個常見的誤解：周轉時間並不會隨著你把量子縮小而平順地改善。你或許以為更小的片段總是代表更好的平均值，但事情並非如此——一旦切換的額外開銷堆積起來，量子變小反而可能讓周轉時間變糟，而真實的關係是顛簸起伏的，而不是一條乾淨向下的滑坡。教訓是：量子是一個貨真價實、沒有白吃午餐的工程取捨，不是一個你只管把它轉向零的旋鈕。
輪詢排程仍然做不到的事
輪詢排程公平、簡單，而且不會餓死任何人——如果有 n 個工作，就緒佇列裡的每個工作都保證在大約 (n-1) 個量子之內輪到一回，所以沒有人會被永遠晾在那裡等。那份保證是真有價值的，也正是輪詢排程能坐鎮如此多真實排程器核心的原因。但公平同時恰恰是它的盲點。輪詢排程把每個工作都當成同樣值得對待，這對平等的工作來說很美好，對不平等的工作來說卻很糟糕。你的音樂播放器和一個背景備份都拿到同樣的片段，即使你其實很樂意讓備份等一等，好讓你的音訊永遠不卡頓。
還有第二種、更細緻的不公平。單純的輪詢排程對做大量輸入／輸出的工作並不友善。回想第 1 篇導覽：行程會在 CPU 執行區段與 I/O 執行區段之間交替。一個 I/O 密集的工作常常只跑掉它量子的一小條，接著就阻塞下來等磁碟或網路，把片段剩下的部分讓了出去。等它回來時，必須重新排到佇列尾端再等一次，而一個 CPU 密集的工作卻每一回都心滿意足地吃掉它整個量子。最少用到 CPU 的那個工作，最後反而等得最久——這正好和良好的產出量所想要的相反。
所以輪詢排程給了我們正確的直覺——搶占、輪流、保持反應靈敏——但一條扁平的佇列搭配一個固定的量子，對於一個充滿各種需求各異的工作的世界來說，還是太鈍了。修正之道不是拋棄輪詢排程，而是把它分層：好幾條佇列、不同的量子，外加一條規則，讓系統單憑觀察工作的行為，就能學會哪些是互動式的、哪些是吃 CPU 的大胃王。那個結構就是多層回饋佇列，而它與優先權結合起來，正是下一篇導覽接手的地方。