如果你的磁盤眼看就要滿了系統(tǒng)不會等到寫入失敗才著急。在寫入動作真正開始之前它就必須精確回答一個(gè)問題哪些盤塊還是空閑的如果每次申請空間都要臨時(shí)做一次全盤掃描文件系統(tǒng)根本扛不住幾次大文件寫入。所以文件系統(tǒng)需要維護(hù)一套“空閑空間賬本”這件事在操作系統(tǒng)里就叫文件存儲空間管理。這是OS筆記系列的第37篇標(biāo)題是《文件存儲空間管理二》。上一篇我把空閑表法這類基礎(chǔ)分配模型梳理過一遍這一篇專門拆兩類經(jīng)典方法鏈接法和位示圖法。前者把空閑盤塊或空閑盤區(qū)串成鏈表后者用二進(jìn)制位給每個(gè)盤塊做一個(gè)狀態(tài)標(biāo)記。兩套思路對照著看會比只背結(jié)論有意思得多。適合看這篇的人也很明確正在學(xué)操作系統(tǒng)的學(xué)生準(zhǔn)備復(fù)試或求職面試的候選人以及想弄懂FAT表為什么那樣設(shè)計(jì)、ext系列塊位圖為什么存在的開發(fā)者。只要你理解文件按盤塊讀寫就能跟完全文。1. 為什么文件系統(tǒng)必須有一本“空閑空間賬本”1.1 先分清兩本賬文件盤塊賬與空閑盤塊賬在以盤塊為單位管理磁盤的文件系統(tǒng)里磁盤被切成大小相同的塊。文件在使用時(shí)需要向磁盤申請若干盤塊用完之后再釋放。系統(tǒng)實(shí)際上要操心兩件事一件是“哪些盤塊已經(jīng)被哪個(gè)文件占用了”這是文件分配表、索引結(jié)點(diǎn)、目錄項(xiàng)要回答的問題另一件是“哪些盤塊沒被占用、可以拿去分配”這是文件存儲空間管理要回答的問題。這兩本賬雖然緊密關(guān)聯(lián)但管理策略完全不同。就好比一棟寫字樓的物業(yè)既要登記“哪家公司租了幾號房間”也要維護(hù)“哪些房間目前空著”。前者對應(yīng)具體租戶后者對應(yīng)可出租房源。如果物業(yè)只登記租戶、不掌握空房清單那新客戶來時(shí)只能從一樓開始一間間敲門問效率極低。文件系統(tǒng)也是同理。如果不知道空閑盤塊在哪兒新數(shù)據(jù)寫入時(shí)也只能把整個(gè)磁盤掃一遍這在幾十GB甚至更大的磁盤上幾乎是災(zāi)難。所以操作系統(tǒng)里專門劃分出一塊邏輯負(fù)責(zé)記錄全部物理塊的占用與空閑狀態(tài)并對外提供“分配盤塊”和“回收盤塊”兩個(gè)入口。鏈接法和位示圖法正是實(shí)現(xiàn)這套邏輯的兩條典型路線。1.2 空閑空間管理必須回答的三個(gè)問題把“賬本”再往細(xì)里拆可以發(fā)現(xiàn)任何空閑空間管理方案都繞不開三件事用什么結(jié)構(gòu)記錄空閑狀態(tài)。是用指針把空閑塊連成鏈表還是用一個(gè)二進(jìn)制位對應(yīng)一個(gè)盤塊甚至維護(hù)一張外存上的空閑表。記錄結(jié)構(gòu)決定了后續(xù)所有操作的數(shù)據(jù)基礎(chǔ)。分配時(shí)按什么粒度找。給文件分配一個(gè)塊和給文件分配一段連續(xù)區(qū)間搜索策略完全不同。前者只需要找到一個(gè)空閑塊后者還要判斷一段連續(xù)區(qū)間的長度是否夠用。回收時(shí)如何維護(hù)空閑信息。文件刪除后釋放出來的塊必須重新進(jìn)入空閑集合。如果相鄰的空閑區(qū)能合并得把它們合并成更大的連續(xù)區(qū)否則大文件后續(xù)會很難分配。這三個(gè)問題就是讀這篇筆記的“總綱”。你可以把所有細(xì)節(jié)都往這三個(gè)問題上掛鏈接法在記錄上的答案是“一根指針鏈”在粒度上的答案是“塊”或“區(qū)”在回收上的答案是“摘塊、掛塊、合并相鄰區(qū)”。位示圖法在記錄上的答案是“一個(gè)二進(jìn)制位”在粒度上的答案是“塊”在回收上的答案是“把1改回0”。理解了回答問題的角度差異再去記操作細(xì)節(jié)就不容易混。2. 鏈接法把空閑盤塊串成一條鏈2.1 空閑盤塊鏈的直接形態(tài)指針就藏在盤塊里鏈接法最先想到的版本是空閑盤塊鏈。磁盤上的每個(gè)空閑盤塊在它內(nèi)部留出幾個(gè)字節(jié)作為指針用來指向下一個(gè)空閑盤塊所有空閑盤塊由此串成一條單向鏈表。系統(tǒng)定義一個(gè)鏈?zhǔn)字羔樦赶虻谝粋€(gè)空閑盤塊鏈尾盤塊的指針置為空。申請一塊時(shí)系統(tǒng)讀取鏈?zhǔn)妆P塊取出它的指針把鏈?zhǔn)字羔樃碌较乱粔K然后把取出的這塊交給文件。釋放一塊時(shí)把該盤塊掛到鏈尾——這里比鏈?zhǔn)撞僮髀闊┮稽c(diǎn)因?yàn)橐日业疆?dāng)前鏈尾盤塊再把它的指針指向新釋放的塊最后把新塊的指針置空。這里有個(gè)細(xì)節(jié)很多資料不講如果每次都從鏈?zhǔn)兹　⑼溛矑炷敲疵看位厥斩家獜逆湵眍^一路走到尾代價(jià)是O(n)。為了避免這種遍歷實(shí)際實(shí)現(xiàn)通常有兩種優(yōu)化。一種是額外維護(hù)一個(gè)“鏈尾指針”回收時(shí)直接拿著尾指針去改最后一塊的指針域復(fù)雜度降到O(1)。另一種干脆把回收的塊也掛到鏈?zhǔn)仔纬深愃茥５男袨榉峙浜突厥斩荚阪滎^操作實(shí)現(xiàn)更簡單代價(jià)是盤塊分配的局部性會變差。教材講原理時(shí)往往只說“掛鏈尾”但真正寫模擬器時(shí)建議至少把尾指針也記下來。舉個(gè)具體例子。假設(shè)鏈?zhǔn)字赶?號盤塊9號盤塊內(nèi)部指針存著2727號里又存著5?，F(xiàn)在要分配兩塊先取走9號鏈?zhǔn)赘闹?7再取走27號鏈?zhǔn)赘闹?。兩步分配各讀一次盤、改一次指針。每取一塊盤系統(tǒng)都要先讀出該塊內(nèi)部存儲的指針才能繼續(xù)往下走。這個(gè)額外的磁盤I/O就是盤塊鏈最大的性能代價(jià)。2.2 從“塊鏈”升級到“區(qū)鏈”空閑盤區(qū)鏈如果擔(dān)心把大量空閑塊一個(gè)個(gè)串起來太零碎可以換一個(gè)管理單元按連續(xù)的空閑盤區(qū)來串鏈。所謂空閑盤區(qū)就是一段連續(xù)的空閑區(qū)域。鏈上每個(gè)節(jié)點(diǎn)記錄三樣信息盤區(qū)起始盤塊號、盤區(qū)長度、下一個(gè)盤區(qū)地址。分配時(shí)系統(tǒng)沿這條區(qū)鏈尋找長度夠用的空閑區(qū)可以采用首次適應(yīng)也可以類似內(nèi)存分配那樣用最佳適應(yīng)、最壞適應(yīng)。因?yàn)橐粋€(gè)盤區(qū)往往能連續(xù)分配出多塊效率比一塊一塊摘要好得多同時(shí)也能更好地滿足大文件對連續(xù)空間的需求?；厥諘r(shí)的關(guān)鍵動作是合并。假設(shè)釋放的塊和某個(gè)空閑盤區(qū)相鄰本質(zhì)上它們屬于同一個(gè)連續(xù)空閑區(qū)域只是被占用的文件拆開了必須把兩者合并成一個(gè)節(jié)點(diǎn)否則系統(tǒng)會把連續(xù)空閑區(qū)誤判成碎片。更麻煩的是如果釋放的盤塊正好夾在兩個(gè)空閑區(qū)中間即左右兩邊都是空閑區(qū)那就需要把三個(gè)節(jié)點(diǎn)合并成一個(gè)。初學(xué)者寫模擬器時(shí)最容易漏掉“左右同時(shí)合并”的情況導(dǎo)致空閑區(qū)鏈上出現(xiàn)“中間明明空著卻分成兩段”的異常。2.3 一次首次適應(yīng)分配與回收的完整推演我們從初始狀態(tài)開始設(shè)盤區(qū)鏈上有三個(gè)節(jié)點(diǎn)。注意這里只演示核心邏輯真實(shí)系統(tǒng)里節(jié)點(diǎn)可能還附帶校驗(yàn)信息或其他管理字段。節(jié)點(diǎn)編號起始盤塊號長度A88B338C10021現(xiàn)在進(jìn)程申請6個(gè)空閑盤塊。系統(tǒng)沿鏈查找A區(qū)長度8滿足需求首次適應(yīng)直接命中。從A區(qū)起始盤塊8開始連續(xù)分配6塊也就是8、9、10、11、12、13A區(qū)剩余盤塊14、15兩個(gè)于是把節(jié)點(diǎn)A修改為“起始14、長度2”。分配后鏈表狀態(tài)變成節(jié)點(diǎn)編號起始盤塊號長度A142B338C10021接著某個(gè)文件刪除后釋放了8到10這連續(xù)3塊。系統(tǒng)需要把這3塊重新插入空閑區(qū)鏈。8到10與當(dāng)前A區(qū)14到15之間夾著11到13這三塊仍然被占用所以釋放區(qū)與A區(qū)并不相接于是直接在鏈上插入一個(gè)新節(jié)點(diǎn)。如果鏈按起始塊號遞增排序新節(jié)點(diǎn)“起始8、長度3”應(yīng)放在A區(qū)之前。從這個(gè)推演可以看出兩個(gè)實(shí)用經(jīng)驗(yàn)。第一首次適應(yīng)分配非常簡單但會把大區(qū)切成小塊節(jié)點(diǎn)數(shù)量會逐漸增多。第二空閑盤區(qū)鏈盡量按起始塊號遞增的順序維護(hù)。這樣回收時(shí)查找鄰近空閑區(qū)會方便很多合并邏輯也更好寫否則插入順序和查找順序一亂分配結(jié)果會變得不可控。2.4 鏈接法在什么場景下好用把兩塊鏈接法版本放一起看空閑盤塊鏈勝在結(jié)構(gòu)簡單能把“分配一塊”的操作近似變成取鏈?zhǔn)追浅＿m合基本只做小塊讀寫、不追求連續(xù)分配的系統(tǒng)空閑盤區(qū)鏈則更貼近連續(xù)分配的文件系統(tǒng)一次可以滿足大文件對大段連續(xù)空間的需求。它們的共同弱點(diǎn)是鏈表本身需要維護(hù)且指針訪問會帶來額外的磁盤I/O。我記得大學(xué)課程設(shè)計(jì)里有人用空閑盤區(qū)鏈做一個(gè)微型文件系統(tǒng)最開始沒維護(hù)尾指針釋放盤塊慢得離譜加了尾指針才把速度提上來。這是一個(gè)很典型的教訓(xùn)教科書講原理真正寫代碼時(shí)還得做一點(diǎn)工程權(quán)衡。3. 位示圖法一比特盯一個(gè)盤塊3.1 位示圖的數(shù)據(jù)結(jié)構(gòu)與盤塊號換算公式位示圖法也叫位圖法思路和鏈接法完全相反。它不把空閑塊串成鏈而是在內(nèi)存中開辟一段連續(xù)的二進(jìn)制位序列讓磁盤上每個(gè)物理盤塊都對應(yīng)其中一個(gè)位。通常約定1表示已分配0表示空閑。由于一位只能存0或1全部狀態(tài)信息可以被壓縮得非常小。教學(xué)中習(xí)慣把這段位序列畫成二維數(shù)組也就是“位示圖”。設(shè)位示圖有m行、n列那么第i行第j列的位就代表磁盤上某個(gè)盤塊。最常用的編號約定是盤塊號從1開始行列也從1開始第1行第1列對應(yīng)盤塊1第1行第2列對應(yīng)盤塊2依此類推一行排滿n個(gè)后第2行第1列接盤塊n1。于是有兩個(gè)換算公式最關(guān)鍵盤塊號b (i - 1) × n j反推行列i (b - 1) / n 1j (b - 1) % n 1這里的n是每行位數(shù)可以是純“位”也可以把一個(gè)機(jī)器字當(dāng)成一行這時(shí)n就等于字長比如16、32或64。用字?jǐn)?shù)組實(shí)現(xiàn)時(shí)找某一位其實(shí)就是對字做移位和按位與、按位或操作速度非?？臁？荚嚾绻o出一張具體位示圖通常會說明每行有多少位套公式即可。3.2 分配流程找0、置1、改狀態(tài)位示圖分配盤塊的過程可以拆成三步。從位示圖中掃描找到第一個(gè)值為0的位。根據(jù)該位所在的行號和列號用公式算出對應(yīng)盤塊號b。把這塊盤分配給文件同時(shí)把位示圖中該位置為1。這里要特別強(qiáng)調(diào)語義掃描找到0說明該盤塊空閑位置為1說明“已分配”狀態(tài)被登記。如果忘記置1下一次掃描還會把這個(gè)塊當(dāng)空閑塊分配出去兩個(gè)文件就會重疊寫到同一塊盤上。這是文件系統(tǒng)最嚴(yán)重的故障類型之一——數(shù)據(jù)被覆蓋而系統(tǒng)本身毫無察覺。舉個(gè)例子。磁盤有1000個(gè)盤塊位示圖每行16列?，F(xiàn)在掃描到第32行第4列為0盤塊號就是(32-1)×164等于500也就是第500號盤塊目前空閑。分配之后把第32行第4位置為1即可。反過來驗(yàn)證一下已知盤塊500反推行列(500-1)/161等于32(500-1)%161等于4正好對應(yīng)(32,4)。這個(gè)對稱關(guān)系在動手做題時(shí)非常有用可以快速檢查算得對不對。3.3 回收流程先校驗(yàn)再置0回收盤塊是分配的逆操作。給定要釋放的盤塊號b先反推它對應(yīng)的行號i和列號j然后檢查位示圖中第i行第j列的值。正常狀態(tài)下該位應(yīng)該是1表示這塊正被占用確認(rèn)無誤后把該位置為0讓塊回到空閑集合。這里有一個(gè)不少初學(xué)者遺漏的細(xì)節(jié)回收時(shí)要先判斷該位是不是真的為1。為什么因?yàn)楸P塊回收往往來自用戶刪除文件的操作而刪除邏輯如果沒寫好完全可能對一個(gè)并未真正占用的盤塊發(fā)起釋放。最常見的是刪除接口被調(diào)了兩次第一次已經(jīng)把塊回收并置0第二次又按舊地址來釋放同一塊。所以實(shí)驗(yàn)代碼里至少應(yīng)該加一行校驗(yàn)if (bitmap[i][j] ! 1) 直接視為非法回收拋出異常。在很多課程作業(yè)和面試考察中這一行校驗(yàn)恰恰是隱藏扣分點(diǎn)也是判斷你是不是真懂位示圖回收語義的試金石。3.4 位示圖的體積一張表能管多大的盤位示圖雖然沒有鏈指針那樣的磁盤讀寫開銷但它需要把整張表常駐內(nèi)存。一個(gè)比較直觀的結(jié)果是位示圖大小等于磁盤總盤塊數(shù)除以8單位是字節(jié)。下面這張表列出了不同容量磁盤對應(yīng)位示圖的大小假設(shè)盤塊大小為4KB。磁盤容量盤塊總數(shù)位示圖大小4MB1024128B1GB26214432KB512GB13421772816MB20TB5368709120640MB1GB的磁盤只需要32KB位示圖完全可以常駐內(nèi)存512GB需要16MB服務(wù)器也能接受但到了20TB級別位示圖本身就要吃640MB內(nèi)存這就不容忽視了。正是因?yàn)檫@個(gè)原因現(xiàn)代超大文件系統(tǒng)幾乎不使用單一整圖而是把位示圖按塊組、按區(qū)拆開管理或者干脆采用成組鏈接法、日志結(jié)構(gòu)分配。這個(gè)現(xiàn)象在第4節(jié)里還會提到。4. 鏈接法 vs 位示圖法同一道題的兩套解法4.1 五維對比記錄方式、分配開銷、回收開銷、連續(xù)分配、內(nèi)存依賴把兩種方法放在一張表里逐維度看差異比零散記憶牢固得多。對比維度鏈接法盤塊鏈鏈接法盤區(qū)鏈位示圖法記錄空閑方式每個(gè)空閑塊存指針每個(gè)空閑區(qū)存起始塊號、長度、下一區(qū)指針每個(gè)盤塊對應(yīng)1個(gè)二進(jìn)制位找空閑塊典型成本從鏈?zhǔn)兹∫粔KO(1)但要讀寫鏈?zhǔn)妆P塊沿鏈搜索合適區(qū)平均O(k)k是節(jié)點(diǎn)數(shù)掃描找0位最壞O(盤塊數(shù))可借助位運(yùn)算加速回收成本插入鏈尾需更新尾指針?biāo)诒P塊查找并合并相鄰區(qū)可能遍歷鏈計(jì)算行列并置0O(1)連續(xù)分配保障不易保證可按區(qū)整體分配保障區(qū)內(nèi)連續(xù)可找連續(xù)多個(gè)0位但碎片化后困難內(nèi)存/外存依賴指針存在盤塊內(nèi)鏈管理在外部節(jié)點(diǎn)可在內(nèi)存數(shù)量較少整張位示圖基本常駐內(nèi)存表里最值得關(guān)注的是“位示圖掃描”的成本。磁盤空閑塊很多時(shí)掃描通常很快磁盤接近滿時(shí)找0位可能要掃很遠(yuǎn)。有些實(shí)現(xiàn)會在內(nèi)存里額外保存“上次找到0位的位置”或者維護(hù)一小段空閑塊加速索引這并不違背位示圖思想屬于典型的空間換時(shí)間。從回收角度看位示圖的O(1)置0非常優(yōu)雅這是它最突出的優(yōu)勢。而盤區(qū)鏈的回收要檢查和合并相鄰區(qū)節(jié)點(diǎn)數(shù)量多時(shí)鏈本身的維護(hù)成本會蓋過分配收益。這也是為什么無論教材還是生產(chǎn)系統(tǒng)位示圖都被當(dāng)成一種更“現(xiàn)代”的默認(rèn)方案。4.2 真實(shí)系統(tǒng)里的影子FAT、ext塊位圖、成組鏈接鏈接法和位示圖法絕不是只存在于教材里的概念它們的影子遍布真實(shí)系統(tǒng)。FAT文件系統(tǒng)的目錄結(jié)構(gòu)里文件按簇鏈?zhǔn)酱娣臚AT表本身用表項(xiàng)把每個(gè)文件的簇串成鏈。同時(shí)FAT表項(xiàng)值為0又表示該簇空閑。它沒有單獨(dú)維護(hù)一條空閑鏈表而是用一張表同時(shí)充當(dāng)“文件簇鏈”和“空閑狀態(tài)登記表”把鏈表思想與表結(jié)構(gòu)雜交在一起。所以你會發(fā)現(xiàn)FAT里既有“鏈”的味道也有“表”的味道。Linux的ext2、ext3、ext4系列則直接使用塊位圖block bitmap。每個(gè)塊組里都有一塊區(qū)域?qū)ｉT記錄該組內(nèi)數(shù)據(jù)塊的占用與空閑情況這明顯是位示圖思想的工程化實(shí)現(xiàn)。塊組的設(shè)計(jì)又恰好解決了超大磁盤一整張位示圖太占內(nèi)存的問題把一張大表拆成多個(gè)小組來管理。早期UNIX系統(tǒng)用過的成組鏈接法又是一種折中思路把空閑塊分組管理組與組之間靠組頭塊里的記錄串起來內(nèi)存中只保留當(dāng)前組的空閑塊號列表。它把“全量位圖常駐內(nèi)存”的問題改成了“小批量組調(diào)度”在內(nèi)存有限的年代是非常實(shí)用的設(shè)計(jì)。這塊內(nèi)容正好是“鏈接位示圖”的混合體后續(xù)筆記我會單獨(dú)開一篇細(xì)講。4.3 用Python模擬一萬次隨機(jī)分配與回收紙上談兵容易動手驗(yàn)證一下更有意思。我寫了一個(gè)幾十行的位示圖模擬器用Python管理100000個(gè)邏輯盤塊隨機(jī)分配、隨機(jī)釋放、每次操作后校驗(yàn)一致性。核心邏輯大概長這樣import random class BitmapAllocator: def __init__(self, total_blocks): self.total total_blocks self.bits [0] * total_blocks # 0表示空閑1表示已分配 self.allocated set() # 記錄已分配塊號方便校驗(yàn) def alloc(self): try: idx self.bits.index(0) # 找第一個(gè)空閑塊 except ValueError: return None # 磁盤已滿 self.bits[idx] 1 self.allocated.add(idx) return idx def free(self, idx): if idx not in self.allocated: raise ValueError(非法回收盤塊{}并未處于分配狀態(tài).format(idx)) self.bits[idx] 0 self.allocated.remove(idx) def consistency_check(self): assert sum(self.bits) len(self.allocated) allocator BitmapAllocator(100000) assert allocator.alloc() 0 for _ in range(10000): if random.random() 0.5 or not allocator.allocated: allocator.alloc() else: allocator.free(random.choice(list(allocator.allocated))) allocator.consistency_check()這個(gè)模擬本身不難但寫的過程中我有一處體會很深。Python列表的index(0)查找是線性掃描當(dāng)位示圖接近滿時(shí)一次分配可能要掃過數(shù)萬個(gè)元素。真實(shí)操作系統(tǒng)里位示圖掃描也是類似線性邏輯只不過引擎會用位運(yùn)算一次性比較多個(gè)位性能仍然可接受。但如果每次都從表頭開始掃磁盤長期處于高占用率時(shí)分配延遲的抖動就會變得很明顯。模擬也驗(yàn)證了一個(gè)現(xiàn)象隨機(jī)釋放會讓位示圖變得“斑駁”連續(xù)0越來越少單塊空洞越來越多。這時(shí)要為大文件一次性分配很多連續(xù)塊單純靠線性找0就會非常吃力往往需要額外掃描最長的連續(xù)0串。這種碎片化問題在真實(shí)文件系統(tǒng)中長期存在ext系列的分組管理、塊預(yù)分配策略本質(zhì)都是在緩解它。5. 學(xué)這套內(nèi)容最容易踩的幾個(gè)坑5.1 位示圖公式的下標(biāo)起點(diǎn)混用復(fù)習(xí)和做課后題時(shí)最常翻車的點(diǎn)就是下標(biāo)起點(diǎn)。大部分教材約定盤塊號從1開始、行號和列號也從1開始但有些題目為出題方便會改成從0開始。兩種約定下公式完全不同。從1開始b (i-1)×n ji (b-1)/n 1j (b-1)%n 1。從0開始b i×n ji b/nj b%n。同一個(gè)“第3行第5列”在兩種約定下算出的盤塊號會差1。我的經(jīng)驗(yàn)是拿到題目先看題干有沒有“盤塊號從0開始”的字樣沒有就默認(rèn)教材的1起始約定。算出結(jié)果后再用一個(gè)小例子驗(yàn)證比如把(1,1)和(1,2)往回代看是否得到盤塊1和盤塊2。做過這一步絕大多數(shù)低級錯(cuò)誤都能被攔住。5.2 盤區(qū)鏈回收時(shí)漏掉“左右雙合并”前面提到的左右雙合并必須單獨(dú)拿出來再說一遍。盤區(qū)鏈回收時(shí)如果釋放區(qū)間的左邊和右邊都是空閑區(qū)正確做法是先把左區(qū)、右區(qū)、釋放區(qū)三段合成一個(gè)大空閑區(qū)再修改鏈上節(jié)點(diǎn)。如果只合并一邊空閑區(qū)鏈上的總空閑空間沒有變但連續(xù)區(qū)被錯(cuò)誤拆成兩份后續(xù)要分配一個(gè)正好跨越兩個(gè)區(qū)的大文件就永遠(yuǎn)不可能成功。每到階段考這幾乎是必考大題而且每年都有人在雙合并這一步丟分。做題時(shí)建議把“檢查左鄰、檢查右鄰、分別合并”寫成三個(gè)顯式步驟而不是憑感覺一次性改指針。三步分開寫即使最后一步出錯(cuò)也能很快定位問題。5.3 判斷題里的高頻陷阱有幾類判斷題值得留個(gè)心眼。一種問法是“采用鏈接法分配和回收空閑盤塊時(shí)不需要訪問磁盤”這明顯不對。塊鏈指針存在盤塊內(nèi)部取塊和掛塊都要讀寫磁盤。另一種問法是“位示圖適合管理太大的磁盤”在單一整圖的前提下也不對因?yàn)楸眢w占內(nèi)存過大才催生了成組鏈接法。做題時(shí)只要抓住一個(gè)原則來推這個(gè)方法到底是怎么記錄空閑信息的分配和回收分別要動什么數(shù)據(jù)結(jié)構(gòu)。抓住這一點(diǎn)比死記結(jié)論可靠得多。同樣一道題換個(gè)說法內(nèi)核不變答案也應(yīng)該能推出來而不是憑印象猜。6. 給正在復(fù)習(xí)這部分內(nèi)容的你一個(gè)實(shí)操建議最后說點(diǎn)實(shí)在的。我復(fù)習(xí)這節(jié)內(nèi)容時(shí)發(fā)現(xiàn)光看不練是真的不行。我的順序是先在紙上畫出一條空閑盤區(qū)鏈假設(shè)只有8個(gè)盤塊手動完成三步分配、三步回收把每個(gè)指針的變化都寫出來確認(rèn)沒有漏掉相鄰合并再用Python把位示圖模擬器跑通最后回到教材習(xí)題把位示圖公式題做三遍。這個(gè)過程聽起來簡單但確實(shí)能把兩套思想變成肌肉記憶。如果你也要應(yīng)對操作系統(tǒng)考試或面試你可以用一個(gè)今天就能做的5分鐘小練習(xí)拿出紙筆畫一個(gè)4行4列的位示圖隨機(jī)填一些0和1。第一題第3行第2列對應(yīng)的盤塊號是多少第二題盤塊11對應(yīng)位示圖的哪一行哪一列第三題分配一個(gè)盤塊再回收它把位示圖的前后變化都寫出來。做完這三題再去看真題里的存儲空間管理大題你會發(fā)現(xiàn)它們本質(zhì)上都在考同一件事空閑信息怎么記錄、分配怎么找、回收怎么更新。另外一個(gè)小建議別把鏈接法想成“過時(shí)的”把位示圖法想成“先進(jìn)的”。兩者管理粒度不同、開銷模型不同應(yīng)用場景也完全不同。FAT用鏈表思想管理文件簇ext系列用位圖管理塊組早期UNIX用成組鏈接法應(yīng)對大磁盤這些方案在各自的時(shí)代和約束下都是合理的解。理解它們背后的取舍邏輯比記住公式本身更有價(jià)值。