Learning Objectives
- 分辨程式與行程，說出行程的五種狀態以及狀態之間怎麼轉換
- 說明單一 CPU 如何輪流執行多個行程（多工、內容切換）
- 用 FCFS、SJF、SRTF、RR、優先權排程畫出甘特圖，計算等待時間與周轉時間
- 比較各種排程演算法的優缺點：護航效應、飢餓、時間片大小的取捨
幾個 CPU 核心，怎麼跑幾百個程式
打開工作管理員（Windows）或活動監視器（macOS），你會看到上百個正在執行的項目，但電腦可能只有 4 到 16 個 CPU 核心。 它們看起來同時在跑，其實是作業系統讓它們輪流使用 CPU：每個只跑一小段時間就換下一個，換得夠快，人就感覺不出來。 電腦「變慢」，常常是因為要輪流的工作太多，每個分到的時間變少了。
先分清楚兩個名詞：
| 名詞 | 比喻 | 說明 |
|---|---|---|
| 程式（program） | 食譜 | 存在磁碟上的指令與資料，不會自己動 |
| 行程（process） | 照著食譜正在做的那一道菜 | 程式被載入記憶體、正在執行的一個實例；同一個程式可以同時有好幾個行程，例如開兩個記事本視窗 |
作業系統替每個行程維護一份行程控制區塊（process control block，PCB），記錄：行程編號、目前狀態、 下一個要執行的指令位址（程式計數器）、暫存器的內容、用了哪些記憶體、開了哪些檔案。
一個行程裡面還可以有好幾條執行緒（thread），共用同一塊記憶體、分頭做事，例如瀏覽器一邊下載、一邊讓你捲動頁面。 這一課為了簡單，把每個行程當成只有一條執行緒。
這一課要回答：作業系統怎麼決定下一個輪到誰？不同的決定方式，大家要等多久？
行程的五種狀態
一個行程從建立到結束，會在這些狀態之間移動：
| 狀態 | 意思 |
|---|---|
| 新建（new） | 剛建立，作業系統還在準備它需要的資源 |
| 就緒（ready） | 一切準備好，只差 CPU；在就緒佇列裡排隊 |
| 執行（running） | 正在使用 CPU；一個 CPU 核心同一時間只有一個行程在這個狀態 |
| 等待（waiting，也叫 blocked） | 在等某件事完成，例如讀檔、網路資料、使用者按鍵；這時給它 CPU 也沒用 |
| 結束（terminated） | 執行完畢，作業系統回收它用過的資源 |
新建 ──允許進入──▶ 就緒 ──分派──▶ 執行 ──執行完畢──▶ 結束
▲ ◀──時間片用完──┘ │
│ │ 等待 I/O
└──I/O 完成── 等待 ◀─┘
注意「等待」的行程在 I/O 完成之後，是回到就緒排隊，不是直接回到執行。
多工與內容切換
作業系統把 CPU 從一個行程換給另一個行程，叫做內容切換（context switch）： 先把目前行程的暫存器、程式計數器存進它的 PCB，再把下一個行程上次存下的內容載回 CPU。 切換本身不做任何有用的計算，所以切得太頻繁也會浪費時間。
決定「下一個輪到誰」的是排程器（scheduler）。排程有兩種：
- 非搶先式（non-preemptive）：行程拿到 CPU 後，一直跑到結束或自己去等 I/O，才交出 CPU。
- 搶先式（preemptive）：作業系統可以中途把 CPU 收回來，例如時間片用完、或有更緊急的行程到了。今天的桌上型與手機作業系統都是搶先式。
用來比較排程好壞的時間：
| 名稱 | 算法 | 在意它的人 |
|---|---|---|
| 周轉時間（turnaround time） | 完成時間 － 到達時間 | 交出一份工作，要多久拿到結果 |
| 等待時間（waiting time） | 周轉時間 － 執行時間＝在就緒佇列裡排隊的總時間 | 排隊排了多久 |
| 回應時間（response time） | 第一次拿到 CPU 的時間 － 到達時間 | 互動程式：按下去多久有反應 |
五種排程演算法
| 演算法 | 規則 | 搶先？ |
|---|---|---|
| FCFS（先到先服務） | 依到達順序，像排隊結帳 | 否 |
| SJF（最短工作優先） | CPU 空出來時，選執行時間最短的 | 否 |
| SRTF（最短剩餘時間優先） | SJF 的搶先版：新來的行程如果剩餘時間更短，就插隊 | 是 |
| RR（時間片輪轉，round robin） | 每個行程最多跑一個時間片（time quantum），沒跑完就排回佇列尾端 | 是 |
| 優先權排程 | 選優先權最高的（這裡數字越小越優先） | 可以是任一種，這裡用非搶先式 |
用一個例子算 FCFS（時間單位可以想成毫秒）：
| 行程 | 到達時間 | 執行時間 |
|---|---|---|
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
| P1 | P2 | P3 | P4 |
0 8 12 21 26
等待時間：P1＝0、P2＝8－1＝7、P3＝12－2＝10、P4＝21－3＝18，平均（0＋7＋10＋18）÷ 4＝8.75。 下面的模擬器用同一組資料，換其他演算法看看平均等待時間怎麼變。
用 Python 模擬時間片輪轉
三個行程都在時間 0 到達，時間片是 2。看上方的就緒佇列：每次從最左邊取出一個行程，跑完一個時間片還沒結束的，排回最右邊。注意 P3 只需要 1 個時間單位，雖然排在最後，卻是第一個完成的。
各種演算法的取捨
| 演算法 | 優點 | 缺點 |
|---|---|---|
| FCFS | 最簡單、公平（照順序） | 護航效應（convoy effect）：一個很長的行程排在前面，後面的短工作全部跟著等 |
| SJF／SRTF | 平均等待時間最短 | 要事先知道每個行程要跑多久（實際上只能用過去的紀錄估計）；長的行程可能一直被插隊，永遠輪不到，叫做飢餓（starvation） |
| RR | 每個行程很快就能輪到一次，回應時間短，適合互動 | 時間片太小，切換太頻繁；時間片太大，就退化成 FCFS |
| 優先權 | 重要的工作先做 | 低優先權的行程可能飢餓；常見的解法是老化（aging）：等得越久，優先權慢慢提高 |
真實的作業系統通常混合這些想法，例如：把行程依優先權分成好幾個佇列，同一個佇列裡用 RR； 常常在等使用者輸入的互動程式提高優先權，讓畫面反應快；長時間占用 CPU 的行程優先權慢慢降低。
多核心的 CPU 就是同時有好幾個「執行」的位置。排程器除了決定順序，還要決定每個行程放在哪一個核心上。
想一想：行程與狀態
你開了兩個記事本視窗在編輯不同的檔案。這是幾個程式、幾個行程？
行程 P1 發出讀檔請求，等到 SSD 把資料讀完之後，P1 會進入哪個狀態？
為什麼行程在等讀檔時要讓出 CPU？
算一算：排程結果
三個行程都在時間 0 到達，依序是 P1（執行 6）、P2（執行 2）、P3（執行 1）。用 SJF，平均等待時間是多少？
同樣三個行程（P1 執行 6、P2 執行 2、P3 執行 1，都在時間 0 到達，佇列順序 P1、P2、P3），用時間片 2 的 RR。哪一個行程最先完成？
RR 的時間片設得非常小（例如比一次內容切換的時間還短），會發生什麼事？
重點整理
- 程式是磁碟上的指令，行程是正在執行的程式；作業系統用 PCB 記錄每個行程的狀態與資源。
- 行程的五種狀態：新建、就緒、執行、等待、結束。I/O 完成後回到就緒，不是直接回到執行。
- 內容切換讓一個 CPU 輪流執行很多行程；切換本身要花時間。
- 周轉時間＝完成－到達；等待時間＝周轉－執行；回應時間＝第一次執行－到達。
- FCFS 簡單但有護航效應；SJF／SRTF 平均等待最短，但要知道執行時間、可能飢餓；RR 回應快，時間片太小切換太多、太大變成 FCFS；優先權排程用老化避免飢餓。
下一課看另一個要分配的資源：記憶體。很多行程同時在記憶體裡，作業系統怎麼讓它們互不干擾，記憶體不夠時又怎麼辦。