外存分配方式

1、6.3 外存的分配方式 為文件分配外存空間要考慮主要問題是怎樣才能有效地利用外存空間和如何提高對文件的訪問速度。常用的外存分配方法：連續(xù)分配（Continuous Allocation）：為每個文件分配一組相鄰接的盤塊；鏈接分配（Chained Allocation）：通過每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表（鏈接文件）；索引分配（Indexed Allocation）：為每個文件分配一個索引塊（表），再把分配給該文件的所有盤塊號都記錄在這個索引塊（盤塊號的數(shù)組）中。16.3.1. 連續(xù)分配連續(xù)分配方式采用連續(xù)分配方式時，可把邏輯文件中的記錄順序地存儲到相鄰的各

2、物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時物理文件稱作順序文件；為了能使系統(tǒng)找到文件存放的地址，在目錄中應(yīng)記錄該文件第一個盤塊號和文件長度如內(nèi)存的動態(tài)分區(qū)分配，隨著文件建立時的空間分配和文件刪除時的空間回收，將使磁盤空間被分割成許多小塊，這些較小的連續(xù)區(qū)（碎片）很難用來存儲文件，可以采用“緊湊”的方法，將盤上的所有文件緊靠在一起，把所有的碎片拼接成一個大片連續(xù)的存儲空間。21. 連續(xù)分配連續(xù)分配方式的優(yōu)缺點優(yōu)點順序訪問容易順序訪問速度快缺點要求有連續(xù)的存儲空間，易產(chǎn)生外部碎片, 降低外存空間的利用率必須事先知道文件的長度0123456789101112131415161718192

3、02122232425262728293031file start lengthcount 0 2 tr 15 3mail 21 6list 29 3f 7 2目 錄countfcounttrmaillist36.3.2 鏈接分配 將文件存放在多個離散的盤塊中,同一文件的盤塊鏈接成一個鏈表,消除外部碎片,顯著的提高了外存空間的利用率, 有利于文件插入和刪除,有利于文件的動態(tài)擴(kuò)充。鏈接方式可分為顯示鏈接和隱式鏈接兩種形式。1. 隱式鏈接 在文件目錄的每個目錄項中,都含有指向鏈接文件第一個盤塊和最后一個盤塊的指針,而在每個盤塊中都含有指向下一個盤塊的指針。4隱式鏈接0101234567816925

4、101112131415161718192021222324-125262728293031file start endjeep 9 25目 錄1缺點: 只適合順序訪問, 隨機(jī)訪問要從頭查找極低效?？煽啃圆? 盤塊的指針出現(xiàn)問題會導(dǎo)致鏈斷開。更多的尋道次數(shù)和尋道時間。解決方法:可將幾個盤塊組成一個簇, 減少查找指定塊的時間，且減少指針?biāo)伎臻g。（內(nèi)部碎片增大）52. 顯式鏈接把用于鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一張鏈接表（稱為文件分配表FAT- Table）中，該表整個磁盤設(shè)置一張；在表中，凡是屬于某一文件的第一個盤塊號，或者每條文件鏈的首指針對應(yīng)的盤塊號，均作為文件地址被填入相應(yīng)

5、文件的FCB的“物理地址”字段中。查找記錄在內(nèi)存中進(jìn)行，顯著提高了檢索速度，大大減少了訪問磁盤的次數(shù)。FCB20451012345FAT物理塊號6文件分配表（FAT）把用于鏈接文件各物理塊的指針，放在內(nèi)存的一張鏈接表中，該表在整個磁盤只有一張，稱為文件分配表（FAT）。一個磁盤分區(qū)能分為多少塊, 則FAT就有多少個表項01N-110N-1磁盤FAT7例：200MB硬盤，盤塊大小=1KB，共有200K個盤塊，每個盤塊在FAT表中占1個表項，F(xiàn)AT表共有200K個表項 若每個表項占2.5個字節(jié)，則FAT共占500KB=200*2.5例：12G硬盤，盤塊大小=4KB，若每個FAT表項占3個字節(jié)，F(xiàn)A

