外存的分配方式課件

第六章

文

件

管

理16.3.1.連續(xù)分配連續(xù)分配方式采用連續(xù)分配方式時，可把邏輯文件中的記錄順序地存儲到相鄰的各物理盤塊中，這樣所形成的文件結構稱為順序文件結構，此時物理文件稱作順序文件；為了能使系統找到文件存放的地址，在目錄中應記錄該文件第一個盤塊號和文件長度如內存的動態(tài)分區(qū)分配，隨著文件建立時的空間分配和

文件刪除時的空間回收，將使磁盤空間被分割成許多小

塊，這些較小的連續(xù)區(qū)（碎片）很難用來存儲文件，可

以采用“緊湊”的方法，將盤上的所有文件緊靠在一起，把所有的碎片拼接成一個大片連續(xù)的存儲空間。第六章

文

件

管

理1.連續(xù)分配連續(xù)分配方式的優(yōu)缺點優(yōu)點順序訪問容易順序訪問速度快缺點要求有連續(xù)的存儲空間，易產生外部碎片,降低外存空間的利用率必須事先知道文件的長度012345678910111213141516171819202122232425262728293031filecount2start

length0

2tr153mail216list293f72目錄fcounttrmaillist第六章

文

件

管

理36.3.2鏈接分配將文件存放在多個離散的盤塊中,同一文件的盤塊鏈接成一個鏈表,消除外部碎片,顯著的提高了外存空間的利用率,

有利于文件插入和刪除,有利于文件的動態(tài)擴充。鏈接方式可分為顯示鏈接和隱式鏈接兩種形式。1.

隱式鏈接在文件目錄的每個目錄項中,都含有指向鏈接文件第一個盤塊和最后一個盤塊的指針,而在每個盤塊中都含有指向下一個盤塊的指針。第六章

文

件

管

理filejeepstart

end9

25目錄隱式鏈接0110234567891610251112131415161171819202122232425-1262728293031缺點:只適合順序訪問,隨機訪問要從頭查找極低效?？煽啃圆?盤塊的指針出現問題會導致鏈斷開。更多的尋道次數和尋道時間。解決方法:可將幾個盤塊組成一個簇,減少查找指定塊的時間，且減少指針所占空間。（內部碎片增大）4第六章

文

件

管

理2.顯式鏈接把用于鏈接文件各物理塊的指針，顯式地存放在內存的一張鏈接表（稱為文件分配表FAT-File

Allocation

Table）中，該表整個磁盤設置一張；在表中，凡是屬于某一文件的第一個盤塊號，或者每條文件鏈的首指針對應的盤塊號，均作為文件地址被填入相應文件的FCB的“物理地址”字段中。查找記錄在內存中進行，顯著提高了檢索速度，大大減少了訪問磁盤的次數。2FCB0451012345FAT5物理塊號第六章

文

件

管

理文件分配表（FAT）把用于鏈接文件各物理塊的指針，放在內存的一

張鏈接表中，該表在整

個磁盤只有一張，稱為

文件分配表（FAT）。一個磁盤分區(qū)能分為多少塊,則FAT就有多少個表項N-160

01

1N-1磁盤FAT第六章

文

件

管

理7例：200MB硬盤，盤塊大小=1KB，共有200K個盤塊，每個盤塊在FAT表中占1個表項，FAT表共有200K個表項若每個表項占2.5個字節(jié)，則FAT共占500KB=200*2.5例：12G硬盤，盤塊大小=4KB，若每個FAT表項占3個字節(jié)，

FAT表占多少字節(jié)？硬盤共有3M個盤塊，每個盤塊在FAT表中占1個表項，FAT表共有3M個表項，則FAT共占9M=3M*3文件分配表（FAT）第六章

文

件

管

理6.3.3

FAT和NTFS技術文件系統的分類FAT文件系統：適用于

Windows98操作系統；8期的DOS和Window95，NTFS（New

Technology

File

System）文件系統：適用于后來的WindowsNT，Windows2000，WindowsXP和vista操作系統。第六章

文

件

管

