第8章磁盤存儲器的管理

1、1 1第八章 磁盤存儲器的管理第八章第八章 磁盤存儲器的管理磁盤存儲器的管理8.1 外存的組織方式8.2 文件存儲空間的管理8.3 提高磁盤I/O速度的途徑8.4 提高磁盤可靠性的技術(shù)8.5 數(shù)據(jù)一致性控制2 2第八章 磁盤存儲器的管理8.1 外存的組織方式文件的物理結(jié)構(gòu)直接與外存的組織方式有關(guān)。目前常用的外存組織方式有：(1) 連續(xù)組織方式。(2) 鏈接組織方式。(3) 索引組織方式。 3 3第八章 磁盤存儲器的管理8.1.1 連續(xù)組織方式連續(xù)組織方式又稱連續(xù)分配方式。連續(xù)分配要求為每一個文件分配一組相鄰接的盤塊。例如，第一個盤塊的地址為b，則第二個盤塊的地址為b+1，第三個盤塊的地址為b+

2、2通常，它們都位于一條磁道上，在進行讀/寫時，不必移動磁頭，僅當訪問到一條磁道的最后一個盤塊后，才需要移到下一條磁道，于是又去連續(xù)地讀/寫多個盤塊。在采用連續(xù)組織方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時的物理文件稱為順序文件。這種分配方式保證了邏輯文件中的記錄順序與存儲器中文件占用盤塊的順序的一致性。4 4第八章 磁盤存儲器的管理為使系統(tǒng)能找到文件存放的地址，應(yīng)在目錄項的“文件物理地址”字段中，記錄該文件第一個記錄所在的盤塊號和文件長度(以盤塊數(shù)進行計量)。圖8-1 示出了連續(xù)分配的情況。圖中假定了記錄與盤塊的大小相同。Count文

3、件的第一個盤塊號是0，文件長度為2，因此是在盤塊號為0和1的兩盤塊中存放文件的數(shù)據(jù)。 5 5第八章 磁盤存儲器的管理圖8-1 磁盤空間的連續(xù)組織方式6 6第八章 磁盤存儲器的管理如同內(nèi)存的動態(tài)分區(qū)分配一樣，隨著文件建立時空間的分配和文件刪除時空間的回收，將使磁盤空間被分割成許多小塊，這些較小的連續(xù)區(qū)已難于用來存儲文件，此即外存的碎片。同樣，我們也可以利用緊湊的方法，將盤上所有的文件緊靠在一起，把所有的碎片拼接成一大片連續(xù)的存儲空間。但為了將外存上的空閑空間進行一次緊湊，所花費的時間遠比將內(nèi)存緊湊一次所花費的時間多得多。 7 7第八章 磁盤存儲器的管理連續(xù)組織方式的主要優(yōu)點有：(1)順序訪問容易

4、。訪問一個占有連續(xù)空間的文件非常容易。系統(tǒng)可從目錄中找到該順序文件所在的第一個盤塊號，從此開始順序地、逐個盤塊地往下讀/寫。連續(xù)分配也支持直接存取。例如，要訪問一個從b塊開始存放的文件中的第i個盤塊的內(nèi)容，就可直接訪問b+i號盤塊。(2)順序訪問速度快。因為由連續(xù)分配所裝入的文件，其所占用的盤塊可能是位于一條或幾條相鄰的磁道上，這時，磁頭的移動距離最少，因此，這種對文件訪問的速度是幾種存儲空間分配方式中最高的一種。 8 8第八章 磁盤存儲器的管理連續(xù)組織方式的主要缺點如下：(1) 要求有連續(xù)的存儲空間。要為每個文件分配一段連續(xù)的存儲空間，這樣，便會產(chǎn)生出許多外部碎片外部碎片，嚴重地降低了外存空