6、T表占多少字節(jié)？硬盤共有3M個盤塊，每個盤塊在FAT表中占1個表項，F(xiàn)AT表共有3M個表項，則FAT共占9M=3M*3文件分配表（FAT）86.3.3 FAT和NTFS技術(shù)文件系統(tǒng)的分類FAT文件系統(tǒng)：適用于早期的DOS和Window95，Windows98操作系統(tǒng)；NTFS（New Technology ）文件系統(tǒng)：適用于后來的WindowsNT，Windows2000，WindowsXP和vista操作系統(tǒng)。9文件系統(tǒng)的發(fā)展FAT12：適用于早期的MS-DOS操作系統(tǒng)，每個FAT表項占12位。最多4096個表項，若盤塊512K，則每個分區(qū)容量2M，支持4個邏輯分區(qū)，相應(yīng)磁盤最大容量為8M；

7、FAT16：增加了FAT表的表項到65536，可以管理最大分區(qū)空間2048M，和FAT12一樣不支持長文件名；FAT32：可以支持4294967296個FAT表項，可以管理最大磁盤空間達(dá)到2TB，但是由于文件分配表擴(kuò)大，運行速度慢；P219NTFS文件系統(tǒng)：專門為Windows NT開發(fā)，的全新的文件系統(tǒng)，它使用64位的磁盤地址；支持長文件名（255個字符以內(nèi)）全路徑名（32767個字符）；具有系統(tǒng)容錯功能；提供數(shù)據(jù)一致性；還提供文件加密、文件壓縮功能。101FAT121) 以盤塊為基本分配單位 早期MS-DOS操作系統(tǒng)所使用的是FAT12文件系統(tǒng)，每個FAT表項占12位。在FAT的每個表項中

8、存放下一個盤塊號，文件的第一個盤塊號放在自己的FCB中。 11圖6-10MS-DOS的文件物理結(jié)構(gòu) 12對于1.2 MB的軟盤，每個盤塊的大小為512 B，在每個FAT中共含有2.4 K個表項，由于每個FAT表項占12位，故FAT表占用3.6 KB的存儲空間。以盤塊為分配單位時，所允許的最大磁盤容量：由于每個FAT表項為12位，因此，在FAT表中最多允許有4096個表項，如果采用以盤塊作為基本分配單位，每個盤塊(也稱扇區(qū))的大小一般是512字節(jié)，那么，每個磁盤分區(qū)的容量為2 MB(4096512 B)。同時，一個物理磁盤支持4個邏輯磁盤分區(qū)，所以相應(yīng)的磁盤最大容量僅為8 MB。132) 簇的基

9、本概念為了適應(yīng)磁盤容量不斷增大的需要，在進(jìn)行盤塊分配時，不再以盤塊而是以簇(cluster)為基本單位。簇是一組連續(xù)的扇區(qū)，在FAT中它是作為一個虛擬扇區(qū)，簇的大小一般是2n (n為整數(shù))個盤塊，在MS-DOS的實際運用中，簇的容量可以僅有一個扇區(qū)(512 B)、兩個扇區(qū)(1 KB)、四個扇區(qū)(2 KB)、八個扇區(qū)(4 KB)等。 一個簇應(yīng)包含扇區(qū)的數(shù)量與磁盤容量的大小直接有關(guān)。例如，當(dāng)一個簇僅有一個扇區(qū)時，磁盤的最大容量為8 MB；當(dāng)一個簇包含兩個扇區(qū)時，磁盤的最大容量可以達(dá)到16 MB；當(dāng)一個簇包含了八個扇區(qū)時，磁盤的最大容量便可達(dá)到64 MB。14以簇作為基本的分配單位所帶來的最主要的好

10、處是，能適應(yīng)磁盤容量不斷增大的情況。值得注意的是，使用簇作為基本的分配單位雖可減少FAT表中的項數(shù)(在相同的磁盤容量下，F(xiàn)AT表的項數(shù)是與簇的大小成反比的)。這一方面會使FAT表占用更少的存儲空間，并減少訪問FAT表的存取開銷，提高文件系統(tǒng)的效率；但這也會造成更大的簇內(nèi)零頭(它與存儲器管理中的頁內(nèi)零頭相似)。 153) FAT12存在的問題FAT12對所允許的磁盤容量存在著嚴(yán)重的限制，通常只能是數(shù)十兆字節(jié)，雖然可以用繼續(xù)增加簇的大小來提高所允許的最大磁盤容量，但隨著支持的硬盤容量的增加，相應(yīng)的簇內(nèi)碎片也將隨之成倍地增加。它只能支持8+3格式的文件名。 162FAT16FAT12表最多只允許40

