第8章磁盤存儲(chǔ)器的管理

1、第八章第八章 磁盤存儲(chǔ)器的管理磁盤存儲(chǔ)器的管理n重點(diǎn)重點(diǎn)n磁盤調(diào)度算法。磁盤調(diào)度算法。n外存組織的連續(xù)組織、鏈接組織、索引組織方外存組織的連續(xù)組織、鏈接組織、索引組織方式。式。n空閑空間管理的功能?？臻e空間管理的功能。n知識(shí)點(diǎn)知識(shí)點(diǎn)n掌握：磁盤調(diào)度算法、外存的組織方式。掌握：磁盤調(diào)度算法、外存的組織方式。n理解：空閑空間的管理。理解：空閑空間的管理。n了解：提高磁盤了解：提高磁盤I/O速度的途徑，提高磁盤可速度的途徑，提高磁盤可靠性的技術(shù)，數(shù)據(jù)一致性控制方法等?？啃缘募夹g(shù)，數(shù)據(jù)一致性控制方法等。第八章磁盤存儲(chǔ)器的管理 8.1磁盤存儲(chǔ)器的性能和調(diào)度磁盤存儲(chǔ)器的性能和調(diào)度8.2外存的組織方式外存的

2、組織方式8.3空閑空閑空間空間的管理的管理8.4提高磁盤提高磁盤I/O速度的途徑速度的途徑8.5提高磁盤可靠性的技術(shù)提高磁盤可靠性的技術(shù)8.6數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制 磁盤存儲(chǔ)器管理的主要任務(wù)磁盤存儲(chǔ)器管理的主要任務(wù)n為文件分配存儲(chǔ)為文件分配存儲(chǔ)空間空間n合理地組織文件的存儲(chǔ)方式，以提高合理地組織文件的存儲(chǔ)方式，以提高磁盤的訪問(wèn)磁盤的訪問(wèn)速度速度n提高磁盤存儲(chǔ)空間的利用率提高磁盤存儲(chǔ)空間的利用率n提高磁盤提高磁盤I/O速度，改善文件性能速度，改善文件性能n確保文件系統(tǒng)的確保文件系統(tǒng)的可靠性可靠性（備份）（備份）8.1 磁盤存儲(chǔ)器的性能和調(diào)度磁盤存儲(chǔ)器的性能和調(diào)度n8.1.1 磁盤性能簡(jiǎn)述磁

3、盤性能簡(jiǎn)述n8.1.2 早期的磁盤調(diào)度算法早期的磁盤調(diào)度算法n8.1.3 基于掃描的磁盤調(diào)度算法基于掃描的磁盤調(diào)度算法8.1.1 磁盤性能簡(jiǎn)述磁盤性能簡(jiǎn)述n數(shù)據(jù)的組織和格式數(shù)據(jù)的組織和格式 n磁盤磁盤包括一個(gè)或多個(gè)包括一個(gè)或多個(gè)盤片盤片，每片分，每片分2面，每面面，每面可分成若干條磁道，各磁道之間有間隙，每條可分成若干條磁道，各磁道之間有間隙，每條磁道上可存儲(chǔ)相同數(shù)目的二進(jìn)制位，磁盤磁道上可存儲(chǔ)相同數(shù)目的二進(jìn)制位，磁盤密度密度即每英寸之中所存儲(chǔ)的位數(shù)。顯然內(nèi)層磁道的即每英寸之中所存儲(chǔ)的位數(shù)。顯然內(nèi)層磁道的密度較外層磁道的密度大。密度較外層磁道的密度大。8.1.1 磁盤性能簡(jiǎn)述磁盤性能簡(jiǎn)述8.1

4、.1 磁盤性能簡(jiǎn)述磁盤性能簡(jiǎn)述8.1.1 磁盤性能簡(jiǎn)述磁盤性能簡(jiǎn)述n數(shù)據(jù)的組織和格式數(shù)據(jù)的組織和格式n盤片（盤片（1個(gè)或多個(gè)）、盤面、磁道、扇區(qū)個(gè)或多個(gè)）、盤面、磁道、扇區(qū)n扇區(qū)有扇區(qū)有標(biāo)識(shí)符字段標(biāo)識(shí)符字段和和數(shù)據(jù)字段數(shù)據(jù)字段Gap102031292293Field Gap Field Gap Gap Field Gap Field Gap17741515201774151520IDDataIDDataGap1292293Field Gap Field1774151520IDDataSectorPhysical Sector 0Physical Sector 1Physical Sector

5、29BytesSynchByteTrack#Head#Sector#Bytes 1211CRC2SynchByteDataCRC15122600 Bytes/SectorGap存儲(chǔ)相同數(shù)目存儲(chǔ)相同數(shù)目的二進(jìn)制位的二進(jìn)制位間隙間隙定界符定界符段校驗(yàn)段校驗(yàn)8.1.1 磁盤性能簡(jiǎn)述磁盤性能簡(jiǎn)述n磁盤的類型磁盤的類型n在在，所有的磁頭都被裝，所有的磁頭都被裝在一剛性磁臂中。通過(guò)這些磁頭可訪問(wèn)所有各磁道，在一剛性磁臂中。通過(guò)這些磁頭可訪問(wèn)所有各磁道，并進(jìn)行并進(jìn)行，有效地，有效地。這種結(jié)構(gòu)的磁盤主要用于這種結(jié)構(gòu)的磁盤主要用于上。上。，也被裝入磁臂中。為，也被裝入磁臂中。為能訪問(wèn)該盤面上的所有磁道，該磁頭必

6、須能移動(dòng)以能訪問(wèn)該盤面上的所有磁道，該磁頭必須能移動(dòng)以進(jìn)行尋道。可見，移動(dòng)磁頭僅能以進(jìn)行尋道?？梢姡苿?dòng)磁頭僅能以，致使其致使其；但由于其結(jié)構(gòu)簡(jiǎn)單，；但由于其結(jié)構(gòu)簡(jiǎn)單， 故仍廣故仍廣泛應(yīng)用于泛應(yīng)用于設(shè)備中。設(shè)備中。8.1.1 磁盤性能簡(jiǎn)述磁盤性能簡(jiǎn)述n磁盤訪問(wèn)時(shí)間磁盤訪問(wèn)時(shí)間n尋道時(shí)間尋道時(shí)間Tsn把磁臂把磁臂(磁頭磁頭)移動(dòng)到指定磁道上所經(jīng)歷的時(shí)移動(dòng)到指定磁道上所經(jīng)歷的時(shí)間。該時(shí)間是啟動(dòng)磁臂的時(shí)間間。該時(shí)間是啟動(dòng)磁臂的時(shí)間s與磁頭移動(dòng)與磁頭移動(dòng)n條磁道所花費(fèi)的時(shí)間之和，條磁道所花費(fèi)的時(shí)間之和， 即即Ts=mn+sn旋轉(zhuǎn)延遲時(shí)間旋轉(zhuǎn)延遲時(shí)間Tn指定扇區(qū)旋轉(zhuǎn)到磁頭下面所經(jīng)歷的時(shí)間。如：指定扇區(qū)旋

7、轉(zhuǎn)到磁頭下面所經(jīng)歷的時(shí)間。如：7200r/min 每轉(zhuǎn)每轉(zhuǎn)=60000ms/7200r=8.33ms 平均旋轉(zhuǎn)延遲平均旋轉(zhuǎn)延遲=（0+8.33)/2=4.16啟動(dòng)磁臂時(shí)間啟動(dòng)磁臂時(shí)間2ms常數(shù)，與磁盤驅(qū)常數(shù)，與磁盤驅(qū)動(dòng)器的速度有關(guān)動(dòng)器的速度有關(guān)一般：一般：0.2ms高速：高速：=0.1ms8.1.1 磁盤性能簡(jiǎn)述磁盤性能簡(jiǎn)述n磁盤訪問(wèn)時(shí)間磁盤訪問(wèn)時(shí)間n傳輸時(shí)間傳輸時(shí)間Ttn指把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)指把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間。歷的時(shí)間。 其大小與每次所讀其大小與每次所讀/寫的字節(jié)數(shù)寫的字節(jié)數(shù)b和旋轉(zhuǎn)速度有關(guān)和旋轉(zhuǎn)速度有關(guān)nr為磁盤每秒鐘的轉(zhuǎn)數(shù)；為磁盤每秒鐘的轉(zhuǎn)數(shù)

