地方政府公務人員四等-資訊處理類科計算機概要112 年第 24 題單選題
一作業系統採取最近最少使用（least recently used, LRU）演算法來管理 3 個記憶體頁框，若初始狀態中 3 個頁框沒有任何分頁（page）資料，系統依序存取以下編號之分頁：3、2、1、3、4、1、3、5、1，將產生多少次的分頁錯誤（page faults）？
B正確答案
LRU 演算法模擬：追蹤最近使用順序，不在頁框內即 page fault，滿了就換掉最久未用的。
為什麼答案是 B
正確答案。模擬：3(F)→[3]；2(F)→[3,2]；1(F)→[3,2,1]；3(H)→[2,1,3]；4(F,換2)→[1,3,4]；1(H)→[3,4,1]；3(H)→[4,1,3]；5(F,換4)→[1,3,5]；1(H)。共 5 次 fault。
載入中…
完整詳解
Pro · 無限重點 LRU 演算法模擬：追蹤最近使用順序，不在頁框內即 page fault，滿了就換掉最久未用的。
逐一模擬：記錄頁框內容與使用順序，每次存取若未命中即 +1 fault，滿了換掉最舊的那個。
逐選項分析
A✕
4 次太少。前 3 個存取（3、2、1）就已產生 3 次 fault，後續還有 4、5 也會 fault，不可能只有 4 次。
B✓ 正確
正確答案。模擬：3(F)→[3]；2(F)→[3,2]；1(F)→[3,2,1]；3(H)→[2,1,3]；4(F,換2)→[1,3,4]；1(H)→[3,4,1]；3(H)→[4,1,3]；5(F,換4)→[1,3,5]；1(H)。共 5 次 fault。
C✕ 陷阱
6 次是常見陷阱，可能誤把某次 hit 當成 fault。注意第 6 次存取 1 時，1 仍在頁框中（未被換出），應為 hit 非 fault。
D✕
7 次過多，可能誤用 FIFO 或未正確更新「最近使用」順序所致。LRU 命中時也要更新使用時間戳。
LRU 逐步模擬（頁框=3）
| 存取 | 命中? | 頁框內容 (舊→新) | Fault 數 |
|---|
| 3 | Fault | [3] | 1 |
| 2 | Fault | [3, 2] | 2 |
| 1 | Fault | [3, 2, 1] | 3 |
| 3 | Hit | [2, 1, 3] | 3 |
| 4 | Fault (換2) | [1, 3, 4] | 4 |
| 1 | Hit | [3, 4, 1] | 4 |
| 3 | Hit | [4, 1, 3] | 4 |
| 5 | Fault (換4) | [1, 3, 5] | 5 |
| 1 | Hit | [3, 5, 1] | 5 |
LRU 最大陷阱是「命中時忘記更新順序」。例如第 4 次存取 3 命中後，3 變成最新，2 才是最舊，所以下次換掉的是 2 不是 3。若忘了更新，會誤判換出對象，導致後續 fault 數全錯。 
