檔案擴充空間

檔案擴充空間

計算機檔案是存儲在某種長期儲存設備或臨時存儲設備中的一段數據流,並且歸屬於計算機檔案系統管理之下。檔案擴充空間是指一個檔案動態擴充已經超出了系統分配給它的空間,需要系統再給檔案分配存儲空間。檔案擴充空間主要原因是檔案大小大於系統分配空間大小。

簡介

檔案是由大量性質相同的記錄組成的集合 ,其中每一個記錄由一個或多個數據項組成,數據項是數據的基本單位(數據項又稱為域),在同一個記錄中各個數據項可取不同的數據類型。檔案擴充空間是指一個檔案動態擴充已經超出了系統分配給它的空間,需要系統再給檔案分配存儲空間。檔案擴充空間的原因有很多,例如數據動態增長;檔案合併等。檔案擴充空間一般與外存分配方式和檔案存儲空間有關。

外存分配方式

由於磁碟具有可直接訪問的特性,故當利用磁碟來存放檔案時,具有很大的靈活性。在為檔案分配外存空間時所要考慮的主要問題是:怎樣才能有效地利用外存空間和如何提高對檔案的訪問速度。目前,常用的外存分配方法有連續分配、連結分配和索引分配三種。通常,在一個系統中,僅採用其中的一種方法來為檔案分配外存空間 。

連續分配

連續分配方法要求每個檔案在磁碟上占有一組連續的塊。磁碟地址定義了磁碟上的一個線性排序。這種排序使作業訪問磁碟時需要的尋道數和尋道時間最小。

檔案的連續分配可以用第一塊的磁碟地址和連續塊的數量來定義。如果檔案有n塊長並從位置b開始,那么該檔案將占有b,b+1,b+2……b+n-1.一個檔案的目錄條目包括開始塊的地址和該檔案所分配區域的長度。

連續分配支持順序訪問和直接訪問。其優點是實現簡單、存取速度快。缺點在於,檔案長度不宜動態增加,因為一個檔案末尾後的盤塊可能已經分配給其他檔案,一旦需要增加,就需要大量移動盤塊。此外,反覆增刪檔案後會產生外部碎片(與記憶體管理分配方式中的碎片相似),並且很難確定一個檔案需要的空間大小,因而只適用於長度固定的檔案。

連結分配

連結分配解決了連續分配的碎片和檔案大小問題。採用連結分配,每個檔案對應一個磁碟塊的鍊表;磁碟塊分布在磁碟的任何地方,除最後一個盤塊外,每個盤塊都有指向下一個盤塊的指針,這些指針對用戶是透明的。目錄包括檔案第一塊的指針和最後一塊的指針。

創建新檔案時,目錄中增加一個新條目。連結分配中每個目錄項都有一個指向檔案首塊的指針。該指針初始化為null以表示空檔案,大小欄位為0.寫檔案會通過空閒空間管理系統找到空閒塊,將該塊連結到檔案的尾部,以便於寫入。讀檔案則通過塊到塊的指針讀塊。

連結分配方式沒有外部碎片,空閒空間列表上的任何塊都可以用來滿足請求。創建檔案時並不需要說明檔案大小。只要有空閒塊檔案就可以增大,也無需合併磁碟空間。

連結分配的缺點在於無法直接訪問盤塊,只能通過指針順序訪問檔案,以及盤塊指針消耗了一定的存儲空間。連結分配方式的穩定性也是一個問題。系統在運行過程中由於軟體或者硬體錯誤導致鍊表中的指針丟失或損壞,會導致檔案數據的丟失。

索引分配

連線分配解決了連續分配的外部碎片和檔案大小管理的問題。但是,連結分配不能有效支持直接訪問(FAT除外)。索引分配解決了這個問題,他把每個檔案的所有的盤塊號都集中在一起構成索引塊。

每個檔案都有其索引塊,這是一個磁碟塊地址的數組。索引塊的第i個條目指向檔案的第i個塊。目錄條目包括索引塊的地址。要讀第i塊,通過索引塊的第i個條目的指針來查找和讀入所需的塊。

