1、Operating SystemOperating SystemPage 12022-4-24第八章 磁盤存儲(chǔ)器管理信電學(xué)院 錢斌Operating SystemOperating SystemPage 22022-4-248.1外存的組織方式外存的組織方式 （1）它為每個(gè)文件分配一片連續(xù)的磁盤空它為每個(gè)文件分配一片連續(xù)的磁盤空間，所形成的文件物理結(jié)構(gòu)是間，所形成的文件物理結(jié)構(gòu)是順序式的文件結(jié)構(gòu)順序式的文件結(jié)構(gòu)。（2）。它為每個(gè)文件分配不連續(xù)的磁盤空間，它為每個(gè)文件分配不連續(xù)的磁盤空間，通過(guò)鏈接指針將文件的所有盤塊鏈接在一起。形成通過(guò)鏈接指針將文件的所有盤塊鏈接在一起。形成鏈接式鏈接式文件結(jié)構(gòu)

2、。文件結(jié)構(gòu)。（3）。系統(tǒng)為每個(gè)文件建立索引表，記錄文系統(tǒng)為每個(gè)文件建立索引表，記錄文件的盤塊號(hào)。件的盤塊號(hào)。Operating SystemOperating SystemPage 32022-4-24q連續(xù)分配連續(xù)分配(Continuous Allocation)要求為每要求為每一個(gè)文件分配一個(gè)文件分配一組相鄰接的盤塊一組相鄰接的盤塊。通常，這些。通常，這些盤塊位于一條磁道上，讀寫時(shí)不必移動(dòng)磁頭。盤塊位于一條磁道上，讀寫時(shí)不必移動(dòng)磁頭。q在采用連續(xù)分配方式時(shí)，可把邏輯文件中的記在采用連續(xù)分配方式時(shí)，可把邏輯文件中的記錄順序地存儲(chǔ)到鄰接的各物理盤塊中，這樣所錄順序地存儲(chǔ)到鄰接的各物理盤塊中，這

3、樣所形成的文件結(jié)構(gòu)稱為形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)順序文件結(jié)構(gòu)，此時(shí)的物，此時(shí)的物理文件稱為理文件稱為順序文件順序文件Operating SystemOperating SystemPage 42022-4-241230567491011813141512171819162122232025262724list29303128mailcountfilestartlengthcount02tr143mail196list284f62目 錄trf目錄項(xiàng)的“文件物理地址”中記錄該文件第一個(gè)記錄所在的盤塊號(hào)和文件長(zhǎng)度。Operating SystemOperating Systemq跟內(nèi)存的動(dòng)態(tài)分區(qū)

4、分配一樣，容易產(chǎn)生“碎片”?？梢圆捎谩熬o湊”技術(shù)，但花費(fèi)時(shí)間更多。q主要優(yōu)點(diǎn)：q 順序訪問(wèn)容易；順序訪問(wèn)速度快；q主要缺點(diǎn)：q 為文件分配連續(xù)存儲(chǔ)空間，產(chǎn)生碎片，降低外存利用率。q 必須事先知道文件的長(zhǎng)度。q 不能靈活地插入刪除記錄。q 動(dòng)態(tài)增長(zhǎng)的文件很難分配。Operating SystemOperating SystemPage 62022-4-24q鏈接分配：鏈接分配：將文件裝到多個(gè)離散的盤塊中。將文件裝到多個(gè)離散的盤塊中。v可通過(guò)在每個(gè)盤塊上的鏈接指針，將同屬于一可通過(guò)在每個(gè)盤塊上的鏈接指針，將同屬于一個(gè)文件的多個(gè)個(gè)文件的多個(gè)離散的離散的盤塊鏈接成一個(gè)盤塊鏈接成一個(gè)鏈表鏈表，把，把這樣

5、形成的物理文件稱為這樣形成的物理文件稱為鏈接文件鏈接文件q鏈接方式鏈接方式v隱式鏈接隱式鏈接v顯式鏈接顯式鏈接Operating SystemOperating SystemPage 72022-4-24q1.隱式鏈接文件名文件名 始址始址 末址末址jeep 9 25文件目錄文件目錄01234567891011121314151617181920212223242526272829303111016-125磁盤空間的鏈接式分配磁盤空間的鏈接式分配每個(gè)目錄項(xiàng)都有指向第一個(gè)和最后一個(gè)盤塊的指針；每個(gè)盤塊中有指向下一個(gè)盤塊的指針。Operating SystemOperating Systemq隱式