8、；N為一條磁道上的字為一條磁道上的字節(jié)數(shù)節(jié)數(shù)nT和和Tt相同，則訪問(wèn)時(shí)間相同，則訪問(wèn)時(shí)間=Ts + T+ TtrNbTt如如b=N/2，則，則T=1/(2r)=Tt可見，尋道時(shí)間可見，尋道時(shí)間TS和旋轉(zhuǎn)和旋轉(zhuǎn)延遲時(shí)間延遲時(shí)間T基本上都與所基本上都與所讀讀/寫數(shù)據(jù)的字節(jié)數(shù)無(wú)關(guān)，寫數(shù)據(jù)的字節(jié)數(shù)無(wú)關(guān)，而且它通常占據(jù)了訪問(wèn)時(shí)而且它通常占據(jù)了訪問(wèn)時(shí)間中的大部分間中的大部分目前磁盤的傳輸速率已達(dá)到目前磁盤的傳輸速率已達(dá)到80MB/s以上，數(shù)據(jù)傳輸時(shí)間所占以上，數(shù)據(jù)傳輸時(shí)間所占的比例更低?？梢?，適當(dāng)?shù)丶袛?shù)據(jù)傳輸，將有利于提高傳輸?shù)谋壤??？梢?，適當(dāng)?shù)丶袛?shù)據(jù)傳輸，將有利于提高傳輸效率效率8.1.1 磁盤

9、性能簡(jiǎn)述磁盤性能簡(jiǎn)述尋道尋道時(shí)間時(shí)間旋轉(zhuǎn)旋轉(zhuǎn)延遲延遲時(shí)間時(shí)間傳輸傳輸時(shí)間時(shí)間8.1.1 磁盤性能簡(jiǎn)述磁盤性能簡(jiǎn)述n磁盤訪問(wèn)時(shí)間磁盤訪問(wèn)時(shí)間尋道時(shí)間尋道時(shí)間: 20ms磁盤通道傳輸速率磁盤通道傳輸速率: 1MB/s轉(zhuǎn)速轉(zhuǎn)速r=3600rpm每扇區(qū)每扇區(qū)512字節(jié)字節(jié)每磁道每磁道32 扇區(qū)扇區(qū)目標(biāo)：讀目標(biāo)：讀 128k 數(shù)據(jù)數(shù)據(jù)1.尋道時(shí)間尋道時(shí)間TS：TS=m*n+S；2.旋轉(zhuǎn)延時(shí)間旋轉(zhuǎn)延時(shí)間Tr：Tr1/2r3.數(shù)據(jù)傳輸時(shí)間數(shù)據(jù)傳輸時(shí)間Tt ：Ttb/rN 訪問(wèn)時(shí)間：訪問(wèn)時(shí)間：Ta=Ts+1/2r+b/rN60*16k=960k1MB/s順序組織順序組織(208.316.7)(8.316.7)

10、7220(ms)隨機(jī)組織隨機(jī)組織(208.30.5)2567373(ms)8.1.2 早期的磁盤調(diào)度算法早期的磁盤調(diào)度算法n先來(lái)先服務(wù)先來(lái)先服務(wù)FCFS(First-Come, First Served)n根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤的先后次序進(jìn)行調(diào)度根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤的先后次序進(jìn)行調(diào)度優(yōu)點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單、公平，：簡(jiǎn)單、公平，不會(huì)出現(xiàn)請(qǐng)求長(zhǎng)期得不會(huì)出現(xiàn)請(qǐng)求長(zhǎng)期得不到滿足；不到滿足；缺點(diǎn)缺點(diǎn)：未優(yōu)化，：未優(yōu)化，平均尋道時(shí)間平均尋道時(shí)間長(zhǎng)。長(zhǎng)。8.1.2 早期的磁盤調(diào)度算法早期的磁盤調(diào)度算法n最短尋道時(shí)間優(yōu)先最短尋道時(shí)間優(yōu)先SSTF(Shortest Seek Time First) n要求訪問(wèn)的磁道與當(dāng)前

11、磁頭所在的磁道距離最要求訪問(wèn)的磁道與當(dāng)前磁頭所在的磁道距離最近。近。優(yōu)點(diǎn)優(yōu)點(diǎn)：使每次尋道時(shí)：使每次尋道時(shí)間最短；間最短；缺點(diǎn)缺點(diǎn)：不能保證平均：不能保證平均尋道時(shí)間最短；可能尋道時(shí)間最短；可能導(dǎo)致距離遠(yuǎn)的進(jìn)程總導(dǎo)致距離遠(yuǎn)的進(jìn)程總也得不到服務(wù)。也得不到服務(wù)。8.1.3 基于掃描的磁盤調(diào)度算法基于掃描的磁盤調(diào)度算法n掃描掃描(SCAN)算法算法 n進(jìn)程進(jìn)程“饑餓饑餓”現(xiàn)象現(xiàn)象nSSTF算法雖然能獲得較好的尋道性能，但卻可能導(dǎo)算法雖然能獲得較好的尋道性能，但卻可能導(dǎo)致某個(gè)進(jìn)程發(fā)生致某個(gè)進(jìn)程發(fā)生“饑餓饑餓”(Starvation)現(xiàn)象。現(xiàn)象。0501608.1.3 基于掃描的磁盤調(diào)度算法基于掃描的磁盤

12、調(diào)度算法n掃描掃描(SCAN)算法算法n算法過(guò)程算法過(guò)程n 磁臂從磁盤的一端開始移動(dòng)；磁臂從磁盤的一端開始移動(dòng)；n 向另一端移動(dòng)；向另一端移動(dòng)；n 同時(shí)當(dāng)磁頭移過(guò)每個(gè)柱面時(shí)，處理位于該柱面上同時(shí)當(dāng)磁頭移過(guò)每個(gè)柱面時(shí)，處理位于該柱面上的服務(wù)請(qǐng)求；的服務(wù)請(qǐng)求；n 當(dāng)?shù)竭_(dá)另一端時(shí)，磁頭改變移動(dòng)方向，處理繼續(xù)；當(dāng)?shù)竭_(dá)另一端時(shí)，磁頭改變移動(dòng)方向，處理繼續(xù)；n 磁頭在磁盤上來(lái)回掃描。磁頭在磁盤上來(lái)回掃描。n又稱又稱“電梯電梯”算法。算法。8.1.3 基于掃描的磁盤調(diào)度算法基于掃描的磁盤調(diào)度算法8.1.3 基于掃描的磁盤調(diào)度算法基于掃描的磁盤調(diào)度算法n循環(huán)掃描循環(huán)掃描(CSCAN)算法算法nSCAN方法的缺

13、點(diǎn)方法的缺點(diǎn)n剛移過(guò)的磁道的等待時(shí)間長(zhǎng)。剛移過(guò)的磁道的等待時(shí)間長(zhǎng)。n解決方法解決方法n規(guī)定磁頭單向移動(dòng)。減少剛移過(guò)的磁道的等規(guī)定磁頭單向移動(dòng)。減少剛移過(guò)的磁道的等待時(shí)間。待時(shí)間。8.1.3 基于掃描的磁盤調(diào)度算法基于掃描的磁盤調(diào)度算法8.1.3 基于掃描的磁盤調(diào)度算法基于掃描的磁盤調(diào)度算法nN-Step-SCAN和和FSCAN調(diào)度算法調(diào)度算法 nN-Step-SCAN算法算法n在在SSTF、 SCAN及及CSCAN幾種調(diào)度算法中，幾種調(diào)度算法中， 都可都可能出現(xiàn)磁臂停留在某處不動(dòng)的情況，稱為能出現(xiàn)磁臂停留在某處不動(dòng)的情況，稱為“磁臂粘磁臂粘著著”(Armstickiness)。nN步步SCAN

14、算法是將磁盤請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為算法是將磁盤請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為N的子隊(duì)列，磁盤調(diào)度將按的子隊(duì)列，磁盤調(diào)度將按FCFS算法依次處理這些算法依次處理這些子隊(duì)列。子隊(duì)列。 而每處理一個(gè)隊(duì)列時(shí)又是按而每處理一個(gè)隊(duì)列時(shí)又是按SCAN算法，算法，對(duì)一個(gè)隊(duì)列處理完后，再處理其他隊(duì)列。對(duì)一個(gè)隊(duì)列處理完后，再處理其他隊(duì)列。nFSCAN算法算法nFSCAN算法是算法是N步步SCAN算法的簡(jiǎn)化，算法的簡(jiǎn)化， 即其只將磁即其只將磁盤請(qǐng)求隊(duì)列分成兩個(gè)子隊(duì)列。一是由當(dāng)前所有請(qǐng)求盤請(qǐng)求隊(duì)列分成兩個(gè)子隊(duì)列。一是由當(dāng)前所有請(qǐng)求I/O的進(jìn)程形成的隊(duì)列，由磁盤調(diào)度按的進(jìn)程形成的隊(duì)列，由磁盤調(diào)度按SCAN算法進(jìn)算法進(jìn)行處理

