操作系統(tǒng)對文件存儲空間的四種管理方式，主要有空閑盤塊表法、空閑塊鏈接法、位示圖法和成組鏈接法。
（一）空閑盤塊表法
計算機系統(tǒng)在工作期間頻繁地創(chuàng)建和刪除文件。為了記載磁盤上哪些盤塊當前是空閑的，文件系統(tǒng)需要創(chuàng)建一個空閑盤塊表，如圖5-18所示。
圖5-18 空閑盤塊表
可以看出，所有連續(xù)的空閑盤塊在表中占據一項，其中標出第一個空閑塊號和該項中所包含的空閑塊個數，以及相應的物理塊號。如第1項（序號為1）中，表示空閑塊有4個，首塊是2，即連續(xù)的空閑塊依次是2、 3、4和5。
空閑塊分配：在建新文件時，要為它分配盤空間。為此，系統(tǒng)檢索空閑盤塊表，尋找合適的表項。如果對應空閑區(qū)的大小恰好是所申請的值，就把該項從表中清除；如果該區(qū)大于所需數量，則把分配后剩余的部分記在表項中。
空閑塊回收：當用戶刪除一個文件時，系統(tǒng)回收該文件占用的盤塊，且把相應的空閑塊信息填回空閑盤塊表中。如果釋放的盤區(qū)和原有空閑區(qū)相鄰接，則把它們合并成一個大的空閑區(qū)，記在一個表項中。
優(yōu)點：把若干連續(xù)的空閑塊組合在一個空閑表項中，它們一起被分配或釋放，特別適用于存放連續(xù)文件。
缺點：若存儲空間有大量的小空閑區(qū)時，則空閑表變得很大，使檢索效率降低。同時，如同內存的動態(tài)分區(qū)分配一樣，隨著文件不斷地創(chuàng)建和刪除，磁盤空間將被分割成許多小塊。這些小空閑區(qū)無法用來存放文件，從而產生了外存的外部碎片，造成磁盤空間的浪費。雖然理論上可采用緊縮辦法，使盤上所有文件緊靠在一起，使所有的外存碎片拼接成一大片連續(xù)的磁盤空閑空間，但這樣做要花費大量的時間，代價很大。
（二）空閑塊鏈接法
這種方法與鏈接文件結構有相似之處，只是鏈上的盤塊都是空閑塊而已。如圖5-19所示，所有的空閑盤塊鏈接在一個隊列中，用一個指針（空閑塊鏈頭）指向第1個空閑塊，而各個空閑塊中都含有下一個空閑區(qū)的塊號，最后一塊的指針項記為NULL，表示鏈尾。
圖5-19 空閑塊鏈接
當分配空閑塊時，從鏈頭取下一塊，然后使空閑鏈頭指向下一塊。若需n塊，則重復上述動作n次。當刪除文件時，只需把新釋放的盤塊依次鏈入空閑鏈頭，且使空閑鏈頭指向最后釋放的那一塊。
優(yōu)缺點：這種技術易于實現(xiàn)，只需要用一個內存單元保留鏈頭指針。但其工作效率低，因為在鏈上增加或移走空閑塊時需要很多I/O操作。
（三）位示圖法
它利用一串二進位值反映磁盤空間的分配情況，也稱位向量（Bit Vector）法。每個盤塊都對應一個二進制位。如果盤塊是空閑的，對應位是1；如果盤塊已分出去，則對應位是0（注意，有些系統(tǒng)標志方式與此恰好相反）。例如，設下列盤塊是空閑的：2，3，4，5，8，9，10，11，12，13，17，18，25，26，27，…，則位示圖向量是：
0011110011111100011000000111…
位示圖法（Bit Map）的優(yōu)點：在尋找第1個空閑塊或幾個連續(xù)的空閑塊時相對簡單和有效。實際上，很多計算機都提供位操作指令，可以有效地用于查找。為了找到第1個空閑塊，系統(tǒng)順序檢查位示圖中的每個字，查看其值是否等于0。第1個不是0的位就對應第1個空閑塊。塊號的計算公式如下：
塊號=字長ד0”值字數 首位“1”的偏移
位示圖大小由盤塊總數確定。如果磁盤容量較小，它占用的空間較少，就可以復制到內存中，使得盤塊的分配和釋放都可高速進行。當關機或文件信息轉儲時，位示圖信息需完整地在盤上保留下來。當然，為節(jié)省位示圖所占用的空間，可把盤塊成簇構造，即若干連續(xù)的盤塊（如22=4塊）為一簇，每一簇在位示圖中占一位。這樣，對盤塊就按簇進行分配了。
（四）空閑塊成組鏈接法
用空閑塊鏈接法可以節(jié)省內存，但實現(xiàn)效率低。一種改進辦法是把所有空閑盤塊按固定數量分組，例如每50個空閑塊為一組，組中的第1塊為“組長”塊。第1組的50個空閑塊塊號放在第2組的組長塊中，而第2組的其余49塊是完全空閑的。第2組的50個塊號又放在第3組的組長塊中。依此類推，組與組之間形成鏈接關系。最后一組的塊號（可能不足50塊）通常放在文件系統(tǒng)超級塊中（每個文件系統(tǒng)都有一個超級塊，其中保存對整個文件系統(tǒng)進行控制和管理的重要信息。它存放在盤塊中。當加載文件系統(tǒng)后，通常把它復制到一個內存緩沖區(qū)中）。這樣，平常對盤塊的分配和釋放就在內存超級塊中進行，如圖5-20所示。UNIX系統(tǒng)中就采用這種方法。
圖5-20 空閑塊成組鏈接
空閑塊分配：如圖5-20所示，在超級塊中有一個保存空閑塊號的數組和一個表示其中有效元素個數的整數。這種結構就相當于堆棧結構。所以，我們把該數組稱為空閑塊號棧，相應的整數稱作棧標。當為新建文件分配空閑盤塊時，總是先把棧標的數值減1，如圖5-20中所示情況：40-1=39。以39作為檢索空閑塊號棧的索引，得到盤塊號111，它就是當前分出去的第1個空閑塊。如果需要分配20個盤塊，則上述操作就重復執(zhí)行20次。
如果當前棧標的值是1，需要分配2個空閑盤塊，那么，棧標值減1后，結果為0，此時系統(tǒng)做特殊處理：以0作為索引下標，得到盤塊號150，它是第78組的組長；然后，把150號盤塊中的內容——下一組（即第77組）所有空閑盤塊的數量（50）和各個盤塊的塊號——分別放入超級塊的棧標和空閑塊號棧中，于是空閑塊號棧中就記載了第77組盤塊的情況；最后把150盤塊分配出去。至此，分出去1塊。接著再分配一個盤塊，此時工作簡單多了：50-1=49，以49為索引得到第77組的151號塊。
空閑塊釋放：在圖5-20所示的情況下，若要刪除一個文件，它占用3個盤塊，塊號分別是69，75和87。首先釋放69號塊，其操作過程是：把塊號69放在棧標40所對應的元素中，然后棧標值加1，變?yōu)?1。接著分別釋放75號塊和87號塊。最后，超級塊中棧標的值為43，空閑塊號棧中新加入的3個盤塊出現(xiàn)的次序是69、75、87。
如果棧標的值是50，表示該棧已滿，此時還要釋放一個盤塊89號，則進行特殊處理：先將該棧中的內容（包括棧標值和各空閑塊塊號）寫到需要釋放的新盤塊（即89號）中；將棧標及棧中盤塊號清為0；以棧標值0為索引，將新盤塊號89寫入相應的棧單元中，然后棧標值加1——棧標值變?yōu)?。這樣，盤塊89號就成為新組的組長塊。
圖5-20中第1組只有49塊，它們的塊號存于第二組的組長塊3950號中。該塊中記錄第1組的總塊數為50，而首塊塊號標志為0。這是什么意思？原來這個“0”并不表示物理塊號，而是分配警戒位，作為空閑盤塊鏈的結束標志。如果盤塊分配用到這個標志，說明磁盤上所有空閑塊都用光了，系統(tǒng)要發(fā)告警信號，必須進行特殊處理。
優(yōu)缺點：成組鏈接法是UNIX系統(tǒng)中采用的空閑盤塊管理技術，它兼具空閑盤塊表法和空閑塊鏈接法的優(yōu)點，克服了兩種方法中表（或鏈）太長的缺點。當然，成組鏈接法在管理上要復雜一些，尤其當盤塊分配出現(xiàn)?？?，盤塊釋放遇到棧滿時，要做特殊處理。
版權聲明：本文內容由互聯(lián)網用戶自發(fā)貢獻，該文觀點僅代表作者本人。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。如發(fā)現(xiàn)本站有涉嫌抄襲侵權/違法違規(guī)的內容， 請發(fā)送郵件至 舉報，一經查實，本站將立刻刪除。