moea_joint
112年
[資訊] 計算機原理、網路概論
第 12 題
有關作業系統對於記憶體管理之方式，包括 7 種分頁替換演算法(Page Replacement Algorithm)，分別為 FIFO(First In First Out)、OPT(Optimal)、LRU(Least Recently Used)、LFU(Least Frequently Used)、MFU(Most Frequently Used)、Second Chance 及 Enhanced Second Chance，請問前述有幾種會遭遇布雷第異常現象(Belady's Anomaly)？
- A 3
- B 4
- C 5
- D 6
思路引導 VIP
請思考一下：如果一個演算法能保證「在擁有 $n$ 個記憶體空間時所保留的頁面，一定也會出現在擁有 $n+1$ 個空間的情況下」，那麼增加記憶體空間還會導致分頁錯誤率上升嗎？在題目列出的演算法中，哪些是嚴格遵循『使用順序』或『預測未來』來維持這種包含關係的？而哪些僅僅是依照『進入時間』或『出現頻率』來做決策，進而可能破壞這種包含性呢？
🤖
AI 詳解
AI 專屬家教
恭喜你答對了！這題考查的是作業系統記憶體管理中非常經典的 布雷第異常 (Belady's Anomaly)。你能從眾多演算法中精確點出五種會發生異常的項目，顯見你對於演算法的底層邏輯與「堆疊演算法 (Stack Algorithms)」的特性掌握得十分透徹。
堆疊演算法與異常判定
布雷第異常是指「當分配的頁框數增加，分頁置換次數反而不減反增」的奇特現象。在作業系統理論中，只要不具備「堆疊特性」的演算法，都有可能遇到此問題。所謂堆疊特性，是指在 $n$ 個頁框中所包含的頁面集合，必須恆為 $n+1$ 個頁框時的子集。在題目給出的名單中，OPT 與 LRU 屬於堆疊演算法，絕對不會發生異常；而 FIFO 及其變體（如 Second Chance、Enhanced Second Chance），以及基於計數的 LFU 與 MFU，都不具備此特性，因此共有 5 種會遭遇異常。
▼ 還有更多解析內容