理文件系統的發(fā)展–FAT12：適用于期的MS-DOS操作系統，每個FAT表項占12位。最多4096個表項，若盤塊512K，則每個分區(qū)容量2M，支持4個邏輯分區(qū)，相應磁盤最大容量為8M；–FAT16：增加了FAT表的表項到65536，可以管理最大分區(qū)空間2048M，和FAT12一樣不支持長文件名；–FAT32：可以支持4294967296個FAT表項，可以管理最大磁盤空間達到2TB，但是由于文件分配表擴大，運行速度慢；

P219–NTFS文件系統：專門為Windows

NT開發(fā)，的全新的文件系統，它使用64位的磁盤地址；支持長文件名（255個字符以內）全路徑名（32767個字符）；具有系統容錯功能；提供數據一致性；還提供文件加密、文件壓縮功能。9第六章

文

件

管

理1．FAT121)以盤塊為基本分配單位期MS-DOS操作系統所使用的是FAT12文件系統，每個

FAT表項占12位。在FAT的每個表項中存放下一個盤塊號，文件的第一個盤塊號放在自己的FCB中。10第六章

文

件

管

理圖6-10MS-DOS的文件物理結構11第六章

文

件

管

理對于1.2

MB

的軟盤，每個盤塊的大小為

FAT

中共含有2.4

K

個表項，由于每個

FAT表占用3.6

KB的存儲空間。12512

B

，在每FAT

表項占以盤塊為分配單位時，所允許的最大磁盤容量：由于每個FAT表項為12位，因此，在FAT表中最多允許有

4096個表項，如果采用以盤塊作為基本分配單位，每個盤塊

(也稱扇區(qū))的大小一般是512字節(jié)，那么，每個磁盤分區(qū)的容量為

2

MB

(4096

×

512 B)

。同時，一個物理磁盤支持4

個輯磁盤分區(qū)，所以相應的磁盤最大容量僅為8

MB。第六章

文

件

管

理2)

簇的基本概念為了適應磁盤容量不斷增大的需要，在進行盤塊分配時，不再以盤塊而是以簇(cluster)為基本單位。簇是一組連續(xù)的

扇區(qū)，在

FAT 中它是作為一個虛擬扇區(qū)，

簇的大小一般(n為整數)個盤塊，在MS-DOS的實際運用中，簇的容量可以僅

有一個扇區(qū)(512

B)

、兩個扇區(qū)(1

KB)

、四個扇區(qū)(2

KB)

、八個扇區(qū)(4

KB)等。一個簇應包含扇區(qū)的數量與磁盤容量的大小直接有關。例如，當一個簇僅有一個扇區(qū)時，磁盤的最大容量為

8

MB當一個簇包含兩個扇區(qū)時，磁盤的最大容量可以達到

16

MB

；當一個簇包含了八個扇區(qū)時，磁盤的最大容量便可達到64

MB。13第六章

文

件

管

理以簇作為基本的分配單位所帶來的最主要的好處是，能

適應磁盤容量不斷增大的情況。值得注意的是，使用簇作為

基本的分配單位雖可減少FAT表中的項數(在相同的磁盤容量下，FAT表的項數是與簇的大小成反比的)。這一方面會使

FAT表占用更少的存儲空間，并減少訪問FAT表的存取開銷，提高文件系統的效率；但這也會造成更大的簇內零頭(它與存儲器管理中的頁內零頭相似)。14第六章

文

件

管

理3)

FAT12存在的問題FAT12對所允許的磁盤容量存在著嚴重的限制，通常只能是數十兆字節(jié)，雖然可以用繼續(xù)增加簇的大小來提高所允許的最大磁盤容量，但隨著支持的硬盤容量的增加，相應的簇內碎片也將隨之成倍地增加。它只能支持8+3格式的文件名。15第六章

文

件

管

理2．FAT16FAT12表最多只允許4096個表項，亦即最多只能將一個磁盤分區(qū)分為4096個簇。隨著磁盤容量的增加，必定會引起簇的大小和簇內碎片也隨之增加。解決方法：應增加FAT表的寬度，將FAT表的寬度增至16位，最大表項數將增至65536個，此時便能將一個磁盤分區(qū)分為65536(216)個簇。具有16位表寬的FAT表稱為FAT16。在FAT16的每個簇中可以有的盤塊數為4、8、16、32直到64，由此得出FAT16可以管理的最大分區(qū)空間為216