6、鏈接的主要問(wèn)題：只適用于順序訪問(wèn)，對(duì)隨機(jī)訪問(wèn)極其低效；可靠性較差。q簇：將幾個(gè)盤塊組成一個(gè)簇（cluster）。進(jìn)行盤塊分配時(shí)，以簇為單位進(jìn)行。q可以成倍減少查找指定塊的時(shí)間，也可以減少指針?biāo)加玫拇鎯?chǔ)空間。 但：增大了內(nèi)部碎片。Operating SystemOperating SystemPage 92022-4-24q2.顯式鏈接顯式鏈接v把鏈接文件中各物理塊的指針顯式存放在內(nèi)存把鏈接文件中各物理塊的指針顯式存放在內(nèi)存的一張鏈接表中。的一張鏈接表中。文件分配表（文件分配表（FATFAT）v這樣既保持了鏈接文件的優(yōu)點(diǎn)，也克服了其缺這樣既保持了鏈接文件的優(yōu)點(diǎn)，也克服了其缺點(diǎn)點(diǎn)，DOS、WIN

7、DOWS系統(tǒng)就采用了這樣結(jié)構(gòu)。系統(tǒng)就采用了這樣結(jié)構(gòu)。q文件分配表（文件分配表（File Allocation Table, FAT）Operating SystemOperating SystemPage 102022-4-24q顯式鏈接012345物理塊號(hào)物理塊號(hào)2FCBFAT0451每個(gè)文件的第一個(gè)盤塊號(hào)，作為文件地址填入相應(yīng)文件的FCB。Operating SystemOperating Systemq 發(fā)展歷史FAT12- FAT16- FAT32 NTFS1.FAT12q 以盤塊為基本分配單位每個(gè)分區(qū)中都有兩張相同的文件分配表FAT1和FAT2文件的第一個(gè)盤塊號(hào)放在自己的文件的第一個(gè)

8、盤塊號(hào)放在自己的FCB中中對(duì)于1.2 MB的軟盤，每個(gè)盤塊的大小為512 B，在每個(gè)FAT中共含有2.4 K個(gè)表項(xiàng)，由于每個(gè)FAT表項(xiàng)占12位，故FAT表占用3.6 KB的存儲(chǔ)空間。Operating SystemOperating System圖8-4MS-DOS的文件物理結(jié)構(gòu) 6EOF11105EOF0123456789FATFCB A4FCB B9Operating SystemOperating Systemq以盤塊為分配單位時(shí)，最大磁盤容量計(jì)算：q每個(gè)FAT表項(xiàng)為12位，因此，在FAT表中最多允許有4096個(gè)表項(xiàng)，q如果采用以盤塊作為基本分配單位，每個(gè)盤塊(也稱扇區(qū))的大小一般是51

9、2字節(jié)，那么，每個(gè)磁盤分區(qū)的容量為2 MB(4096512 B)。同時(shí)，一個(gè)物理磁盤支持4個(gè)邏輯磁盤分區(qū)，所以相應(yīng)的磁盤最大容量?jī)H為8 MB。Operating SystemOperating Systemq2）以簇為分配單位的FAT12在進(jìn)行盤塊分配時(shí)，不再以盤塊而是以簇(cluster)為基本單位。簇是一組連續(xù)的扇區(qū)，在簇是一組連續(xù)的扇區(qū)，在FAT中它中它是作為一個(gè)虛擬扇區(qū)，是作為一個(gè)虛擬扇區(qū)，簇的大小一般是2n (n為整數(shù))個(gè)盤塊，在MS-DOS的實(shí)際運(yùn)用中，簇的容量可以僅有一個(gè)扇區(qū)(512 B)、兩個(gè)扇區(qū)(1 KB)、四個(gè)扇區(qū)(2 KB)、八個(gè)扇區(qū)(4 KB)等。當(dāng)一個(gè)簇包含了八個(gè)扇區(qū)

10、時(shí)，磁盤的最大容量便可達(dá)到64 MB。Operating SystemOperating Systemq以簇作為基本的分配單位所帶來(lái)的最主要的好處是，能適應(yīng)磁盤容量不斷增大的情況。qFAT12的主要問(wèn)題：q對(duì)所允許的磁盤容量存在著嚴(yán)重的限制對(duì)所允許的磁盤容量存在著嚴(yán)重的限制，它只能支持它只能支持8+3格式的文件名格式的文件名。 Operating SystemOperating SystemqFAT12表問(wèn)題根源在于，最多只允許4096個(gè)表項(xiàng)q解決方法，那就是增加FAT表的表項(xiàng)數(shù)。q將將FAT表的寬度增至表的寬度增至16位，最大表項(xiàng)數(shù)將增至位，最大表項(xiàng)數(shù)將增至65536個(gè)，個(gè)，此時(shí)便能將一個(gè)磁

