第8章磁盤存儲器的管理

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

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

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

4、.1 磁盤性能簡述磁盤性能簡述8.1.1 磁盤性能簡述磁盤性能簡述n數(shù)據(jù)的組織和格式數(shù)據(jù)的組織和格式n盤片（盤片（1個或多個）、盤面、磁道、扇區(qū)個或多個）、盤面、磁道、扇區(qū)n扇區(qū)有扇區(qū)有標識符字段標識符字段和和數(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存儲相同數(shù)目存儲相同數(shù)目的二進制位的二進制位間隙間隙定界符定界符段校驗段校驗8.1.1 磁盤性能簡述磁盤性能簡述n磁盤的類型磁盤的類型n在在，所有的磁頭都被裝，所有的磁頭都被裝在一剛性磁臂中。通過這些磁頭可訪問所有各磁道，在一剛性磁臂中。通過這些磁頭可訪問所有各磁道，并進行并進行，有效地，有效地。這種結(jié)構(gòu)的磁盤主要用于這種結(jié)構(gòu)的磁盤主要用于上。上。，也被裝入磁臂中。為，也被裝入磁臂中。為能訪問該盤面上的所有磁道，該磁頭必

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

7、轉(zhuǎn)到磁頭下面所經(jīng)歷的時間。如：7200r/min 每轉(zhuǎn)每轉(zhuǎn)=60000ms/7200r=8.33ms 平均旋轉(zhuǎn)延遲平均旋轉(zhuǎn)延遲=（0+8.33)/2=4.16啟動磁臂時間啟動磁臂時間2ms常數(shù)，與磁盤驅(qū)常數(shù)，與磁盤驅(qū)動器的速度有關(guān)動器的速度有關(guān)一般：一般：0.2ms高速：高速：=0.1ms8.1.1 磁盤性能簡述磁盤性能簡述n磁盤訪問時間磁盤訪問時間n傳輸時間傳輸時間Ttn指把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)指把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時間。歷的時間。 其大小與每次所讀其大小與每次所讀/寫的字節(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相同，則訪問時間相同，則訪問時間=Ts + T+ TtrNbTt如如b=N/2，則，則T=1/(2r)=Tt可見，尋道時間可見，尋道時間TS和旋轉(zhuǎn)和旋轉(zhuǎn)延遲時間延遲時間T基本上都與所基本上都與所讀讀/寫數(shù)據(jù)的字節(jié)數(shù)無關(guān)，寫數(shù)據(jù)的字節(jié)數(shù)無關(guān)，而且它通常占據(jù)了訪問時而且它通常占據(jù)了訪問時間中的大部分間中的大部分目前磁盤的傳輸速率已達到目前磁盤的傳輸速率已達到80MB/s以上，數(shù)據(jù)傳輸時間所占以上，數(shù)據(jù)傳輸時間所占的比例更低?？梢?，適當?shù)丶袛?shù)據(jù)傳輸，將有利于提高傳輸?shù)谋壤??？梢?，適當?shù)丶袛?shù)據(jù)傳輸，將有利于提高傳輸效率效率8.1.1 磁盤

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

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

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

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

13、點方法的缺點n剛移過的磁道的等待時間長。剛移過的磁道的等待時間長。n解決方法解決方法n規(guī)定磁頭單向移動。減少剛移過的磁道的等規(guī)定磁頭單向移動。減少剛移過的磁道的等待時間。待時間。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)磁臂停留在某處不動的情況，稱為能出現(xiàn)磁臂停留在某處不動的情況，稱為“磁臂粘磁臂粘著著”(Armstickiness)。nN步步SCAN

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

15、。在掃描期間，新出現(xiàn)的所有請求行處理。在掃描期間，新出現(xiàn)的所有請求I/O的進程，的進程， 則放入另一個等待處理的請求隊列。則放入另一個等待處理的請求隊列。當當N值很大時，值很大時，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)， 又稱為文件的存儲結(jié)構(gòu)，又稱為文件的存儲結(jié)構(gòu)， 文件在外存上的存儲組織形式。文件在外存上的存儲組織形式。n 問題問題n如何才能有效地利用外

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

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

