空間分配

空間分配

存儲器是計算機系統的重要資源之一,計算機系統的存儲器分為兩類:主存和輔助存儲器。空間分配是指對主存和輔助存儲器空間的分配。主存和外存空間分配很多相同之處:提高空間利用率;都有空間分配記錄表;提高存取速度。

基本介紹

  • 中文名:空間分配
  • 外文名:space allocation
  • 學科:計算機
  • 定義:主存和輔助存儲器空間的的分配
  • 有關術語:存儲器
  • 領域:計算機系統
簡介,主存空間分配方法,直接存儲分配方式,靜態存儲分配方式,動態存儲分配方式,外存空間分配方式,連續分配方式,連結分配,索引分配,

簡介

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

主存空間分配方法

直接存儲分配方式

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

靜態存儲分配方式

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

動態存儲分配方式

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

外存空間分配方式

連續分配方式

連續分配(Continuous Allocation)要求為每一個檔案分配一組相鄰接的盤塊。 一組盤塊的地址定義了磁碟上的一段線性地址。例如,第一個盤塊的地址為 b,則第二個盤塊的地址為b+1,第三個盤塊的地址為 b+2……。通常,它們都位於一條磁軌上,在進行讀/寫時,不必移動磁頭,僅當訪問到一條磁軌的最後一個盤塊後,才需要移到下一條磁軌,於是又去連續地讀/寫多個盤塊。在採用連續分配方式時,可把邏輯檔案中的記錄順序地存儲到鄰接的各物理盤塊中,這樣所形成的檔案結構稱為順序檔案結構,此時的物理檔案稱為順序檔案。這種分配方式保證了邏輯檔案中的記錄順序與存儲器中檔案占用盤塊的順序的一致性。為使系統能找到檔案存放的地址,應在目
錄項的“檔案物理地址”欄位中,記錄該檔案第一個記錄所在的盤塊號和檔案長度(以盤塊數進行計量)。圖 1示出了連續分配的情況。圖1中假定了記錄與盤塊的大小相同。Count 檔案的第一個盤塊號是 0,檔案長度為 2,因此是在盤塊號為 0 和 1 的兩盤塊中存放檔案 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
記憶體。為此,應將每個檔案所對應的盤塊號集中地放在一起。索引分配方法就是基於這種想法所形成的一種分配方法。它為每個檔案分配一個索引塊(表),再把分配給該檔案的所有盤塊號都記錄在該索引塊中,因而該索引塊就是一個含有許多盤塊號的數組。在建立一個檔案時,只需在為之建立的目錄項中填上指向該索引塊的指針。圖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 時,便可直接從索引結點中讀出該檔案的全部盤塊號。
空間分配
圖4
2) 一次間接地址
對於大、中型檔案,只採用直接地址是不現實的。為此,可再利用索引結點中的地址項 iaddr(10)來提供一次
間接地址。這種方式的實質就是一級索引分配方式。圖4中的一次間址塊也就是索引塊,系統將分配給檔案的多個盤塊號記入其中。在一次間址塊中可存放 1 K個盤塊號,因而允許檔案長達 4 MB。
3) 多次間接地址
當檔案長度大於 4 MB + 40 KB 時(一次間址與 10 個直接地址項), 系統還須採用二次間址分配方式。這時,用地址項 iaddr(11)提供二次間接地址。該方式的實質是兩級索引分配方式。系統此時是在二次間址塊中記入所有一次間址塊的盤號。在採用二次間址方式時,檔案最大長度可達 4 GB。同理,地址項 iaddr(12)作為三次間接地址,其所允許的檔案最大長度可達 4 TB。

相關詞條

熱門詞條

聯絡我們