×

64

×

512

=2048

MB=2GB。16第六章

文

件

管

理3．FAT32FAT32是FAT系列文件系統的最后一個產品。每一簇在

FAT表中的表項占據4字節(jié)(232)，FAT表可以表示4

294

967296項，即FAT32允許管理比FAT16更多的簇。這樣就允許在

FAT32中采用較小的簇，FAT32的每個簇都固定為4KB，即每簇用8個盤塊代替FAT16的64個盤塊，每個盤塊仍為512字節(jié)，FAT32分區(qū)格式可以管理的單個最大磁盤空間大到4KB×232

=2

TB。三種FAT類型的最大分區(qū)以及所對應的塊的大小如圖6-11所示。17第六章

文

件

管

理圖6-11

FAT中簇的大小與最大分區(qū)的對應關系18第六章

文

件

管

理4．NTFSNTFS

文件系統：專門為Windows

NT

開發(fā)，的全新的文件系統，它使用64位的磁盤地址；支持長文件名（255個字符以內）全路徑名（32767個字符）；具有系統容錯功能；提供數據一致性；還提供文件加密、文件壓縮功能。19第六章

文

件

管

理206.3.4.索引分配鏈接方式存在問題（1）不能支持高效直接存?。?）FAT需占用較大的內存空間。1.

單級索引分配：為每個文件分配一個集中存放的索引塊(表),包含文件的所有物理塊號，因而索引塊實質就是磁盤塊地址數組,其中第i項存放指向文件的第i塊盤塊號。在該文件的目錄項中存儲了指向該索引塊的指針。第六章

文

件

管

理012345678910111213141516171819202122232425262728293031目錄file

塊序號jeep

1991611025-1-1-12119索引表索引分配方式支持直接存取。第六章

文

件

管

理優(yōu)點：避免了連續(xù)空間分配存在的外部碎片問題和文件長度受限制的問題，便于文件的增、刪、改。支持對任何一個文件塊的直接訪問。缺點：由于索引塊的分配增加了系統存儲空間的開銷。每個文件都要單獨分配一個索引塊，小文件不適合。另外，存取文件需要兩次訪問外存——首先要讀取索引塊的內容，然后再訪問具體的磁盤塊，因而降低了文件的存取速度。22第六章

文

件

管

理232.多級索引分配對于大文件，當分配的盤塊號已裝滿一個索引塊時，必須另分配索引塊，各索引塊通過指針連

結起來，文件太大索引塊太多時，檢索索引塊將

是低效的，此時應為這些索引塊再建立一級索引，形成兩級索引，必要時還可建立更多級的索引分

配方式。第六章

文

件

管

理兩級索引分配：適用于文件太大、索引太多的情況。360主索引740……1125二級索引360磁盤空間105106254356357740985…1125……………01210510635635725498524第六章文件管理如果每個盤塊的大小為1

KB，每個盤塊號占4個字節(jié)，則在一個索引塊中可存放256個盤塊號。這樣，在兩級索引時，最多可包含的存放文件的盤塊的盤塊號總數N=256×256=64

K個盤塊號。由此可得出結論:采用兩級索引時，所允許的文件最大長度為64

MB。倘若盤塊的大小為4

KB，在采用單級索引時所允許的最大文件長度為4

MB；而在采用兩級索引時所允許的最大文件長度可達4

GB。25第六章

文

件

管

理3.混合索引分配方式索引分配方式的索引塊花費較多空間,小文件索引塊利用率更低。UNIX用混合索引模式避免此缺點。即將多種索引分配方式相結合而形成的一種分配方式。每個文件的索引結點含13個地址項

i.addr(0)~

i.addr(12),前10項存放直接地址(物理塊號),假如盤塊大小為4KB，當文件不大于40KB時，可從直接地址項得到文件所有的盤塊號；若文件大于40kB，則用i.addr(10)指向單級索引塊進行一次間接尋址,每個盤塊號占4個字節(jié)，該塊中最多可放1k個物理塊號,文件可長達4MB; 還可用

i.addr(11)

和

i.addr(12) 作為二次和三次間接尋址,

文件最大長度分別可達4GB和4TB。26第六章

文

件

管

