檔案系統實作

可用空間管理(free-space management)

經營一座繁忙的停車場,你必須隨時知道哪些車位是空的。車一進來,你得迅速給它一個空位;車一離開,你得再把那個位子標記為空。檔案系統對磁碟區塊面對相同的問題:隨著檔案被建立、擴大、縮小、刪除,它必須持續追蹤哪些區塊在用、哪些是空閒的,並在需要時發出空閒的區塊。這份記帳工作就是可用空間管理。

保存空閒區塊清單有幾種經典做法。位元向量(位元圖)對每個區塊用一個位元——1 代表空閒、0 代表已用(或相反)——所以找空閒區塊就是掃描某個被設定的位元,而位元圖既精簡又便於搜尋一段連續的空閒區塊。鏈結式空閒清單把每個空閒區塊串成一條鏈,每個空閒區塊指向下一個空閒的,這不浪費額外空間,但要找連續區段就很慢。分組法在第一個空閒區塊裡一次存放許多空閒區塊的位址(這樣一次讀取就得到多個空閒區塊)。計數法存放成對的(第一個空閒區塊, 後面接著幾個連續區塊),當空閒空間以長段出現時很精簡。檔案被刪除時,它的區塊就歸還給目前使用的那種結構。

可用空間管理樸實無華卻不可或缺,並且位於每一次寫入的關鍵路徑上:在你找到並保留一個空閒區塊之前,無法寫入檔案的新區塊。這個結構還必須在當機之間保持一致——如果系統在寫完資料、卻還沒把區塊標記為已用之前死掉,後來的一次配置可能把同一個區塊發給兩個檔案。這正是日誌式與寫入時複製設計所要解決的一致性問題之一。

要建立一個 2 區塊的檔案,檔案系統掃描它的可用空間位元圖,找到第 41 與第 73 個位元被設為空閒,把它們翻成已用,在那裡寫入資料,並把 41 與 73 記進該檔案的索引節點。日後刪除這個檔案,那兩個位元翻回空閒,把區塊歸還給空閒池。

配置與刪除,無非是在檔案系統所維護的可用空間結構裡,把區塊標記為已用或空閒。

可用空間的追蹤必須能撐過當機:若一個區塊被標記為空閒卻仍被某檔案引用(或標記為已用卻沒人用),檔案系統就毀損了——這正是為什麼這份中繼資料在日誌式與寫入時複製的保護清單上排在前面。

又称
free-space listfree-block management空閒空間管理可用區塊管理