15、。在掃描期間，新出現(xiàn)的所有請(qǐng)求行處理。在掃描期間，新出現(xiàn)的所有請(qǐng)求I/O的進(jìn)程，的進(jìn)程， 則放入另一個(gè)等待處理的請(qǐng)求隊(duì)列。則放入另一個(gè)等待處理的請(qǐng)求隊(duì)列。當(dāng)當(dāng)N值很大時(shí)，值很大時(shí)，N步掃步掃描性能接近于描性能接近于SCAN性性能；能；N=1， N步掃描性步掃描性能便退化為能便退化為FCFS8.2 外存的組織方式外存的組織方式n文件的結(jié)構(gòu)文件的結(jié)構(gòu)n文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)(File Logical Structure)。n文件的物理結(jié)構(gòu)，文件的物理結(jié)構(gòu)， 又稱為文件的存儲(chǔ)結(jié)構(gòu)，又稱為文件的存儲(chǔ)結(jié)構(gòu)， 文件在外存上的存儲(chǔ)組織形式。文件在外存上的存儲(chǔ)組織形式。n 問(wèn)題問(wèn)題n如何才能有效地利用外

16、存空間如何才能有效地利用外存空間?n如何提高對(duì)文件的訪問(wèn)速度如何提高對(duì)文件的訪問(wèn)速度?8.2 外存的組織方式外存的組織方式n外存的特點(diǎn)外存的特點(diǎn)n容量大，斷電后仍可保存信息，速度較慢，成容量大，斷電后仍可保存信息，速度較慢，成本較低本較低n兩部分組成：驅(qū)動(dòng)部分兩部分組成：驅(qū)動(dòng)部分+ +存儲(chǔ)介質(zhì)存儲(chǔ)介質(zhì)n種類很多種類很多n外存空間組織、地址與存取方式非常復(fù)雜外存空間組織、地址與存取方式非常復(fù)雜nI/O過(guò)程方式非常復(fù)雜過(guò)程方式非常復(fù)雜8.2 外存的組織方式外存的組織方式n對(duì)外存的要求對(duì)外存的要求方便、效率、安全方便、效率、安全n在讀寫外存時(shí)不涉及硬件細(xì)節(jié)，使用邏輯地址在讀寫外存時(shí)不涉及硬件細(xì)節(jié)，使

17、用邏輯地址和邏輯操作。和邏輯操作。n存取速度盡可能快，容量大且空間利用率高存取速度盡可能快，容量大且空間利用率高n外存上存放的信息安全可靠，防止來(lái)自硬件的外存上存放的信息安全可靠，防止來(lái)自硬件的故障和他人的侵權(quán)。故障和他人的侵權(quán)。n方便地共享，動(dòng)態(tài)擴(kuò)縮，攜帶拆卸，了解存儲(chǔ)方便地共享，動(dòng)態(tài)擴(kuò)縮，攜帶拆卸，了解存儲(chǔ)情況和使用情況。情況和使用情況。n以盡可能小的代價(jià)完成上述要求。以盡可能小的代價(jià)完成上述要求。8.2 外存的組織方式外存的組織方式n文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)n指邏輯文件指邏輯文件在存儲(chǔ)設(shè)備在存儲(chǔ)設(shè)備（外存）上的（外存）上的存儲(chǔ)組織形式存儲(chǔ)組織形式，它與存儲(chǔ)介，它與存儲(chǔ)介質(zhì)的存儲(chǔ)特性有

18、關(guān)質(zhì)的存儲(chǔ)特性有關(guān)n一個(gè)文件存儲(chǔ)介質(zhì)，格式化后就分成許多大小相等的單一個(gè)文件存儲(chǔ)介質(zhì)，格式化后就分成許多大小相等的單位位存儲(chǔ)塊（物理盤塊），一般來(lái)說(shuō)，每個(gè)物理塊是一存儲(chǔ)塊（物理盤塊），一般來(lái)說(shuō)，每個(gè)物理塊是一個(gè)磁盤的扇區(qū)，個(gè)磁盤的扇區(qū)，512B。并給每個(gè)存儲(chǔ)塊有個(gè)編號(hào)，稱為。并給每個(gè)存儲(chǔ)塊有個(gè)編號(hào)，稱為物理塊號(hào)。物理塊號(hào)。n物理塊是物理塊是分配和傳輸分配和傳輸信息的信息的基本單位基本單位，其與外存設(shè)備有關(guān)，其與外存設(shè)備有關(guān)，但與邏輯記錄大小無(wú)關(guān)，如但與邏輯記錄大小無(wú)關(guān)，如扇區(qū)、簇。扇區(qū)、簇。n文件在邏輯上都可看作是連續(xù)的，但在物理設(shè)備上存放時(shí)文件在邏輯上都可看作是連續(xù)的，但在物理設(shè)備上存放時(shí)卻

19、有不同的方式，如卻有不同的方式，如連續(xù)結(jié)構(gòu)（順序結(jié)構(gòu)）、鏈接結(jié)構(gòu)連續(xù)結(jié)構(gòu)（順序結(jié)構(gòu)）、鏈接結(jié)構(gòu)（串聯(lián)結(jié)構(gòu)）、索引結(jié)構(gòu)、（串聯(lián)結(jié)構(gòu)）、索引結(jié)構(gòu)、HASH文件文件等等8.2 外存的組織方式外存的組織方式。把邏輯文件中的記錄順序地存儲(chǔ)到。把邏輯文件中的記錄順序地存儲(chǔ)到連續(xù)的物理盤塊中。連續(xù)的物理盤塊中。文件中的各個(gè)記錄可以存放在不相。文件中的各個(gè)記錄可以存放在不相鄰接的各個(gè)物理盤塊中，通過(guò)物理塊中的鏈接鄰接的各個(gè)物理盤塊中，通過(guò)物理塊中的鏈接指針，將它們連接成一個(gè)鏈表。指針，將它們連接成一個(gè)鏈表。文件中的各個(gè)記錄可存儲(chǔ)在不相鄰。文件中的各個(gè)記錄可存儲(chǔ)在不相鄰接的各個(gè)物理塊中。接的各個(gè)物理塊中。8.2

20、 外存的組織方式外存的組織方式n8.2.1 連續(xù)組織方式連續(xù)組織方式n8.2.2 鏈接組織方式鏈接組織方式n8.2.3 FAT技術(shù)技術(shù)n8.2.4 NTFS技術(shù)技術(shù)n8.2.5 索引組織方式索引組織方式8.2.1 連續(xù)組織方式連續(xù)組織方式n每個(gè)文件分配每個(gè)文件分配一組相鄰接的盤塊一組相鄰接的盤塊。一組盤。一組盤塊定義了磁盤上的一段線性地址。又稱為塊定義了磁盤上的一段線性地址。又稱為連續(xù)分配方式。連續(xù)分配方式。n把邏輯文件中的記錄順序地存儲(chǔ)到鄰接的把邏輯文件中的記錄順序地存儲(chǔ)到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為為順序文件結(jié)構(gòu)順序文件結(jié)構(gòu)，此時(shí)的物理文

21、件稱為，此時(shí)的物理文件稱為順順序文件。序文件。8.2.1 連續(xù)組織方式連續(xù)組織方式8.2.1 連續(xù)組織方式連續(xù)組織方式n連續(xù)組織方式的主要優(yōu)缺點(diǎn)連續(xù)組織方式的主要優(yōu)缺點(diǎn)n優(yōu)點(diǎn)優(yōu)點(diǎn)n結(jié)構(gòu)簡(jiǎn)單，容易實(shí)現(xiàn)。結(jié)構(gòu)簡(jiǎn)單，容易實(shí)現(xiàn)。n支持順序存取和隨機(jī)存取。支持順序存取和隨機(jī)存取。n順序存取速度快。順序存取速度快。n所需的磁盤尋道次數(shù)和尋道時(shí)間最少。所需的磁盤尋道次數(shù)和尋道時(shí)間最少。n缺點(diǎn)缺點(diǎn)n要求有連續(xù)的存儲(chǔ)空間，不利于動(dòng)態(tài)擴(kuò)充。要求有連續(xù)的存儲(chǔ)空間，不利于動(dòng)態(tài)擴(kuò)充。n容易形成容易形成碎片，空間利用不充分。碎片，空間利用不充分。n必須事先知道文件的長(zhǎng)度，用戶不方便。必須事先知道文件的長(zhǎng)度，用戶不方便。8

22、.2.2 鏈接組織方式鏈接組織方式n基本方法基本方法n通過(guò)在每個(gè)盤塊上的鏈接指針，將同屬于一個(gè)通過(guò)在每個(gè)盤塊上的鏈接指針，將同屬于一個(gè)文件的多個(gè)文件的多個(gè)離散的離散的盤塊鏈接成一個(gè)盤塊鏈接成一個(gè)鏈表鏈表，把這，把這樣形成的物理文件稱為樣形成的物理文件稱為鏈接文件鏈接文件n特點(diǎn)：特點(diǎn)：不要求連續(xù)存放不要求連續(xù)存放n對(duì)于記錄式文件一塊中可包含一個(gè)或多個(gè)邏輯記對(duì)于記錄式文件一塊中可包含一個(gè)或多個(gè)邏輯記錄，也可以若干物理塊包含一個(gè)邏輯記錄。錄，也可以若干物理塊包含一個(gè)邏輯記錄。n鏈接方式鏈接方式n隱式鏈接隱式鏈接n顯式鏈接顯式鏈接8.2.2 鏈接組織方式鏈接組織方式n隱式鏈接隱式鏈接文件名文件名 始址

