2009年408統(tǒng)考的第26題操作系統(tǒng)內(nèi)存管理。這道題我在復(fù)習(xí)時第一次做就栽了——不是不會算而是把“缺頁次數(shù)”和“置換次數(shù)”混在了一起最后對答案時發(fā)現(xiàn)整道題的思路就偏了。后來我拿格子法在草稿紙上重新推了一遍才發(fā)現(xiàn)這種題目只要把“幀”的狀態(tài)變化列清楚根本不會錯。今天就把這題拆開講透順便把頁面置換算法、Belady異常、考場速算技巧一次說清楚。1. 先把這道題“翻譯”成人話1.1 題目原文與選項設(shè)置這道題在歷年資料中的轉(zhuǎn)述版本如下在一個請求分頁存儲管理系統(tǒng)中頁面走向訪問序列為1、2、3、4、1、2、5、1、2、3、4、5。若采用FIFO頁面置換算法分配給進(jìn)程的物理塊數(shù)為3則缺頁次數(shù)是多少A. 8 B. 9 C. 10 D. 12因?yàn)?08統(tǒng)考的真題版權(quán)不公開網(wǎng)絡(luò)和各種輔導(dǎo)資料里普遍使用這個“回憶版”。大部分資料給出的標(biāo)準(zhǔn)答案是B. 9。很多同學(xué)考場上真正糾結(jié)的其實(shí)不是FIFO算法本身而是算到第7、第8步時把自己繞暈了把“缺頁次數(shù)”累加到了11、12甚至更高。這題表面上看是一道單純的“置換算法模擬計算題”但它踩中的是操作系統(tǒng)內(nèi)存管理里最核心的“請求分頁”模型。如果你只背過“FIFO就是先進(jìn)先出”這句話不把幀的變化過程走一遍大概率會錯。所以下面我從最基礎(chǔ)的概念開始重新過一遍。1.2 題干里幾個容易理解偏差的詞這題里幾個關(guān)鍵術(shù)語需要先校準(zhǔn)一下頁面走向reference string進(jìn)程訪問頁面的順序。不是讓你排序也不是讓你數(shù)有哪些不同頁面而是嚴(yán)格按照給出的1、2、3……順序逐個判斷。物理塊frame內(nèi)存中真正裝頁的位置。本題給了3個物理塊表示內(nèi)存同時最多容納3個頁面。缺頁page fault訪問的頁面不在任意一個物理塊中就需要從磁盤調(diào)入算一次缺頁。置換replacement內(nèi)存滿了還要訪問新頁面時必須把某個舊頁面踢出去騰地方。FIFO踢的是“最早進(jìn)入內(nèi)存”的那個頁面。這里最容易搞混的是“缺頁”和“置換”的區(qū)別。缺頁不一定發(fā)生置換——前3次訪問時物理塊有空位直接裝入即可只算缺頁不算置換。我第一次算錯就是覺得既然題目問“缺了幾次頁”應(yīng)該從第4次才開始數(shù)直接把前3次給漏掉了。顯然不對物理塊初始為空時前3次訪問全是缺頁。2. 頁面置換到底在解決什么問題一段恰到好處的背景2.1 為什么會有“置換”這一步你要理解這道題必須先理解虛擬內(nèi)存里的按需分頁demand paging。程序運(yùn)行時CPU給的邏輯地址并不會直接對應(yīng)內(nèi)存物理地址而是要先通過頁表把“頁號”換成“物理塊號”。如果這一頁明明被程序引用了卻不在內(nèi)存里硬件會觸發(fā)缺頁中斷由操作系統(tǒng)把磁盤上對應(yīng)的頁面調(diào)入內(nèi)存。問題來了內(nèi)存的物理塊數(shù)是有限的。一個進(jìn)程可能有好幾百頁但內(nèi)存只給它3個塊、4個塊。當(dāng)3個塊都裝滿了進(jìn)程又訪問一個不在內(nèi)存中的新頁怎么辦必須踢掉某一頁給新頁騰地方。那么踢誰這個“踢誰”的決策規(guī)則就叫頁面置換算法。你可以把它理解為一家只有3張桌子的自習(xí)室。來的人頁面必須坐桌子才能學(xué)習(xí)訪問。桌子沒空位時新來的人必須把某個人趕走。FIFO的規(guī)則很簡單——誰來得最早就先趕誰走不管他是不是正在學(xué)習(xí)、是不是馬上還要回來。這就是“先進(jìn)先出”的直覺也是這道題的核心邏輯。2.2 FIFO、LRU、OPT三種算法到底差在哪先建立全局觀不然你就算會做這一題換一道LRU的類似題還是容易懵。OPT最佳置換理論上的“上帝視角”——選未來最長時間不會被用到的頁面淘汰。它缺頁率最低但未來不可知所以只作為衡量標(biāo)準(zhǔn)不能真實(shí)現(xiàn)實(shí)系統(tǒng)。FIFO按進(jìn)入內(nèi)存的時間排隊最早進(jìn)來的先被淘汰。實(shí)現(xiàn)成本低用一個隊列就行但“最早進(jìn)來的”不一定“將來最沒用”所以效果不算好。LRU最近最久未使用淘汰“最近最長時間沒有被訪問”的頁面。它比FIFO更貼近局部性原理是考試最愛考的算法之一。這里要特別提一個直覺誤區(qū)FIFO不是按“當(dāng)前時刻哪個頁面最久沒被訪問”來淘汰的而是按“哪個頁面最早被裝入”來淘汰的。一個頁面哪怕剛剛被訪問過只要它是最早裝入的那一個FIFO照樣會把它踢出去。后面的Belady異常就跟這一點(diǎn)直接相關(guān)。題外話生產(chǎn)環(huán)境里的近似LRU算法比如Clock算法都做了折中不會真去按訪問時間精確排序因?yàn)槟莻€代價太高了。但考試和概念題還是以這三種最經(jīng)典算法為主。3. 逐步推演3個物理塊下的FIFO全過程3.1 用表格手把手算一遍下面這張表是整個題的解體過程。我按照“第幾步、訪問哪個頁、三個物理塊的內(nèi)容、命中還是缺頁、累計缺頁次數(shù)”五個維度來寫。FIFO的特點(diǎn)在于“按裝入順序”排發(fā)生淘汰時踢的是隊列最前面的那個頁面。步驟訪問頁三個物理塊內(nèi)容按裝入順序結(jié)果累計缺頁11[1, 空, 空]缺頁裝入122[1, 2, 空]缺頁裝入233[1, 2, 3]缺頁裝入344[4, 2, 3] 淘汰1缺頁置換451[4, 1, 3] 淘汰2缺頁置換562[4, 1, 2] 淘汰3缺頁置換675[5, 1, 2] 淘汰4缺頁置換781[5, 1, 2]命中792[5, 1, 2]命中7103[5, 3, 2] 淘汰1缺頁置換8114[5, 3, 4] 淘汰2缺頁置換9125[5, 3, 4]命中9逐行核對一遍第1步到第3步物理塊從空到裝滿全部缺頁沒有置換。第4步訪問4物理塊已滿FIFO看誰最早裝進(jìn)來的——是1所以淘汰1把4放進(jìn)去。此時物理塊里是4、2、3。注意它們的“裝入先后”是234。第5步訪問1最早裝進(jìn)來的是2淘汰2物理塊變成4、1、3。第6步訪問2最早裝進(jìn)來的是3淘汰3物理塊變成4、1、2。第7步訪問5最早裝進(jìn)來的是4淘汰4物理塊變成5、1、2。到這里走到一個容易慌亂的地方第8步訪問1物理塊里有1命中第9步訪問2物理塊里有2命中。命中的時候FIFO的裝入順序完全不變。很多同學(xué)會把命中的頁面重新視為“新裝入”然后在下一步錯誤地先淘汰它。這是FIFO和LRU最關(guān)鍵的操作差異。第10步訪問3此時物理塊5、1、2里沒有3需要置換。最早裝入的是1淘汰1變成5、3、2。第11步訪問4最早裝入的是2淘汰2變成5、3、4。第12步訪問5命中。累計缺頁剛好9次。3.2 我在草稿紙上的“標(biāo)記法”這種題你在考場上真的畫表格嗎畫完整表格不是不行但12步還好如果出現(xiàn)20步的LRU題時間就緊張了。我復(fù)習(xí)時總結(jié)了一個簡化寫法非常順手先寫一行頁號1 2 3 4 1 2 5 1 2 3 4 5下面畫三個格子從左到右表示三個物理塊但每個格子標(biāo)注一個“進(jìn)入時間序號”。訪問某個頁時先在三個格子里掃一眼如果命中直接什么都不改如果沒命中就找到一個“進(jìn)入時間序號最小”的格子把里面內(nèi)容替換掉并把它的進(jìn)入時間改成當(dāng)前步驟序號。舉個例子第8步訪問1看到1在第5步被裝進(jìn)第二格所以現(xiàn)在它的進(jìn)入時間序號是5不是1?？傻?0步淘汰1的時候?yàn)槭裁床豢催M(jìn)入時間因?yàn)榈?步“命中1”時沒有改變1的進(jìn)入時間1仍然是第5步裝入的所以它是當(dāng)前最早裝入的一個。這就是FIFO與LRU在標(biāo)記法上的唯一區(qū)別——FIFO標(biāo)記“裝入時間”LRU標(biāo)記“最近訪問時間”。這個標(biāo)記法可以一口氣寫下來不用畫大表格而且出錯后容易檢查。考場上如果時間緊張直接用它平時練習(xí)則建議老老實(shí)實(shí)畫完整表格因?yàn)楫嫳砀衲軒湍憷斫饷恳徊阶兓绕涫翘鎿Q那一刻的隊列狀態(tài)。4. 換4個物理塊后答案為什么“反直覺”了4.1 完整推演4物理塊的情況我剛做這題時產(chǎn)生過一個大疑問物理塊從3個增加到4個內(nèi)存變多了缺頁次數(shù)就算不減少也至少不該增加吧這題如果追問一句把物理塊數(shù)改成4FIFO的缺頁次數(shù)是多少結(jié)果會讓你大跌眼鏡。仍然是同樣的訪問序列1、2、3、4、1、2、5、1、2、3、4、5但這次分配4個物理塊。按FIFO逐步推步驟訪問頁四個物理塊內(nèi)容按裝入順序結(jié)果累計缺頁11[1, 空, 空, 空]缺頁裝入122[1, 2, 空, 空]缺頁裝入233[1, 2, 3, 空]缺頁裝入344[1, 2, 3, 4]缺頁裝入451[1, 2, 3, 4]命中462[1, 2, 3, 4]命中475[5, 2, 3, 4] 淘汰1缺頁置換581[5, 1, 3, 4] 淘汰2缺頁置換692[5, 1, 2, 4] 淘汰3缺頁置換7103[5, 1, 2, 3] 淘汰4缺頁置換8114[4, 1, 2, 3] 淘汰5缺頁置換9125[4, 5, 2, 3] 淘汰1缺頁置換10答案是10次。物理塊從3個增加到4個缺頁次數(shù)反而從9次增加到了10次。這是FIFO算法最著名的“黑點(diǎn)”也是408操作系統(tǒng)里一個必須掌握的知識點(diǎn)——Belady異常。4.2 Belady異常的本質(zhì)Belady異常指的是在采用FIFO置換算法時分配物理塊數(shù)增加缺頁次數(shù)反而增加的異?，F(xiàn)象。為什么4個塊會比3個塊的缺頁次數(shù)還多核心原因要從FIFO的淘汰邏輯說。FIFO總是淘汰最早裝入的內(nèi)存頁面完全不參考“未來會不會被訪問”。當(dāng)物理塊是4個時前4次訪問把1、2、3、4裝滿第7次訪問5時淘汰的是1。接著第8、9、10、11次連續(xù)訪問1、2、3、4而這時每個新訪問頁都會導(dǎo)致一次缺頁因?yàn)榍耙徊絼倓偘哑渲袔讉€淘汰了。也就是說FIFO在4個塊下形成了一種“輪流把老頁面趕走馬上又要把它們請回來”的死循環(huán)。反觀LRU和OPT它們都有“棧式性質(zhì)”——分配更多物理塊時缺頁次數(shù)一定不增加。LRU按“最近訪問時間”淘汰內(nèi)存框更多時最近被訪問的頁面更容易留在里面不會出現(xiàn)物理塊多了反而頻繁把剛用過的頁面踢走的情況。考場上一旦選項里有“Belady異常只可能出現(xiàn)在FIFO算法”這種判斷你要能立刻聯(lián)想到這題。反過來如果題干說“物理塊為4缺頁次數(shù)為10”你要能反推出這基本是在考FIFO的Belady異常。我在復(fù)習(xí)時記了一句口訣來避免自己再懵FIFO看“誰先來”LRU看“誰最久沒來”O(jiān)PT看“誰最后才來”。Belady異常只跟FIFO綁在一起。5. 這道題背后的408命題風(fēng)格看著是計算題考的是概念5.1 別只把它當(dāng)成算術(shù)題很多人以為這種題難在“算”。其實(shí)不算難。它真正想考的是你能不能把“請求分頁、頁表、缺頁、置換”這一整條鏈路串起來。與這題配套的知識點(diǎn)至少還有三個頁表項組成頁表里有多少位用來映射物理塊號、多少位是狀態(tài)位/訪問位/修改位。地址轉(zhuǎn)換過程邏輯地址 → 頁號 頁內(nèi)偏移 → 查頁表 → 物理塊號 頁內(nèi)偏移 → 物理地址。兩級頁表/多級頁表為什么需要分級頁目錄表怎么定位。比如2009年同卷的其他題目要么考地址變換要么考文件系統(tǒng)的索引結(jié)構(gòu)。第26題選擇了“缺頁次數(shù)計算”這種看起來偏計算的考法但它的提法是“內(nèi)存管理”那就要你快速定位到請求分頁而不要聯(lián)想到連續(xù)分配、分區(qū)管理那些模型否則從一開始就會選錯方向。5.2 考場上的三個判斷技巧我把自己做這類題踩過的坑總結(jié)成三條考場上非常實(shí)用第一先看初始狀態(tài)。按大多數(shù)408題目的隱含假設(shè)頁面初始時內(nèi)存為空。如果題目明確說“內(nèi)存已經(jīng)裝入某些頁”則這些頁不算缺頁。每一份試卷的表達(dá)可能不完全相同做題前先花五秒確認(rèn)不要默認(rèn)。第二命中時不要動“進(jìn)入時間”。這在FIFO題里太重要了。如果某頁面在訪問序列里第二次出現(xiàn)且在物理塊內(nèi)那么“命中”并不改變它的裝入順序下一個被淘汰的還是它。只要你在這一步把命中頁的優(yōu)先級往后挪了之后每一步都會錯。第三替換只看“現(xiàn)在的物理塊”不是看“頁表”。有些同學(xué)會去翻頁表的有效位、狀態(tài)位然后自己腦補(bǔ)“這個頁在磁盤上已經(jīng)失效了”于是提前淘汰它。但是頁面置換算法操作的對象是物理塊內(nèi)容不是頁表項。頁表項只是記錄映射關(guān)系的“賬本”算法是在內(nèi)存資源有限時決定把哪個物理塊騰出來。先有物理塊被淘汰再有頁表項的對應(yīng)更新不要搞反因果。5.3 實(shí)戰(zhàn)建議頁面置換題怎么練才扎實(shí)我自己的練習(xí)方法是把常見的三種算法FIFO、LRU、OPT放在同一張表里對同一訪問序列各算一遍然后對比缺頁次數(shù)。推薦一個百試不厭的序列7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1物理塊數(shù)3。這個序列在很多經(jīng)典教材里出現(xiàn)過三塊下OPT缺頁次數(shù)最少FIFO最多LRU居中。你親手把三種算法的幀狀態(tài)變化寫一遍比背任何結(jié)論都管用。再進(jìn)階一步試試把FIFO的物理塊數(shù)改成4看看是否出現(xiàn)Belady異常再把LRU的物理塊數(shù)改成4驗(yàn)證LRU單調(diào)性。這樣你就能直觀感受到為什么操作系統(tǒng)的真實(shí)實(shí)現(xiàn)更傾向用LRU近似算法如時鐘算法而不是簡單FIFO。如果備考時間比較緊我建議至少做到看到任意訪問序列和置換算法能在兩分鐘內(nèi)寫出缺頁次數(shù)并能準(zhǔn)確描述每一步發(fā)生了“缺頁裝入”“缺頁置換”還是“命中”。這個能力在選擇題和大題里都是基本功。最后再分享一個我到考前的習(xí)慣遇到這種模擬題我不直接算答案而是先在題目旁邊用一句話寫出該算法的淘汰規(guī)則比如“FIFO淘汰最早進(jìn)入的頁面”。寫完之后再往下算?？雌饋矶嗷ㄊ腌姷珜?shí)際上它能攔住絕大多數(shù)因?yàn)槭只鴮?dǎo)致的低級錯誤。我自己考場上就是靠著這個習(xí)慣把這道題的確認(rèn)時間壓縮到了四十秒以內(nèi)。包含置換的模擬題每一步都寫清楚才是最快的解法。