文件存儲(chǔ)空間分配方法與內(nèi)存分配有許多相同之處，即同樣采用連續(xù)或離散分配方式。文件存儲(chǔ)空間的分配單位是磁盤塊而不是字節(jié)。

1 空閑表法

空閑表法屬于連續(xù)分配方式，它與內(nèi)存的動(dòng)態(tài)分配方式雷同，它為每個(gè)文件分配一塊連續(xù)的存儲(chǔ)空間，即系統(tǒng)也為外存上所有空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對(duì)應(yīng)于一個(gè)空閑表項(xiàng)，其中包括表項(xiàng)序號(hào)、該空閑區(qū)的第一個(gè)盤塊號(hào)、該區(qū)的空閑盤塊號(hào)等信息，再將所有空閑區(qū)按其起始盤塊號(hào)遞增排列。

空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，同樣采用首次適應(yīng)算法，循環(huán)首次適應(yīng)算法等。

系統(tǒng)在對(duì)用戶所釋放的存儲(chǔ)空間進(jìn)行回收時(shí)，也采取類似于內(nèi)存回收的方法，即考慮回收區(qū)是否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，對(duì)相鄰接者應(yīng)該予以合并。

當(dāng)文件較小時(shí)，采用連續(xù)分配方式，當(dāng)文件較大時(shí)，可采用離散分配方式。

2 空閑鏈表法

空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。把鏈表分成兩種形式，空閑盤塊鏈和空閑盤區(qū)鏈。

2.1 空閑盤塊鏈

這是將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈。

當(dāng)用戶因創(chuàng)建文件而請(qǐng)求分配存儲(chǔ)空間時(shí)，系統(tǒng)從鏈?zhǔn)组_始，依次摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶。

當(dāng)刪除文件而釋放空間時(shí)，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾，其優(yōu)點(diǎn)是用于分配和回收一個(gè)盤塊的過程簡(jiǎn)單，但在為文件分配盤塊時(shí)，可能要重復(fù)操作多次。

2.2 空閑盤區(qū)鏈

這是將磁盤上的所有空閑盤區(qū)（每個(gè)盤區(qū)可包含若干個(gè)盤塊）拉成一條鏈，在每個(gè)盤區(qū)上除了含有只是下一個(gè)空閑盤區(qū)的指針外，還應(yīng)有能指明本盤區(qū)大小（盤塊數(shù)）的信息。

盤區(qū)分配與內(nèi)存的動(dòng)態(tài)分配類似，可采用首次適應(yīng)算法，在回收盤區(qū)時(shí)，同樣也要將回收區(qū)和相鄰接的空閑盤區(qū)相合并，在采用首次適應(yīng)算法時(shí)，可以采用顯式鏈接法提高檢索速度，在內(nèi)存中為空閑盤區(qū)建立一張鏈表。

3 位示圖法

利用二進(jìn)制的一位表示磁盤中的一個(gè)盤塊的使用情況，當(dāng)其值為0時(shí)，表示對(duì)應(yīng)的盤塊空閑，為1時(shí)，表示已經(jīng)分配，磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)。由所有盤塊所對(duì)應(yīng)的位構(gòu)成一個(gè)集合，稱為位示圖，通?？捎胢×n個(gè)位數(shù)來構(gòu)成位示圖，并使m×n等于磁盤的總塊數(shù)。

• 順序掃描位示圖，從中找出一個(gè)或一組值為0的二進(jìn)制位。

• 將所找到的一個(gè)或一組二進(jìn)制位轉(zhuǎn)換成與之賭贏的盤塊號(hào)。

• 修改位示圖。

對(duì)于盤塊的回收分為如下兩步：

• 將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。
• 修改位示圖。

優(yōu)點(diǎn)

• 從位示圖中很容易找到一個(gè)或一組相鄰接的空閑盤塊。

• 由于位示圖很小，占用空間少，因而可將其保存在內(nèi)存中，進(jìn)而使在每次進(jìn)行盤區(qū)分配時(shí)，無需首先把盤區(qū)分配表讀入內(nèi)存，節(jié)省磁盤啟動(dòng)時(shí)間。

3 成組鏈接法

空閑表法和空閑鏈表法都不適用于大型系統(tǒng)，因?yàn)檫@會(huì)使空閑表或空閑鏈表很長(zhǎng)，在UNIX采用的成組鏈接法，結(jié)合上述兩種方法。

• 1. 空線盤塊的組織，空閑盤塊棧用來存放當(dāng)前可用的一組空閑盤塊的盤塊號(hào)（最多含100個(gè)號(hào)），以及棧中尚有的空閑盤塊號(hào)數(shù)N，順便指出，N兼做棧頂指針使用，棧是臨界資源，系統(tǒng)設(shè)置一把鎖供進(jìn)程互斥訪問。其中，S.free(0)是棧底，棧滿時(shí)棧頂為S.free(99)。
• 2. 文件區(qū)中的所有空閑盤塊被分成若干個(gè)組，如每100個(gè)盤塊作為一組。
• 3. 將每一組含有的盤塊總數(shù)N和該組所有的盤塊號(hào)記入其前一組的第一個(gè)盤塊S.free(0)~S.free(99)中，這樣，由各組的第一個(gè)盤塊可鏈接成一條鏈。
• 4. 將第一組的盤塊總數(shù)和所有的盤塊號(hào)記入空閑盤塊號(hào)棧中，作為當(dāng)前可供分配的空閑盤塊號(hào)。
• 5. 最末一組只有99個(gè)盤塊，其盤塊號(hào)分別記入其前一組的S.free(1)~S.free(99)中，而在S.free(0)中則存放0，作為空閑盤塊鏈的結(jié)束。

當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí)，須調(diào)用盤塊分配過程來完成：

• 首先檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格。

• 若該盤塊號(hào)已是棧底，即S.free(0)，這是當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào)。將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號(hào)棧的內(nèi) 容，并把原棧底對(duì)應(yīng)的盤塊分配出去(其中的有用數(shù)據(jù)已讀入棧中)。

• 然后，再分配一相應(yīng)的緩沖區(qū)(作為該盤塊的緩沖區(qū))。最后，把棧中的空閑盤塊數(shù)減1并返回。

在系統(tǒng)回收空閑盤塊時(shí)，須調(diào)用盤塊回收過程進(jìn)行回收：

• 它是將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的頂部，并執(zhí)行空閑盤塊數(shù)加1操作。

• 當(dāng)棧中空閑盤塊號(hào)數(shù)目已達(dá)100時(shí)，表示棧已滿，便將現(xiàn)有棧中的100個(gè)盤塊號(hào)，記入新回收的盤塊中，再將其盤塊號(hào)作為新棧底