操作系統(tǒng)對文件存儲空間的四種管理方式，主要有空閑盤塊表法、空閑塊鏈接法、位示圖法和成組鏈接法。

（一）空閑盤塊表法

計(jì)算機(jī)系統(tǒng)在工作期間頻繁地創(chuàng)建和刪除文件。為了記載磁盤上哪些盤塊當(dāng)前是空閑的，文件系統(tǒng)需要創(chuàng)建一個空閑盤塊表，如圖5-18所示。

圖5-18 空閑盤塊表

可以看出，所有連續(xù)的空閑盤塊在表中占據(jù)一項(xiàng)，其中標(biāo)出第一個空閑塊號和該項(xiàng)中所包含的空閑塊個數(shù)，以及相應(yīng)的物理塊號。如第1項(xiàng)（序號為1）中，表示空閑塊有4個，首塊是2，即連續(xù)的空閑塊依次是2、 3、4和5。

空閑塊分配：在建新文件時，要為它分配盤空間。為此，系統(tǒng)檢索空閑盤塊表，尋找合適的表項(xiàng)。如果對應(yīng)空閑區(qū)的大小恰好是所申請的值，就把該項(xiàng)從表中清除；如果該區(qū)大于所需數(shù)量，則把分配后剩余的部分記在表項(xiàng)中。

空閑塊回收：當(dāng)用戶刪除一個文件時，系統(tǒng)回收該文件占用的盤塊，且把相應(yīng)的空閑塊信息填回空閑盤塊表中。如果釋放的盤區(qū)和原有空閑區(qū)相鄰接，則把它們合并成一個大的空閑區(qū)，記在一個表項(xiàng)中。

優(yōu)點(diǎn)：把若干連續(xù)的空閑塊組合在一個空閑表項(xiàng)中，它們一起被分配或釋放，特別適用于存放連續(xù)文件。

缺點(diǎn)：若存儲空間有大量的小空閑區(qū)時，則空閑表變得很大，使檢索效率降低。同時，如同內(nèi)存的動態(tài)分區(qū)分配一樣，隨著文件不斷地創(chuàng)建和刪除，磁盤空間將被分割成許多小塊。這些小空閑區(qū)無法用來存放文件，從而產(chǎn)生了外存的外部碎片，造成磁盤空間的浪費(fèi)。雖然理論上可采用緊縮辦法，使盤上所有文件緊靠在一起，使所有的外存碎片拼接成一大片連續(xù)的磁盤空閑空間，但這樣做要花費(fèi)大量的時間，代價很大。

（二）空閑塊鏈接法

這種方法與鏈接文件結(jié)構(gòu)有相似之處，只是鏈上的盤塊都是空閑塊而已。如圖5-19所示，所有的空閑盤塊鏈接在一個隊(duì)列中，用一個指針（空閑塊鏈頭）指向第1個空閑塊，而各個空閑塊中都含有下一個空閑區(qū)的塊號，最后一塊的指針項(xiàng)記為NULL，表示鏈尾。

圖5-19 空閑塊鏈接

當(dāng)分配空閑塊時，從鏈頭取下一塊，然后使空閑鏈頭指向下一塊。若需n塊，則重復(fù)上述動作n次。當(dāng)刪除文件時，只需把新釋放的盤塊依次鏈入空閑鏈頭，且使空閑鏈頭指向最后釋放的那一塊。

優(yōu)缺點(diǎn)：這種技術(shù)易于實(shí)現(xiàn)，只需要用一個內(nèi)存單元保留鏈頭指針。但其工作效率低，因?yàn)樵阪溕显黾踊蛞谱呖臻e塊時需要很多I/O操作。

（三）位示圖法

它利用一串二進(jìn)位值反映磁盤空間的分配情況，也稱位向量（Bit Vector）法。每個盤塊都對應(yīng)一個二進(jìn)制位。如果盤塊是空閑的，對應(yīng)位是1；如果盤塊已分出去，則對應(yīng)位是0（注意，有些系統(tǒng)標(biāo)志方式與此恰好相反）。例如，設(shè)下列盤塊是空閑的：2，3，4，5，8，9，10，11，12，13，17，18，25，26，27，…，則位示圖向量是：

0011110011111100011000000111…

位示圖法（Bit Map）的優(yōu)點(diǎn)：在尋找第1個空閑塊或幾個連續(xù)的空閑塊時相對簡單和有效。實(shí)際上，很多計(jì)算機(jī)都提供位操作指令，可以有效地用于查找。為了找到第1個空閑塊，系統(tǒng)順序檢查位示圖中的每個字，查看其值是否等于0。第1個不是0的位就對應(yīng)第1個空閑塊。塊號的計(jì)算公式如下：

塊號=字長ד0”值字?jǐn)?shù) 首位“1”的偏移

