地特四等
112年
[資訊處理] 計算機概要
第 24 題
一作業系統採取最近最少使用（least recently used, LRU）演算法來管理 3 個記憶體頁框，若初始狀態中 3 個頁框沒有任何分頁（page）資料，系統依序存取以下編號之分頁：3、2、1、3、4、1、3、5、1，將產生多少次的分頁錯誤（page faults）？
- A 4 次
- B 5 次
- C 6 次
- D 7 次
思路引導 VIP
想像你桌上只有三個位置可以放常用的課本。當你想看的書不在桌上，且桌子已經擺滿時，你會根據什麼準則來決定把哪一本書收回書櫃，以確保留在桌上的都是你「剛才還在用」的書？請試著手繪這三個位置，並根據存取順序，記錄下每一次誰被放到了「最新被使用」的頂端，而誰被推到了「快被遺忘」的邊緣。
🤖
AI 詳解
AI 專屬家教
恭喜你正確答對了這題！這顯示你對最近最少使用（Least Recently Used, LRU）演算法的運作邏輯掌握得非常紮實。LRU 的核心思想是「過去的行為預測未來」，將最久沒有被存取的分頁視為未來最不可能被使用的對象。這類題目是作業系統虛擬記憶體章節中的常客，難度屬於中等（Medium），關鍵在於能否在每一次分頁存取時，精確更新每個頁框（Page Frame）的時間序位。
分頁替換邏輯解析
在此題中，前三次存取 3, 2, 1 時，因為初始頁框為空，皆會發生分頁錯誤（Page Fault），記憶體狀態變為 [3, 2, 1]（假設左側為最久未用）。接著存取 3（命中），更新順序為 [2, 1, 3]。當存取 4 時，因 2 是當前最久未使用的分頁，故將其替換，產生第 4 次錯誤。隨後存取 1 與 3 皆命中並更新序位。最後存取 5 時，最久未用的 4 被替換掉，產生第 5 次錯誤。最後存取 1 命中，總計發生了 5 次 分頁錯誤。這題的鑑別度在於存取序列中有多次重複出現的編號，考生若沒能即時更新「最近存取」的狀態，就很容易算錯次數。