11、盤分區(qū)分為65 536(216)個(gè)簇。q具有16位表寬的FAT表稱為FAT16。qFAT16的每個(gè)簇中可以有的盤塊數(shù)為4、8、16、32直到64，由此得出FAT16可以管理的最大分區(qū)空可以管理的最大分區(qū)空間為間為216 64 512 = 2048 MBOperating SystemOperating System由上述分析不難看出，F(xiàn)AT16對(duì)FAT12的局限性有所改善，但改善很有限。當(dāng)磁盤容量迅速增加時(shí)，如果再繼續(xù)使用FAT16，由此所形成的簇內(nèi)碎片所造簇內(nèi)碎片所造成的浪費(fèi)也越大成的浪費(fèi)也越大。例如，當(dāng)要求磁盤分區(qū)的大小為8 GB時(shí)，則每個(gè)簇的大小達(dá)到128 KB，這意味著內(nèi)部零頭最大可達(dá)

12、到128 KB。一般而言，對(duì)于14 GB的硬盤來(lái)說(shuō)，大約會(huì)浪費(fèi)1020的空間。為了解決這一問(wèn)題，微軟推出了FAT32。 Operating SystemOperating System增加FAT表的寬度，F(xiàn)AT16演變?yōu)镕AT32。q每一簇在FAT表中的表項(xiàng)占據(jù)4字節(jié)(232)，F(xiàn)AT表可以表示4 294 967 296項(xiàng)，即FAT32允許管理比FAT16更多的簇。這樣就允許在FAT32中采用較小的簇，F(xiàn)AT32的每個(gè)簇都固定為的每個(gè)簇都固定為4 KB，即每簇用8個(gè)盤塊代替FAT16的64個(gè)盤塊，每個(gè)盤塊仍為512字節(jié)，F(xiàn)AT32分區(qū)格式可以管理的單個(gè)最大分區(qū)格式可以管理的單個(gè)最大磁盤空間大到

13、磁盤空間大到q4 KB232 = 2 TB。？ Operating SystemOperating SystemFAT32是FAT系列文件系統(tǒng)的最后一個(gè)產(chǎn)品。三種FAT類型的最大分區(qū)以及所對(duì)應(yīng)的塊的大小如圖所示。 塊大小/KB FAT12/MB FAT16/MB FAT32/TB 0.5 2 1 4 2 8 128 4 16 256 1 8 512 2 16 1024 2 32 2048 2 圖8-5 FAT中簇的大小與最大分區(qū)的對(duì)應(yīng)關(guān)系 Operating SystemOperating SystemqFAT32的不足：q運(yùn)行速度比FAT16慢。q有最小管理空間的限制：512MBq單個(gè)文件長(zhǎng)

14、度不能大于4GBq不能保持向下兼容Operating SystemOperating Systemq1) NTFS (New Technology File System)新特征q它使用了它使用了64位磁盤地址，理論上可以支持位磁盤地址，理論上可以支持2的的64次方字節(jié)的磁盤分區(qū)次方字節(jié)的磁盤分區(qū)；q其次，在NTFS中可以很好地支持長(zhǎng)文件名很好地支持長(zhǎng)文件名，單個(gè)文件名限制在255個(gè)字符以內(nèi)，全路徑名為32 767個(gè)字符；q第三，具有系統(tǒng)容錯(cuò)功能，具有系統(tǒng)容錯(cuò)功能，即在系統(tǒng)出現(xiàn)故障或差錯(cuò)時(shí)，仍能保證系統(tǒng)正常運(yùn)行；q第四，提供了數(shù)據(jù)的一致性提供了數(shù)據(jù)的一致性，這是一個(gè)非常有用的功能，此外，NTF

15、S還提供了文件加密、文件壓縮等功能Operating SystemOperating Systemq2) 磁盤組織qNTFS也是以簇作為磁盤空間分配和回收的基本單位。一個(gè)文件占用若干個(gè)簇，一個(gè)簇只屬于一個(gè)文件。通過(guò)簇來(lái)間接管理磁盤，可以不需要知道盤塊(扇區(qū))的大小，使NTFS具有了與磁盤物理扇區(qū)大小無(wú)關(guān)的獨(dú)立性，很容易支持扇區(qū)大小不是512字節(jié)的非標(biāo)準(zhǔn)磁盤，從而可以根據(jù)不同的磁盤選擇匹配的簇大小。Operating SystemOperating Systemq 2) 磁盤組織q 在NTFS文件系統(tǒng)中，把卷上簇的大小稱為卷上簇的大小稱為“卷因子卷因子”，卷因子是在磁盤格式化時(shí)確定在磁盤格式化時(shí)