5、間的利用率。如果是定期地利用緊湊方法來消除碎片，則又需花費大量的機器時間。(2) 必須事先知道文件的長度。要將一個文件裝入一個連續(xù)的存儲區(qū)中，必須事先知道文件的長度，然后根據(jù)長度，在存儲空間中找出一塊其大小足夠的存儲區(qū)，將文件裝入。有些情況下知道文件的大小很難，只能靠估算。(3) 不能靈活地刪除和插入記錄。需移動相鄰的記錄，改變文件大小。(4) 對于那些動態(tài)增長的文件，即使事先知道文件的最終大小，也會使大量的存儲空間長期地空閑著。9 9第八章 磁盤存儲器的管理8.1.2 鏈接組織方式如果可以將文件裝到多個離散的盤塊中，就可消除連續(xù)組織方式的上述缺點。在采用鏈接組織方式時，可為文件分配多個不連續(xù)

6、的盤塊，再通過每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，由此所形成的物理文件稱為鏈接文件。鏈接組織方式的主要優(yōu)點是： (1) 消除了磁盤的外部碎片，提高了外存的利用率。 (2) 對插入、刪除和修改記錄都非常容易。 (3) 能適應(yīng)文件的動態(tài)增長，無需事先知道文件的大小。10 10第八章 磁盤存儲器的管理1. 隱式鏈接在采用隱式鏈接分配方式時，在文件目錄的每個目錄項中，都須含有指向鏈接文件第一個盤塊和最后一個盤塊的指針。而在每個盤塊中都含有一個指向下一個盤塊的指針。圖8-2 中示出了一個占用5個盤塊的鏈接式文件。在相應(yīng)的目錄項中，指示了其第一個盤塊號是9，最后一個盤塊號

7、是25。在第一個盤塊9中設(shè)置了第二個盤塊的盤塊號是16；在16號盤塊中又設(shè)置了第三個盤塊的盤塊號1。如果指針占用4個字節(jié)，對于盤塊大小為512字節(jié)的磁盤，則每個盤塊中只有508個字節(jié)可供用戶使用。11 11第八章 磁盤存儲器的管理圖8-2 磁盤空間的鏈接式分配12 12第八章 磁盤存儲器的管理隱式鏈接分配方式的主要問題在于：它只適合于順序訪問，它對隨機訪問是極其低效的。如果要訪問文件所在的第i個盤塊，則必須先讀出文件的第一個盤塊，就這樣順序地查找直至第i塊。當i=100時，須啟動100次磁盤去實現(xiàn)讀盤塊的操作，平均每次都要花費幾十毫秒。可見，隨機訪問的速度相當?shù)?。此外，只通過鏈接指針來將一大批

8、離散的盤塊鏈接起來，其可靠性較差，因為只要其中的任何一個指針出現(xiàn)問題，都會導(dǎo)致整個鏈的斷開。為了提高檢索速度和減小指針占用的存儲空間，可以將幾個盤塊組成一個簇(cluster)。分配時和鏈接時都以簇為單位。但這會增大內(nèi)部碎片。 13 13第八章 磁盤存儲器的管理2. 顯式鏈接這是指把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存內(nèi)存的一張鏈接表中。該表在整個磁盤中僅設(shè)置一張，如圖8-3所示。 表的序號是物理盤塊號，從0開始，直至N-1；N為盤塊總數(shù)。在每個表項中存放鏈接指針，即下一個盤塊號。在該表中，凡是屬于某一文件的第一個盤塊號，均作為文件地址被填入相應(yīng)文件的FCB（目錄項）的“物理地址”字段

9、中。由于查找記錄的過程是在內(nèi)存中進行的，因而不僅顯著地提高了檢索速度，而且大大減少了訪問磁盤的次數(shù)。由于分配給文件的所有盤塊號都放在該表中，故把該表稱為文件分配表 FAT (File Allocation Table)。14 14第八章 磁盤存儲器的管理圖8-3 顯式鏈接結(jié)構(gòu)15 15第八章 磁盤存儲器的管理8.1.3 FAT技術(shù)將一個物理磁盤分成多個邏輯磁盤，或者把多個物理磁盤組成一個邏輯磁盤，作為能被單獨格式化和使用的邏輯單元，稱為卷卷或分區(qū)分區(qū)。1. FAT12 1) 早期的FAT12文件系統(tǒng) 早期MS-DOS操作系統(tǒng)所使用的是FAT12文件系統(tǒng)。它以盤塊為基本分配單位的。由于FAT是文

