空閒

操作系統的磁盤管理為了和內存管理配合，也是將磁盤分割為最小單元進行統一調度，和內存的頁幀概念對應，磁盤管理模塊以磁盤塊作為最小單元管理磁盤（常見的磁盤塊為1KB，對應2個512B扇區，磁盤塊是OS概念，磁盤驅動讀取是以扇區作為最小單元）。

繼承內存頁幀的段頁式管理思想，自然可以想到磁盤管理的空閒空間表法和空閒塊鏈法。前者是指為所有空閒區建立一張空閒表，每個空閒項表示該空閒區的序號、第一個磁盤塊號以及空閒盤塊數目等信息。該表格管理的磁盤空閒區和內存的動態分配類似，以空間大小為評判標準，可採用首次適用匹配法、循環首次適用算法（平均各磁盤塊出場機會），還可以採用合併措施增加某相鄰兩塊空閒區，以提供更大的空閒區。可以預想這張表格將會很大（一般該空閒表都存在外存，需要多次低效率的I/O讀操作分批次讀入內存），並且由於各空閒區的大小不一致引入的變量，這導致在分配過程中需要增加遍歷空閒表項匹配size需求，無疑為磁盤管理增加了不小的設計負擔。 ^[1] 

空間塊鏈表管理的思路，則是在每個空閒塊中留出部分固定位用來指向下一塊空閒磁盤塊。這種思路當然是無需操作增加額外的輔助結構，但是由於若是需要分配多塊空閒空間，則需要多次I/O操作以提取下一塊空閒塊，故而效率其實是很低的，而且是隱式鏈接，一旦磁盤某個空盤塊的nextfree_block指針位置出現故障，很可能出現磁盤無法使用的情況，魯棒性較差。 ^[2] 

其實從以上分析中可以發現，磁盤空閒塊管理需要儘可能地加快磁盤塊索引速度，同時又要儘可能地減少空閒塊管理所需的輔助空間。考慮這些要求，顯然Bitmap是不得不提的方法（位圖算法也是布隆過濾器的基礎）。用每個bit來表示一個盤塊的使用情況（0為空，1為佔用，則對於1KB的盤塊，1G的磁盤，總共有2^20塊，則需要128KB的空間來描述所有磁盤塊）。但是這樣子的話，磁盤直接以磁盤塊與OS內核交互，需要CPU根據Bitmap中bit位置信息換算成盤塊位置，增加了計算負擔，同時粒度過小讓磁盤塊難以成片出現，這會導致一個文件分佈在磁盤各個跨區很大的盤塊中，增加了I/O操作時間（頻繁更換磁頭號，更換磁道位置）。