Learning Objectives
- 算出周轉時間、等待時間與回應時間，並說明它們各自在乎什麼
- 用護航效應說明為什麼 FCFS 的平均等待可能很差
- 比較 SJF、SRTF、RR、優先權排程的優點與代價
- 判斷時間片太大或太小各會怎樣，並親手寫出 RR
- 說明飢餓怎麼發生，以及老化怎麼解決它
同一批工作，順序不同，等待時間差很多
影印店只有一台機器。有人要印整本論文，他後面排了三個人，每人只印一張。如果照到店順序印，三個人都要等完整本論文；如果先讓他們印，論文只多等一下，大家的平均等待就短很多。
CPU 也一樣。只有一顆核心、有好幾個行程想跑時，「下一個輪到誰」由核心裡的排程器（scheduler）決定。這一課先假設每個行程只用 CPU、不做 I/O，下一課再把 I/O 和多核心加進來。
要比較排程好不好，先要有量尺：
| 指標 | 算法 | 在乎的是 |
|---|---|---|
| 周轉時間（turnaround time） | 完成時間 − 到達時間 | 從交出去到做完要多久，批次工作最在意 |
| 等待時間（waiting time） | 周轉時間 − 執行時間 | 白白排隊的時間 |
| 回應時間（response time） | 第一次拿到 CPU 的時間 − 到達時間 | 多久才有反應，互動程式最在意 |
這三個指標會互相衝突，所以沒有一個演算法在所有指標上都最好。
用程式算出順序的影響
FCFS（First-Come, First-Served，先到先服務）就是排隊：先到的先跑，跑完才換下一個。看同一批工作換個順序，平均等待變成多少。
四種常見的排程規則
短工作被長工作擋在後面，叫護航效應（convoy effect）。針對它的想法是讓短的先走：
- SJF（Shortest Job First，最短工作優先）：CPU 空出來時，挑執行時間最短的。它是非搶先（non-preemptive）的，開始跑就跑到完。工作同時到達時，平均等待時間是所有非搶先排程裡最小的。
- SRTF（Shortest Remaining Time First，最短剩餘時間優先）：SJF 的搶先版。新工作到達時，如果剩餘時間比正在跑的更短，就立刻搶走 CPU。
這兩個都有同一個問題：排程器怎麼知道工作還要跑多久？ 一般來說它不知道，只能從過去的行為估計，下一課會處理這件事。另外，短工作一直來的話，長工作可能永遠輪不到。
另一條路是不管長短，輪流來：
- RR（Round Robin，時間片輪轉）：每個行程跑一段時間片（time slice，也叫 quantum），用完就排到佇列尾端。沒有人需要等太久才有反應，所以回應時間好；代價是工作被切得很碎，周轉時間通常比 SJF 差。
最後一種是用重要性決定：
- 優先權排程（priority scheduling）：每個行程有一個優先權，先跑最優先的。本課的模擬器是非搶先版，數字越小越優先。問題同樣是低優先權的行程可能一直等。
下面的模擬器不計切換行程本身花的時間。真實系統每次切換都要保存與載入狀態，第 2 課看過這個代價。
時間片要設多長
剛才兩種極端的時間片，方向相反：
| 時間片 | 好處 | 代價 |
|---|---|---|
| 很大 | 切換少，CPU 時間都花在工作上 | 退化成 FCFS，回應變慢 |
| 很小 | 大家很快都輪到一次，回應好 | 切換太頻繁；真實系統裡切換有成本，切太細時大部分時間都花在切換，真正做事的時間變少 |
模擬器裡切換不花時間，所以看不到第二種代價，只看得到切換次數變多。設計時間片就是在這兩者之間取捨，而且取捨會隨工作類型改變。
飢餓與老化
只要高優先權的工作一直來，低優先權的工作就永遠輪不到，這叫飢餓（starvation）。常見的解法是老化（aging）：等得越久，優先權就提高一點。看看有沒有老化的差別。
實作：寫出 RR 排程
補完迴圈裡的四個步驟。規則和上面的模擬器相同：同一時刻先放新到達的行程，再放用完時間片的行程。寫好之後，可以把模擬器切到 RR、時間片 3，比對每個行程的完成時間與平均等待。
確認一下
三個工作同時到達，FCFS 依序跑，執行時間是 6、3、3。平均等待時間是多少？
一個行程到達時間 2、第一次拿到 CPU 在時間 5、完成在時間 11，執行時間 4。它的周轉、等待、回應時間依序是？
有人在編輯器裡打字，同時另一個行程在算大型矩陣。如果目標是讓打字不卡，下面哪一個考量最重要？
RR 的時間片調到比所有行程的執行時間都大，會發生什麼？
系統用 SRTF，短工作源源不絕地到達。下面哪一個最可能發生？
重點整理
- 周轉時間在乎做完，回應時間在乎有反應，等待時間是白白排隊的部分。這些目標互相衝突。
- FCFS 最簡單，但短工作會被長工作擋住（護航效應）。
- SJF、SRTF 讓平均等待變小，但要知道工作長度，而且長工作可能飢餓。
- RR 回應好，時間片太大退化成 FCFS，太小則切換成本吃掉工作時間。
- 優先權排程會讓低優先權的工作飢餓，老化是常見的解法。
這一課假設排程器知道每個工作要跑多久，而且只有一顆核心。真實世界兩個假設都不成立，下一課處理這兩件事。