23、始址 末址末址jeep 9 25文件目錄文件目錄01234567891011121314151617181920212223242526272829303111016-1258.2.2 鏈接組織方式鏈接組織方式n隱式鏈接隱式鏈接n每個(gè)物理塊的最末一個(gè)字每個(gè)物理塊的最末一個(gè)字(或第一個(gè)字或第一個(gè)字)作為鏈作為鏈接字，它指出后繼塊的物理地址。鏈?zhǔn)字羔槾娼幼郑赋龊罄^塊的物理地址。鏈?zhǔn)字羔槾娣旁谠撐募夸浿?。文件的結(jié)尾塊的指針為放在該文件目錄中。文件的結(jié)尾塊的指針為“”。n優(yōu)點(diǎn)優(yōu)點(diǎn)n離散存儲(chǔ)，空間利用率高；離散存儲(chǔ)，空間利用率高；n順序存取效率高。順序存取效率高。n缺點(diǎn)缺點(diǎn)n隨機(jī)存取效率太低，若要

24、訪問(wèn)第隨機(jī)存取效率太低，若要訪問(wèn)第i個(gè)物理塊，個(gè)物理塊，必須讀出前必須讀出前i-1個(gè)。個(gè)。8.2.2 鏈接組織方式鏈接組織方式n顯式鏈接顯式鏈接n為了克服鏈接文件的存取效率太低的問(wèn)題，提為了克服鏈接文件的存取效率太低的問(wèn)題，提出出文件映照的技術(shù)文件映照的技術(shù)，即把鏈接文件中的鏈接字，即把鏈接文件中的鏈接字集中在一結(jié)構(gòu)中，集中在一結(jié)構(gòu)中，這樣既保持了鏈接文件的優(yōu)這樣既保持了鏈接文件的優(yōu)點(diǎn)，也克服了其缺點(diǎn)點(diǎn)，也克服了其缺點(diǎn)，DOS、WINDOWS系統(tǒng)系統(tǒng)就采用了這樣結(jié)構(gòu)。就采用了這樣結(jié)構(gòu)。n文件分配表（文件分配表（File Allocation Table, FAT）n在在FAT中每個(gè)物理塊占一個(gè)

25、表項(xiàng)，增加一個(gè)指中每個(gè)物理塊占一個(gè)表項(xiàng)，增加一個(gè)指針指向下一個(gè)物理塊，最末一個(gè)物理塊的指針針指向下一個(gè)物理塊，最末一個(gè)物理塊的指針為為“”。8.2.2 鏈接組織方式鏈接組織方式n顯式鏈接顯式鏈接8.2.2 鏈接組織方式鏈接組織方式n主要優(yōu)缺點(diǎn)主要優(yōu)缺點(diǎn)n優(yōu)點(diǎn)優(yōu)點(diǎn)n消除了外部碎片，提高外存利用率；消除了外部碎片，提高外存利用率；n文件動(dòng)態(tài)增長(zhǎng)時(shí)，可動(dòng)態(tài)地為它分配盤塊；文件動(dòng)態(tài)增長(zhǎng)時(shí)，可動(dòng)態(tài)地為它分配盤塊；n文件的增刪改方便，不需事先知道文件長(zhǎng)。文件的增刪改方便，不需事先知道文件長(zhǎng)。n缺點(diǎn)缺點(diǎn)n存取速度慢；存取速度慢；n只適于只適于順序存取順序存取，不適于隨機(jī)存?。徊贿m于隨機(jī)存??；n可靠性差，若某

26、一塊可靠性差，若某一塊指針指針出錯(cuò)，則鏈斷開；出錯(cuò)，則鏈斷開；n更多的尋道次數(shù)和尋道時(shí)間；更多的尋道次數(shù)和尋道時(shí)間；n鏈接指針占用一定的空間。鏈接指針占用一定的空間。8.2.3 FAT技術(shù)技術(shù)n文件分配表（文件分配表（File Allocation Table, FAT）n磁盤格式化后建立，從磁盤的第二個(gè)開始，有磁盤格式化后建立，從磁盤的第二個(gè)開始，有兩個(gè)相同的兩個(gè)相同的FAT。n用于記錄外存分配狀況，每個(gè)盤塊（或簇）占用于記錄外存分配狀況，每個(gè)盤塊（或簇）占一項(xiàng)，放在內(nèi)存中，整個(gè)系統(tǒng)一張一項(xiàng)，放在內(nèi)存中，整個(gè)系統(tǒng)一張F(tuán)AT。n表的序號(hào)為物理盤塊號(hào)或簇號(hào)，從表的序號(hào)為物理盤塊號(hào)或簇號(hào)，從0至至

27、N-1。n分配給一個(gè)文件的所有物理塊都在該表中標(biāo)出，分配給一個(gè)文件的所有物理塊都在該表中標(biāo)出，文件的第一個(gè)盤塊號(hào)記入文件的文件的第一個(gè)盤塊號(hào)記入文件的FCB中。中。8.2.3 FAT技術(shù)技術(shù)8.2.3 FAT技術(shù)技術(shù)區(qū)名區(qū)名內(nèi)容內(nèi)容 軟盤軟盤 占扇區(qū)數(shù)占扇區(qū)數(shù) 扇區(qū)號(hào)扇區(qū)號(hào)保留區(qū)保留區(qū)引導(dǎo)記錄與磁引導(dǎo)記錄與磁盤參數(shù)表盤參數(shù)表 1 0控制區(qū)控制區(qū)FAT1文件分文件分配表配表 2 12FAT2 2 34FDT文件目錄文件目錄表表 7 511文件區(qū)文件區(qū) 文件內(nèi)容文件內(nèi)容 余下部分余下部分 128.2.3 FAT技術(shù)技術(shù)nDOSDOS磁盤訪問(wèn)操作流程磁盤訪問(wèn)操作流程8.2.3 FAT技術(shù)技術(shù)nFAT

28、12n簇的基本概念簇的基本概念n簇是一組連續(xù)的扇區(qū)，在簇是一組連續(xù)的扇區(qū)，在FAT中它是作為一個(gè)虛擬中它是作為一個(gè)虛擬扇區(qū)，簇的大小一般是扇區(qū)，簇的大小一般是2n (n為整數(shù)為整數(shù))個(gè)盤塊，在個(gè)盤塊，在MS-DOS的實(shí)際運(yùn)用中，簇的容量可以僅有一個(gè)扇區(qū)的實(shí)際運(yùn)用中，簇的容量可以僅有一個(gè)扇區(qū)(512 B)、兩個(gè)扇區(qū)、兩個(gè)扇區(qū)(1 KB)、四個(gè)扇區(qū)、四個(gè)扇區(qū)(2 KB)、八個(gè)、八個(gè)扇區(qū)扇區(qū)(4 KB)等。等。n一個(gè)簇應(yīng)包含扇區(qū)的數(shù)量與磁盤容量的大小直接有一個(gè)簇應(yīng)包含扇區(qū)的數(shù)量與磁盤容量的大小直接有關(guān)。例如，當(dāng)一個(gè)簇僅有一個(gè)扇區(qū)時(shí)，磁盤的最大關(guān)。例如，當(dāng)一個(gè)簇僅有一個(gè)扇區(qū)時(shí)，磁盤的最大容量為容量為2

29、 MB；當(dāng)一個(gè)簇包含兩個(gè)扇區(qū)時(shí)，磁盤的最；當(dāng)一個(gè)簇包含兩個(gè)扇區(qū)時(shí)，磁盤的最大容量可以達(dá)到大容量可以達(dá)到4 MB；當(dāng)一個(gè)簇包含了八個(gè)扇區(qū)時(shí)，；當(dāng)一個(gè)簇包含了八個(gè)扇區(qū)時(shí)，磁盤的最大容量便可達(dá)到磁盤的最大容量便可達(dá)到16 MB。8.2.3 FAT技術(shù)技術(shù)nFAT12nFAT12存在的問(wèn)題存在的問(wèn)題n對(duì)所允許的磁盤容量存在著嚴(yán)重的限制，通對(duì)所允許的磁盤容量存在著嚴(yán)重的限制，通常只能是數(shù)十兆字節(jié)，雖然可以用繼續(xù)增加常只能是數(shù)十兆字節(jié)，雖然可以用繼續(xù)增加簇的大小來(lái)提高所允許的最大磁盤容量，但簇的大小來(lái)提高所允許的最大磁盤容量，但隨著支持的硬盤容量的增加，相應(yīng)的簇內(nèi)碎隨著支持的硬盤容量的增加，相應(yīng)的簇內(nèi)碎片

