CPU 排程與虛擬記憶體：時間與空間的資源分配
本頁為依教材與考古題整理的原創摘要；考古題答案經技術覆核，但不是官方答案。
第一次接觸也沒關係
這堂先懂這些詞
先記住白話意思，不必急著背英文。看到正文時，再把正式名稱接回來。
上下文切換
也會看到：context switch、情境切換系統保存目前工作的執行狀態，再載入另一項工作的狀態。
- 生活例子：
- 像客服先記下 A 客戶談到哪，再打開 B 客戶紀錄接著處理。
- 別搞混：
- 切換本身有成本，頻繁切換不會免費增加效能。
頁表
也會看到：page table、virtual page、physical frame記錄虛擬頁面目前對應到哪個實體記憶體頁框。
- 生活例子：
- 像公寓信箱號碼對照住戶目前實際房號的查詢表。
- 別搞混：
- Page table 做位址映射，不等於存放檔案內容本身。
排程器
也會看到：scheduler、CPU scheduler、排程演算法作業系統決定哪個可執行工作何時取得 CPU 的機制。
- 生活例子：
- 像診所叫號，依規則安排下一位看診者。
- 別搞混：
- 排程器不是工作自己決定何時執行，也不保證每個工作立刻執行。
虛擬記憶體
也會看到：virtual memory、page、page fault、分頁把程式看到的位址空間映射到實體記憶體，必要時再從儲存裝置載入頁面。
- 生活例子：
- 像書桌只放正在看的資料，其餘文件先收在櫃子，需要時再拿出來。
- 別搞混：
- 虛擬記憶體不是單純把硬碟當 RAM；page fault 也不一定是程式故障。
工作集合與顛簸
也會看到：working set、thrashingWorking set 是程式近期常用的頁面；若實體記憶體容不下，系統可能頻繁換頁而幾乎做不了正事。
- 生活例子：
- 像桌面太小，做一道菜就不停把同一批工具搬進搬出櫃子。
- 別搞混：
- Thrashing 不是 CPU 計算太慢，而是 page fault 與換頁活動過多。
以 ready queue、waiting time、throughput 與 fairness 比較 FCFS、SJF、Round Robin、Priority 和 MLFQ，再由 paging、page table、page fault、working set 與 thrashing 理解虛擬記憶體。所引用考古題答案皆為非官方技術覆核；爭議題與題面不完整題均不列入 refs。
先抓住這幾件事
- 區分 CPU scheduling 的 utilization、throughput、waiting time、response time 與 fairness 目標
- 比較 FCFS、SJF、Round Robin、Priority 與 multilevel feedback queue 的選擇規則和風險
- 將 virtual page number 經 page table 映射成 physical frame number
- 說明 page fault、working set 與 thrashing 的因果關係
先想像這個場景
診所同時安排看診順序與診間門牌
一間診所只有一位當班醫師與有限診間。櫃檯一方面要從候診名單決定下一位病人，另一方面要把掛號單上的邏輯門牌查表映射到實際診間。短診先看可能降低平均等待，固定時間輪流看能避免某位持續候診者永久被略過；若可用診間不足，工作人員反覆把病歷送進送出，反而沒時間真正看診。
先別急著往下看，花十秒想一想：
三位病人同時到達，預估看診時間是 6、2、4 分鐘；若時間估計可靠，哪種順序會降低這三人的平均等待時間？若改成每人固定看 2 分鐘再輪到下一位，又對應哪種排程？
把故事換成電腦語言
| 生活中的角色 | 對應到 | 技術概念 |
|---|---|---|
| 已報到並等待醫師服務的候診病人 | ready queue 中等待 CPU 的 processes | |
| 櫃檯依政策選出下一位進診間的病人 | CPU scheduler 從 ready processes 選擇下一個執行者 | |
| 每位病人先取得固定 2 分鐘，看完一段就回隊尾輪候 | Round Robin 讓 processes 依序取得固定 time quantum | |
| 掛號單上的邏輯門牌由櫃檯目錄查到實際診間，門內位置編號保持不變 | Page table 將 virtual page number 映射到 physical frame number，page offset 在轉換後不變 | |
| 診間不足時不斷搬入搬出目前需要的病歷，搬運時間多於實際看診 | Active working sets 超過可用 frames 時，頻繁 page faults／paging 可能形成 thrashing |
題目出現這些字，先想到
- 提高 utilization／throughput、降低 waiting／response time、兼顧 fairness 都是 scheduling 目標，彼此可能衝突。
- Burst 已知等前提下 SJF 可最小化平均等待；Round Robin 依 time quantum 輪流，MLFQ 則允許 process 跨 queues 移動。
- Virtual address 拆成 page number 與 offset；page table 把 page number 映射到 frame number，offset 保持不變。
- 合法 page 尚未在 memory 也會 page fault；頻繁換頁且 paging 多於有效執行才是 thrashing。
1.排程器在互相衝突的目標間取捨
CPU scheduling（CPU 排程）是 OS 決定哪個 process 獲得 CPU 使用權的機制。排程器（scheduler）必須在多個互相衝突的目標之間取捨： (1) CPU utilization（CPU 使用率）— 盡量讓 CPU 忙碌，避免閒置。理想目標 > 90%。 (2) Throughput（吞吐量）— 單位時間內完成的 process 數量越多越好。 (3) Turnaround time（週轉時間）— 從 process 提交到完成的總時間越短越好。 (4) Waiting time（等待時間）— process 在 ready queue 中等待的總時間越短越好。 (5) Response time（回應時間）— 從提交到第一次產生輸出的時間越短越好。對互動式系統特別重要。 這些目標往往衝突：追求高 throughput 可能犧牲個別 process 的 response time。例如把所有 CPU 時間給一個長 process 可以提高 utilization，但其他短 process 必須等很久。 【Preemptive vs Non-preemptive】 • Non-preemptive（非搶占式）：一旦 process 獲得 CPU，就執行到完成或自願放棄（如 I/O）。簡單但可能造成長 process 壟斷 CPU。 • Preemptive（搶占式）：OS 可以在 time slice 到期或更高優先權的 process 到達時，強制中斷當前 process 的 CPU 使用權。現代 OS 幾乎都使用 preemptive scheduling。 【考試連結】(1) 五個排程目標的定義。(2) Turnaround time = waiting time + burst time。(3) 區分 preemptive 和 non-preemptive — 考古題常問「以下哪個排程演算法是 preemptive 的」。
- Waiting time 是 process 在 ready queue 等待的總時間
- Turnaround time 是完成時間減到達時間
- Response time 是到達後首次獲得回應的時間
- Fairness 與 starvation avoidance 也是典型排程考量
2.用選擇規則辨認排程演算法
不同的排程演算法用不同的規則選擇下一個要執行的 process： 【FCFS（First-Come, First-Served）】按到達順序執行。Non-preemptive。最簡單但可能造成 convoy effect — 一個長 process 後面排著很多短 process，平均 waiting time 很高。 範例：P1(24ms), P2(3ms), P3(3ms) 依序到達。 FCFS 執行順序：P1→P2→P3。Waiting time：P1=0, P2=24, P3=27。平均 = 17ms。 如果改成 P2→P3→P1：Waiting time：P2=0, P3=3, P1=6。平均 = 3ms。 【SJF（Shortest Job First）】選擇 burst time 最短的 process。可證明在所有非搶占式演算法中平均 waiting time 最短（optimal）。問題：無法精確預知 burst time，且可能造成長 process starvation。 【SRTF（Shortest Remaining Time First）】SJF 的搶占式版本。每當新 process 到達時，比較新 process 的 burst time 和當前 process 的剩餘時間，選較短的。 【Priority Scheduling】每個 process 有 priority number，CPU 分配給最高優先權的 process。可以是 preemptive 或 non-preemptive。問題：低優先權的 process 可能永遠得不到 CPU → starvation。解法：Aging — 隨時間逐漸提高等待中 process 的優先權。 【Round Robin（RR）】每個 process 獲得一個固定的 time quantum（時間片，如 10ms），用完就被搶占回到 ready queue 尾端。公平但 time quantum 的大小很關鍵：太大 → 退化成 FCFS；太小 → context switch overhead 太高。 【考試連結】給定一組 process 的到達時間和 burst time，計算各演算法下的 waiting time 和 turnaround time。最常考 RR 和 SJF。
- Time quantum 太大時，Round Robin 趨近 FCFS
- Time quantum 太小會增加 context-switch overhead
- SJF 的理論優勢依賴已知或可準確預估 CPU burst
- Aging 是逐步提高等待中 process 的 priority
3.MLFQ 以行為回饋調整優先序
MLFQ（Multilevel Feedback Queue）是現代 OS 最常用的排程機制，結合了多種演算法的優點。它有多個 priority levels 的 queue，每個 queue 有自己的排程規則： 【運作原則】 (1) 新 process 進入最高優先權的 queue。 (2) 如果 process 在 time quantum 內完成 → 離開。 (3) 如果 process 用完整個 time quantum（CPU-bound 行為）→ 降級到下一個較低優先權的 queue。 (4) 如果 process 在 time quantum 內主動放棄 CPU（I/O-bound 行為）→ 留在當前 queue 或升級。 (5) 較高優先權 queue 的 time quantum 較短（如 8ms），較低優先權的較長（如 16ms、32ms...）。 【為什麼這樣設計？】 • I/O-bound process 通常只需要短暫的 CPU 時間就會做 I/O，它們停留在高優先權 queue，獲得快速回應 → 好的 response time。 • CPU-bound process 需要大量 CPU 時間，逐漸降到低優先權 queue，但每次獲得更長的 time quantum → 減少 context switch overhead。 • 系統自動根據行為調整，不需要人工指定 priority。 【Starvation 解法】長期停留在低優先權 queue 的 process 可能 starvation。解法：Priority boosting — 定期把所有 process 搬回最高優先權 queue。 【具體範例】三層 MLFQ：Q0(quantum=8ms, RR), Q1(quantum=16ms, RR), Q2(FCFS)。 新 process P 進入 Q0。如果 P 在 8ms 內完成 → 結束。如果用完 8ms → 降到 Q1。在 Q1 用完 16ms → 降到 Q2。Q2 用 FCFS 執行（不再搶占）。 【考試連結】(1) MLFQ 降級和升級的條件。(2) 為什麼 I/O-bound process 優先權較高（不是因為更重要，而是因為它們很快就會放棄 CPU）。(3) MLFQ 的 starvation 問題和 priority boosting 解法。
- Feedback 的重點是 process 可跨 queue 移動
- 高優先序 queue 通常可搶占低優先序 queue
- 各 queue 可採不同 quantum 或排程規則
- Periodic priority boost 可避免低層 queue starvation
4.Paging 用固定大小單位連接虛擬與實體記憶體
Virtual memory（虛擬記憶體）讓每個 process 以為自己擁有一大塊連續的 address space，但實際上這些位址映射到分散在 physical memory 各處的區塊，甚至可能部分存放在磁碟上。 【Paging 機制】Paging 把 virtual address space 切成固定大小的 page（通常 4 KB），把 physical memory 切成相同大小的 frame。Page table 記錄每個 page 映射到哪個 frame。 地址轉換：virtual address = (page number, offset)。CPU 用 page number 查 page table 找到 frame number，再加上 offset 得到 physical address。 例如 page size = 4KB（2¹² bytes），virtual address = 0x3A7F： • Page number = 0x3（前面的 bits） • Offset = 0xA7F（後面 12 bits） • 查 page table：page 3 → frame 7 • Physical address = frame 7 的起始位址 + 0xA7F 【Page Fault】當 process 存取的 page 不在 physical memory 中（可能被 swap 到磁碟），CPU 產生 page fault exception。OS 處理：(1) 找到該 page 在磁碟的位置。(2) 找一個空的 frame（如果沒有，用 page replacement algorithm 淘汰一個）。(3) 從磁碟載入 page 到 frame。(4) 更新 page table。(5) 重新執行造成 fault 的指令。 【Page Replacement Algorithms】 • FIFO：淘汰最先載入的 page。簡單但可能淘汰常用的 page。有 Belady's anomaly — 增加 frame 數反而增加 page fault。 • LRU（Least Recently Used）：淘汰最久沒被存取的 page。效果好但實作成本高。 • Optimal（OPT）：淘汰未來最久不會被使用的 page。理論最佳但需要預知未來，只用作比較基準。 【TLB（Translation Lookaside Buffer）】Page table 存在 memory 中，每次地址轉換都要先查 page table（memory access）再存取資料（又一次 memory access），等於每次存取要兩次 memory access。TLB 是一個小型高速快取，存放最近使用的 page-to-frame 映射。TLB hit → 直接得到 frame number（不需要查 page table），TLB miss → 查 page table 並更新 TLB。 【考試連結】(1) 給定 page size 和 virtual address，計算 page number 和 offset。(2) 給定 page reference string 和 frame 數，用 FIFO/LRU/OPT 計算 page fault 數。(3) FIFO 有 Belady's anomaly 但 LRU 沒有。
- 4 KiB 是常見基本 page size，但架構也可能支援其他或 huge pages
- Page table 的核心用途是 virtual-to-physical address mapping
- Page fault 不等於程式錯誤；合法頁面可能只是尚未駐留
- Thrashing 的症狀是頻繁換頁與有效 CPU 工作下降
一起拆題目
範例 1：三個 process 同時在時間 0 到達，CPU burst 分別為 P1=6、P2=2、P3=4。比較 non-preemptive FCFS（順序 P1,P2,P3）與 SJF 的平均等待時間。
- FCFS 等待時間為 P1=0、P2=6、P3=8，平均 (0+6+8)/3=14/3。
- SJF 順序為 P2、P3、P1。
- SJF 等待時間為 P2=0、P3=2、P1=6，平均 (0+2+6)/3=8/3。
- 比較 8/3 < 14/3；本例符合 burst 已知且同時到達的前提。
所以答案是：FCFS 平均等待時間為 14/3，SJF 為 8/3；在此明確前提下 SJF 較小。
範例 2：Round Robin 的 quantum=2，P1 與 P2 在時間 0 到達，CPU burst 分別為 5 與 3。忽略 context-switch cost，列出執行片段。
- P1 先執行 2 單位，剩 3；ready queue 後方是 P2。
- P2 執行 2 單位，剩 1；P1 回到前方。
- P1 再執行 2 單位，剩 1。
- P2 執行最後 1 單位完成，P1 再執行最後 1 單位完成。
所以答案是：執行片段為 P1(0–2)、P2(2–4)、P1(4–6)、P2(6–7)、P1(7–8)。
範例 3：系統 page size=4 KiB；某 virtual address 的 page number=9、offset=100，page table 顯示 page 9 對應 frame 20。求 physical address；若 page 9 的 valid bit 為 0 又代表什麼？
- 4 KiB=4096 bytes，physical address = frame number × page size + offset。
- 代入得到 20×4096+100=81920+100。
- Physical address 為 82020。
- 若 valid／present bit 為 0，這次合法存取通常觸發 page fault，由 OS 檢查並載入頁面；若位址本身非法，則會進一步形成存取錯誤。
所以答案是：映射後 physical address=82020；page 不在 memory 時會觸發 page fault，而不是直接由 scheduler 解決。
這裡最容易選錯
- 宣稱某排程演算法在所有 workload 下都同時最佳化所有指標
- 忽略 SJF 最小平均等待時間依賴 burst 已知等前提
- 認為 Priority scheduling 與 SJF 天生不會 starvation
- 把 MLFQ 誤認為 process 永遠固定在單一 queue
- 把 page 與 frame 當成大小不同的單位
- 把 page table 誤當成儲存 PCB 或負責 CPU scheduling
- 把任何 page fault 都等同 thrashing 或非法記憶體存取
換你快速判斷
先在心中作答，再展開答案。答不出來時，回頭找本課的對照關係。
1CPU scheduling 常見的最佳化目標有哪些？
提高 utilization 與 throughput、降低 waiting／turnaround／response time，並兼顧 fairness 與避免 starvation。
不同 workload 對指標權重不同，目標之間也可能互相衝突。
2SJF 為何能降低平均等待時間，又有什麼限制？
在工作 burst 已知等前提下，先執行短工作可最小化該組工作的平均等待時間；但 burst 難以精確預知，長工作也可能 starvation。
不能把有條件的理論最佳性誤寫成所有動態 workload 下都無條件最佳。
3MLFQ 與固定 multilevel queue 最重要的差異是什麼？
MLFQ 允許 process 依行為與政策在不同優先序 queues 之間移動。
使用完整 quantum 的工作常被降級；priority boost 等機制可降低低層工作 starvation。
4Paging 中 page、frame 與 page table 各扮演什麼角色？
Page 是固定大小的虛擬位址區塊，frame 是同大小的實體記憶體區塊，page table 將 virtual page number 映射到 frame number。
位址中的 offset 在映射前後保持不變；page 與 frame 必須同大小才能直接替換頁框。
5Page fault 是否必然代表程式發生非法記憶體存取？
不是。合法 virtual page 尚未駐留於 physical memory 時也會 page fault，OS 可將它載入後重啟指令。
只有當位址或權限非法時，fault handler 才會把它當成存取錯誤，而不是正常 demand paging。
6Virtual memory 發生 thrashing 時，系統在做什麼？
系統花在 page faults 與換頁的時間多於有效執行，通常因 active working sets 超過可用 frames。
頻繁 paging 會使 CPU utilization 與 throughput 下降；增加 multiprogramming degree 反而可能惡化。
最後用考古題驗證
本課連結的題目都已通過可重現的技術覆核，可逐題練習與判分。
開始本課考古題練習參考來源
- Computer Science: An Overview, 13th Edition — J. Glenn Brookshear
- 作業系統 — 周志遠