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

（一）空閑盤塊表法

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

圖5-18 空閑盤塊表

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

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

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

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

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

（二）空閑塊鏈接法

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

圖5-19 空閑塊鏈接

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

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

（三）位示圖法

它利用一串二進(jìn)位值反映磁盤空間的分配情況，也稱位向量（Bit Vector）法。每個(gè)盤塊都對(duì)應(yīng)一個(gè)二進(jìn)制位。如果盤塊是空閑的，對(duì)應(yīng)位是1；如果盤塊已分出去，則對(duì)應(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個(gè)空閑塊或幾個(gè)連續(xù)的空閑塊時(shí)相對(duì)簡(jiǎn)單和有效。實(shí)際上，很多計(jì)算機(jī)都提供位操作指令，可以有效地用于查找。為了找到第1個(gè)空閑塊，系統(tǒng)順序檢查位示圖中的每個(gè)字，查看其值是否等于0。第1個(gè)不是0的位就對(duì)應(yīng)第1個(gè)空閑塊。塊號(hào)的計(jì)算公式如下：

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

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

（四）空閑塊成組鏈接法

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

圖5-20 空閑塊成組鏈接

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

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

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

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

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

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