11、96個表項，亦即最多只能將一個磁盤分區(qū)分為4096個簇。隨著磁盤容量的增加，必定會引起簇的大小和簇內(nèi)碎片也隨之增加。解決方法：應(yīng)增加FAT表的寬度，將FAT表的寬度增至16位，最大表項數(shù)將增至65536個，此時便能將一個磁盤分區(qū)分為65 536(216)個簇。具有16位表寬的FAT表稱為FAT16。在FAT16的每個簇中可以有的盤塊數(shù)為4、8、16、32直到64，由此得出FAT16可以管理的最大分區(qū)空間為216 64 512 = 2048 MB=2GB。 173FAT32FAT32是FAT系列文件系統(tǒng)的最后一個產(chǎn)品。每一簇在FAT表中的表項占據(jù)4字節(jié)(232)，F(xiàn)AT表可以表示4 294 96

12、7 296項，即FAT32允許管理比FAT16更多的簇。這樣就允許在FAT32中采用較小的簇，F(xiàn)AT32的每個簇都固定為4 KB，即每簇用8個盤塊代替FAT16的64個盤塊，每個盤塊仍為512字節(jié)，F(xiàn)AT32分區(qū)格式可以管理的單個最大磁盤空間大到4 KB232 = 2 TB。三種FAT類型的最大分區(qū)以及所對應(yīng)的塊的大小如圖6-11所示。 18圖6-11 FAT中簇的大小與最大分區(qū)的對應(yīng)關(guān)系 194NTFSNTFS文件系統(tǒng)：專門為Windows NT開發(fā)，的全新的文件系統(tǒng)，它使用64位的磁盤地址；支持長文件名（255個字符以內(nèi)）全路徑名（32767個字符）；具有系統(tǒng)容錯功能；提供數(shù)據(jù)一致性；還提

13、供文件加密、文件壓縮功能。206.3.4. 索引分配鏈接方式存在問題（1）不能支持高效直接存?。?）FAT需占用較大的內(nèi)存空間。1. 單級索引分配：為每個文件分配一個集中存放的索引塊(表),包含文件的所有物理塊號，因而索引塊實質(zhì)就是磁盤塊地址數(shù)組,其中第i項存放指向文件的第i塊盤塊號。在該文件的目錄項中存儲了指向該索引塊的指針。21012345678910111213141516171819202122232425262728293031file 塊序號jeep 19目 錄91611025-1-1-119索引表索引分配方式支持直接存取。22優(yōu)點：避免了連續(xù)空間分配存在的外部碎片問題和文件長度受

14、限制的問題，便于文件的增、刪、改。支持對任何一個文件塊的直接訪問。缺點：由于索引塊的分配增加了系統(tǒng)存儲空間的開銷。每個文件都要單獨分配一個索引塊，小文件不適合。另外，存取文件需要兩次訪問外存首先要讀取索引塊的內(nèi)容，然后再訪問具體的磁盤塊，因而降低了文件的存取速度。 232. 多級索引分配 對于大文件，當(dāng)分配的盤塊號已裝滿一個索引塊時，必須另分配索引塊，各索引塊通過指針連結(jié)起來，文件太大索引塊太多時，檢索索引塊將是低效的，此時應(yīng)為這些索引塊再建立一級索引，形成兩級索引，必要時還可建立更多級的索引分配方式。24兩級索引分配：適用于文件太大、索引太多的情況。360主索引7401125二級索引磁盤空間

15、105106254360356357740985112501210510635635725498525如果每個盤塊的大小為1 KB，每個盤塊號占4個字節(jié)，則在一個索引塊中可存放256個盤塊號。這樣，在兩級索引時， 最多可包含的存放文件的盤塊的盤塊號總數(shù)N = 256 256 = 64 K個盤塊號。由此可得出結(jié)論: 采用兩級索引時，所允許的文件最大長度為64 MB。倘若盤塊的大小為4 KB，在采用單級索引時所允許的最大文件長度為4 MB；而在采用兩級索引時所允許的最大文件長度可達(dá)4 GB。 263. 混合索引分配方式索引分配方式的索引塊花費較多空間,小文件索引塊利用率更低。UNIX用混合索引模式