18、關(guān)質(zhì)的存儲特性有關(guān)n一個文件存儲介質(zhì)，格式化后就分成許多大小相等的單一個文件存儲介質(zhì)，格式化后就分成許多大小相等的單位位存儲塊（物理盤塊），一般來說，每個物理塊是一存儲塊（物理盤塊），一般來說，每個物理塊是一個磁盤的扇區(qū)，個磁盤的扇區(qū)，512B。并給每個存儲塊有個編號，稱為。并給每個存儲塊有個編號，稱為物理塊號。物理塊號。n物理塊是物理塊是分配和傳輸分配和傳輸信息的信息的基本單位基本單位，其與外存設(shè)備有關(guān)，其與外存設(shè)備有關(guān)，但與邏輯記錄大小無關(guān)，如但與邏輯記錄大小無關(guān)，如扇區(qū)、簇。扇區(qū)、簇。n文件在邏輯上都可看作是連續(xù)的，但在物理設(shè)備上存放時文件在邏輯上都可看作是連續(xù)的，但在物理設(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 外存的組織方式外存的組織方式。把邏輯文件中的記錄順序地存儲到。把邏輯文件中的記錄順序地存儲到連續(xù)的物理盤塊中。連續(xù)的物理盤塊中。文件中的各個記錄可以存放在不相。文件中的各個記錄可以存放在不相鄰接的各個物理盤塊中，通過物理塊中的鏈接鄰接的各個物理盤塊中，通過物理塊中的鏈接指針，將它們連接成一個鏈表。指針，將它們連接成一個鏈表。文件中的各個記錄可存儲在不相鄰。文件中的各個記錄可存儲在不相鄰接的各個物理塊中。接的各個物理塊中。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每個文件分配每個文件分配一組相鄰接的盤塊一組相鄰接的盤塊。一組盤。一組盤塊定義了磁盤上的一段線性地址。又稱為塊定義了磁盤上的一段線性地址。又稱為連續(xù)分配方式。連續(xù)分配方式。n把邏輯文件中的記錄順序地存儲到鄰接的把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為為順序文件結(jié)構(gòu)順序文件結(jié)構(gòu)，此時的物理文

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

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

23、始址 末址末址jeep 9 25文件目錄文件目錄01234567891011121314151617181920212223242526272829303111016-1258.2.2 鏈接組織方式鏈接組織方式n隱式鏈接隱式鏈接n每個物理塊的最末一個字每個物理塊的最末一個字(或第一個字或第一個字)作為鏈作為鏈接字，它指出后繼塊的物理地址。鏈首指針存接字，它指出后繼塊的物理地址。鏈首指針存放在該文件目錄中。文件的結(jié)尾塊的指針為放在該文件目錄中。文件的結(jié)尾塊的指針為“”。n優(yōu)點優(yōu)點n離散存儲，空間利用率高；離散存儲，空間利用率高；n順序存取效率高。順序存取效率高。n缺點缺點n隨機存取效率太低，若要

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

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

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

27、N-1。n分配給一個文件的所有物理塊都在該表中標出，分配給一個文件的所有物理塊都在該表中標出，文件的第一個盤塊號記入文件的文件的第一個盤塊號記入文件的FCB中。中。8.2.3 FAT技術(shù)技術(shù)8.2.3 FAT技術(shù)技術(shù)區(qū)名區(qū)名內(nèi)容內(nèi)容 軟盤軟盤 占扇區(qū)數(shù)占扇區(qū)數(shù) 扇區(qū)號扇區(qū)號保留區(qū)保留區(qū)引導記錄與磁引導記錄與磁盤參數(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磁盤訪問操作流程磁盤訪問操作流程8.2.3 FAT技術(shù)技術(shù)nFAT

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

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

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

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

32、際2TB）8.2.3 FAT技術(shù)技術(shù)nFAT中簇的大小與最大分區(qū)的對應(yīng)關(guān)系中簇的大小與最大分區(qū)的對應(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 可以很好地支持長文件名，單個文件名限制在可以很好地支持長文件名，單個文件名限制在255個字符以內(nèi)，全路徑名為個字符以內(nèi)，

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

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

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

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

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

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

39、的物個邏輯塊。對應(yīng)的物理塊號記錄在該塊中。理塊號記錄在該塊中。8.2.5 索引組織方式索引組織方式n單級索引組織方式單級索引組織方式n為為每個文件分配一個索引塊每個文件分配一個索引塊，把分配給該文件，把分配給該文件的所有盤塊號都記錄在該索引塊中；的所有盤塊號都記錄在該索引塊中；n在建立一個文件時，便為之建立的目錄項中填在建立一個文件時，便為之建立的目錄項中填上指向該索引塊的指針。上指向該索引塊的指針。n支持直接訪問支持直接訪問n對于大文件而言，該方式優(yōu)于鏈式分配方式。對于大文件而言，該方式優(yōu)于鏈式分配方式。8.2.5 索引組織方式索引組織方式01234567891011121314151617

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

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

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

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

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

45、問效率很高。適應(yīng)于順序存取。的訪問效率很高。適應(yīng)于順序存取。缺點缺點是動態(tài)地增是動態(tài)地增長和縮小系統(tǒng)開銷很大；文件創(chuàng)建時要求用戶提供文長和縮小系統(tǒng)開銷很大；文件創(chuàng)建時要求用戶提供文件的大?。淮鎯臻g浪費較大。件的大??；存儲空間浪費較大。n鏈式文件克服了連續(xù)文件的不足之處，但文件的隨機鏈式文件克服了連續(xù)文件的不足之處，但文件的隨機訪問系統(tǒng)開銷較大。適應(yīng)于順序訪問。訪問系統(tǒng)開銷較大。適應(yīng)于順序訪問。DOS系統(tǒng)中改系統(tǒng)中改造了鏈式文件的結(jié)構(gòu)，使其克服了鏈式文件的不足，造了鏈式文件的結(jié)構(gòu)，使其克服了鏈式文件的不足，但增加了系統(tǒng)的危險性。但增加了系統(tǒng)的危險性。8.2 外存的組織方式外存的組織方式n文件物

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

47、間的管理n解決的問題：解決的問題：n如何為新創(chuàng)建的文件分配存儲空間？如何為新創(chuàng)建的文件分配存儲空間？n解決的方法：解決的方法：n（分配的基本單位都是磁盤塊）。（分配的基本單位都是磁盤塊）。n分配方式：分配方式：n連續(xù)分配：訪問速度高，但會產(chǎn)生外存零頭。連續(xù)分配：訪問速度高，但會產(chǎn)生外存零頭。n離散分配：訪問速度慢，但能有效利用外存空間。離散分配：訪問速度慢，但能有效利用外存空間。n分配時數(shù)據(jù)結(jié)構(gòu)分配時數(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)存的動態(tài)分配方式相同，為每個文件分配一與內(nèi)存的動態(tài)分配方式相同，為每個文件分配一個連續(xù)的存儲空間。個連續(xù)的存儲空間。n為外存上的所有空閑區(qū)建立一張空閑表，每個空為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應(yīng)于一個閑表項，將所有空閑區(qū)按起始盤閑區(qū)對應(yīng)于一個閑表項，將所有空閑區(qū)按起始盤塊號遞增的順序排列塊號遞增的順序排列n存儲空間的分配與回收可采用存儲空間的分配與回收可采用首次適應(yīng)算法、循首次適應(yīng)算法、循環(huán)首次適應(yīng)算法環(huán)首次適應(yīng)算法等等n如對換方式中對如對換方式中對對換空間對換空間的分配就采用連續(xù)分配，

49、的分配就采用連續(xù)分配，主要目的是提高速度。主要目的是提高速度。n系統(tǒng)中的系統(tǒng)中的較小文件較小文件也也采用連續(xù)采用連續(xù)分配方式，如分配方式，如“簇簇”8.3.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法n空閑表法空閑表法分配與回收分配與回收n空閑盤區(qū)的分配與內(nèi)存的動態(tài)分配類似，同樣空閑盤區(qū)的分配與內(nèi)存的動態(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ū)空間，以盤塊為單位拉成一條鏈，當用戶因創(chuàng)建文件而請求分配存儲空間時，系鏈，當用戶因創(chuàng)建文件而請求分配存儲空間時，系統(tǒng)從鏈首開始，依次摘下適當數(shù)目的空閑盤塊鏈給統(tǒng)從鏈首開始，依次摘下適當數(shù)目的空閑盤塊鏈給用戶。當用戶因刪除文件而釋放存儲空間時，系統(tǒng)用戶。當用戶因刪除文件而釋放存儲空間時，系統(tǒng)將回收的盤塊依次插入空閑盤塊鏈的末尾。將回收的盤塊依次插入空閑盤塊鏈的末尾。：分配和回收一個盤塊的過程非常簡單。分配和回收一個盤塊的過程非常簡單。：但在為一個文件分配盤塊時，可能要重復多但在為一個文件分配盤塊時，可能要重復多次操作。次操作。8.3.1 空閑表法和空閑鏈表法空閑表法和空閑鏈表法n空閑鏈表法空

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

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

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

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

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

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

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

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

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

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