16、確定的。q 為了在傳輸效率和簇內(nèi)碎片之間進(jìn)行折中，NTFS在大多在大多數(shù)情況下都是使用數(shù)情況下都是使用4 KB。q 對(duì)于簇的定位，NTFS是采用邏輯簇號(hào)LCN(Logical Cluster Number)和虛擬簇號(hào)VCN(Virtual Cluster Number)進(jìn)行的。LCN是以卷為單位，將整個(gè)卷中所有的簇按順序進(jìn)行簡(jiǎn)是以卷為單位，將整個(gè)卷中所有的簇按順序進(jìn)行簡(jiǎn)單的編號(hào)，單的編號(hào)，NTFS在進(jìn)行地址映射時(shí)，可以通過(guò)卷因子與LCN的乘積，便可算出卷上的物理字節(jié)偏移量，從而得到文件數(shù)據(jù)所在的物理磁盤地址。為了方便文件中數(shù)據(jù)的引用，NTFS還可以使用VCN，以文件為單位，將屬于某個(gè)，以文件為

17、單位，將屬于某個(gè)文件的簇按順序進(jìn)行編號(hào)文件的簇按順序進(jìn)行編號(hào)。只要知道了文件開(kāi)始的簇地址，便可將VCN映射到LCNOperating SystemOperating Systemq3) 文件的組織q在NTFS文件系統(tǒng)中，以卷為單位，將一個(gè)卷中的以卷為單位，將一個(gè)卷中的所有文件信息、目錄信息以及可用的未分配空間所有文件信息、目錄信息以及可用的未分配空間信息，都以文件記錄的方式記錄在一張主控文件信息，都以文件記錄的方式記錄在一張主控文件表表MFT(Master File Table)中。中。該表是NTFS 卷結(jié)構(gòu)的中心，從邏輯上講，卷中的每個(gè)文件作為一條記錄，在MFT 表中占有一行，其中還包括MF

18、T 自己的這一行。每行大小固定為1 KB，每行稱為該行所對(duì)應(yīng)文件的元數(shù)據(jù)元數(shù)據(jù)(metadata)，也稱為文件控制字。 Operating SystemOperating Systemq 3) 文件的組織q 在MFT表中，每個(gè)元數(shù)據(jù)將其所對(duì)應(yīng)文件的所有信息，包括文件的內(nèi)容等，都被組織在所對(duì)應(yīng)文件的一組屬性中。由于文件大小相差懸殊，其屬性所需空間大小也相差很大，因此，在MFT表中，對(duì)于元數(shù)據(jù)的1 KB空間，可能記錄不下文件的全部信息。所以當(dāng)文件較小時(shí)，其屬性值所占當(dāng)文件較小時(shí)，其屬性值所占空間也較小，可以將文件的所有屬性直接記錄在元數(shù)據(jù)中空間也較小，可以將文件的所有屬性直接記錄在元數(shù)據(jù)中。而當(dāng)文

19、件較大時(shí)，元數(shù)據(jù)僅記錄該文件的一部分屬性，文件較大時(shí)，元數(shù)據(jù)僅記錄該文件的一部分屬性，其余屬性，如文件的內(nèi)容等，可以記錄到卷中的其它可用其余屬性，如文件的內(nèi)容等，可以記錄到卷中的其它可用簇中，并將簇中，并將這些簇按其所記錄文件的屬性進(jìn)行分類，分別鏈接成多個(gè)隊(duì)列，將指向這些隊(duì)列的指針保存在元數(shù)據(jù)中Operating SystemOperating SystemqNTFS的不足之處：只能被WindowsNT所識(shí)別。qNTFS系統(tǒng)可以存取FAT等文件系統(tǒng)的文件，反之則不能，缺乏兼容性。Operating SystemOperating System8.1.58.1.5索引組織方式索引組織方式1 1單

20、級(jí)索引組織方式單級(jí)索引組織方式鏈接分配方式雖然解決了連續(xù)分配方式所存在的問(wèn)題，但又出現(xiàn)了下述另外兩個(gè)問(wèn)題：(1) 不能支持高效的直接存取不能支持高效的直接存取。要對(duì)一個(gè)較大的文件進(jìn)行直接存取，須首先在FAT中順序地查找許多盤塊號(hào)。 (2) FATFAT需占用較大的內(nèi)存空間需占用較大的內(nèi)存空間。由于一個(gè)文件所占用盤塊的盤塊號(hào)是隨機(jī)地分布在FAT中的，因而只有將整個(gè)只有將整個(gè)FATFAT調(diào)入內(nèi)存，才能保證調(diào)入內(nèi)存，才能保證在在FATFAT中找到一個(gè)文件的所有盤塊號(hào)中找到一個(gè)文件的所有盤塊號(hào)。當(dāng)磁盤容量較大時(shí)，F(xiàn)AT可能要占用數(shù)兆字節(jié)以上的內(nèi)存空間，這是令人難以接受的。Operating Syste

