一句話講清楚這個問題
你在前一個階段已經知道，一個行程一生大部分時間都處於就緒或等待，而非執行中，而且 CPU 是靠一次情境切換從某個行程交到另一個行程手上。現在請想像此刻的就緒佇列：十幾個行程都已載入、都完整、都願意執行——而恰好只有一顆空閒的 CPU。總得有人指著其中一個說「接下來換你」。這個一再重複的單一決策，就是 CPU 排程，而核心中負責做這決定的部分叫短期排程器。它就像大樓管理員，每次電梯門一開，就要決定哪位住戶能搭上那台唯一還能用的電梯。
值得停下來想想：這為什麼有必要。如果每個行程從頭到尾都得不間斷地用 CPU，排程就會無趣到極點：把它們排成一列，跑完一個再跑下一個就好。排程之所以有趣——也之所以讓你的機器變快——是因為真實的程式幾乎從不需要連續占用 CPU。它們跑一小段，就停下來等某樣東西。理解這種「跑跑停停、停下來等」的節奏，正是整個基礎，所以我們接著就來看它。
分發週期：讓排程划算的那個節奏
仔細觀察任何一個行程，你會看到一種一再重複、由兩拍構成的節奏，稱為 CPU–I/O 分發週期。CPU 分發（CPU burst）是一段行程正在運算的時間——把數字相加、比較字串、跑迴圈——它是真的想要 CPU。接著它撞上某件自己辦不到的事：它要求用 read(fd, buf, n) 讀一個檔案、等待一次按鍵，或把資料送上網路。於是一段 I/O 分發（I/O burst）就此開始，在這段期間行程被阻塞在等待狀態，沒替任何人占住 CPU，而由磁碟或網路去做那件慢工。然後 I/O 完成、行程醒來，下一段 CPU 分發又開始。運算、等待、運算、等待——如此反覆，直到它結束。
process P over time: |== CPU ==| (read) ....I/O wait.... |= CPU =| (read) ...I/O... |==CPU==| exit compute block disk busy compute block net compute CPU bursts are usually SHORT and MANY; I/O bursts are LONG.
重點來了。一個行程一旦為了 I/O 而阻塞，它的 CPU 若不另作安排，就會在整段緩慢的等待裡閒著、什麼都不做。那段閒置時間就是機會。當行程 P 在等磁碟時，排程器可以把 CPU 交給此刻就能運算的行程 Q。當 P 的資料到來，P 再重新加入就緒佇列。把許多行程的 CPU 分發互相穿插進彼此的 I/O 空檔裡，作業系統就能讓 CPU 幾乎一直忙著——這正是多重程式設計那個老想法，而排程就是讓它運作的機制。沒有分發週期，就沒有空檔可填，也就沒有排程的理由。
分派器：是肌肉，不是頭腦
把兩件初學者常常混在一起的工作分開來看，會很有幫助。排程器是頭腦：它依某種策略決定「接下來該換哪個行程跑」。分派器是肌肉：一旦選定，分派器才真正把那個行程放上 CPU。排程器回答「換誰」；分派器負責「怎麼換」。它們之所以不同，是因為「選誰」的策略可以很聰明、可以慢慢演進，而「切換」這個動作則必須每一次都是同一套又快又機械的例行公事。
- 執行情境切換：把要離開的行程的暫存器存進它的 PCB，再載入要進來的行程先前儲存的暫存器（你在前一階段見過這完全相同的步驟）。
- 把記憶體對映切換到新行程的位址空間，讓它的（分頁編號, 位移）位址現在指向它自己的記憶體。
- 把 CPU 從核心模式切回使用者模式，放下核心剛才為了做這些事所需要的較高權限。
- 跳到新行程上次正要執行的那一條指令上，放它去跑。新行程完全察覺不到自己曾被暫停。
從排程器決定要停下某個行程的那一刻，到被選中的行程真正開始執行的那一刻，這段時間叫做分派延遲，我們希望它愈小愈好。為什麼？因為分派器挪移暫存器所花的每一微秒，都是「沒有」任何使用者程式在做事的一微秒。分派器純粹是額外負擔——就像幕間換景的舞台工作人員，台下觀眾乾等、台上沒人演戲。一個好的分派器之所以隱形，正是因為它夠快。
搶占與否：什麼時候可以打斷它？
排程器還需要一條關於時機的規則：它可以從正在執行的行程手上「硬把」CPU 搶回來嗎，還是必須客氣地等到那個行程自己交出來？這就是搶占式與非搶占式之分。非搶占式（又稱合作式）排程器只在正在執行的行程「自願」停下時才重新排程——也就是它為了 I/O 而阻塞、或是結束的時候。一旦你開始跑，CPU 就是你的，直到你自己選擇釋放。相對地，搶占式排程器可以強制把 CPU 收回來，通常是在一個計時器中斷觸發時——那就是告訴核心「時間到了」的門鈴。
這個取捨是真實的，而誠實地命名很要緊。非搶占式排程簡單，也避開了某些討厭的臭蟲（你絕不會被排程器在更新共享資料更新到一半時打斷），但它很脆弱：只要有一個行為不端的行程無限迴圈、永不阻塞，它就會霸占 CPU、把其他一切都凍住。搶占式排程才是讓系統感覺靈敏又公平的關鍵——即使一支吃重的程式正在跑，你的打字依然有反應——但它的代價是更多次切換，並迫使核心對競爭條件格外小心，因為一個行程現在隨時可能在某個尷尬的時刻被停下。今天幾乎每一個互動式作業系統都是搶占式的；那個門鈴永遠是上膛待命的。
五把尺：評斷一個排程器
在我們能於後續幾篇裡比較各種演算法之前，得先就「好」到底是什麼達成共識。沒有單一完美的排程器，因為各個目標彼此拉扯；排程準則就是我們用來衡量的五把標準尺。CPU 使用率是 CPU 在做有用工作（而非閒置）的時間比例（我們希望它高）。吞吐量是每單位時間有多少行程完成（高的好）。其餘三項是逐行程衡量、而且我們希望它們低：周轉時間是從提交到完成的總時間；等待時間純粹是待在就緒佇列裡的時間；而回應時間是從提交到行程「首次」開始產出輸出的時間。
最後兩項有著微妙的差別，而這道差距正是排程器設計的所在。等待時間和回應時間起算的是同一個時鐘，但回應時間在行程產出第一個看得見的結果時就停了，等待時間卻是在行程的整段生命裡持續累加。對一個互動式工作——你的文字編輯器對一次按鍵的反應——你感受到的是回應時間；你不在乎編輯器要花 30 毫秒才把整件事做完，你在乎的是游標在你輕點後 50 毫秒內就動了。對一個輾過十億列資料的批次工作，你根本感覺不到回應時間；你只在乎周轉時間。一個為俐落回應而調校的排程器，往往是「對抗」純粹吞吐量而調的，反之亦然。
這個階段接下來要去哪裡
你現在已經有了整個框架。排程之所以存在，是因為分發模式留下了值得填補的 CPU 空檔；排程器決定換誰跑，而分派器以低分派延遲執行切換；系統通常是搶占式的，好讓它保持公平又靈敏；而我們用五把尺去評斷每一個選擇。這個階段裡其餘的一切，都不過是對同一個問題的不同答案——給定就緒佇列，接下來換誰？——而每個答案都在那些尺之間做了不同的取捨。
接下來我們會遇見最簡單的兩個想法，並親身感受它們的缺陷：先到先服務，它看似公平，直到一個巨無霸工作在後面塞出一條車陣；以及最短工作優先，它對等待時間來說可證明為最佳，卻需要一個它無法真正得知的事實——每個工作究竟會跑多久。之後是輪詢，以及它那至關重要的時間量子；再來是優先權，以及它帶來的飢餓風險；最後是把這些想法縫合在一起的真實世界排程器。同一個問題，多種取捨；我們這就開始討價還價吧。