30、也將隨之成倍地增加。片也將隨之成倍地增加。n它只能支持它只能支持8+3格式的文件名。格式的文件名。 8.2.3 FAT技術(shù)技術(shù)nFAT16n將將FAT表的寬度增至表的寬度增至16位，最大表項(xiàng)數(shù)將增至位，最大表項(xiàng)數(shù)將增至65536個(gè)，此時(shí)便能將一個(gè)磁盤分區(qū)分為個(gè)，此時(shí)便能將一個(gè)磁盤分區(qū)分為65 536(216)個(gè)簇。把具有個(gè)簇。把具有16位表寬的位表寬的FAT表稱為表稱為FAT16。在。在FAT16的每個(gè)簇中可以有的盤塊數(shù)的每個(gè)簇中可以有的盤塊數(shù)為為4、8、16、32直到直到64，由此得出，由此得出FAT16可以可以管理的最大分區(qū)空間為管理的最大分區(qū)空間為 216 64 512 = 2048 M

31、B。8.2.3 FAT技術(shù)技術(shù)nFAT32n每一簇在每一簇在FAT表中的表項(xiàng)占據(jù)表中的表項(xiàng)占據(jù)4字節(jié)字節(jié)(232)，F(xiàn)AT表可以表示表可以表示4 294 967 296項(xiàng)，即項(xiàng)，即FAT32允許管允許管理比理比FAT16更多的簇。這樣就允許在更多的簇。這樣就允許在FAT32中中采用較小的簇，采用較小的簇，F(xiàn)AT32的每個(gè)簇都固定為的每個(gè)簇都固定為4 KB，即每簇用即每簇用8個(gè)盤塊代替?zhèn)€盤塊代替FAT16的的64個(gè)盤塊，每個(gè)個(gè)盤塊，每個(gè)盤塊仍為盤塊仍為512字節(jié)，字節(jié)，F(xiàn)AT32分區(qū)格式可以管理的分區(qū)格式可以管理的單個(gè)最大磁盤空間大到單個(gè)最大磁盤空間大到 4 KB232 = 16 TB（實(shí)際（實(shí)

32、際2TB）8.2.3 FAT技術(shù)技術(shù)nFAT中簇的大小與最大分區(qū)的對(duì)應(yīng)關(guān)系中簇的大小與最大分區(qū)的對(duì)應(yīng)關(guān)系8.2.4 NTFS技術(shù)技術(shù)nNTFS (New Technology File System)新特征新特征n專門為專門為Windows NT開發(fā)的、全新的文件系統(tǒng)，并適用開發(fā)的、全新的文件系統(tǒng)，并適用于于Windows 2000/XP及以后的系統(tǒng)。及以后的系統(tǒng)。n 使用使用64位磁盤地址，理論上可以支持位磁盤地址，理論上可以支持264字節(jié)的磁字節(jié)的磁盤分區(qū)；盤分區(qū)； n 可以很好地支持長(zhǎng)文件名，單個(gè)文件名限制在可以很好地支持長(zhǎng)文件名，單個(gè)文件名限制在255個(gè)字符以內(nèi)，全路徑名為個(gè)字符以內(nèi)，

33、全路徑名為32 767個(gè)字符；個(gè)字符； n 具有系統(tǒng)容錯(cuò)功能，即在系統(tǒng)出現(xiàn)故障或差錯(cuò)時(shí)，具有系統(tǒng)容錯(cuò)功能，即在系統(tǒng)出現(xiàn)故障或差錯(cuò)時(shí)，仍能保證系統(tǒng)正常運(yùn)行；仍能保證系統(tǒng)正常運(yùn)行； n 提供了數(shù)據(jù)的一致性功能；提供了數(shù)據(jù)的一致性功能；n 提供了文件加密、文件壓縮等功能提供了文件加密、文件壓縮等功能。8.2.4 NTFS技術(shù)技術(shù)n磁盤組織磁盤組織n以簇作為磁盤空間分配和回收的基本單位。以簇作為磁盤空間分配和回收的基本單位。n一個(gè)文件占用若干個(gè)簇，一個(gè)簇只屬于一個(gè)文一個(gè)文件占用若干個(gè)簇，一個(gè)簇只屬于一個(gè)文件。件。n通過(guò)簇來(lái)間接管理磁盤，可以不需要知道盤塊通過(guò)簇來(lái)間接管理磁盤，可以不需要知道盤塊(扇區(qū)扇

34、區(qū))的大小，使的大小，使NTFS具有了與磁盤物理扇區(qū)具有了與磁盤物理扇區(qū)大小無(wú)關(guān)的獨(dú)立性，很容易支持扇區(qū)大小不是大小無(wú)關(guān)的獨(dú)立性，很容易支持扇區(qū)大小不是512字節(jié)的非標(biāo)準(zhǔn)磁盤，從而可以根據(jù)不同的字節(jié)的非標(biāo)準(zhǔn)磁盤，從而可以根據(jù)不同的磁盤選擇匹配的簇大小。磁盤選擇匹配的簇大小。8.2.4 NTFS技術(shù)技術(shù)n卷因子卷因子n卷中簇的大小。在磁盤格式化時(shí)確定的，一個(gè)簇包含卷中簇的大小。在磁盤格式化時(shí)確定的，一個(gè)簇包含2n(n為整數(shù)為整數(shù))個(gè)盤塊。個(gè)盤塊。n簇的大小可由格式化命令或格式化程序按磁盤容量和簇的大小可由格式化命令或格式化程序按磁盤容量和應(yīng)用需求來(lái)確定，可以為應(yīng)用需求來(lái)確定，可以為512 B、1

35、 KB、2 KB，最，最大可達(dá)大可達(dá)64 KB。對(duì)于小磁盤。對(duì)于小磁盤(512 MB)，默認(rèn)簇大小為，默認(rèn)簇大小為512字節(jié)；對(duì)于字節(jié)；對(duì)于1 GB磁盤，默認(rèn)簇大小為磁盤，默認(rèn)簇大小為1 KB；對(duì)于；對(duì)于2 GB磁盤，則默認(rèn)簇大小為磁盤，則默認(rèn)簇大小為4 KB。事實(shí)上，為了在傳輸。事實(shí)上，為了在傳輸效率和簇內(nèi)碎片之間進(jìn)行折中，效率和簇內(nèi)碎片之間進(jìn)行折中，NTFS在大多數(shù)情況下在大多數(shù)情況下都是使用都是使用4 KB。8.2.4 NTFS技術(shù)技術(shù)n簇的定位簇的定位n邏輯簇號(hào)邏輯簇號(hào)LCN(Logical Cluster Number)：以卷為單：以卷為單位，將整個(gè)卷中所有的簇按順序進(jìn)行簡(jiǎn)單的編號(hào)。

36、位，將整個(gè)卷中所有的簇按順序進(jìn)行簡(jiǎn)單的編號(hào)。n地址映射過(guò)程：通過(guò)卷因子與地址映射過(guò)程：通過(guò)卷因子與LCN的乘積，便可算的乘積，便可算出卷上的物理字節(jié)偏移量，從而得到文件數(shù)據(jù)所在出卷上的物理字節(jié)偏移量，從而得到文件數(shù)據(jù)所在的物理磁盤地址。的物理磁盤地址。n虛擬簇號(hào)虛擬簇號(hào)VCN(Virtual Cluster Number)：為了方便：為了方便文件中數(shù)據(jù)的引用，以文件為單位，將屬于某個(gè)文文件中數(shù)據(jù)的引用，以文件為單位，將屬于某個(gè)文件的簇按順序進(jìn)行編號(hào)。件的簇按順序進(jìn)行編號(hào)。n地址映射過(guò)程地址映射過(guò)程 ：文件開始的簇地址，將：文件開始的簇地址，將VCN映射到映射到LCN。8.2.4 NTFS技術(shù)技

37、術(shù)n文件的組織文件的組織n以卷為單位，將一個(gè)卷中的所有文件信息、目以卷為單位，將一個(gè)卷中的所有文件信息、目錄信息以及可用的未分配空間信息，都以文件錄信息以及可用的未分配空間信息，都以文件記錄的方式記錄在一張記錄的方式記錄在一張主控文件表主控文件表MFT(Master File Table)中。該表是中。該表是NTFS 卷結(jié)卷結(jié)構(gòu)的中心，從邏輯上講，卷中的每個(gè)文件作為構(gòu)的中心，從邏輯上講，卷中的每個(gè)文件作為一條記錄，在一條記錄，在MFT 表中占有一行，其中還包表中占有一行，其中還包括括MFT 自己的這一行。每行大小固定為自己的這一行。每行大小固定為1 KB，每行稱為該行所對(duì)應(yīng)文件的元數(shù)據(jù)每行稱為