21、mOperating System8.1.58.1.5索引組織方式索引組織方式1 1單級(jí)索引組織方式單級(jí)索引組織方式事實(shí)上，在打開(kāi)某個(gè)文件時(shí)，只需把該文件占用的盤塊只需把該文件占用的盤塊的編號(hào)調(diào)入內(nèi)存即可，完全沒(méi)有必要將整個(gè)的編號(hào)調(diào)入內(nèi)存即可，完全沒(méi)有必要將整個(gè)FAT調(diào)入內(nèi)存調(diào)入內(nèi)存。為此，應(yīng)將每個(gè)文件所對(duì)應(yīng)的盤塊號(hào)集中地放在一起每個(gè)文件所對(duì)應(yīng)的盤塊號(hào)集中地放在一起。索引分配方法就是基于這種想法所形成的一種分配方法。它為每為每個(gè)文件分配一個(gè)索引塊個(gè)文件分配一個(gè)索引塊(表表)，再把分配給該文件的所有盤塊再把分配給該文件的所有盤塊號(hào)都記錄在該索引塊中，因而該索引塊就是一個(gè)含有許多盤號(hào)都記錄在該索引

22、塊中，因而該索引塊就是一個(gè)含有許多盤塊號(hào)的數(shù)組。在建立一個(gè)文件時(shí)，只需在為之建立的目錄項(xiàng)塊號(hào)的數(shù)組。在建立一個(gè)文件時(shí)，只需在為之建立的目錄項(xiàng)中填上指向該索引塊的指針。中填上指向該索引塊的指針。圖8-6 示出了磁盤空間的索引分配圖Operating SystemOperating SystemPage 292022-4-24012345678910111213141516171819202122232425262728293031文件名文件名 索引塊地址索引塊地址文件目錄文件目錄Jeep 19 916 11025 -1 -1 -119Operating SystemOperating Syste

23、mq索引組織方式的優(yōu)點(diǎn)是支持直接訪問(wèn)；不會(huì)產(chǎn)生外部碎片。q主要問(wèn)題是，每個(gè)文件都要分配一個(gè)索引塊。對(duì)于小文件，其索引塊的利用率極低。Operating SystemOperating Systemq 2多級(jí)索引分配多級(jí)索引分配q 當(dāng)OS為一個(gè)大文件大文件分配磁盤空間時(shí)，如果所分配出去的盤塊的盤塊號(hào)已經(jīng)裝滿一個(gè)索引塊時(shí)，OS便為該文件分配另一個(gè)索引塊，用于將以后繼續(xù)為之分配的盤塊號(hào)記錄于其中。依此類推，再通過(guò)鏈指針將各索引塊按序鏈接起來(lái)。顯然，當(dāng)文件太大，其索引塊太多時(shí)，這種方法是低效的。此時(shí)，應(yīng)為這些索引塊再建立一級(jí)索引為這些索引塊再建立一級(jí)索引，稱為第一級(jí)索引，即系統(tǒng)再分配一個(gè)索引塊，作為第

24、一級(jí)索引的索引塊，將第一塊、第二塊等索引塊的盤塊號(hào)填入到此索引表中，這樣便形成了兩級(jí)索引分配方式。如果文件非常大時(shí)，還可用三級(jí)、四級(jí)索引分配方式Operating SystemOperating Systemq2多級(jí)索引分配多級(jí)索引分配q圖8-7示出了兩級(jí)索引分配方式下各索引塊之間的鏈接情況。如果每個(gè)盤塊的大小為1 KB，每個(gè)盤塊號(hào)占4個(gè)字節(jié)，則在一個(gè)索引塊中可存放256個(gè)盤塊號(hào)。這樣，在兩級(jí)索引時(shí)， 最多可包含的存放文件的盤塊的盤塊號(hào)總數(shù)N = 256 256 = 64 K個(gè)盤塊號(hào)。由此可得出結(jié)論: 采用兩級(jí)索引時(shí)，所允許的文件最大長(zhǎng)度為64 MB。倘若盤塊的大小為4 KB，在采用單級(jí)索引時(shí)

25、所允許的最大文件長(zhǎng)度為4 MB；而在采用兩級(jí)索引時(shí)所允許的最大文件長(zhǎng)度可達(dá)4 GBOperating SystemOperating SystemPage 332022-4-24q多級(jí)索引分配012-105106254356357985105106254740356357-1125985360740-1125-主索引主索引360第二級(jí)索引第二級(jí)索引磁盤空間磁盤空間Operating SystemOperating Systemq多級(jí)索引的優(yōu)點(diǎn)：大大加快了對(duì)大型文件的查找速度。q主要缺點(diǎn)：在訪問(wèn)一個(gè)盤塊時(shí)，其所需啟動(dòng)磁盤的次數(shù)隨著索引級(jí)數(shù)的增加而增多。Operating SystemOperat