10、件系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu)，為了安全起見，在每個分區(qū)中都配有兩張相同的文件分配表FAT1和FAT2。在FAT的每個表項中存放下一個盤塊號，它實際上是用于盤塊之間的鏈接的指針，通過它可以將一個文件的所有的盤塊鏈接起來，而將文件的第一個盤塊號放在自己的FCB中。 16 16第八章 磁盤存儲器的管理圖8-4 MS-DOS的文件物理結(jié)構(gòu)17 17第八章 磁盤存儲器的管理對于1.2 MB的軟盤，每個盤塊的大小為512 B，在每個FAT中共含有2.4 K個表項，由于每個FAT表項占12位，故FAT表占用3.6 KB的存儲空間。 計算以盤塊為分配單位時，所允許的最大磁盤容量：由于每個FAT表項為12位，因此，

11、在FAT表中最多允許有4096個表項，如果采用以盤塊作為基本分配單位，每個盤塊的大小一般是512字節(jié)，那么，每個磁盤分區(qū)的容量為2MB (4096 512 B)。同時，一個物理磁盤支持4個邏輯磁盤分區(qū)，所以相應(yīng)的磁盤最大容量僅為8 MB。這對最早時期的硬盤還可應(yīng)付，但很快磁盤的容量就超過了8 MB，F(xiàn)AT12是否還可繼續(xù)用呢？回答雖是肯定的，但需要引入一個新的分配單位簇。 18 18第八章 磁盤存儲器的管理2) 以簇為單位的FAT12文件系統(tǒng) 分析表明：如果把每個盤塊的容量增大n倍，則磁盤的最大容量便可增加n倍。為此，引入了簇(cluster)的概念。簇是一組連續(xù)的扇區(qū)，簇的大小一般是2n(n

12、為整數(shù))個盤塊，為了適應(yīng)磁盤容量不斷增大的需要，在為文件分配外存時，不再以盤塊而是以簇為基本單位。一個簇應(yīng)包含扇區(qū)的數(shù)量與磁盤容量的大小直接有關(guān)。例如，當一個簇僅有一個扇區(qū)時，磁盤的最大容量為8 MB；當一個簇包含兩個扇區(qū)時，磁盤的最大容量可以達到16 MB；當一個簇包含了八個扇區(qū)時，磁盤的最大容量便可達到64 MB。在MS-DOS的實際運用中，簇的容量可以僅有一個扇區(qū)(512 B)、兩個扇區(qū)(1 KB)、四個扇區(qū)(2 KB)、八個扇區(qū)(4 KB)等。 19 19第八章 磁盤存儲器的管理由上所述可以看出，以簇作為基本的分配單位所帶來的最主要的好處是，能適應(yīng)磁盤容量不斷增大的情況。使用簇作為基本

13、的分配單位可以減少FAT表中的項數(shù)，使FAT表占用更少的存儲空間，并減少訪問FAT表的存取開銷，提高文件系統(tǒng)的效率，但這也會造成更大的簇內(nèi)零頭(它與存儲器管理中的頁內(nèi)零頭相似)。 FAT12的主要問題是，對所允許的磁盤容量存在著嚴重的限制，通常只能是數(shù)十兆字節(jié)，雖然可以用繼續(xù)增加簇的大小來提高所允許的最大磁盤容量，但相應(yīng)的簇內(nèi)碎片也將隨之成倍地增加。此外，它只能支持8+3格式的文件名。前八個字符是文件名，最后三個是擴展名，點是隱含的。2020第八章 磁盤存儲器的管理2. FAT16 FAT12對磁盤容量限制的原因在于， FAT12表中的表項有限制，亦即最多只允許4096個。解決方法就是增加FA

14、T表的表項數(shù)，亦即應(yīng)增加FAT表的寬度，如果我們將FAT表的寬度增至16位，最大表項數(shù)將增至65536(216)個，此時便能將一個磁盤分區(qū)分為65536個簇。我們把具有16位表寬的FAT表稱為FAT16。在FAT16的每個簇中可以有的盤塊數(shù)為4、8、16、32直到64，由此得出FAT16可以管理的最大分區(qū)空間為216 64 512 = 2048 MB。 21 21第八章 磁盤存儲器的管理由上述分析不難看出，F(xiàn)AT16對FAT12的局限性有所改善，但改善很有限。當磁盤容量迅速增加時，如果再繼續(xù)使用FAT16，由此所形成的簇內(nèi)碎片所造成的浪費也越大。例如，當要求磁盤分區(qū)的大小為8 GB時，則每個簇

