簡介
磁碟檔案管理程式即對磁碟上檔案進行管理的程式。磁碟屬於外存，磁碟檔案管理程式也可以說是對外存空間上的檔案進行管理的程式。
由於 磁碟具有可直接訪問的特性，故當利用磁碟來存放檔案時，具有很大的靈活性。在為檔案分配外存空間時所要考慮的主要問題是：怎樣才能有效地利用外存空間和如何提高對檔案的訪問速度，這也是磁碟檔案管理程式要實現的目標。磁碟檔案管理程式的實現一般與外存分配方法有關。目前，常用的外存分配方法有連續分配、連結分配和索引分配三種。
連續分配
連續分配方式
磁碟檔案管理程式連續分配(Continuous Allocation)要求為每一個檔案分配一組相鄰接的盤塊。 一組盤塊的地址定義了磁碟上的一段線性地址。例如，第一個盤塊的地址為 b，則第二個盤塊的地址為b+1，第三個盤塊的地址為 b+2……。通常，它們都位於一條磁軌上，在進行讀/寫時，不必移動磁頭，僅當訪問到一條磁軌的最後一個盤塊後，才需要移到下一條磁軌，於是又去連續地讀/寫多個盤塊。在採用連續分配方式時，可把邏輯檔案中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的檔案結構稱為順序檔案結構，此時的物理檔案稱為順序檔案。這種分配方式保證了邏輯檔案中的記錄順序與存儲器中檔案占用盤塊的順序的一致性。為使系統能找到檔案存放的地址，應在目錄項的“檔案物理地址”欄位中，記錄該檔案第一個記錄所在的盤塊號和檔案長度(以盤塊數進行計量)。圖 1示出了連續分配的情況。圖中假定了記錄與盤塊的大小相同。Count 檔案的第一個盤塊號是 0，檔案長度為 2，因此是在盤塊號為 0 和 1 的兩盤塊中存放檔案 1 的數據。
如同記憶體的動態分區分配一樣，隨著檔案建立時空間的分配和檔案刪除時空間的回收，將使磁碟空間被分割成許多小塊，這些較小的連續區已難於用來存儲檔案，此即外存的碎片。同樣，我們也可以利用緊湊的方法，將盤上所有的檔案緊靠在一起，把所有的碎片拼接成一大片連續的存儲空間。例如，可以運行一個再裝配例程(repack routine)，由它將磁碟A 上的大量檔案拷貝到一張軟碟 B 或幾張軟碟(C，D，…)上，並釋放原來的 A 盤，使之成為一個空閒盤。然後再將軟碟 B(C，D，…)上的檔案拷回 A 盤上。這種方法能將含有多個檔案的盤上的所有空閒盤塊都集中在一起，從而消除了外部碎片。但為了將外存上的空閒空間進行一次緊湊，所花費的時間遠比將記憶體緊湊一次所花費的時間多得多。
連續分配的主要優缺點
連續分配的主要優點如下：
(1) 順序訪問容易。訪問一個占有連續空間的檔案非常容易。系統可從目錄中找到該順序檔案所在的第一個盤塊號，從此開始順序地、逐個盤塊地往下讀/寫。連續分配也支持直接存取。例如，要訪問一個從 b 塊開始存放的檔案中的第 i 個盤塊的內容，就可直接訪問b+i 號盤塊。
(2) 順序訪問速度快。因為由連續分配所裝入的檔案，其所占用的盤塊可能是位於一條或幾條相鄰的磁軌上，這時，磁頭的移動距離最少，因此，這種對檔案訪問的速度是幾種存儲空間分配方式中最高的一種。
連續分配的主要缺點如下：
(1) 要求有連續的存儲空間。要為每一個檔案分配一段連續的存儲空間，這樣，便會產生出許多外部碎片，嚴重地降低了外存空間的利用率。如果是定期地利用緊湊方法來消除碎片，則又需花費大量的機器時間。
(2) 必須事先知道檔案的長度。要將一個檔案裝入一個連續的存儲區中，必須事先知道檔案的大小，然後根據其大小，在存儲空間中找出一塊其大小足夠的存儲區，將檔案裝入。在有些情況下，知道檔案的大小是件非常容易的事，如可拷貝一個已存檔案。但有時卻很難，在此情況下，只能靠估算。如果估計的檔案大小比實際檔案小，就可能因存儲空間不足而中止檔案的拷貝，須再要求用戶重新估算，然後再次執行。這樣，顯然既費時又麻煩。這就促使用戶往往將檔案長度估得比實際的大，甚至使所計算的檔案長度比實際長度大得多，顯然，這會嚴重地浪費外存空間。對於那些動態增長的檔案，由於開始時檔案很小，在運行中逐漸增大，比如，這種增長要經歷幾天、幾個月。在此情況下，即使事先知道檔案的最終大小，在採用預分配存儲空間的方法時，顯然也將是很低效的，即它使大量的存儲空間長期地空閒著。
連結分配
如同記憶體管理一樣， 連續分配所存在的問題就在於: 必須為一個檔案分配連續的磁碟空間。如果在將一個邏輯檔案存儲到外存上時，並不要求為整個檔案分配一塊連續的空間，而是可以將檔案裝到多個離散的盤塊中，這樣也就可以消除上述缺點。在採用連結分配(Chained Allocation)方式時，可通過在每個盤塊上的連結指針，將同屬於一個檔案的多個離散的盤塊連結成一個鍊表，把這樣形成的物理檔案稱為連結檔案。
由於連結分配是採取離散分配方式，消除了外部碎片，故而顯著地提高了外存空間的利用率；又因為是根據檔案的當前需要，為它分配必需的盤塊，當檔案動態增長時，可動態地再為它分配盤塊，故而無需事先知道檔案的大小。此外，對檔案的增、刪、改也十分方便。連結方式又可分為隱式連結和顯式連結兩種形式。
隱式連結
磁碟檔案管理程式在採用隱式連結分配方式時，在檔案目錄的每個目錄項中，都須含有指向連結檔案第一個盤塊和最後一個盤塊的指針。圖 2中示出了一個占用 5 個盤塊的連結式檔案。在相應的目錄項中，指示了其第一個盤塊號是 9，最後一個盤塊號是 25。而在每個盤塊中都含一個指向下一個盤塊的指針，如在第一個盤塊 9 中設定了第二個盤塊的盤塊號是 16；在16 號盤塊中又設定了第三個盤塊的盤塊號 1。如果指針占用 4 個位元組，對於盤塊大小為 512位元組的磁碟，則每個盤塊中只有 508 個位元組可供用戶使用。
隱式連結分配方式的主要問題在於：它只適合於順序訪問，它對隨機訪問是極其低效的。如果要訪問檔案所在的第 i 個盤塊，則必須先讀出檔案的第一個盤塊……，就這樣順序地查找直至第 i 塊。當 i=100 時，須啟動 100 次磁碟去實現讀盤塊的操作，平均每次都要花費幾十毫秒。可見，隨機訪問的速度相當低。此外，只通過連結指針來將一大批離散的盤塊連結起來，其可靠性較差，因為只要其中的任何一個指針出現問題，都會導致整個鏈的斷開。
為了提高檢索速度和減小指針所占用的存儲空間， 可以將幾個盤塊組成一個簇(cluster)。比如，一個簇可包含 4 個盤塊，在進行盤塊分配時，是以簇為單位進行的。在連結檔案中的每個元素也是以簇為單位的。這樣將會成倍地減小查找指定塊的時間，而且也可減小指針所占用的存儲空間，但卻增大了內部碎片，而且這種改進也是非常有限的。
顯式連結
磁碟檔案管理程式這是指把用於連結檔案各物理塊的指針，顯式地存放在記憶體的一張連結表中。該表在整個磁碟僅設定一張，如圖 3所示。表的序號是物理盤塊號，從 0 開始，直至 N-1；N 為盤塊總數。在每個表項中存放連結指針，即下一個盤塊號。在該表中，凡是屬於某一檔案的第一個盤塊號，或者說是每一條鏈的鏈首指針所對應的盤塊號，均作為檔案地址被填入相應檔案的 FCB 的“物理地址”欄位中。由於查找記錄的過程是在記憶體中進行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁碟的次數。由於分配給檔案的所有盤塊號都放在該表中，故把該表稱為檔案分配表 FAT(File Allocation Table)。
索引分配
單級索引分配
連結分配方式雖然解決了連續分配方式所存在的問題，但又出現了下述另外兩個問題：
(1) 不能支持高效的直接存取。 要對一個較大的檔案進行直接存取， 須首先在 FAT 中順序地查找許多盤塊號。
(2) FAT 需占用較大的記憶體空間。由於一個檔案所占用盤塊的盤塊號是隨機地分布在FAT 中的， 因而只有將整個 FAT 調入記憶體， 才能保證在 FAT 中找到一個檔案的所有盤塊號。當磁碟容量較大時，FAT 可能要占用數兆位元組以上的記憶體空間，這是令人難以接受的。
磁碟檔案管理程式事實上，在打開某個檔案時，只需把該檔案占用的盤塊的編號調入記憶體即可，完全沒有必要將整個 FAT 調入記憶體。為此，應將每個檔案所對應的盤塊號集中地放在一起。索引分配方法就是基於這種想法所形成的一種分配方法。它為每個檔案分配一個索引塊(表)，再把分配給該檔案的所有盤塊號都記錄在該索引塊中，因而該索引塊就是一個含有許多盤塊號的數組。在建立一個檔案時，只需在為之建立的目錄項中填上指向該索引塊的指針。圖3示出了磁碟空間的索引分配圖。
索引分配方式支持直接訪問。當要讀檔案的第 i 個盤塊時，可以方便地直接從索引塊中找到第 i 個盤塊的盤塊號；此外，索引分配方式也不會產生外部碎片。當檔案較大時，索引分配方式無疑要優於連結分配方式。
索引分配方式的主要問題是：可能要花費較多的外存空間。每當建立一個檔案時，便須為之分配一個索引塊，將分配給該檔案的所有盤塊號記錄於其中。但在一般情況下，總是中、小型檔案居多，甚至有不少檔案只需 1～2 個盤塊，這時如果採用連結分配方式，只需設定 1～2 個指針。如果採用索引分配方式，則同樣仍須為之分配一索引塊。通常是採用一個專門的盤塊作為索引塊，其中可存放成百個、甚至上千個盤塊號。可見，對於小檔案採用索引分配方式時，其索引塊的利用率將是極低的。
多級索引分配
當 OS 為一個大檔案分配磁碟空間時， 如果所分配出去的盤塊的盤塊號已經裝滿一個索引塊時， OS 便為該檔案分配另一個索引塊， 用於將以後繼續為之分配的盤塊號記錄於其中。依此類推，再通過鏈指針將各索引塊按序連結起來。顯然，當檔案太大，其索引塊太多時，這種方法是低效的。此時，應為這些索引塊再建立一級索引，稱為第一級索引，即系統再分配一個索引塊，作為第一級索引的索引塊，將第一塊、第二塊……等索引塊的盤塊號填入到此索引表中，這樣便形成了兩級索引分配方式。如果檔案非常大時，還可用三級、四級索引分配方式。
混合索引分配方式
所謂混合索引分配方式，是指將多種索引分配方式相結合而形成的一種分配方式。例如，系統既採用了直接地址，又採用了一級索引分配方式，或兩級索引分配方式，甚至還採用了三級索引分配方式。 這種混合索引分配方式已在 UNIX 系統中採用。 在 UNIX SystemⅤ的索引結點中， 共設定了13個地址項， 即iaddr(0)～iaddr(12)， 如圖所示。 在BSD UNIX的索引結點中，共設定了 13 個地址項，它們都把所有的地址項分成兩類，即直接地址和間接地址。
1) 直接地址
為了提高對檔案的檢索速度，在索引結點中可設定 10 個直接地址項，即用 iaddr(0)～iaddr(9)來存放直接地址。換言之，在這裡的每項中所存放的是該檔案數據所在盤塊的盤塊號。假如每個盤塊的大小為 4 KB，當檔案不大於 40 KB 時，便可直接從索引結點中讀出該檔案的全部盤塊號。
2) 一次間接地址
磁碟檔案管理程式對於大、中型檔案，只採用直接地址是不現實的。為此，可再利用索引結點中的地址項 iaddr(10)來提供一次間接地址。這種方式的實質就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統將分配給檔案的多個盤塊號記入其中。在一次間址塊中可存放 1 K個盤塊號，因而允許檔案長達 4 MB。
3) 多次間接地址
當檔案長度大於 4 MB + 40 KB 時(一次間址與 10 個直接地址項)， 系統還須採用二次間址分配方式。這時，用地址項 iaddr(11)提供二次間接地址。該方式的實質是兩級索引分配方式。系統此時是在二次間址塊中記入所有一次間址塊的盤號。在採用二次間址方式時，檔案最大長度可達 4 GB。同理，地址項 iaddr(12)作為三次間接地址，其所允許的檔案最大長度可達 4 TB。