26、ing Systemq3、增量式索引組織方式q1）基本思想：全面照顧到小、中、大、特大文件。q小文件（1K10K）：直接尋址。q中等文件（11K256K或5K4M）一次間址q大型、特大型：二次間址和三次間址q2）UNIX System Vq索引節(jié)點(diǎn)中設(shè)13個(gè)地址項(xiàng)。Operating SystemOperating SystemPage 362022-4-24qUNIX系統(tǒng)采用索引文件結(jié)構(gòu)，UNIX系統(tǒng)采用多級(jí)間接索引結(jié)構(gòu)，對(duì)小型文件采用直接索引，對(duì)大型文件采用間接索引，從而，既保證絕大多數(shù)的文件有高的存取效率，又能適應(yīng)存取一些大型文件。（既保證了文件系統(tǒng)的高效率，又使其有很寬的適應(yīng)面）012

27、-105106254356357985105106254740356357-1125985360740-1125-主索引主索引360第二級(jí)索引第二級(jí)索引磁盤空間磁盤空間Operating SystemOperating Systemq1) 直接地址q為了提高對(duì)文件的檢索速度，在索引結(jié)點(diǎn)中可設(shè)置10個(gè)直接地址項(xiàng)，即用iaddr(0)iaddr(9)來(lái)存放直接地址。換言之，在這里的每項(xiàng)中所存放的是該文件數(shù)據(jù)所在盤塊的盤塊號(hào)。假如每個(gè)盤塊的大小為 4 KB，當(dāng)文件不大于40 KB時(shí)，便可直接從索引結(jié)點(diǎn)中讀出該文件的全部盤塊號(hào)。Operating SystemOperating System2) 一次

28、間接地址對(duì)于大、中型文件，只采用直接地址是不現(xiàn)實(shí)的。為此，可再利用索引結(jié)點(diǎn)中的地址項(xiàng)iaddr(10)來(lái)提供一次間接地址。這種方式的實(shí)質(zhì)就是一級(jí)索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個(gè)盤塊號(hào)記入其中。在一次間址塊中可存放1 K個(gè)盤塊號(hào)，因而允許文件長(zhǎng)達(dá)4 MB。 Operating SystemOperating System3) 多次間接地址當(dāng)文件長(zhǎng)度大于4 MB + 40 KB時(shí)(一次間址與10個(gè)直接地址項(xiàng))，系統(tǒng)還須采用二次間址分配方式。這時(shí)，用地址項(xiàng)iaddr(11)提供二次間接地址。該方式的實(shí)質(zhì)是兩級(jí)索引分配方式。系統(tǒng)此時(shí)是在二次間址塊中記入所有一次間址塊的

29、盤號(hào)。在采用二次間址方式時(shí)，文件最大長(zhǎng)度可達(dá)4 GB。同理，地址項(xiàng)iaddr(12)作為三次間接地址，其所允許的文件最大長(zhǎng)度可達(dá)4 TB。 Operating SystemOperating Systemq8.2.1空閑表法和空閑鏈表法空閑表法和空閑鏈表法q1空閑表法空閑表法q1) 空閑表q空閑表法屬于連續(xù)分配方式，它與內(nèi)存的動(dòng)態(tài)分配方式雷同，它為每個(gè)文件分配一塊連續(xù)的存儲(chǔ)空間，即系統(tǒng)也為外存上的所有空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對(duì)應(yīng)于一個(gè)空閑表項(xiàng)，其中包括表項(xiàng)序號(hào)、該空閑區(qū)的第一個(gè)盤塊號(hào)、該區(qū)的空閑盤塊數(shù)等信息。再將所有空閑區(qū)按其起始盤塊號(hào)遞增的次序排列，如圖8-9所示。 Operatin

30、g SystemOperating System圖8-9空閑盤塊表 序 號(hào) 第一空閑盤塊號(hào) 空閑盤塊數(shù) 1 2 4 2 9 3 3 15 5 4 Operating SystemOperating System2) 存儲(chǔ)空間的分配與回收 空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。例如，在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時(shí)，先順序地檢索空閑表的各表項(xiàng)，直至找到第一個(gè)其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配給用戶(進(jìn)程)，同時(shí)修改空閑表。系統(tǒng)在對(duì)用戶所釋放的存儲(chǔ)空間進(jìn)行回收時(shí)，也采取類似于內(nèi)存回收的方法，即要考慮回收區(qū)是否與空閑表中插入點(diǎn)的前區(qū)和后區(qū)相鄰接，對(duì)