38、該行所對(duì)應(yīng)文件的元數(shù)據(jù)(metadata)，也稱為也稱為文件控制字文件控制字。8.2.5 索引組織方式索引組織方式n鏈接組織方式存在的問(wèn)題鏈接組織方式存在的問(wèn)題n不能支持高效的直接存取不能支持高效的直接存取，要對(duì)一個(gè)，要對(duì)一個(gè)較大的文較大的文件件進(jìn)行進(jìn)行直接存取直接存取，需首先在，需首先在FAT中順序地查找中順序地查找許多盤塊號(hào)。許多盤塊號(hào)。nFAT需需占用較大占用較大的的內(nèi)存內(nèi)存空間。空間。n索引表索引表n文件數(shù)據(jù)存放的存儲(chǔ)介質(zhì)上的物理塊號(hào)與文件文件數(shù)據(jù)存放的存儲(chǔ)介質(zhì)上的物理塊號(hào)與文件的邏輯塊號(hào)一一對(duì)應(yīng)。的邏輯塊號(hào)一一對(duì)應(yīng)。n第第i i個(gè)條目指向文件的第個(gè)條目指向文件的第i i個(gè)邏輯塊。對(duì)應(yīng)

39、的物個(gè)邏輯塊。對(duì)應(yīng)的物理塊號(hào)記錄在該塊中。理塊號(hào)記錄在該塊中。8.2.5 索引組織方式索引組織方式n單級(jí)索引組織方式單級(jí)索引組織方式n為為每個(gè)文件分配一個(gè)索引塊每個(gè)文件分配一個(gè)索引塊，把分配給該文件，把分配給該文件的所有盤塊號(hào)都記錄在該索引塊中；的所有盤塊號(hào)都記錄在該索引塊中；n在建立一個(gè)文件時(shí)，便為之建立的目錄項(xiàng)中填在建立一個(gè)文件時(shí)，便為之建立的目錄項(xiàng)中填上指向該索引塊的指針。上指向該索引塊的指針。n支持直接訪問(wèn)支持直接訪問(wèn)n對(duì)于大文件而言，該方式優(yōu)于鏈?zhǔn)椒峙浞绞?。?duì)于大文件而言，該方式優(yōu)于鏈?zhǔn)椒峙浞绞健?.2.5 索引組織方式索引組織方式01234567891011121314151617

40、1819202122232425262728293031文件名文件名 索引表地址索引表地址文件目錄文件目錄Jeep 19 916 11025 -1 -1 -1198.2.5 索引組織方式索引組織方式n單級(jí)索引組織方式單級(jí)索引組織方式n主要問(wèn)題主要問(wèn)題n可能要花費(fèi)較多的外存空間，尤其是對(duì)于小可能要花費(fèi)較多的外存空間，尤其是對(duì)于小文件。文件。n文件大小受盤塊大小限制。文件大小受盤塊大小限制。n例，若每個(gè)盤塊大小為例，若每個(gè)盤塊大小為1KB，每個(gè)盤塊號(hào)占，每個(gè)盤塊號(hào)占4B，則索引塊中可存放則索引塊中可存放256個(gè)盤塊號(hào)，即采用這種索個(gè)盤塊號(hào)，即采用這種索引方式時(shí)每個(gè)文件引方式時(shí)每個(gè)文件大小不能大小不

41、能超過(guò)超過(guò)256KB。n解決方法解決方法n使用多個(gè)索引塊，而對(duì)索引塊再建索引。使用多個(gè)索引塊，而對(duì)索引塊再建索引。8.2.5 索引組織方式索引組織方式n多級(jí)索引組織方式多級(jí)索引組織方式8.2.5 索引組織方式索引組織方式n多級(jí)索引組織方式多級(jí)索引組織方式n若每個(gè)盤塊大小為若每個(gè)盤塊大小為1KB，每個(gè)盤塊號(hào)占，每個(gè)盤塊號(hào)占4B，則，則一級(jí)索引塊中可存放一級(jí)索引塊中可存放256個(gè)盤塊號(hào)，即對(duì)應(yīng)個(gè)盤塊號(hào)，即對(duì)應(yīng)256個(gè)二級(jí)索引塊個(gè)二級(jí)索引塊n每個(gè)二級(jí)索引塊可對(duì)應(yīng)每個(gè)二級(jí)索引塊可對(duì)應(yīng)256個(gè)物理磁盤塊，采個(gè)物理磁盤塊，采用這種索引方式時(shí)每個(gè)文件大小不能超過(guò)用這種索引方式時(shí)每個(gè)文件大小不能超過(guò)256*2

42、56*1KB=64MBn若每個(gè)盤塊大小為若每個(gè)盤塊大小為4K，則最大文件大小為，則最大文件大小為1K*1K*4K=4GB8.2.5 索引組織方式索引組織方式n混合索引組織方式混合索引組織方式n直接地址直接地址提高文件的檢索速度提高文件的檢索速度n在索引結(jié)點(diǎn)中設(shè)置在索引結(jié)點(diǎn)中設(shè)置10個(gè)直接地址項(xiàng)，個(gè)直接地址項(xiàng)， 即用即用iaddr(0)iaddr(9)來(lái)存放直接地址來(lái)存放直接地址n一次間接地址一次間接地址n對(duì)于大、對(duì)于大、 中型文件，可再利用索引結(jié)點(diǎn)中的地址項(xiàng)中型文件，可再利用索引結(jié)點(diǎn)中的地址項(xiàng)iaddr(10)來(lái)提供一次間接地址。這種方式的實(shí)質(zhì)就來(lái)提供一次間接地址。這種方式的實(shí)質(zhì)就是一級(jí)索引分

43、配方式是一級(jí)索引分配方式n多次間接地址多次間接地址n當(dāng)文件長(zhǎng)度大于當(dāng)文件長(zhǎng)度大于4 MB+40 KB時(shí)時(shí)(一次間址與一次間址與10個(gè)直個(gè)直接地址項(xiàng)接地址項(xiàng))， 系統(tǒng)還須采用二次間址分配方式。這系統(tǒng)還須采用二次間址分配方式。這時(shí)，用地址項(xiàng)時(shí)，用地址項(xiàng)iaddr(11)提供二次間接地址。該方式提供二次間接地址。該方式的實(shí)質(zhì)是兩級(jí)索引分配方式。的實(shí)質(zhì)是兩級(jí)索引分配方式。8.2.5 索引組織方式索引組織方式直接地址直接地址物理盤塊物理盤塊索引塊索引塊8.2.5 索引組織方式索引組織方式n優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)n優(yōu)點(diǎn)：優(yōu)點(diǎn)：n保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn)保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn), ,又解決了其缺點(diǎn)：又解決了其缺點(diǎn)：即能順序存

44、取即能順序存取, ,又能隨機(jī)存取，滿足了文件又能隨機(jī)存取，滿足了文件動(dòng)態(tài)增長(zhǎng)、插入刪除的要求，也能充分利用動(dòng)態(tài)增長(zhǎng)、插入刪除的要求，也能充分利用外存空間。外存空間。n缺點(diǎn)：缺點(diǎn)：n較多的尋道次數(shù)和尋道時(shí)間，索引表本身帶較多的尋道次數(shù)和尋道時(shí)間，索引表本身帶來(lái)了系統(tǒng)開銷，如：內(nèi)外存空間，存取時(shí)間。來(lái)了系統(tǒng)開銷，如：內(nèi)外存空間，存取時(shí)間。8.2 外存的組織方式外存的組織方式n文件物理結(jié)構(gòu)的比較文件物理結(jié)構(gòu)的比較n連續(xù)文件的連續(xù)文件的優(yōu)點(diǎn)優(yōu)點(diǎn)是不需要額外的空間開銷，只要在文是不需要額外的空間開銷，只要在文件目錄中指出文件的大小和首塊的塊號(hào)即可，對(duì)順序件目錄中指出文件的大小和首塊的塊號(hào)即可，對(duì)順序的訪

45、問(wèn)效率很高。適應(yīng)于順序存取。的訪問(wèn)效率很高。適應(yīng)于順序存取。缺點(diǎn)缺點(diǎn)是動(dòng)態(tài)地增是動(dòng)態(tài)地增長(zhǎng)和縮小系統(tǒng)開銷很大；文件創(chuàng)建時(shí)要求用戶提供文長(zhǎng)和縮小系統(tǒng)開銷很大；文件創(chuàng)建時(shí)要求用戶提供文件的大??；存儲(chǔ)空間浪費(fèi)較大。件的大??；存儲(chǔ)空間浪費(fèi)較大。n鏈?zhǔn)轿募朔诉B續(xù)文件的不足之處，但文件的隨機(jī)鏈?zhǔn)轿募朔诉B續(xù)文件的不足之處，但文件的隨機(jī)訪問(wèn)系統(tǒng)開銷較大。適應(yīng)于順序訪問(wèn)。訪問(wèn)系統(tǒng)開銷較大。適應(yīng)于順序訪問(wèn)。DOS系統(tǒng)中改系統(tǒng)中改造了鏈?zhǔn)轿募慕Y(jié)構(gòu)，使其克服了鏈?zhǔn)轿募牟蛔?，造了鏈?zhǔn)轿募慕Y(jié)構(gòu)，使其克服了鏈?zhǔn)轿募牟蛔?，但增加了系統(tǒng)的危險(xiǎn)性。但增加了系統(tǒng)的危險(xiǎn)性。8.2 外存的組織方式外存的組織方式n文件物

