從最顯而易見的規則開始
從上一篇你已經有了整個框架：給定一個就緒佇列，排程器必須挑出接下來換誰跑，而我們用五把尺評斷它的選擇。所以請坐進排程器的位子，問一個最偷懶的問題：能行得通的最簡單規則是什麼？答案就是任何有公平心的小孩都會喊出來的那句——誰先到誰先來。這就是先到先服務（FCFS），它就和麵包店的排隊一模一樣：抽一張號碼牌，然後嚴格依號碼順序服務你。
FCFS 是非搶占式的（回想搶占式與非搶占式之分）：一個行程一旦開始它的 CPU 分發，就會一路跑到那段分發的最末端——直到它為了 I/O 而阻塞、或是結束——之後下一位持票者才輪得到。它的實作便宜到幾乎令人不好意思：一條先進先出的佇列。新行程加到尾端；排程器永遠從前端取走。沒有計時器、沒有比較、沒有任何花招。這份簡單是 FCFS 唯一真正的優點，所以我們來看看它的代價。
推演 FCFS，並遇見那列護衛車隊
用數字會讓這個缺陷令人難忘。假設三個行程都在時間 0 抵達、都已在就緒佇列中，而我們知道它們的 CPU 分發長度：P1 需要 24、P2 需要 3、P3 需要 3（單位隨你，就叫它們毫秒吧）。它們恰好以 P1、P2、P3 的順序抵達，所以 FCFS 就完全照這個順序跑它們。我們把它鋪在時間軸上，算出每個行程的等待時間——也就是它在首次拿到 CPU 之前，待在佇列裡的時間。
Order P1, P2, P3 (FCFS): 0 24 27 30 | P1 | P2 | P3 | wait: P1=0 P2=24 P3=27 avg wait = (0+24+27)/3 = 17 Order P2, P3, P1 (shortest first): 0 3 6 30 |P2 |P3 | P1 | wait: P2=0 P3=3 P1=6 avg wait = (0+3+6)/3 = 3
看看發生了什麼。在第一種順序裡，兩個小不點工作 P2 和 P3 被卡在那隻 24 單位的怪物 P1 後面，儘管它們各自只需要 3 單位的工作量。它們的等待——以及隨之而來的周轉時間——毫無道理地暴漲。這就是著名的護衛效應：佇列前端一個長行程，讓後面每一個短行程全都堆積起來，就像單線道上一輛慢吞吞的卡車，逼著後面一整列快車跟著用爬的。那些快車不慢，它們只是被困住了。在真實的作業系統裡，被困住的工作往往正是你正在等的那些互動式工作，所以護衛效應正是讓一台忙碌機器感覺像當機的元兇。
反過來想：最短工作優先
剛才的推演已經暗示了解方。第二種順序——P2、P3，然後 P1——不是什麼把戲，它是一條策略：永遠先跑下一段 CPU 分發最短的那個行程。這就是最短工作優先（SJF）。排程器不再尊重抵達順序，而是偷看每個就緒行程需要多少工作量，接著先服務最小的那個。直覺上，這就是超市的快速結帳道：讓只拿兩件商品的人插到推著滿車的人前面，能把大家的平均等待壓低，因為手腳快的那些人很快就清空、不再堵住隊伍。
真正美妙的部分來了，而且這不只是一種好感覺——它是一條定理。對任何一組固定的行程，SJF 給出可能達到的最小平均等待時間。沒有別的順序能贏過它。理由很短：平均等待時間主要取決於每個工作後面有多少工作得跟著等，所以你會希望「占用別人時間最少」的那些工作先走——而那些恰恰就是最短的那些。把一個短工作擺到一個長工作前面，受惠的行程永遠多於受害的行程。所以在所有只看分發長度的排程器當中，SJF 可證明為最佳。在系統的工作裡，能講出這種話是既稀有又可愛的事。
那個關卡：SJF 需要預知未來
如果 SJF 可證明為最佳，那為什麼任何真實系統還會用別的東西？因為「最短工作」這個說法裡，藏著一個悄無聲息卻致命的假設。要跑 SJF，你必須在一個行程跑之前，就知道它下一段 CPU 分發會有多長。但那個數字活在未來——它取決於程式還沒讀到的資料、還沒走過的分支、次數連它自己都不知道的迴圈。排程器無法真正得知它。照字面看，SJF 需要一個在做決定的當下無法得知的事實。這就是這個演算法誠實的核心：它同時是最佳的、又是無法實作的。
所以真實的排程器只能做唯一還算誠實的事：用猜的，而且從歷史去猜。一個程式最近的幾段分發，是它下一段不錯的線索——等按鍵的編輯器傾向於持續有短分發；輾過程式碼的編譯器傾向於持續有長分發。標準的招式是「指數平均」，它把最近一次量到的分發和持續累積的估計值混在一起，偏重最近的行為，卻又從不完全忘掉過去。結果不是 SJF，而是「近似 SJF」，一種預測。它通常不錯，偶爾出錯，而「可證明的理想」和「只能用猜的現實」之間這道差距，是你會一再遇見的主題。
加上利齒：SRTF 與飢餓的危險
純粹的 SJF 是非搶占式的：一個工作一旦開始，即使中途來了更短的工作，它也會把這段分發跑完。我們可以讓它更鋒利，方法是允許新來的工作打斷正在跑的。它的搶占式版本就是最短剩餘時間優先（SRTF）：在每一刻，都跑「剩餘」分發最小的那個行程，而一旦有新行程帶著比正在跑的那個更短的剩餘時間抵達，就搶占——把 CPU 硬收回來（記住，這是一次乾淨的搶占、回到就緒，而不是阻塞）。如果一個正在跑、還剩 5 單位的工作，中途來了一個 2 單位的新工作，SRTF 就停下大的、先跑小的。它把平均等待時間壓得比非搶占式 SJF 還低。
但更鋒利的利齒總會咬到誰。SJF 和 SRTF 共有一個陰暗面：一個長工作可能永遠等下去。如果短工作源源不絕地湧入——在忙碌的伺服器上它們就是會——一個大工作可能永遠當不成最短的那個，於是永遠拿不到 CPU。這就是飢餓：一個行程被無限期地拒於服務之外，不是因為它壞了，而是因為策略總能找到一個更值得服務的人。它就像熟食店裡那位有耐心的年長顧客，一次又一次被跳過，只因為總有人拿著單單一件商品走上前。FCFS 雖有護衛之苦，至少還保證你終究會排到最前面；SJF 和 SRTF 卻給不出這種承諾。
所以我們以一張誠實的成績單作結。FCFS 簡單到不行、不會飢餓，卻苦於護衛效應，而且當一個長工作領頭時，平均等待時間糟糕透頂。SJF 對平均等待時間可證明為最佳，卻需要無法得知的未來，而且會餓死長工作。SRTF 在等待時間上甚至更好，卻搶占得更多、餓死別人也更起勁。兩個極端都不能照原樣拿來用。下一篇會接過那個缺漏的點子——給每個人一段公平、有上限的回合，而不是把任何人跑到底——把它變成輪詢，在那裡有一個單一的旋鈕，也就是時間量子，讓我們在靈敏與額外負擔之間做取捨。