31、相鄰接者應(yīng)予以合并。 Operating SystemOperating System應(yīng)該說(shuō)明，在內(nèi)存分配上，雖然很少采用連續(xù)分配方式，然而在外存的管理中，由于這種分配方式具有較高的分配速度，可減少訪問(wèn)磁盤的I/O頻率，故它在諸多分配方式中仍占有一席之地。例如，在前面所介紹的對(duì)換方式中，對(duì)對(duì)換對(duì)換空間空間一般都采用連續(xù)分配方式。對(duì)于文件系統(tǒng)，當(dāng)文件較小(14個(gè)盤塊)時(shí)，仍采用連續(xù)分配方式，為文件分配相鄰接的幾個(gè)盤塊；當(dāng)文件較大時(shí)，便采用離散分配方式。對(duì)于多多媒體文件媒體文件，為了減少磁頭尋道時(shí)間，也采用連續(xù)分配。 Operating SystemOperating System2空閑鏈表法空閑

32、鏈表法空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成鏈所用基本元素的不同，可把鏈表分成兩種形式：空閑盤塊鏈和空閑盤區(qū)鏈。(1) 空閑盤塊鏈。這是將磁盤上的所有空閑空間，以盤塊以盤塊為單位拉成一條鏈為單位拉成一條鏈。當(dāng)用戶因創(chuàng)建文件而請(qǐng)求分配存儲(chǔ)空間時(shí)，系統(tǒng)從鏈?zhǔn)组_(kāi)始，依次摘下適當(dāng)數(shù)目的空閑盤塊分配給從鏈?zhǔn)组_(kāi)始，依次摘下適當(dāng)數(shù)目的空閑盤塊分配給用戶。用戶。當(dāng)用戶因刪除文件而釋放存儲(chǔ)空間時(shí)，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾。這種方法的優(yōu)點(diǎn)是用于分配和回收一個(gè)盤塊的過(guò)程非常簡(jiǎn)單，但在為一個(gè)文件分配盤塊時(shí)，可能要重復(fù)操作多次。 Operating SystemOperating Syste

33、m(2) 空閑盤區(qū)鏈。這是將磁盤上的所有空閑盤區(qū)(每個(gè)盤區(qū)可包含若干個(gè)盤塊)拉成一條鏈。在每個(gè)盤區(qū)上除含有用于指示下一個(gè)空閑盤區(qū)的指針外，還應(yīng)有能指明本盤區(qū)大小(盤塊數(shù))的信息。分配盤區(qū)的方法與內(nèi)存的動(dòng)態(tài)分區(qū)分配類似，通常采用首次適應(yīng)算法。在回收盤區(qū)時(shí)，同樣也要將回收區(qū)與相鄰接的空閑盤區(qū)相合并。在采用首次適應(yīng)算法時(shí)，為了提高對(duì)空閑盤區(qū)的檢索速度，可以采用顯式鏈接方法，亦即，在內(nèi)存中為空閑盤區(qū)建立一張鏈表。 Operating SystemOperating System8.2.2位示圖法位示圖法1位示圖位示圖位示圖是利用二進(jìn)制的一位來(lái)表示磁盤中一個(gè)盤塊的使利用二進(jìn)制的一位來(lái)表示磁盤中一個(gè)盤塊的

34、使用情況。用情況。當(dāng)其值為“0”時(shí)，表示對(duì)應(yīng)的盤塊空閑；為“1”時(shí)，表示已分配。有的系統(tǒng)把“0”作為盤塊已分配的標(biāo)志，把“1”作為空閑標(biāo)志。(它們?cè)诒举|(zhì)上是相同的，都是用一位的兩種狀態(tài)來(lái)標(biāo)志空閑和已分配兩種情況。)磁盤上的所有磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)，盤塊都有一個(gè)二進(jìn)制位與之對(duì)應(yīng)，這樣，由所有盤塊所對(duì)應(yīng)的位構(gòu)成一個(gè)集合，稱為位示圖。通常可用m n個(gè)位數(shù)來(lái)構(gòu)成位示圖，并使m n等于磁盤的總塊數(shù)，如圖8-10所示。 位示圖也可描述為一個(gè)二維數(shù)組map【m，n】：Var map: array of bit； Operating SystemOperating System圖8-10位