15、的大小達到128 KB，這意味著內(nèi)部零頭最大可達到128 KB。一般而言，對于14 GB的硬盤來說，大約會浪費1020的空間。為了解決這一問題，微軟推出了FAT32。 2222第八章 磁盤存儲器的管理3. FAT32為了減小磁盤的簇內(nèi)零頭，應(yīng)當選擇適當大小的簇，需要再增加FAT表的寬度，這樣也就由FAT16演變?yōu)镕AT32。FAT32 是FAT系列文件系統(tǒng)的最后一個產(chǎn)品。每一簇在FAT表中的表項占據(jù)4字節(jié)。理論上，F(xiàn)AT表可以表示4,294,967,296(232)項。實際上，有幾個高位是保留位(通常是0)。三種FAT的最大分區(qū)及對應(yīng)的塊大小見圖8-5。FAT32的缺點是：由于文件分配表的擴大

16、，比FAT16運行速度慢；不支持容量小于512MB的分區(qū)；單個文件長度不能大于4G；不能向下兼容。2323第八章 磁盤存儲器的管理圖8-5 FAT中簇的大小與最大分區(qū)的對應(yīng)關(guān)系2424第八章 磁盤存儲器的管理8.1.4 NTFS(New Technology File System)的文件組織方式1. NTFS新特征是一個專門為Windows NT開發(fā)的文件系統(tǒng)，并適用于Windows 2000/XP及后續(xù)的Windows OS。 具有如下新特征：1) 使用了64位磁盤地址；2) 支持長文件名，單個文件名限制在255個字符以內(nèi)，全路徑名為32, 767個字符；3) 具有系統(tǒng)容錯功能，即在系統(tǒng)出

17、現(xiàn)故障或差錯時，仍能保證系統(tǒng)正常運行；4) 提供數(shù)據(jù)一致性，確保關(guān)聯(lián)數(shù)據(jù)之間邏輯關(guān)系正確完整。5) NTFS還提供了文件加密、文件壓縮等功能。2525第八章 磁盤存儲器的管理2. 磁盤組織同F(xiàn)AT一樣，NTFS也是以簇作為磁盤空間分配和回收的基本單位。 一個文件占用若干個簇，一個簇只屬于一個文件。 通過簇來管理磁盤，可以不需要知道盤塊(扇區(qū))的大小，使NTFS具有了與磁盤物理扇區(qū)大小無關(guān)的獨立性，從而可以根據(jù)不同的磁盤選擇不同的簇大小。 在NTFS文件系統(tǒng)中，把卷上簇的大小稱為“卷因子”，卷因子是在磁盤格式化時確定的，其大小為 2n (n為整數(shù))個盤塊，可以為512 B、1 KB、2 KB，最

18、大可達64 KB。為了在傳輸效率和簇內(nèi)碎片之間進行折中，在大多數(shù)情況下都是使用4 KB。 2626第八章 磁盤存儲器的管理對于簇的定位，NTFS是采用邏輯簇號LCN(Logical Cluster Number)和虛擬簇號VCN(Virtual Cluster Number)進行的。LCN是以卷為單位，將整個卷中所有的簇按順序進行簡單的編號，NTFS在進行地址映射時，可以通過卷因子與LCN的乘積，便可算出卷上的物理字節(jié)字節(jié)偏移量，從而得到文件數(shù)據(jù)所在的物理磁盤地址。為了方便文件中數(shù)據(jù)的引用，NTFS還可以使用VCN，以文件為單位，將屬于某個文件的簇按順序進行編號。只要知道了文件開始的簇地址，便

19、可將VCN映射到LCN。 2727第八章 磁盤存儲器的管理3. 文件的組織在NTFS中，以卷為單位，將一個卷中的所有文件信息文件信息、目目錄信息錄信息以及可用的未分配空間信息未分配空間信息，都以文件記錄的方式記錄在一張主控文件表MFT(Master File Table)中。卷中的每個文件作為一條記錄，在MFT 表中占有一行，其中還包括MFT 自己的這一行。每行大小固定為1 KB，每行稱為該行所對應(yīng)文件的元數(shù)據(jù)(metadata)，也稱為文件控制字。 2828第八章 磁盤存儲器的管理在MFT表中，每個元數(shù)據(jù)所對應(yīng)文件的所有信息（包括文件的內(nèi)容等）都被組織在所對應(yīng)文件的一組屬性中。所以當文件較小