理模式擁有者時間戳大小塊數量ｉ節(jié)點(直接塊)一級間接塊二級間接塊三級間接塊數據塊數據塊一次間接地址二次間接地址數據塊數據塊數據塊數據塊地址數據塊地址數據塊數據塊數據塊數據塊……直接地址：提高文件的檢索速度；一次間接地址：針對大中型文件，允許文件長達4M；多次間接地址：二次間接地址方式，支持文件長度可達4GB，三次間接地址，支持文件長度可達4TB。27第六章

文

件

管

理題型分析：1、混合索引下計算最大文件這類題目中，混合索引一般包括若干個直接索引、一個一級間接索引和一個二級間接索引項。計算步驟如下：步驟一：計算直接索引對應的空間，直接索引項個數*物理塊大??；步驟二：計算一級間接索引對應的空間，(物理塊大小/每個索引項占用的字節(jié)) *物理塊大??；步驟三：計算二級間接索引對應的空間，(物理塊大小/每個索引項占用的字節(jié))2*物理塊大??；步驟四：將上述各步驟計算所得空間相加，即得最大文件大小。說明：對于n級間接索引，其對應的空間為(物理塊大小/每個索引項占用的字節(jié))n

*物理塊大小。28第六章

文

件

管

理2、給定文件的實際大小，計算其實際占用磁盤空間文件實際占用磁盤空間大?。海〝祿璧奈锢韷K+索引所需的物理塊）*物理塊大小。

設每塊可以存儲的索引項個數為k，則k=(物理塊大小/每個索引項占用的字節(jié))。步驟一：計算文件數據部分理論所需塊數n，。步驟二：首先使用直接索引，直接索引不產生索引塊；計算直接索引之外的數據塊m1=n-直接索引項個數。步驟三：如果m1>0，則需要一個一級間接索引，索引需要1個索引塊；計算一級間接索引之外的數據塊m2=m1-k。29第六章

文

件

管

理步驟四：如果m2>0，則需要一個二級間接索引，如果m2<=k2，索引需要 個索引塊；否則索引需要（1+k）個索引塊，然后，繼續(xù)計算二級間接索引之外的數據塊m3=m2-k2。說明：一般題目在一個二級間接索引范圍內，如果超出一個二級間接索引，則對m3繼續(xù)做處理，可以采用再增加幾個二級間接索引的方法，也可以采用三級間接索引。步驟五：文件實際占用磁盤空間大?。海〝祿璧奈锢韷K+索引所需的物理塊）*物理塊大小。索引所需的物理塊為一級間接索引和二級間接索引所需的物理塊之和。30第六章

文

件

管

理【例】某操作系統的文件管理采用直接索引和多級索引混合方式，文件索引表共有10項，其中前8項是直接索引項，第9項是一次間接索引項，第10項是二次間接索引項，假定物理塊31的大小是2K，每個索引項占用4個字節(jié)，試問：工2004】（1）該文件系統中最大的文件可以達到多大？【華南理（2）假定一個文件的實際大小是128M字節(jié)，該文件實際占用磁盤空間多大（包括間接索引塊）？第六章

文

件

管

理解：（1）本題目中，混合索引包括8個直接索引、一個一級間接索引和一個二級間接索引項。步驟一：計算直接索引對應的空間，8*2K=16K；步驟二：計算一級間接索引對應的空間，(2*1024/4)*2K=1M；步驟三：計算二級間接索引對應的空間，(2*1024/4)*(2*1024/4)

*2K=512M；步驟四：將上述各步驟計算所得空間相加，即得最大文件大?。?6K+1M+512M≈513M。32第六章

文

件

管

理（2）設每塊可以存儲的索引項個數為k，則k=2*1024/4=512。步驟一：計算文件數據部分理論所需塊數n，n=128*1024/2=65536；步驟二：首先使用直接索引，直接索引不產生索引塊；計算直接索引之外的數據塊m1=65536-8=65528。步驟三：m1>0，則需要一個一級間接索引，索引需要1個索引塊；計算一級間接索引之外的數據塊m2=65528-512=65016。步驟四：m2>0，則需要一個二級間接索引，m2<=k2，索引需要 個索引塊。步驟五：文件實際占用磁盤空間大?。海?5536+1+128）*2K≈128.25M。33第六章