35、示圖 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 1 1 0 0 0 1 1 1 0 0 1 0 0 1 1 0 2 0 0 0 1 1 1 1 1 1 0 0 0 0 1 1 1 3 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 4 16 Operating SystemOperating System2盤塊的分配盤塊的分配根據(jù)位示圖進(jìn)行盤塊分配時(shí)，可分三步進(jìn)行：(1) 順序掃描位示圖，從中找出一個(gè)或一組其值為“0”的二進(jìn)制位(“0”表示空閑時(shí))。(2) 將所找到的一個(gè)或一組二進(jìn)制位轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)。假定找到的其值為“0”的二進(jìn)制

36、位位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算： b = n(i - 1) + j 式中，n代表每行的位數(shù)。 (3) 修改位示圖，令mapi,j=1。 Operating SystemOperating System3盤塊的回收盤塊的回收盤塊的回收分兩步：(1) 將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。轉(zhuǎn)換公式為： i = (b - 1)DIV n + 1j = (b - 1)MOD n + 1 Operating SystemOperating System(2) 修改位示圖。令mapi,j =0。這種方法的主要優(yōu)點(diǎn)是，從位示圖中很容易找到一個(gè)或一組相鄰接的空閑盤塊。例如，

37、我們需要找到6個(gè)相鄰接的空閑盤塊，這只需在位示圖中找出6個(gè)其值連續(xù)為“0”的位即可。此外，由于位示圖很小，占用空間少，因而可將它保存在內(nèi)存中，進(jìn)而使在每次進(jìn)行盤區(qū)分配時(shí)，無(wú)需首先把盤區(qū)分配表讀入內(nèi)存，從而節(jié)省了許多磁盤的啟動(dòng)操作。因此，位示圖常用于微型機(jī)和小型機(jī)中，如CP/M、Apple-DOS等OS中。 Operating SystemOperating System8.2.3成組鏈接法成組鏈接法1空閑盤塊的組織空閑盤塊的組織(1) 空閑盤塊號(hào)?？臻e盤塊號(hào)棧用來(lái)存放當(dāng)前可用的一組空閑盤塊的盤塊號(hào)(最多含最多含100個(gè)號(hào)個(gè)號(hào))，以及棧中尚有的空閑盤塊號(hào)數(shù)棧中尚有的空閑盤塊號(hào)數(shù)N。順便指出，N還

38、兼作棧頂指針用。例如，當(dāng)N=100時(shí)，它指向S.free(99)。由于棧是臨界資源，每次只允許一個(gè)進(jìn)程去訪問(wèn)，故系統(tǒng)為棧設(shè)置了一把鎖。圖8-11左部示出了空閑盤塊號(hào)棧的結(jié)構(gòu)。其中，S.free(0)是棧底，棧滿時(shí)的棧頂為S.free(99)。 Operating SystemOperating System圖8-11空閑盤塊的成組鏈接法 1004003993013001003002992022012991004003992013019907999790179007899780179997901空閑盤塊號(hào)棧S.free019899Operating SystemOperating System(

39、2) 文件區(qū)中的所有空閑盤塊被分成若干個(gè)組，比如，將每每100個(gè)盤塊作為一組個(gè)盤塊作為一組。假定盤上共有10 000個(gè)盤塊，每塊大小為1 KB，其中第2017999號(hào)盤塊用于存放文件，即作為文件區(qū)，這樣，該區(qū)的最末一組盤塊號(hào)應(yīng)為79017999；次末組為78017900；第二組的盤塊號(hào)為301400；第一組為201300，如圖 8-11右部所示。(3) 將每一組含有的盤塊總數(shù)將每一組含有的盤塊總數(shù)N和該組所有的盤塊號(hào)記和該組所有的盤塊號(hào)記入其前一組的第一個(gè)盤塊的入其前一組的第一個(gè)盤塊的S.free(0)S.free(99)中中。這樣，由各組的第一個(gè)盤塊可鏈成一條鏈。 Operating Sys

40、temOperating System(4) 將第一組的盤塊總數(shù)和所有的盤塊號(hào)記入空閑盤塊號(hào)棧中，作為當(dāng)前可供分配的空閑盤塊號(hào)。(5) 最末一組只有99個(gè)盤塊，其盤塊號(hào)分別記入其前一組的S.free(1) S.free(99)中，而在S.free(0)中則存放“0”，作為空閑盤塊鏈的結(jié)束標(biāo)志。(注：最后一組的盤塊數(shù)應(yīng)為99，不應(yīng)是100，因?yàn)檫@是指可供使用的空閑盤塊，其編號(hào)應(yīng)為(199)，0號(hào)中放空閑盤塊鏈的結(jié)尾標(biāo)志。) Operating SystemOperating System2空閑盤塊的分配與回收空閑盤塊的分配與回收當(dāng)系統(tǒng)要為用戶分配文件所需的盤塊時(shí)，須調(diào)用盤塊分配過(guò)程來(lái)完成。該過(guò)程首先檢查空