20、時，其屬性值所占空間也較小，可以將文件的所有屬性直接記錄在元數(shù)據(jù)中。而當文件較大時，元數(shù)據(jù)僅記錄該文件的一部分屬性，其余屬性，如文件的內(nèi)容等，可以記錄到卷中的其它可用簇中，并將這些簇按其所記錄的屬性分類并分別鏈接成多個隊列，將指向這些隊列的指針保存在元數(shù)據(jù)中。NTFS的不足在于缺乏兼容性：它能存取FAT等文件系統(tǒng)的文件，但NTFS文件卻不能被FAT 等文件系統(tǒng)存取。Windows 95/98/ME都不能識別NTFS文件系統(tǒng)。2929第八章 磁盤存儲器的管理8.1.5 索引組織方式1. 單級索引組織方式鏈接組織方式雖然解決了連續(xù)組織方式所存在的問題(即不便于隨機訪問)，但又出現(xiàn)了另外兩個問題，即

21、： 不能支持高效的直接存取，要對一個較大的文件進行存取，須在FAT中順序地查找許多盤塊號； FAT需占用較大的內(nèi)存空間。由于一個文件所占用盤塊的盤塊號是隨機地分布在FAT中的，因而只有將整個FAT調(diào)入內(nèi)存，才能保證在FAT中找到一個文件的所有盤塊號。 3030第八章 磁盤存儲器的管理事實上，在打開某個文件時，只需把該文件占用的盤塊的編號調(diào)入內(nèi)存即可，完全沒有必要將整個FAT調(diào)入內(nèi)存。為此，應(yīng)將每個文件所對應(yīng)的盤塊號集中地放在一起。索引分配方法就是基于這種想法所形成的一種分配方法。它為每個文件分配一個索引塊，再把分配給該文件的所有盤塊號都記錄在該索引塊中，因而該索引塊就是一個含有許多盤塊號的數(shù)組

22、。在建立一個文件時，只需在為之建立的目錄項中填上指向該索引塊的指針。圖8-6 示出了磁盤空間的索引分配圖。 31 31第八章 磁盤存儲器的管理圖8-6 索引分配方式3232第八章 磁盤存儲器的管理2. 多級索引組織方式在為一個大文件分配磁盤空間時，如果所分配出去的盤塊的盤塊號已經(jīng)裝滿一個索引塊時，OS便為該文件分配另一個索引塊，用于將以后繼續(xù)為之分配的盤塊號記錄于其中。依此類推，再通過指針將各索引塊按序鏈接起來。顯然，當文件太大，其索引塊太多時，這種方法是低效的。此時，應(yīng)為這些索引塊再建立一級索引，稱為第一級索引，即系統(tǒng)再分配一個索引塊，作為第一級索引的索引塊，將第一塊、第二塊等索引塊的盤塊號

23、填入到此索引表中，這樣便形成了兩級索引分配方式。如果文件非常大時，還可用三級、四級索引分配方式。 3333第八章 磁盤存儲器的管理圖8-7示出了兩級索引分配方式下各索引塊之間的鏈接情況。如果每個盤塊的大小為1 KB，每個盤塊號占4個字節(jié)，則在一個索引塊中可存放256個盤塊號。這樣，在兩級索引時， 最多可包含的存放文件的盤塊的盤塊號總數(shù)N = 256 256 = 64 K個盤塊號。由此可得出結(jié)論: 采用兩級索引時，所允許的文件最大長度為64 MB。倘若盤塊的大小為4 KB，在采用單級索引時所允許的最大文件長度為4 MB；而在采用兩級索引時所允許的最大文件長度可達4 GB。 3434第八章 磁盤存