位示圖大小由盤塊總數(shù)確定。如果磁盤容量較小，它占用的空間較少，就可以復(fù)制到內(nèi)存中，使得盤塊的分配和釋放都可高速進(jìn)行。當(dāng)關(guān)機(jī)或文件信息轉(zhuǎn)儲時，位示圖信息需完整地在盤上保留下來。當(dāng)然，為節(jié)省位示圖所占用的空間，可把盤塊成簇構(gòu)造，即若干連續(xù)的盤塊（如22=4塊）為一簇，每一簇在位示圖中占一位。這樣，對盤塊就按簇進(jìn)行分配了。

（四）空閑塊成組鏈接法

用空閑塊鏈接法可以節(jié)省內(nèi)存，但實(shí)現(xiàn)效率低。一種改進(jìn)辦法是把所有空閑盤塊按固定數(shù)量分組，例如每50個空閑塊為一組，組中的第1塊為“組長”塊。第1組的50個空閑塊塊號放在第2組的組長塊中，而第2組的其余49塊是完全空閑的。第2組的50個塊號又放在第3組的組長塊中。依此類推，組與組之間形成鏈接關(guān)系。最后一組的塊號（可能不足50塊）通常放在文件系統(tǒng)超級塊中（每個文件系統(tǒng)都有一個超級塊，其中保存對整個文件系統(tǒng)進(jìn)行控制和管理的重要信息。它存放在盤塊中。當(dāng)加載文件系統(tǒng)后，通常把它復(fù)制到一個內(nèi)存緩沖區(qū)中）。這樣，平常對盤塊的分配和釋放就在內(nèi)存超級塊中進(jìn)行，如圖5-20所示。UNIX系統(tǒng)中就采用這種方法。

圖5-20 空閑塊成組鏈接

空閑塊分配：如圖5-20所示，在超級塊中有一個保存空閑塊號的數(shù)組和一個表示其中有效元素個數(shù)的整數(shù)。這種結(jié)構(gòu)就相當(dāng)于堆棧結(jié)構(gòu)。所以，我們把該數(shù)組稱為空閑塊號棧，相應(yīng)的整數(shù)稱作棧標(biāo)。當(dāng)為新建文件分配空閑盤塊時，總是先把棧標(biāo)的數(shù)值減1，如圖5-20中所示情況：40-1=39。以39作為檢索空閑塊號棧的索引，得到盤塊號111，它就是當(dāng)前分出去的第1個空閑塊。如果需要分配20個盤塊，則上述操作就重復(fù)執(zhí)行20次。

如果當(dāng)前棧標(biāo)的值是1，需要分配2個空閑盤塊，那么，棧標(biāo)值減1后，結(jié)果為0，此時系統(tǒng)做特殊處理：以0作為索引下標(biāo)，得到盤塊號150，它是第78組的組長；然后，把150號盤塊中的內(nèi)容——下一組（即第77組）所有空閑盤塊的數(shù)量（50）和各個盤塊的塊號——分別放入超級塊的棧標(biāo)和空閑塊號棧中，于是空閑塊號棧中就記載了第77組盤塊的情況；最后把150盤塊分配出去。至此，分出去1塊。接著再分配一個盤塊，此時工作簡單多了：50-1=49，以49為索引得到第77組的151號塊。

空閑塊釋放：在圖5-20所示的情況下，若要刪除一個文件，它占用3個盤塊，塊號分別是69，75和87。首先釋放69號塊，其操作過程是：把塊號69放在棧標(biāo)40所對應(yīng)的元素中，然后棧標(biāo)值加1，變?yōu)?1。接著分別釋放75號塊和87號塊。最后，超級塊中棧標(biāo)的值為43，空閑塊號棧中新加入的3個盤塊出現(xiàn)的次序是69、75、87。

如果棧標(biāo)的值是50，表示該棧已滿，此時還要釋放一個盤塊89號，則進(jìn)行特殊處理：先將該棧中的內(nèi)容（包括棧標(biāo)值和各空閑塊塊號）寫到需要釋放的新盤塊（即89號）中；將棧標(biāo)及棧中盤塊號清為0；以棧標(biāo)值0為索引，將新盤塊號89寫入相應(yīng)的棧單元中，然后棧標(biāo)值加1——棧標(biāo)值變?yōu)?。這樣，盤塊89號就成為新組的組長塊。

圖5-20中第1組只有49塊，它們的塊號存于第二組的組長塊3950號中。該塊中記錄第1組的總塊數(shù)為50，而首塊塊號標(biāo)志為0。這是什么意思？原來這個“0”并不表示物理塊號，而是分配警戒位，作為空閑盤塊鏈的結(jié)束標(biāo)志。如果盤塊分配用到這個標(biāo)志，說明磁盤上所有空閑塊都用光了，系統(tǒng)要發(fā)告警信號，必須進(jìn)行特殊處理。

優(yōu)缺點(diǎn)：成組鏈接法是UNIX系統(tǒng)中采用的空閑盤塊管理技術(shù)，它兼具空閑盤塊表法和空閑塊鏈接法的優(yōu)點(diǎn)，克服了兩種方法中表（或鏈）太長的缺點(diǎn)。當(dāng)然，成組鏈接法在管理上要復(fù)雜一些，尤其當(dāng)盤塊分配出現(xiàn)棧空，盤塊釋放遇到棧滿時，要做特殊處理。