創建檔案時,索引塊的所有指針都設為空。當首次寫入第i塊時,先從空閒空間中取得一個塊,再將其地址寫到索引塊的第i個條目。索引分配支持直接訪問,且沒有外部碎片問題。其缺點是由於索引塊的分配,增加了系統存儲空間的開銷。索引塊的大小是一個重要的問題,每個檔案必須有一個索引塊,因此索引塊應儘可能小,但索引塊太小就無法支持大檔案。可以採用以下機制來處理這個問題。

連結方案:一個索引塊通常為一個磁碟塊,因此,他本身能直接讀寫。為了處理大檔案,可以將多個索引塊連結起來。

多層索引:多層索引使第一層索引塊指向第二層的索引塊,第二層的索引塊再指向檔案塊。這種方法根據最大檔案的大小的要求,可以繼續到第三層或第四層。例如,4096B的塊,能在索引塊中存入1024個4B的指針。兩層索引允許1048576個數據塊,即允許最大檔案為4G。

混合索引:將多種索引分配方式相結合的分配方式。例如,系統即採用直接地址,又採用單級索引分配方式或兩級索引分配方式。

此外,訪問檔案需要兩次訪問外存——手想要讀取索引塊的內容,然後在訪問具體的磁碟塊,因而降低了檔案的存取速度。為了解決這一問題,通常將檔案的索引塊讀入記憶體的緩衝區,以加快檔案的訪問速度。

檔案存儲空間管理方法

空閒表法

空閒表法屬於連續分配方式,它與記憶體的動態分配方式雷同,它為每個檔案分配一塊連續的存儲空間,即系統也為外存上的所有空閒區建立一張空閒表,每個空閒區對應於一個空閒表項,其中包括表項序號、該空閒區的第一個盤塊號、該區的空閒盤塊數等信息。再將所有空閒區按其起始盤塊號遞增的次序排列。

空閒盤區的分配與記憶體的動態分配類似,同樣是採用首次適應算法、循環首次適應算法等。例如,在系統為某新創建的檔案分配空閒盤塊時,先順序地檢索空閒表的各表項,直至找到第一個其大小能滿足要求的空閒區,再將該盤區分配給用戶(進程),同時修改空閒表。系統在對用戶所釋放的存儲空間進行回收時,也採取類似於記憶體回收的方法,即要考慮回收區是否與空閒表中插入點的前區和後區相鄰接,對相鄰接者應予以合併。[1]

空閒鍊表法

空閒鍊表法是將所有空閒盤區拉成一條空閒鏈。根據構成鏈所用基本元素的不同,可把鍊表分成兩種形式:空閒盤塊鏈和空閒盤區鏈。

(1)空閒盤塊鏈。這是將磁碟上的所有空閒空間,以盤塊為單位拉成一條鏈。當用戶因創建檔案而請求分配存儲空間時,系統從鏈首開始,依次摘下適當數目的空閒盤塊分配給用戶。當用戶因刪除檔案而釋放存儲空間時,系統將回收的盤塊依次插入空閒盤塊鏈的末尾。這種方法的優點是用於分配和回收一個盤塊的過程非常簡單,但在為一個檔案分配盤塊時,可能要重複操作多次。

(2)空閒盤區鏈。這是將磁碟上的所有空閒盤區(每個盤區可包含若干個盤塊)拉成一條鏈。在每個盤區上除含有用於指示下一個空閒盤區的指針外,還應有能指明本盤區大小(盤塊數)的信息。分配盤區的方法與記憶體的動態分區分配類似,通常採用首次適應算法。在回收盤區時,同樣也要將回收區與相鄰接的空閒盤區相合併。在採用首次適應算法時,為了提高對空閒盤區的檢索速度,可以採用顯式連結方法,亦即,在記憶體中為空閒盤區建立一張鍊表。

位示圖法

位示圖是利用二進制的一位來表示磁碟中一個盤塊的使用情況。當其值為“0”時,表示對應的盤塊空閒;為“1”時,表示已分配。有的系統把“0”作為盤塊已分配的標誌,把“1”作為空閒標誌。(它們在本質上是相同的,都是用一位的兩種狀態來標誌空閒和已分配兩種情況。)磁碟上的所有盤塊都有一個二進制位與之對應,這樣,由所有盤塊所對應的位構成一個集合,稱為位示圖。通常可用 m × n 個位數來構成位示圖,並使 m × n 等於磁碟的總塊數。

位示圖也可描述為一個二維數組 map:

Var map: array of bit;

相關詞條

熱門詞條

聯絡我們