恐龍書CH10的課後題是我當年把全書刷完一遍之後又決定回頭重刷的存在。操作系統這門課裡程序、調度、同步好歹還有代碼結構和圖示可以幫忙理清邏輯到了Virtual Memory這一章畫風突變滿頁都是抽象機制按需調頁、缺頁處理、頁面置換、工作集、抖動……每個術語單獨拿出來都認識湊到一起做題就頻頻翻車。後來復盤才發現問題不是題目難而是我沒有先把這一章的知識模型在腦子裡搭起來。CH10的課後題其實有非常固定的題型規律把每種題型的底層邏輯和答題範式吃透比單純去背一份“答案”有用得多。1. CH10課後題全景考點分佈與解題思維1.1 為什麼第十章是全書的分水嶺第十章之前恐龍書講的多半是“作業系統怎麼管理單一資源”CPU調度、同步、死鎖每一章都有明確的演算法和可視化流程。但第十章把「主記憶體」和「磁碟」串起來之後整個系統的視角從“資源管理”跳到了“資源虛擬化”。虛擬記憶體的核心思想可以一句話講完把主記憶體當成一塊大型的「快取」後端放著的是磁碟。程序以為自己擁有一片連續且巨大的位址空間實際上只有正在使用的那些分頁才待在記憶體裡其他分頁乖乖躺在磁碟上。這個思想一出來後續所有機制都像多米諾骨牌一樣被推倒要讓“只有部分頁在記憶體”成立 → 需要按需調頁按需調頁會遇到“要的頁不在” → 需要缺頁處理記憶體滿了需要騰位置 → 需要頁面置換多個程序怎麼分有限的頁框 → 需要幀分配分得不合理導致程序瘋狂缺頁 → 這就是抖動。CH10的課後題基本上沿著這條因果鏈逐個設點。你只要這條鏈在腦子裡是通的絕大多數題一眼就能看出它在考哪一環。1.2 先看題型地圖再談做題我當時犯過一個錯拿到課後題就按題號順序硬刷。刷到第10題才發現前面幾題考的概念後面根本沒用上後面幾題需要的理論前面又沒複習。後來我改成“按題型刷”效率瞬間拉滿。CH10的課後題大致可以分成四類題型對應知識點準備方式概念複述題demand paging、Copy-on-Write、mmap背清楚機制能畫出流程計算題EAT計算、置換缺頁數、工作集大小純手算多練表格推演機制解釋題Belady異常、抖動成因、程序局部性掌握因果鏈答題按“現象→原因→對策”對比題全域/局部分配、buddy/slab列表對比優缺點概念複述題靠背計算題靠算機制解釋題靠因果鏈對比題靠表格式記憶。下面各章節我就按這四類分別拆。2. 按需調頁與EAT題原理、推演與常見翻車點2.1 缺頁錯誤處理的完整順序第十章前半部分的課後題幾乎繞不開“缺頁錯誤page fault怎麼處理”。就算題目沒有直接問後面算EAT、算置換缺頁數也都要以這個流程為背景。所以這一段值得背到肌肉記憶。一次缺頁處理的標準步驟是程序訪問一個「有效位為0」的頁硬體觸發缺頁陷阱page fault trap。作業系統檢查頁表項如果這次訪問本來就是非法位址直接終止程序如果合法繼續。OS找到一個空閒幀free frame。如果被換出的幀在記憶體期間被寫過髒位為1必須先把它寫回磁碟。OS啟動磁碟I/O把需要的頁從磁碟讀入這個幀。I/O完成後更新頁表項把有效位置1。重新執行觸發缺頁的那條指令。很多同學在寫答案時漏掉第4步的“髒位判斷”。為什麼這一步重要因為如果頁沒被修改過根本不需要寫回磁碟直接覆蓋即可。缺頁處理時間從“一次磁碟讀一次磁碟寫”變成“只有一次磁碟讀”代價差了一倍。題目裡一旦出現“dirty bit”通常就是在考這個點。2.2 EAT計算題把單位換算做對這題就贏了按需調頁最經典的計算題是算有效存取時間EATEffective Access Time。題目一般會給你記憶體存取時間、缺頁服務時間和缺頁率讓你算EAT。公式長這樣EAT (1 − p) × 記憶體存取時間 p × 缺頁服務時間其中 p 是缺頁率。看起來不難但翻車點非常隱蔽——單位。來一個我經常用的例子。假設記憶體存取時間是 200 ns缺頁服務時間是 8 ms缺頁率 p 0.0001。代入公式EAT (1 − 0.0001) × 200 0.0001 × 8,000,000 199.98 800 999.98 ns ≈ 1 μs看到了嗎缺頁率只有萬分之一有效存取時間卻已經從 200 ns 膨脹到將近 1000 ns變成原來的 5 倍。這就是為什麼虛擬記憶體系統裡降低缺頁率的收益遠比降低記憶體存取時間的收益來得大。如果把不同缺頁率放在一起對比會更直觀缺頁率EAT相對於純記憶體存取的倍數10⁻⁶≈ 208 ns約 1.04 倍10⁻⁴≈ 1000 ns約 5 倍10⁻³≈ 8.2 μs約 41 倍10⁻²≈ 80.2 μs約 401 倍建議做這類題時先把“ms”換成“ns”再代入。考試時因為單位沒統一而算錯十分真的非常冤。另外有些題會加一層 TLB。公式會變成EAT TLB命中率 × (TLB存取 記憶體存取) TLB未命中率 × (TLB存取 頁表走訪 記憶體存取)核心邏輯還是“命中走快路未命中走慢路”只是多了一層權重。把每一條路徑的開銷列清楚再乘上對應機率就不會亂。2.3 頁表標誌位與Copy-on-Write概念題第十章前段還有一類常見概念題考頁表項裡那些位元的作用。有效位valid/invalid bit決定“這頁到底在不在記憶體”髒位dirty bit決定“換出時要不要寫回”參照位reference bit是頁面置換演算法的輸入。Copy-on-WriteCOW則是 fork 相關的熱門考點。題目要你解釋COW為什麼能省記憶體或者反過來問“什麼情況下COW反而沒優勢”。答題時建議按三層來寫機制fork 後父子程序共享所有頁並把這些頁標記為唯讀任一方嘗試寫入時觸發保護錯誤OS複製該頁再把雙方的頁表項更新為可寫。省在哪如果 fork 之後立刻 exec根本不需要複製任何頁省掉一整批記憶體複製和頁表建立開銷。邊界如果父子程序都頻繁寫入大量頁COW的複製次數會上升這時候它帶來的收益就不如直接複製來得明顯。有次面試被問到“COW的觸發條件”我當時只答了“寫入時觸發”面試官追問“誰來觸發、觸發之後誰來複製”我才意識到機制題要答到“陷阱→OS介入→複製→更新頁表”這條鏈才算完整。這條鏈跟2.1的缺頁流程是同一套思維可以一起記。3. 頁面置換手算題FIFO、LRU、OPT的完整推演3.1 手算表格的標準寫法頁面置換手算題是CH10課後題裡佔比最高、也最容易因為“算亂”而失分的一類。題目通常給你一個引用串reference string和幀數要你分別用FIFO、LRU、OPT算缺頁次數。手算時我推薦用這種表格每一列代表引用串的一次存取格子裡記錄當前幀中的頁面缺頁的那一列做個明顯標記被換出的頁面加個箭頭或括號方便回頭檢查。我自己算題時習慣用“F”代表缺頁fault、“H”代表命中hit。這樣最後數F的個數就是缺頁次數不會數到眼花。還有一點要提醒題目沒特別說的話初始載入也算缺頁。也就是說剛開始幾個頁依次填入空幀每一步都是F。有些同學算完之後少算了前幾次答案整整差了好幾頁。3.2 經典引用串逐幀推演Belady異常的完整證據我用教科書最經典的引用串來演示1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5先用 FIFO3 個幀。我把每一步都列出來步驟存取頁3幀狀態結果111F221,2F331,2,3F44換出1 → 4,2,3F51換出2 → 4,1,3F62換出3 → 4,1,2F75換出4 → 5,1,2F815,1,2H925,1,2H103換出1 → 3,2,5F114換出2 → 3,4,5F1253,4,5HFIFO 3幀9次缺頁。那 FIFO 用 4 個幀呢前 4 個存取都是F第 5、6 步命中第 7 步開始連續換頁換1、換2、換3、換4、換5、換1一路換到尾。數下來是10次缺頁。注意到問題了嗎幀從3個增加到4個缺頁次數反而從9變成10。這就是課本裡反覆強調的Belady異常幀變多命中率不一定變好。FIFO之所以會這樣是因為它只認“來的先後”完全不看“用的頻率”。一個程序最常訪問的頁可能恰好是最早進入的頁結果一直被FIFO優先掃地出門。我當年第一次看到這個結論時非常震驚後來自己把4幀的推演完整寫了一遍才接受。建議你也親手推一次比背十遍結論都管用。3.3 LRU與OPT的手算差異往前看和往後看LRU最近最少使用和OPT最佳置換看起來很像實際上一個往過去看一個往未來看LRU換掉「過去最久沒有被存取」的頁。OPT換掉「未來最久不會被存取」的頁。OPT 的理想性質是它對任何引用串都能給出理論上的最少缺頁數但因為OS不可能預知未來OPT只能拿來做“理論下界”用來衡量其他演算法的好壞。用同一條引用串算出來的結果演算法3個幀4個幀FIFO910LRU108OPT76這張表資訊量很大。FIFO出現Belady異常LRU在3幀時比FIFO差4幀時又明顯好於FIFOOPT不管幾幀都維持在最低水準。有意思的是LRU在3幀時比FIFO差這說明單一引用串下“區域最優”不代表“全域最優”演算法比較要看統計性質不能拿一條串就下結論。考試如果問“LRU是不是永遠優於FIFO”答案是“統計上LRU更好但不是每一條引用串都更好”。手算OPT時我的技巧是先往後掃一遍給每個頁標出下一次出現的位置選位置最遠的那個換掉。如果某個頁在當前步之後再也不出現那它就是第一優先被換的物件。這比邊算邊猜穩得多。3.4 近似LRU題reference bit怎麼用LRU實現起來需要記錄每個頁的精確使用時間硬體成本太高所以課本會介紹帶參照位reference bit的近似演算法。最常見的是二次機會演算法Second-Chance以及它的環形結構實現——Clock演算法。假如題目給你3個幀每個幀有R位初始值都為1。遇到缺頁時時鐘指針從目前位置開始掃遇到R1的幀把R清零指針移到下一格該頁獲得“第二次機會”遇到R0的幀直接換出指針停在下一格。白話講R1代表“這頁最近被用過先別踢它”給它一輪緩刑如果一輪掃下來大家都用過那就回到第一個R0的頁把它換掉。答這類題時要寫清楚兩件事一是R位週期性清零的機制二是“掃一圈找不到R0就繼續轉圈”的環形行為。考試不會要求你推演很長的串但會考你“哪一頁會被換走”把指針的移動規則掌握好就能拿分。4. 幀分配與抖動答好推導題的三個關鍵4.1 最少幀數的判斷依據頁面置換題做完緊接著就是幀分配問題。第10章課後題很喜歡問“一個程序最少需要多少幀”答案不是1。為什麼因為一條指令可能同時涉及多個頁。比如某些指令的位址展延indirect addressing會連續存取多個實體位址資料在一個頁、指令在另一個頁中間還可能踩到堆疊頁。幀給得太少一條指令還沒執行完就連續缺頁好幾次程序會陷入“剛換進來馬上又被換出去”的狀態。最經典的結論是理論下限取決於單一指令可能跨越的最大頁數。架構不同這個數字不同但你要能解釋“為什麼不是1幀”從指令執行這個角度切入分數就到手了。4.2 全域分配與局部分配選擇題的最後一公里幀分配有兩種策略全域置換缺頁時可以從全系統所有幀中挑一個換掉只要不是保留幀就行。局部置換缺頁時只能在自己的幀集合裡挑。局部置換好處是程序之間“互不搶奪”一個程序爆發缺頁不會拖垮其他程序缺點是就算系統有空閒幀這個程序也分不到瓦時利用率上不去。全域置換則是反過來記憶體利用率高但一個失控的程序可能把別人的頁踢出去造成連鎖缺頁。課後題常問“這兩種哪個更能防止抖動”答案要落到**“局部置換可以作為抖動的緩衝”**因為每個程序的缺頁代價由自己承擔不會因為某個程序異常而拖累整個系統。但要注意局部置換只能緩解局部問題抖動的根源是“總需求超過物理記憶體”這個只能靠全域決策解決。4.3 工作集模型的窗口計算工作集模型是用來量“程序最近到底用了多少頁”的。定義不複雜工作集 W(t, Δ) 在時間區間 [t−Δ1, t] 內被存取過的不同頁面集合Δ是窗口大小t是當前時刻。舉個例子引用串1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6如果Δ10在第10步時刻窗口內是「1, 2, 3, 4, 2, 1, 5, 6, 2, 1」去重後是 {1,2,3,4,5,6}工作集大小 WSS 6。把系統裡所有程序的工作集大小加起來記作 D ΣWSS。如果 D 超過了可用幀總數就說明“系統想同時留下的頁比實際能留下的頁多”抖動幾乎必然發生。這句判據非常重要考工作集的題十有八九要你寫它。課後題有時會問“Δ增大工作集會怎麼變”。答案是一般會變大或持平不會變小——因為窗口變寬覆蓋的過去引用更多集合只會增加不會減少。4.4 抖動題的“現象—原因—對策”三段論抖動thrashing是CH10最愛考的概念題之一。答題別散著寫按三段走現象程序頻繁等待分頁I/OCPU利用率急劇下降但缺頁率卻暴增。原因每個程序分配的幀太少連工作集都裝不下導致每次執行都連續缺頁。對策使用工作集模型預估每個程序的需求讓總分配量不超過物理幀數或者使用頁錯誤頻率PFF機制動態調整幀數——缺頁率高於上限就多給幀低於下限就回收幀。PFF那一段我建議答題時補一筆“目標是讓缺頁率維持在一個可接受區間而不是追求極低或極高。”這句話能讓閱卷人知道你理解了動態調節的本質。5. 概念與應用題的得分要點mmap、核心記憶體分配與局部性5.1 Memory-Mapped Files答出一層“減少拷貝”記憶體映射檔案mmap是第十章後半的高頻概念題。一句話解釋就是把檔案映射到程序的位址空間程式對檔案的存取就變成對記憶體的讀寫。首次存取某個映射頁時發生缺頁作業系統從磁碟把對應檔案塊讀進來之後的讀寫全是記憶體操作。比較題最愛問的是“mmap和普通read/write差在哪”。普通read/write至少經過“磁碟→核心緩衝區→使用者緩衝區”兩次拷貝mmap直接把檔案頁映射進程序位址空間省掉了中間那次使用者態與核心態之間的拷貝。另一個隱藏考點是多個程序映射同一個檔案時可以共享相同的實體頁。這跟共享記憶體的本質是一回事。答題時提到“共享頁面”和“省拷貝”這題的分就穩了。5.2 Buddy System與Slab分配器的對比題內核要給task_struct、inode這類小物件分配記憶體用malloc那套使用者態分配器是不合適的。恐龍書第十章末尾會講兩種核心記憶體分配機制夥伴系統buddy system和slab分配器。對比題直接列表面向Buddy SystemSlab分配器分配單位以2的冪次為單位可分裂/合併針對特定型別物件預先建立快取碎片合併後外部碎片較可控幾乎無碎片速度快速但每次分配顆粒大快建立/銷毀物件開銷小場景實體頁級別的分配核心頻繁建立的小物件Slab的核心思路是“物件快取”某個型別的物件用完之後不真正釋放記憶體而是留在快取裡等下次重用。這對作業系統這種“同型別物件被反覆建立銷毀”的場景特別合適。有不少課後題會反過來問“核心為什麼不直接用使用者態的malloc”。答題時抓住三點核心需要實體連續記憶體、分配時常在中斷上下文執行不能用阻塞呼叫、物件小而大量需要避免記憶體碎片。這三點寫出來就是一份完整答案。5.3 按行按列遍歷的局部性題算一次就不會忘第十章課後題很喜歡出“程式結構影響缺頁數”的題。最經典的案例是二維陣列遍歷。假設陣列是 int a[1024][1024]頁大小4KB一個int佔4位元組一頁正好裝下1024個int。按行遍歷a[i][j]位址連續每1024個元素才跨一頁從空記憶體開始算缺頁次數約為 1024 次。按列遍歷a[j][i]相鄰兩次存取之間隔了整整一頁1024×4 4KB幾乎每個元素都缺頁缺頁次數約為 1024×1024 1,048,576 次。差了整整1000倍。這道題不是考算術是考空間局部性。程式碼的循環順序決定了頁面訪問模式頁面訪問模式決定了缺頁率缺頁率決定了程序跑多快。我第一次做這題時只算出“按列比較慢”沒有把次數量級算出來。後來發現面試官問到程式效能時很喜歡拿這個說事因為它直接指向“你在寫程式時有沒有考慮記憶體佈局”。CH10的題目能串到這種程度已經超出應試範圍了。6. 做完CH10習題後的個人復盤刷完這一章的題我有幾個比較深的體會第一手算置換表一定要“一格一格推”。跳步省下來的時間最後都會變成檢查時的坑。尤其FIFO換誰、LRU換誰、OPT換誰三種演算法換出的頁完全不一樣跳步極容易把自己繞暈。第二缺頁計數規則要統一。初始載入算不算缺頁題目沒明說時一律算。缺頁是“媽想要的頁不在記憶體”空幀也算不在記憶體所以算F。第三CH10的知識畢業後比你想的還常用。資料庫的buffer pool、檔案系統的page cache、JVM的GC分代移動本質上都在跟“怎麼把有限的記憶體分配給大量需要被訪問的頁”打交道。用恐龍書第十章的思維去看這些系統很多設計都豁然開朗。最後分享一個小技巧做完這章題之後可以試著自己出三道題——一道EAT計算、一道置換手算、一道工作集計算。能出得出來說明你是真的把這一章的因果鏈吃透了出不出來回去再把第1節的知識模型過一遍。這比再刷十道題都有效。