16、避免此缺點。即將多種索引分配方式相結(jié)合而形成的一種分配方式。每個文件的索引結(jié)點含13個地址項 i.addr(0) i.addr(12), 前10項存放直接地址(物理塊號),假如盤塊大小為4KB，當(dāng)文件不大于40KB時，可從直接地址項得到文件所有的盤塊號；若文件大于40kB，則用i.addr(10)指向單級索引塊進(jìn)行一次間接尋址,每個盤塊號占4個字節(jié)，該塊中最多可放1k個物理塊號,文件可長達(dá)4MB; 還可用 i.addr(11) 和 i.addr(12) 作為二次和三次間接尋址, 文件最大長度分別可達(dá)4GB和4TB。27模式擁有者時間戳大小塊數(shù)量節(jié)點(直接塊)一級間接塊二級間接塊三級間接塊數(shù)據(jù)塊

17、數(shù)據(jù)塊一次間接地址二次間接地址數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊地址數(shù)據(jù)塊地址數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊數(shù)據(jù)塊直接地址：提高文件的檢索速度；一次間接地址：針對大中型文件，允許文件長達(dá)4M；多次間接地址：二次間接地址方式，支持文件長度可達(dá)4GB，三次間接地址，支持文件長度可達(dá)4TB。28題型分析：1、混合索引下計算最大文件這類題目中，混合索引一般包括若干個直接索引、一個一級間接索引和一個二級間接索引項。計算步驟如下：步驟一：計算直接索引對應(yīng)的空間，直接索引項個數(shù)*物理塊大??；步驟二：計算一級間接索引對應(yīng)的空間，(物理塊大小/每個索引項占用的字節(jié)) *物理塊大??；步驟三：計算二級間接索引對應(yīng)的空間，(物理塊大小/每

18、個索引項占用的字節(jié))2*物理塊大小；步驟四：將上述各步驟計算所得空間相加，即得最大文件大小。說明：對于n級間接索引，其對應(yīng)的空間為(物理塊大小/每個索引項占用的字節(jié))n *物理塊大小。292、給定文件的實際大小，計算其實際占用磁盤空間文件實際占用磁盤空間大小：（數(shù)據(jù)所需的物理塊+索引所需的物理塊）*物理塊大小。設(shè)每塊可以存儲的索引項個數(shù)為k，則k=(物理塊大小/每個索引項占用的字節(jié))。步驟一：計算文件數(shù)據(jù)部分理論所需塊數(shù)n，。步驟二：首先使用直接索引，直接索引不產(chǎn)生索引塊；計算直接索引之外的數(shù)據(jù)塊m1=n-直接索引項個數(shù)。步驟三：如果m10，則需要一個一級間接索引，索引需要1個索引塊；計算一級

19、間接索引之外的數(shù)據(jù)塊m2=m1-k。30步驟四：如果m20，則需要一個二級間接索引，如果m20，則需要一個一級間接索引，索引需要1個索引塊；計算一級間接索引之外的數(shù)據(jù)塊m2=65528-512=65016。步驟四：m20，則需要一個二級間接索引，m2=k2，索引需要 個索引塊。步驟五：文件實際占用磁盤空間大?。海?5536+1+128）*2K128.25M。343、指定要讀取一個文件中的具體位置的內(nèi)容，計算需要訪問磁盤的次數(shù)：需要訪問磁盤的次數(shù)=需要訪問的索引塊數(shù)（每塊訪問磁盤1次）+1個數(shù)據(jù)塊（訪問磁盤1次）。步驟一：計算要讀取的內(nèi)容所在的物理數(shù)據(jù)塊號；步驟二：確定該塊屬于哪種索引，是直接索

20、引、一級間接索引還是二級間接索引；步驟三：確定需要訪問的索引塊數(shù)，直接索引為0，一級間接索引為1，二級間接索引為2；步驟四：需要訪問磁盤的次數(shù)=需要訪問的索引塊數(shù)（每塊訪問磁盤1次）+1個數(shù)據(jù)塊（訪問磁盤1次）。35【例】在UNIX操作系統(tǒng)中，給文件分配外存空間采用的是混合索引分配方式，UNIX系統(tǒng)中的某個文件的索引結(jié)點指示出了為該文件分配的物理塊的尋找方法。在該索引結(jié)點中，有10個直接塊（每個直接塊都直接指向一個數(shù)據(jù)塊），有1個一級間接塊、1個二級間接塊以及1個三級間接塊，間接塊指向的是一個索引塊，每個索引塊和數(shù)據(jù)塊的大小均為4KB，而UNIX系統(tǒng)中地址所占空間為4B（指針大小為4B），假設(shè)