46、理結(jié)構(gòu)的比較文件物理結(jié)構(gòu)的比較n索引文件既適應(yīng)于順序存訪問(wèn)，也適應(yīng)于隨機(jī)索引文件既適應(yīng)于順序存訪問(wèn)，也適應(yīng)于隨機(jī)訪問(wèn)，是一種比較好的文件物理結(jié)構(gòu)，但要有訪問(wèn)，是一種比較好的文件物理結(jié)構(gòu)，但要有用于索引表的空間開銷和文件索引的時(shí)間開銷。用于索引表的空間開銷和文件索引的時(shí)間開銷。UNIX系統(tǒng)是使用索引結(jié)構(gòu)成功的例子。系統(tǒng)是使用索引結(jié)構(gòu)成功的例子。n在當(dāng)前流行的一些在當(dāng)前流行的一些UNIX操作系統(tǒng)的版本中，操作系統(tǒng)的版本中，同時(shí)支持連續(xù)文件結(jié)構(gòu)和索引文件結(jié)構(gòu)。同時(shí)支持連續(xù)文件結(jié)構(gòu)和索引文件結(jié)構(gòu)。DOS、WINDOWS系統(tǒng)支撐類似于文件映照結(jié)構(gòu)。系統(tǒng)支撐類似于文件映照結(jié)構(gòu)。8.3 空閑空間的管理空閑空

47、間的管理n解決的問(wèn)題：解決的問(wèn)題：n如何為新創(chuàng)建的文件分配存儲(chǔ)空間？如何為新創(chuàng)建的文件分配存儲(chǔ)空間？n解決的方法：解決的方法：n（分配的基本單位都是磁盤塊）。（分配的基本單位都是磁盤塊）。n分配方式：分配方式：n連續(xù)分配：訪問(wèn)速度高，但會(huì)產(chǎn)生外存零頭。連續(xù)分配：訪問(wèn)速度高，但會(huì)產(chǎn)生外存零頭。n離散分配：訪問(wèn)速度慢，但能有效利用外存空間。離散分配：訪問(wèn)速度慢，但能有效利用外存空間。n分配時(shí)數(shù)據(jù)結(jié)構(gòu)分配時(shí)數(shù)據(jù)結(jié)構(gòu)n分配回收算法分配回收算法8.3 空閑空間的管理空閑空間的管理n8.3.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法n8.3.2 位示圖法位示圖法n8.3.3 成組鏈接法成組鏈接法8.3.

48、1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法n空閑表法空閑表法連續(xù)分配方式連續(xù)分配方式n與內(nèi)存的動(dòng)態(tài)分配方式相同，為每個(gè)文件分配一與內(nèi)存的動(dòng)態(tài)分配方式相同，為每個(gè)文件分配一個(gè)連續(xù)的存儲(chǔ)空間。個(gè)連續(xù)的存儲(chǔ)空間。n為外存上的所有空閑區(qū)建立一張空閑表，每個(gè)空為外存上的所有空閑區(qū)建立一張空閑表，每個(gè)空閑區(qū)對(duì)應(yīng)于一個(gè)閑表項(xiàng)，將所有空閑區(qū)按起始盤閑區(qū)對(duì)應(yīng)于一個(gè)閑表項(xiàng)，將所有空閑區(qū)按起始盤塊號(hào)遞增的順序排列塊號(hào)遞增的順序排列n存儲(chǔ)空間的分配與回收可采用存儲(chǔ)空間的分配與回收可采用首次適應(yīng)算法、循首次適應(yīng)算法、循環(huán)首次適應(yīng)算法環(huán)首次適應(yīng)算法等等n如對(duì)換方式中對(duì)如對(duì)換方式中對(duì)對(duì)換空間對(duì)換空間的分配就采用連續(xù)分配，

49、的分配就采用連續(xù)分配，主要目的是提高速度。主要目的是提高速度。n系統(tǒng)中的系統(tǒng)中的較小文件較小文件也也采用連續(xù)采用連續(xù)分配方式，如分配方式，如“簇簇”8.3.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法n空閑表法空閑表法分配與回收分配與回收n空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，同樣空閑盤區(qū)的分配與內(nèi)存的動(dòng)態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等。8.3.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法n空閑鏈表法空閑鏈表法n將所有空閑盤區(qū)，拉成一條空閑鏈。將所有空閑盤區(qū)，拉成一條空閑鏈。n將磁盤上所有空閑區(qū)空間，以盤塊為單位拉成一條將磁盤上所有空

50、閑區(qū)空間，以盤塊為單位拉成一條鏈，當(dāng)用戶因創(chuàng)建文件而請(qǐng)求分配存儲(chǔ)空間時(shí)，系鏈，當(dāng)用戶因創(chuàng)建文件而請(qǐng)求分配存儲(chǔ)空間時(shí)，系統(tǒng)從鏈?zhǔn)组_始，依次摘下適當(dāng)數(shù)目的空閑盤塊鏈給統(tǒng)從鏈?zhǔn)组_始，依次摘下適當(dāng)數(shù)目的空閑盤塊鏈給用戶。當(dāng)用戶因刪除文件而釋放存儲(chǔ)空間時(shí)，系統(tǒng)用戶。當(dāng)用戶因刪除文件而釋放存儲(chǔ)空間時(shí)，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾。將回收的盤塊依次插入空閑盤塊鏈的末尾。：分配和回收一個(gè)盤塊的過(guò)程非常簡(jiǎn)單。分配和回收一個(gè)盤塊的過(guò)程非常簡(jiǎn)單。：但在為一個(gè)文件分配盤塊時(shí)，可能要重復(fù)多但在為一個(gè)文件分配盤塊時(shí)，可能要重復(fù)多次操作。次操作。8.3.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法n空閑鏈表法空

51、閑鏈表法n將磁盤上所有空閑盤區(qū)拉成一條鏈，在每個(gè)盤將磁盤上所有空閑盤區(qū)拉成一條鏈，在每個(gè)盤區(qū)上包含若干用于指示下一個(gè)空閑盤區(qū)的指針，區(qū)上包含若干用于指示下一個(gè)空閑盤區(qū)的指針，指明盤區(qū)大小的信息。指明盤區(qū)大小的信息。n分配盤塊時(shí)，通常采用首次適應(yīng)算法（顯式鏈分配盤塊時(shí)，通常采用首次適應(yīng)算法（顯式鏈接法）。接法）。n在回收時(shí)，將回收區(qū)與空閑盤區(qū)相合并在回收時(shí)，將回收區(qū)與空閑盤區(qū)相合并。8.3.2 位示圖法位示圖法n位示圖位示圖n用用二進(jìn)制的一位二進(jìn)制的一位來(lái)表示磁盤中一個(gè)盤塊來(lái)表示磁盤中一個(gè)盤塊的使用情況的使用情況n0：盤塊空閑；盤塊空閑；n1：盤塊已分配盤塊已分配n由所有盤塊所對(duì)應(yīng)的二進(jìn)制位構(gòu)成

52、的一由所有盤塊所對(duì)應(yīng)的二進(jìn)制位構(gòu)成的一個(gè)集合稱為位示圖，通?？捎脗€(gè)集合稱為位示圖，通?？捎胢n個(gè)位個(gè)位數(shù)來(lái)構(gòu)成位示圖，并使數(shù)來(lái)構(gòu)成位示圖，并使mn等于磁盤總等于磁盤總塊數(shù)。塊數(shù)。8.3.2 位示圖法位示圖法內(nèi)存中表示內(nèi)存中表示外存中表示外存中表示8.3.2 位示圖法位示圖法n盤塊的分配盤塊的分配n順序掃描位示圖，從中找出一個(gè)或一組其值為順序掃描位示圖，從中找出一個(gè)或一組其值為“0”的二進(jìn)制位；的二進(jìn)制位；n將所找到的一個(gè)或一組二進(jìn)制位，將所找到的一個(gè)或一組二進(jìn)制位， 轉(zhuǎn)換成與之轉(zhuǎn)換成與之相應(yīng)的盤塊號(hào)。假定找到的其值為相應(yīng)的盤塊號(hào)。假定找到的其值為“0”的二進(jìn)的二進(jìn)制位，位于位示的第制位，位于位

