空間分配

存儲器是計算機系統的重要組成部分。對於通用計算機而言，存儲層次至少應具有三級：最高層為 CPU 寄存器，中間為主存，最底層是輔存。空間分配是指對主存和輔存空間分配。主存空間分配是指根據一定規則和策略將主存空間分配給進程或程序；外存空間分配則是按照一定策略將將文件存儲到外存中。

直接存儲分配方式要求存儲器的可用空間已經確定，且確保各程序所用的地址之間互不重疊。缺點是用户感到不方便，存儲器的利用率也不高。

靜態存儲分配方式中。在程序被裝入、連接時，才確定它們在主存中的相應位置(物理地址)。系統必須分配其要求的全部存儲空間．否則不能裝入該用户程序。程序將佔據着分配給它的存儲空間直到程序結束。該存儲空間的位置固定不變，也不能動態地申請存儲空間。這種方式無法實現用户對存儲空間的動態擴展，而且也不能有效地實現存儲器資源的共享。

動態存儲分配方式是不一次性將整個程序裝入到主存中。可根據執行的需要，部分地動態裝入。同時，在裝入主存的程序不執行時，系統可以收回該程序所佔據的主存空間。再者，用户程序裝入主存後的位置，在運行期間可根據系統需要而發生改變。此外，用户程序在運行期間也可動態地申請存儲空間以滿足程序需求。由此可見，動態存儲分配方式在存儲空間的分配和釋放上，表現得十分靈活，現代的操作系統常採用這種存儲方式 ^[1]  。

連續分配(Continuous Allocation)要求為每一個文件分配一組相鄰接的盤塊。 一組盤塊的地址定義了磁盤上的一段線性地址。例如，第一個盤塊的地址為 b，則第二個盤塊的地址為b+1，第三個盤塊的地址為 b+2……。通常，它們都位於一條磁道上，在進行讀/寫時，不必移動磁頭，僅當訪問到一條磁道的最後一個盤塊後，才需要移到下一條磁道，於是又去連續地讀/寫多個盤塊。在採用連續分配方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結構稱為順序文件結構，此時的物理文件稱為順序文件。這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件佔用盤塊的順序的一致性。為使系統能找到文件存放的地址，應在目

錄項的“文件物理地址”字段中，記錄該文件第一個記錄所在的盤塊號和文件長度(以盤塊數進行計量)。圖 1示出了連續分配的情況。圖1中假定了記錄與盤塊的大小相同。Count 文件的第一個盤塊號是 0，文件長度為 2，因此是在盤塊號為 0 和 1 的兩盤塊中存放文件 1 的數據。

如同內存的動態分區分配一樣，隨着文件建立時空間的分配和文件刪除時空間的回收，將使磁盤空間被分割成許多小塊，這些較小的連續區已難於用來存儲文件，此即外存的碎片。同樣，我們也可以利用緊湊的方法，將盤上所有的文件緊靠在一起，把所有的碎片拼接成一大片連續的存儲空間。例如，可以運行一個再裝配例程(repack routine)，由它將磁盤A 上的大量文件拷貝到一張軟盤 B 或幾張軟盤(C，D，…)上，並釋放原來的 A 盤，使之成為一個空閒盤。然後再將軟盤 B(C，D，…)上的文件拷回 A 盤上。這種方法能將含有多個文件的盤上的所有空閒盤塊都集中在一起，從而消除了外部碎片。但為了將外存上的空閒空間進行一次緊湊，所花費的時間遠比將內存緊湊一次所花費的時間多得多。

如同內存管理一樣， 連續分配所存在的問題就在於: 必須為一個文件分配連續的磁盤空間。如果在將一個邏輯文件存儲到外存上時，並不要求為整個文件分配一塊連續的空間，而是可以將文件裝到多個離散的盤塊中，這樣也就可以消除上述缺點。在採用鏈接分配(Chained Allocation)方式時，可通過在每個盤塊上的鏈接指針，將同屬於一個文件的多個離散的盤塊鏈接成一個鏈表，把這樣形成的物理文件稱為鏈接文件。

由於鏈接分配是採取離散分配方式，消除了外部碎片，故而顯著地提高了外存空間的利用率；又因為是根據文件的當前需要，為它分配必需的盤塊，當文件動態增長時，可動態地再為它分配盤塊，故而無需事先知道文件的大小。此外，對文件的增、刪、改也十分方便。鏈接方式又可分為隱式鏈接和顯式鏈接兩種形式。

鏈接分配方式雖然解決了連續分配方式所存在的問題，但又出現了下述另外兩個問題：

(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)， 如圖4所示。 在BSD UNIX的索引結點中，共設置了 13 個地址項，它們都把所有的地址項分成兩類，即直接地址和間接地址。

1) 直接地址

為了提高對文件的檢索速度，在索引結點中可設置 10 個直接地址項，即用 iaddr(0)～iaddr(9)來存放直接地址。換言之，在這裏的每項中所存放的是該文件數據所在盤塊的盤塊號。假如每個盤塊的大小為 4 KB，當文件不大於 40 KB 時，便可直接從索引結點中讀出該文件的全部盤塊號。

2) 一次間接地址

對於大、中型文件，只採用直接地址是不現實的。為此，可再利用索引結點中的地址項 iaddr(10)來提供一次

間接地址。這種方式的實質就是一級索引分配方式。圖4中的一次間址塊也就是索引塊，系統將分配給文件的多個盤塊號記入其中。在一次間址塊中可存放 1 K個盤塊號，因而允許文件長達 4 MB。

3) 多次間接地址

當文件長度大於 4 MB + 40 KB 時(一次間址與 10 個直接地址項)， 系統還須採用二次間址分配方式。這時，用地址項 iaddr(11)提供二次間接地址。該方式的實質是兩級索引分配方式。系統此時是在二次間址塊中記入所有一次間址塊的盤號。在採用二次間址方式時，文件最大長度可達 4 GB。同理，地址項 iaddr(12)作為三次間接地址，其所允許的文件最大長度可達 4 TB。