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