常用的外存分配方法有：連續分配、連結分配和索引分配。通常，在一個系統中，僅採用其中的一種方法來為檔案分配外存空間。
基本介紹
- 中文名：檔案空間分配
- 外文名：file space allocation
- 方法：連續分配、連結分配和索引分配
- 定義：檔案分配外存空間
- 系統：計算機
- 套用學科：計算機原理
連續分配,連結分配,隱式連結,顯式連結,索引分配,
連續分配
連續分配(continuous allocation)要求為每一個檔案分配一組相鄰接的盤塊。若物理塊的大小為2 K，則50 K的檔案需要分配25個連續的物理塊，其地址是線性的。例如，第一個盤塊的地址為b，則第二個盤塊的地址為b+l，第三個盤塊的地址為b+2……。通常，它們都位於一條磁軌上，在進行讀/寫時不必移動磁頭。僅當訪問到一條磁軌的最末一個盤塊時，才需要移到下一條磁軌，於是又去連續地讀/寫多個盤塊。為使系統能找到檔案存放的地址，應在目錄項的“檔案物理地址”欄位中，記錄該檔案第一個記錄所在的盤塊號和檔案長度(以盤塊進行計量)。
在採用連續分配方式時，可把邏輯檔案中的記錄順序地存儲到鄰接的各物理盤塊中，這樣形成的物理檔案稱為順序檔案。這種分配方式保證了邏輯檔案中的記錄順序與存儲器中檔案占用盤塊的順序的一致性。如同記憶體的動態分區分配一樣，隨著檔案空間的分配和檔案刪除時的收回，將使磁碟空間被分割成許多小塊，這些較小的連續區已難於用來存儲檔案，稱為外部碎片。同樣，也可利用緊湊的方法，來將盤上所有的檔案緊靠在一起，使所有的碎片拼接成一大片連續的存儲空間。例如，可以運行磁碟整理程式，使之成為一個連續的存儲空間，從而消除了外部碎片。但是將外存上的空閒空間進行一次緊湊所花費的時間，遠比將記憶體緊湊一次所花費的時間多得多。
連續分配的主要優點如下：
(1)順序訪問容易。訪問一個占有連續空間的檔案非常容易。系統可從目錄中找到該順序檔案所在的第一個盤塊號，從此開始順序地、逐個盤塊地往下讀/寫。連續分配也支持直接存取。例如，要訪問一個從b塊開始存放的檔案中的第i個盤塊內容，就可直接訪問b+i號盤塊。
(2)順序訪問速度快。因為由連續分配所裝入的檔案，其所占用的盤塊可能是位於一條或幾條相鄰的磁軌上。這時，磁頭的移動距離最少。因此，用這種方法對檔案訪問，其速度是幾種存儲空間分配方式中最高的一種。
連續分配的主要缺點是：
(1)要求有連續的存儲空間。要為每一個檔案分配一段連續的存儲空間。因此，便會產生出許多外部碎片，嚴重地降低了外存空間的利用率。如果是定期地利用緊湊的方法來消除碎片，則又需花費大量的機器時間。
(2)必須事先知道檔案的長度。要將一個檔案裝入到一個連續的存儲區中，必須事先知道檔案的大小，然後根據其大小，在存儲空間中找出一塊大小足夠的存儲區，將檔案裝入。在有些情況下，知道檔案的大小是件非常容易的事，如拷貝一個已存檔案。但有時卻很難，只能靠估算。如果估計的檔案大小比實際檔案小。就可能因存儲空間不足而中止檔案的拷貝，需再要求用戶重新估算，然後再次執行。這樣，既費時又麻煩。這就使用戶往往將檔案長度估得比實際要大，甚至使所計算的檔案長度比實際長度大得多，這嚴重地浪費了外存空間。對於那些動態增長的檔案，雖然開始時檔案很小，但在運行中逐漸增大。比如，這種增長要經歷幾天、幾個月。在此情況下，即使事先知道檔案的最終大小，採用預分配存儲空間的方法，顯然也將是很低效的，而且它使大量的存儲空間長期地空閒。
連結分配
如同記憶體管理一樣，連續分配所存在的問題在於：必須為一個檔案分配連續的磁碟空間。如果將一個邏輯檔案存儲到外存上時，並不要求為整個檔案分配一塊連續的空間，而是可以將檔案裝到多個離散的盤塊中，這樣就可以消除上述的缺點。在採用連結分配(linked allocation)方式時，可通過在每個盤塊上的連結指針，將同屬於一個檔案的多個離散的盤塊連結成一個鍊表，由此所形成的物理檔案稱為連結檔案。
由於連結分配採取了離散分配方式，從而消除了外部碎片，故可顯著地提高外存空間的利用率，而且也無需事先知道檔案的長度，只是根據檔案的當前需要，為它分配必需的盤塊。當檔案動態增長時，可動態地再為它分配盤塊。此外，對檔案的增、刪、改也十分方便。
連結方式又可分為隱式連結和顯式連結兩種。
隱式連結
在採用隱式連結分配方式時，在檔案目錄的每個目錄項中，都需含有指向連結檔案第一個盤塊和最後一個盤塊的指針。隱式連結分配方式的主要問題是：它只適合於順序訪問，對於隨機訪問是極其低效的。如果要訪問檔案所在的第i個盤塊，就必須先讀出檔案的第一個盤塊，從中得到其第二個盤塊的盤塊號，然後再讀出第二個盤塊，從中得到其第三個盤塊的盤塊號……，就這樣順序地查找直至第i塊。當i=100時，就需啟動磁碟100次去實現讀盤塊的操作，平均每次都要花費幾十毫秒。可見，隨機訪問是非常耗時的。此外，只通過連結指針來將一大批離散的盤塊連結起來，其可靠性較差，因為只要其中的任何一個指針出現問題，都會導致整個鏈的斷開。
為提高檢索速度和減小指針所占用的存儲空間，可以將幾個盤塊組成一個簇(cluster)。比如，一個簇可包含4個盤塊，在進行盤塊分配時是以簇為單位的，像FAT檔案系統盤塊的分配就是以簇為單位的。這樣將會成倍地減小查找指定塊的時間，而且也可減小指針所占用的存儲空間。但缺點是增大了內部碎片，而且這種改進也是非常有限的。
顯式連結
顯示連結是指把連結檔案各物理塊的指針，顯式地存放在記憶體的一張連結表中。該表是整個磁碟僅有的一張表，表的序號是物理盤塊號，從0開始直至N一1，N為盤塊總數。在每個表項中，存放連結指針，即下一個盤塊號。在該表中，凡是屬於某一檔案的第一個盤塊號，或說是每一個鏈的鏈首指針所對應的盤塊號，均作為檔案地址被填入相應檔案的
FCB的“物理地址”欄位中。由於查找記錄的過程是在記憶體中進行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁碟的次數。由於分配給檔案的所有盤塊號都放在該表中，故把該表稱為檔案分配表FAT(File Allocation Table)，MS-DOS及OS/2等作業系統都採用FAT。
連結分配方式雖然解決了連續分配方式所存在的問題，但又出現另外兩個問題：
(1)不能支持高效的直接存取。要對一個較大的檔案進行直接存取，需要首先在FAT中順序地查找許多盤塊號。
(2)FAT需占用較大的記憶體空間。由於一個檔案所占用盤塊的盤塊號是隨機地分布在FAT中的，因而只有將整個FAT調入記憶體，才能保證在FAT中找到一個檔案的盤塊號。當磁碟容量較大時，比如幾百MB以上，FAT可能要占用數百KB以上的記憶體空間。
索引分配
連結分配檔案存在不少缺點。首先，當要求隨機訪問檔案上一個記錄時，需要按鏈指針進行查找，這是十分緩慢的操作。其次，鏈指針要占用盤塊空間的幾個位元組，這使得盤塊的可用空間大小已不再是2的冪。這就使得這些盤塊無法在要求是2的冪的大小的情況下使用。索引分配檔案沒有這些缺點。
在索引分配方法中，系統在檔案分配表(FAT)中為每一個檔案分配一個表目，指出該檔案的索引表所在的物理塊。索引表所在塊並不是物理地屬於檔案分配表中所指出的分給檔案的磁碟塊之一，索引塊是與檔案盤塊分離的(實際上索引表物理塊是由檔案目錄中的檔案屬性指出的)。檔案索引表的每個表目對應分給檔案的每一個物理塊。索引表通常是以檔案的邏輯塊號為索引的，但必要時也可以以記錄中的關鍵字值為索引。
如果對索引表增加一個長度域，用以指出每個索引表目相應分區的起始塊和長度。那么這種方法就支持索引分配和變長連續分配的結合(也可以說支持變長分區索引分配)，這將節省索引表空間，有助於提高效率。
