基本介紹
- 中文名：檔案空間管理模式
- 外文名：File space management mode
- 學科：計算機
- 目的：分配、回收、較好的訪問速度
- 有關術語：檔案系統
- 領域：作業系統
檔案空間管理,常見管理方法,空閒表法,空閒鍊表法,位示圖法,成組連結法,
檔案空間管理
為了方便用戶的使用，對於一些當前需要使用的系統檔案和用戶檔案，都必須放在可隨機存取的磁碟上。在多用戶環境下，若由用戶自己對檔案的存儲進行管理，不僅非常困難，而且也必然是十分低效的。因而，需要由檔案系統對諸多檔案及檔案的存儲空間實施統一的管理。其主要任務是為每個檔案分配必要的外存空間，提高外存的利用率，並能有助於提高檔案系統的存、取速度。為此，系統應設定相應的數據結構，用於記錄檔案存儲空間的使用情況，以供分配存儲空間時參考；系統還應具有對存儲空間進行分配和回收的功能。為了提高存儲空間的利用率，對存儲空間的分配，通常是採用離散分配方式，以減少外存零頭，並以盤塊為基本分配單位。盤塊的大小通常為 1～8 KB。
常見管理方法
空閒表法
空閒表法屬於連續分配方式，它與記憶體的動態分配方式雷同，它為每個檔案分配一塊連續的存儲空間，即系統也為外存上的所有空閒區建立一張空閒表，每個空閒區對應於一個空閒表項，其中包括表項序號、該空閒區的第一個盤塊號、該區的空閒盤塊數等信息。再將所有空閒區按其起始盤塊號遞增的次序排列。
空閒盤區的分配與記憶體的動態分配類似，同樣是採用首次適應算法、循環首次適應算法等。例如，在系統為某新創建的檔案分配空閒盤塊時，先順序地檢索空閒表的各表項，直至找到第一個其大小能滿足要求的空閒區，再將該盤區分配給用戶(進程)，同時修改空閒表。系統在對用戶所釋放的存儲空間進行回收時，也採取類似於記憶體回收的方法，即要考慮回收區是否與空閒表中插入點的前區和後區相鄰接，對相鄰接者應予以合併。
空閒鍊表法
空閒鍊表法是將所有空閒盤區拉成一條空閒鏈。根據構成鏈所用基本元素的不同，可把鍊表分成兩種形式：空閒盤塊鏈和空閒盤區鏈。
(1) 空閒盤塊鏈。這是將磁碟上的所有空閒空間，以盤塊為單位拉成一條鏈。當用戶因創建檔案而請求分配存儲空間時，系統從鏈首開始，依次摘下適當數目的空閒盤塊分配給用戶。當用戶因刪除檔案而釋放存儲空間時，系統將回收的盤塊依次插入空閒盤塊鏈的末尾。這種方法的優點是用於分配和回收一個盤塊的過程非常簡單，但在為一個檔案分配盤塊時，可能要重複操作多次。
(2) 空閒盤區鏈。這是將磁碟上的所有空閒盤區(每個盤區可包含若干個盤塊)拉成一條鏈。在每個盤區上除含有用於指示下一個空閒盤區的指針外，還應有能指明本盤區大小(盤塊數)的信息。分配盤區的方法與記憶體的動態分區分配類似，通常採用首次適應算法。在回收盤區時，同樣也要將回收區與相鄰接的空閒盤區相合併。在採用首次適應算法時，為了提高對空閒盤區的檢索速度，可以採用顯式連結方法，亦即，在記憶體中為空閒盤區建立一張鍊表。
位示圖法
位示圖是利用二進制的一位來表示磁碟中一個盤塊的使用情況。當其值為“0”時，表示對應的盤塊空閒；為“1”時，表示已分配。有的系統把“0”作為盤塊已分配的標誌，把“1”作為空閒標誌。(它們在本質上是相同的，都是用一位的兩種狀態來標誌空閒和已分配兩種情況。)磁碟上的所有盤塊都有一個二進制位與之對應，這樣，由所有盤塊所對應的位構成一個集合，稱為位示圖。通常可用 m × n 個位數來構成位示圖，並使 m × n 等於磁碟的總塊數。
位示圖也可描述為一個二維數組 map：
Var map: array of bit；
成組連結法
空閒表法和空閒鍊表法都不適用於大型檔案系統，因為這會使空閒表或空閒鍊表太長。在 UNIX 系統中採用的是成組連結法，這是將上述兩種方法相結合而形成的一種空閒盤塊管理方法，它兼備了上述兩種方法的優點而克服了兩種方法均有的表太長的缺點。
空閒盤塊的組織
(1) 空閒盤塊號棧用來存放當前可用的一組空閒盤塊的盤塊號(最多含 100 個號)，以及棧中尚有的空閒盤塊號數 N。順便指出，N 還兼作棧頂指針用。例如，當 N=100 時，它指向 S.free(99)。由於棧是臨界資源，每次只允許一個進程去訪問，故系統為棧設定了一把鎖。其中，S.free(0)是棧底，棧滿時的棧頂為S.free(99)。
(2) 檔案區中的所有空閒盤塊被分成若干個組，比如，將每 100 個盤塊作為一組。假定盤上共有 10 000 個盤塊，每塊大小為 1 KB，其中第 201～7999 號盤塊用於存放檔案，即作為檔案區，這樣，該區的最末一組盤塊號應為 7901～7999；次末組為 7801～7900……；第二組的盤塊號為 301～400；第一組為 201～300，如圖1所示。
圖1
(3) 將每一組含有的盤塊總數 N 和該組所有的盤塊號記入其前一組的第一個盤塊的S.free(0)～S.free(99)中。這樣，由各組的第一個盤塊可鏈成一條鏈。
(4) 將第一組的盤塊總數和所有的盤塊號記入空閒盤塊號棧中， 作為當前可供分配的空閒盤塊號。
(5) 最末一組只有 99 個盤塊，其盤塊號分別記入其前一組的 S.free(1) ～S.free(99)中，而在 S.free(0)中則存放“0” ，作為空閒盤塊鏈的結束標誌。(註：最後一組的盤塊數應為 99，不應是 100，因為這是指可供使用的空閒盤塊，其編號應為(1～99)，0 號中放空閒盤塊鏈的結尾標誌。)