24、儲器的管理圖8-7 兩級索引分配3535第八章 磁盤存儲器的管理3. 增量式索引組織方式1) 增量式索引組織方式的基本思想為了能較全面地照顧到小、中、大及特大型作業(yè)，可以采取多種組織方式來構(gòu)成文件的物理結(jié)構(gòu)。對于小文件(如1KB10KB或4KB40KB)而言，最多只會占用10個盤塊，為了提高訪問速度，將它們的每一個盤塊地址都直接放入文件控制塊FCB(或索引結(jié)點)中，即直接尋址。對于中型文件，采用單級索引組織方式。尋址時從FCB找到索引表，從表中就可獲得盤塊號，即一次間址。對于大型和特大型文件，采用兩級或三級索引組織方式，尋址時使用二次或三次間址。3636第八章 磁盤存儲器的管理2) UNIX

25、System V的組織方式在UNIX System 的索引結(jié)點索引結(jié)點中，共設(shè)置了13個地址項，即i.addr(0)i.addr(12)，如圖8-8所示。 (1) 直接地址直接地址。為了提高對文件的檢索速度，在索引結(jié)點中可設(shè)置10個直接地址項，即用i.addr(0)i.addr(9)來存放直接地址。換言之，在這里的每項中所存放的是該文件數(shù)據(jù)所在盤塊的盤塊號。假如每個盤塊的大小為 4 KB，當文件不大于40 KB時，便可直接從索引結(jié)點中讀出該文件的全部盤塊號。 3737第八章 磁盤存儲器的管理圖8-8 混合索引方式3838第八章 磁盤存儲器的管理(2) (2) 一次間接地址一次間接地址對于大、中

26、型文件，只采用直接地址是不現(xiàn)實的。為此，可再利用索引結(jié)點中的地址項iaddr(10)來提供一次間接地址。這種方式的實質(zhì)就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個盤塊號記入其中。在一次間址塊中可存放1 K個盤塊號，因而允許文件長達4 MB。 3939第八章 磁盤存儲器的管理(3) (3) 多次間接地址多次間接地址當文件長度大于4 MB + 40 KB時(一次間址與10個直接地址項)，系統(tǒng)還須采用二次間址分配方式。這時，用地址項i.addr(11)提供二次間接地址。該方式的實質(zhì)是兩級索引分配方式。系統(tǒng)此時是在二次間址塊中記入所有一次間址塊的盤號。在采用二次間址方式時

27、，文件最大長度可達4 GB。同理，地址項i.addr(12)作為三次間接地址，其所允許的文件最大長度可達4 TB。 上次課回顧上次課回顧7/3/2022 12:47 AM400:474041 41第八章 磁盤存儲器的管理8.2 文件存儲空間的管理與內(nèi)存分配相似，連續(xù)分配或離散分配，基本單位：磁盤塊8.2.1 空閑表法和空閑鏈表法1. 空閑表法1) 空閑表空閑表法屬于連續(xù)分配方式，它與內(nèi)存的動態(tài)分配方式類似。它為每個文件分配一塊連續(xù)的存儲空間。系統(tǒng)也為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于一個空閑表項，其中包括表項序號、該空閑區(qū)的第一個盤塊號、該區(qū)的空閑盤塊數(shù)等信息。再將所有空閑區(qū)按

28、其起始盤塊號遞增的次序排列，如圖8-9所示。4242第八章 磁盤存儲器的管理圖8-9 空閑盤塊表4343第八章 磁盤存儲器的管理2) 存儲空間的分配與回收空閑盤區(qū)的分配與內(nèi)存的分區(qū)(動態(tài))分配類似，同樣是采用首次適應(yīng)算法和最佳適應(yīng)算法等，它們對存儲空間的利用率大體相當，都優(yōu)于最壞適應(yīng)算法。在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順序地檢索空閑表的各表項，直至找到第一個其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶(進程)，同時修改空閑表。 系統(tǒng)在對用戶所釋放的存儲空間進行回收時，也采取類似于內(nèi)存回收的方法，即要考慮回收區(qū)是否與空閑表中插入點的前區(qū)和后區(qū)相鄰接，對相鄰接者應(yīng)予以合并。 4444第