21、以下問題都建立在該索引結(jié)點已經(jīng)在內(nèi)存中的前提下。現(xiàn)請回答：（1）文件的大小為多大時可以只用到索引結(jié)點的直接塊？（2）該索引結(jié)點能訪問到的地址空間大小總共為多大？（小數(shù)點后保留2位）（3）若要讀取一個文件的第10 000B的內(nèi)容，需要訪問磁盤多少次？（4）若要讀取一個文件的第10MB的內(nèi)容，需要訪問磁盤多少次？36【分析】對于第1小題，當(dāng)文件大小小于等于所有直接索引所引導(dǎo)的物理數(shù)據(jù)塊之和時，可以只用到索引結(jié)點的直接塊；對于第2小題，根據(jù)題型二中混合索引下計算最大文件的解題思路進(jìn)行解答；對于第3、4小題，根據(jù)題型三中的解題思路進(jìn)行解答。解：（1）直接塊為10個，數(shù)據(jù)塊的大小為4KB，10*4K=4

22、0K，因此，當(dāng)文件大小小于等于40K時，可以只用到索引結(jié)點的直接塊。（2）步驟一：計算直接索引對應(yīng)的空間，10*4K=40K；步驟二：計算一級間接索引對應(yīng)的空間，(4*1024/4) *4K=4M；步驟三：計算二級間接索引對應(yīng)的空間，(4*1024/4)2*4K=4G；步驟四：計算三級間接索引對應(yīng)的空間，(4*1024/4)3*4K=4TG；步驟五：將上述各步驟計算所得空間相加，即得最大文件大?。?0K+4M+4G+4TG4TG。37（3）步驟一：計算要讀取的內(nèi)容所在的物理數(shù)據(jù)塊號：10 000B/(4*1024B)2.44，2號塊，即第3塊；步驟二：第3塊屬于直接索引；步驟三：確定需要訪問的

23、索引塊數(shù)，直接索引為0；步驟四：需要訪問磁盤的次數(shù)=需要訪問的索引塊數(shù)（每塊訪問磁盤1次）+1個數(shù)據(jù)塊（訪問磁盤1次），即0+1=1。（4）步驟一：計算要讀取的內(nèi)容所在的物理數(shù)據(jù)塊號：10 *1024K/4K=2560，2560號塊，即第2561塊；步驟二：確定該塊屬于哪種索引，直接索引有10塊、一級間接索引有1024（即，4*1024/4）塊、二級間接索引有10242塊，可見，2560在直接索引和一級間接索引之外且在二級間接索引范圍內(nèi)，因此該塊屬于二級間接索引；步驟三：確定需要訪問的索引塊數(shù)，二級間接索引為2；步驟四：需要訪問磁盤的次數(shù)=需要訪問的索引塊數(shù)（每塊訪問磁盤1次）+1個數(shù)據(jù)塊（訪

24、問磁盤1次），即2+1=3。38作業(yè)：1、存放在某個磁盤上的文件系統(tǒng)采用混合索引分配方式，其FCB中共有13個地址項，第0到9個地址項為直接地址，第10個地址項為一次間接地址，第11個地址項為二次間接地址。如果每個盤塊的大小為512字節(jié)，若盤塊號需用3個字節(jié)來描述，而每個盤塊最多存放170個盤塊地址，則（1）該文件系統(tǒng)允許文件的最大長度是多少？（2）將文件的字節(jié)偏移量5000、15000、150000轉(zhuǎn)換為物理塊號和塊內(nèi)偏移量。（3）假設(shè)某個文件的FCB已在內(nèi)存，但其他信息均在外存，為了訪問該文件中某個位置的內(nèi)容，最少需要訪問幾次磁盤？最多需要訪問幾次磁盤？39思考題： 一個文件系統(tǒng)中有一個20MB大文件和一個