53、示的第i行、第行、第j列，則其相應(yīng)的列，則其相應(yīng)的盤塊號(hào)應(yīng)按下式計(jì)算盤塊號(hào)應(yīng)按下式計(jì)算b = n(i - 1) + jn修改位示圖，修改位示圖， 令令mapij=1。8.3.2 位示圖法位示圖法n盤塊的回收盤塊的回收n將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。 轉(zhuǎn)換公式為轉(zhuǎn)換公式為i = (b - 1) DIV n + 1j = (b - 1) MOD n + 1n修改位示圖，修改位示圖， 令令map ij=0n如上例中，第如上例中，第16號(hào)物理塊，可計(jì)算得號(hào)物理塊，可計(jì)算得ni = (16 - 1) DIV 16 + 1 = 1nj = (1

54、6 - 1) MOD 16 + 1 = 16n同理，第同理，第17塊可計(jì)算得塊可計(jì)算得ni = (17 - 1) DIV 16 + 1 = 2nj = (17 - 1) MOD 16 + 1 = 1 8.3.2 位示圖法位示圖法n主要優(yōu)點(diǎn)主要優(yōu)點(diǎn)n很容易找到一個(gè)或一組相鄰接的空閑盤塊。很容易找到一個(gè)或一組相鄰接的空閑盤塊。n例，我們需要找到例，我們需要找到6個(gè)相鄰接的空閑盤塊，這只需個(gè)相鄰接的空閑盤塊，這只需在位示圖中找出在位示圖中找出6個(gè)其值連續(xù)為個(gè)其值連續(xù)為“0”的位即可。的位即可。n由于位示圖很小，占用空間少，因而可將它保由于位示圖很小，占用空間少，因而可將它保存在內(nèi)存中，進(jìn)而使在每次進(jìn)

55、行盤區(qū)分配時(shí)，存在內(nèi)存中，進(jìn)而使在每次進(jìn)行盤區(qū)分配時(shí)，無(wú)需首先把盤區(qū)分配表讀入內(nèi)存，從而節(jié)省了無(wú)需首先把盤區(qū)分配表讀入內(nèi)存，從而節(jié)省了許多磁盤的啟動(dòng)操作。因此，常用于微型機(jī)和許多磁盤的啟動(dòng)操作。因此，常用于微型機(jī)和小型機(jī)中，如小型機(jī)中，如CP/M、Apple-DOS等等OS中。中。 8.3.3 成組鏈接法成組鏈接法n在大型文件系統(tǒng)中，空閑表或空閑鏈表太長(zhǎng)，在在大型文件系統(tǒng)中，空閑表或空閑鏈表太長(zhǎng)，在UNIX系統(tǒng)中，兩種方法結(jié)合形成系統(tǒng)中，兩種方法結(jié)合形成成組鏈接法。成組鏈接法。n空閑盤塊的組織空閑盤塊的組織n將將空閑表空閑表和和空閑鏈表空閑鏈表結(jié)合形成的空閑盤塊管理方結(jié)合形成的空閑盤塊管理方法

56、。法。n空閑盤塊號(hào)棧空閑盤塊號(hào)棧 用來(lái)存放當(dāng)前可用的一組空閑盤塊用來(lái)存放當(dāng)前可用的一組空閑盤塊號(hào)以及棧中尚有的空閑盤塊數(shù)號(hào)以及棧中尚有的空閑盤塊數(shù)N。n文件區(qū)中的所有空閑盤塊被分成若干個(gè)組，如文件區(qū)中的所有空閑盤塊被分成若干個(gè)組，如100塊塊/組。組。n將每組含的有盤塊數(shù)和該組所有盤塊號(hào)記入前一將每組含的有盤塊數(shù)和該組所有盤塊號(hào)記入前一組第一個(gè)盤塊中。組第一個(gè)盤塊中。n將第一組的空閑盤塊數(shù)和所有盤塊號(hào)記入空閑盤將第一組的空閑盤塊數(shù)和所有盤塊號(hào)記入空閑盤塊號(hào)棧。塊號(hào)棧。8.3.3 成組鏈接法成組鏈接法8.3.3 成組鏈接法成組鏈接法n空閑盤塊的分配與回收空閑盤塊的分配與回收n分配分配n檢查空閑盤

57、塊號(hào)棧是否上鎖，如未上鎖，便從棧頂檢查空閑盤塊號(hào)棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶，取出一空閑盤塊號(hào)，將與之對(duì)應(yīng)的盤塊分配給用戶，然后將棧頂指針下移一格然后將棧頂指針下移一格n若該盤塊號(hào)已是棧底，若該盤塊號(hào)已是棧底， 即即S.free(0)，當(dāng)前棧中最后，當(dāng)前棧中最后一個(gè)可分配的盤塊號(hào)一個(gè)可分配的盤塊號(hào)n調(diào)用磁盤讀過(guò)程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容調(diào)用磁盤讀過(guò)程，將棧底盤塊號(hào)所對(duì)應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號(hào)棧的內(nèi)容，并把原棧底讀入棧中，作為新的盤塊號(hào)棧的內(nèi)容，并把原棧底對(duì)應(yīng)的盤塊分配出去對(duì)應(yīng)的盤塊分配出去n分配一相應(yīng)的緩沖區(qū)分配一相應(yīng)的緩沖區(qū)n把

58、棧中的空閑盤塊數(shù)減把棧中的空閑盤塊數(shù)減1并返回并返回8.3.3 成組鏈接法成組鏈接法n空閑盤塊的分配與回收空閑盤塊的分配與回收n回收回收n將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的頂將回收盤塊的盤塊號(hào)記入空閑盤塊號(hào)棧的頂部，并執(zhí)行空閑盤塊數(shù)加部，并執(zhí)行空閑盤塊數(shù)加1操作；操作；n當(dāng)棧已滿時(shí)，記入新回收的盤塊中，再將其當(dāng)棧已滿時(shí)，記入新回收的盤塊中，再將其盤塊號(hào)作為新棧底。盤塊號(hào)作為新棧底。8.4 提高磁盤提高磁盤I/O速度的途徑速度的途徑n8.4.1 磁盤高速緩存磁盤高速緩存n8.4.2 提高磁盤提高磁盤I/O速度的其它方法速度的其它方法n8.4.3 廉價(jià)磁盤冗余陣列廉價(jià)磁盤冗余陣列8.4.1 磁盤

59、高速緩存磁盤高速緩存n磁盤高速緩存的形式磁盤高速緩存的形式n利用利用內(nèi)存內(nèi)存中的存儲(chǔ)空間，來(lái)暫存從中的存儲(chǔ)空間，來(lái)暫存從磁盤磁盤中讀出中讀出的一系列盤塊中的信息的一系列盤塊中的信息n一組在邏輯上屬于磁盤，一組在邏輯上屬于磁盤， 而物理上是駐留在內(nèi)而物理上是駐留在內(nèi)存中的盤塊存中的盤塊n在內(nèi)存中的形式在內(nèi)存中的形式n在內(nèi)存中開辟一個(gè)在內(nèi)存中開辟一個(gè)單獨(dú)的存儲(chǔ)空間單獨(dú)的存儲(chǔ)空間來(lái)作為磁來(lái)作為磁盤高速緩存，其大小是固定的盤高速緩存，其大小是固定的n把所有把所有未利用的內(nèi)存空間變?yōu)橐粋€(gè)緩沖池未利用的內(nèi)存空間變?yōu)橐粋€(gè)緩沖池，供請(qǐng)求分頁(yè)系統(tǒng)和磁盤供請(qǐng)求分頁(yè)系統(tǒng)和磁盤I/O時(shí)時(shí)(作為磁盤高速作為磁盤高速緩存

60、緩存)共享共享不受應(yīng)用程序不受應(yīng)用程序多少的限制多少的限制應(yīng)用程序多時(shí)應(yīng)用程序多時(shí)緩存可能很小緩存可能很小8.4.1 磁盤高速緩存磁盤高速緩存n數(shù)據(jù)交付方式數(shù)據(jù)交付方式n數(shù)據(jù)交付（數(shù)據(jù)交付（Data Delivery）是指將磁盤高速緩是指將磁盤高速緩存中的數(shù)據(jù)傳送給請(qǐng)求者進(jìn)程存中的數(shù)據(jù)傳送給請(qǐng)求者進(jìn)程n當(dāng)有進(jìn)程請(qǐng)求訪問(wèn)某個(gè)盤塊時(shí)，先查看磁盤高當(dāng)有進(jìn)程請(qǐng)求訪問(wèn)某個(gè)盤塊時(shí)，先查看磁盤高速緩存速緩存n兩種方式兩種方式n數(shù)據(jù)交付數(shù)據(jù)交付。直接將高速緩存中的數(shù)據(jù)，。直接將高速緩存中的數(shù)據(jù)， 傳傳送到請(qǐng)求者進(jìn)程的內(nèi)存工作區(qū)中。送到請(qǐng)求者進(jìn)程的內(nèi)存工作區(qū)中。n指針交付指針交付。只將指向高速緩存中某區(qū)域的指。