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