文

件

管

理3、指定要讀取一個文件中的具體位置的內容，計算需要訪問磁盤的次數：需要訪問磁盤的次數=需要訪問的索引塊數（每塊訪問磁盤

1次）+1個數據塊（訪問磁盤1次）。步驟一：計算要讀取的內容所在的物理數據塊號；步驟二：確定該塊屬于哪種索引，是直接索引、一級間接索引還是二級間接索引；步驟三：確定需要訪問的索引塊數，直接索引為0，一級間接索引為1，二級間接索引為2；步驟四：需要訪問磁盤的次數=需要訪問的索引塊數（每塊訪問磁盤1次）+1個數據塊（訪問磁盤1次）。34第六章

文

件

管

理【例】在UNIX操作系統中，給文件分配外存空間采用的是混合索引分配方式，UNIX系統中的某個文件的索引結點指示出了為該文件分配的物理塊的尋找方法。在該索引結點中，有10個直接塊（每個直接塊都直接指向一個數據塊），有1個一級間接塊、1個二級間接塊以及1個三級間接塊，間接塊指向的是一個索引塊，每個索引塊和數據塊的大小均為4KB，而UNIX系統中地址所占空間為

4B（指針大小為4B），假設以下問題都建立在該索引結點已經在內存中的前提下。現請回答：文件的大小為多大時可以只用到索引結點的直接塊？該索引結點能訪問到的地址空間大小總共為多大？（小數點后保留2位）若要讀取一個文件的第10

000B的內容，需要訪問磁盤多少次？若要讀取一個文件的第10MB的內容，需要訪問磁盤多少次？35第六章

文

件

管

理【分析】對于第1小題，當文件大小小于等于所有直接索引所引導的物理數據塊之和時，可以只用到索引結點的直接塊；對于第2小題，根據題型二中混合索引下計算最大文件的解題思路進行解答；對于第3、4小題，根據題型三中的解題思路進行解答。解：（1）直接塊為10個，數據塊的大小為4KB，10*4K=40K，因此，當文件大小小于等于40K時，可以只用到索引結點的直接塊。（2）步驟一：計算直接索引對應的空間，10*4K=40K；步驟二：計算一級間接索引對應的空間，(4*1024/4)

*4K=4M；步驟三：計算二級間接索引對應的空間，(4*1024/4)2*4K=4G；步驟四：計算三級間接索引對應的空間，(4*1024/4)3*4K=4TG；步驟五：將上述各步驟計算所得空間相加，即得最大文件大?。?0K+4M+4G+4TG≈4TG。36第六章

文

件

管

理步驟一：計算要讀取的內容所在的物理數據塊號：10

000B/(4*1024B)≈2.44，2號塊，即第3塊；步驟二：第3塊屬于直接索引；步驟三：確定需要訪問的索引塊數，直接索引為0；步驟四：需要訪問磁盤的次數=需要訪問的索引塊數（每塊訪問磁盤1次）+1個數據塊（訪問磁盤1次），即0+1=1。步驟一：計算要讀取的內容所在的物理數據塊號：10*1024K/4K=2560，2560號塊，即第2561塊；步驟二：確定該塊屬于哪種索引，直接索引有10塊、一級間接索引有

1024（即，4*1024/4）塊、二級間接索引有10242塊，可見，2560在直接索引和一級間接索引之外且在二級間接索引范圍內，因此該塊屬于二級間接索引；步驟三：確定需要訪問的索引塊數，二級間接索引為2；步驟四：需要訪問磁盤的次數=需要訪問的索引塊數（每塊訪問磁盤1次）+1個數據塊（訪問磁盤1次），即2+1=3。37第六章

文

件

管

理作業(yè)：1、存放在某個磁盤上的文件系統采用混合索引分配方式，其FCB中共有13個地址項，第0到9個地址項為直接地址，第10個地址項為一次間接地址，第11個地址項為二次間接地址。如果每個盤塊的大小為512字節(jié)，若盤塊號需用3個字節(jié)來描述，而每個盤塊最多存放170個盤塊地址，則該文件系統允許文件的最大長度是多少？將文件的字節(jié)偏移量5000、15000、150000轉換為物理塊號和塊內偏移量。假設某個文件的FCB