29、八章 磁盤存儲器的管理應(yīng)該說明，在內(nèi)存分配上，很少采用連續(xù)分配方式，然而在外存的管理中，由于這種分配方式具有較高的分配速度，可減少訪問磁盤的I/O頻率，故它在諸多分配方式中仍占有一席之地。例如，在前面所介紹的對換方式中，對對換空間一般都采用連續(xù)分配方式。對于文件系統(tǒng)，當文件較小(14個盤塊)時，仍采用連續(xù)分配方式，為文件分配相鄰接的幾個盤塊；當文件較大時，便采用離散分配方式。 對于多媒體文件，為了能減少磁頭的尋道時間，也采用連續(xù)分配方式。4545第八章 磁盤存儲器的管理2. 空閑鏈表法空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成鏈所用基本元素的不同，可把鏈表分成兩種形式：(1)空閑盤塊盤

30、塊鏈。是將磁盤上的所有空閑空間，以盤塊為單位拉成一條鏈。當用戶因創(chuàng)建文件而請求分配存儲空間時，系統(tǒng)從鏈首開始，依次摘下適當數(shù)目的空閑盤塊分配給用戶。當用戶因刪除文件而釋放存儲空間時，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾。這種方法的優(yōu)點是用于分配和回收一個盤塊的過程非常簡單，但在為一個文件分配盤塊時，可能要重復(fù)操作多次。 4646第八章 磁盤存儲器的管理(2)空閑盤區(qū)盤區(qū)鏈。是將磁盤上的所有空閑盤區(qū)(每個盤區(qū)可包含若干個盤塊)拉成一條鏈。每個盤區(qū)上除含有用于指示下一個空閑盤區(qū)的指針外，還有指明盤區(qū)大小(盤塊數(shù))的信息。分配盤區(qū)的方法與內(nèi)存的動態(tài)分區(qū)分配類似，通常采用首次適應(yīng)算法。在回收盤區(qū)時

31、，同樣也要將回收區(qū)與相鄰接的空閑盤區(qū)相合并。為了提高對空閑盤區(qū)的檢索速度，可以采用顯式鏈接方法，亦即，在內(nèi)存中為空閑盤區(qū)建立一張鏈表。 這種方法的缺點是用于分配和回收的過程非常復(fù)雜，但在效率較高，每次分配多個連續(xù)的塊，而且鏈較短。 4747第八章 磁盤存儲器的管理8.2.2 位示圖法1. 位示圖位示圖是利用二進制的一位來表示磁盤中一個盤塊的使用情況。當其值為“0”時，表示對應(yīng)的盤塊空閑；為“1”時，表示已分配(或者相反)。由所有盤塊所對應(yīng)的位構(gòu)成一個集合，稱為位示圖。 位示圖也可描述為一個二維數(shù)組map：Var map: array of bit； 通?？捎胢 n個位數(shù)來構(gòu)成位示圖，并使m n

32、等于磁盤的總塊數(shù)，如圖8-10所示。4848第八章 磁盤存儲器的管理圖8-10 位示圖4949第八章 磁盤存儲器的管理2. 盤塊的分配根據(jù)位示圖進行盤塊分配時，可分三步進行： (1) 順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位(“0”表示空閑)。 (2) 將所找到的二進制位轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進制位位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式計算：b=n(i-1)+j式中，n代表每行的位數(shù)。 (3) 修改位示圖，令mapi, j=1。5050第八章 磁盤存儲器的管理3. 盤塊的回收盤塊的回收分兩步： (1) 將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的

33、行號和列號。轉(zhuǎn)換公式為：i=(b-1)DIV n+1j=(b-1)MOD n+1 (2) 修改位示圖。令mapi, j =0。51 51第八章 磁盤存儲器的管理這種方法的主要優(yōu)點是：從位示圖中很容易找到一個或一組相鄰接的空閑盤塊。例如，我們需要找到6個相鄰接的空閑盤塊，這只需在位示圖中找出6個其值連續(xù)為“0”的位即可。此外，由于位示圖很小，占用空間少，因而可將它保存在內(nèi)存中，進而使在每次進行盤區(qū)分配時，無需首先把盤區(qū)分配表讀入內(nèi)存，從而節(jié)省了許多磁盤的啟動操作。因此，位示圖常用于微型機和小型機中，如CP/M、Apple-DOS等OS中。 5252第八章 磁盤存儲器的管理8.2.3 成組鏈接法空閑表法