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

1、1第八章 磁盤存儲(chǔ)器的管理2 磁盤存儲(chǔ)器管理磁盤存儲(chǔ)器管理8.1 外存的組織方式外存的組織方式8.2 文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理8.3 提高磁盤提高磁盤I/O速度的途徑速度的途徑8.4 提高磁盤可靠性的技術(shù)提高磁盤可靠性的技術(shù)8.5 數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制38.1 外存的組織外存的組織(分配）方式分配）方式 磁盤具有可直接訪問(wèn)可直接訪問(wèn)的特性，利用磁盤來(lái)存放文件具有靈活性。在為文件分配外存空間時(shí)考慮的主要問(wèn)題主要問(wèn)題有： 有效利用外存空間有效利用外存空間 提高對(duì)文件的提高對(duì)文件的訪問(wèn)速率訪問(wèn)速率 8.1.1 連續(xù)連續(xù)組織組織 8. 1.2 鏈接鏈接組織組織8. 1.3 FAT

2、8. 1.3 NTFS技術(shù)技術(shù) 8. 1.4 索引索引組織組織4文件的三大物理結(jié)構(gòu)文件的三大物理結(jié)構(gòu)1 連續(xù)連續(xù)分配分配 （連續(xù)連續(xù)/順序順序結(jié)構(gòu)）結(jié)構(gòu)） 2 鏈接鏈接分配分配 （鏈接鏈接結(jié)構(gòu)）結(jié)構(gòu)）( FAT和和NTFS技術(shù)技術(shù) )3 索引索引分配分配 （索引索引結(jié)構(gòu)）結(jié)構(gòu)）連續(xù)連續(xù)結(jié)構(gòu):文件信息存于外存儲(chǔ)器的若干連續(xù)連續(xù)塊中；鏈接鏈接結(jié)構(gòu)：文件信息散布在外存儲(chǔ)器的若干不連續(xù)不連續(xù)塊中，由指針連接指針連接起來(lái)；索引索引結(jié)構(gòu)：文件信息散存于外存儲(chǔ)器的若干塊中，另外建立一個(gè)索引表建立一個(gè)索引表，表中存有該記錄在外存儲(chǔ)器位置的對(duì)應(yīng)關(guān)系58.1.1 連續(xù)分配連續(xù)分配(又稱“順序分配”)1. 連續(xù)分配

3、方式連續(xù)分配方式（Continuous Allocation） 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)：文件分配一組連續(xù)的盤塊 文件地址文件地址：第一盤塊號(hào)和文件長(zhǎng)度（圖8-1） 外存碎片：外存碎片：通過(guò)緊縮將外存空閑空間合并成連續(xù)的區(qū)域2. 連續(xù)分配的優(yōu)缺點(diǎn)連續(xù)分配的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 順序訪問(wèn)容易 順序訪問(wèn)速度快 缺點(diǎn)：缺點(diǎn)： 要求有連續(xù)的磁盤空間 必須事先知道文件的長(zhǎng)度P251TU8-11230567491011813141512171819162122232025262724list29303128mailcountfilestart lengthcount 02tr153mail216list293f7

4、2目錄trf圖8-1磁盤空間的連續(xù)分配 678.1.2 鏈接組織（鏈接組織（Chained Allocation） 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu) 文件分配到文件分配到離散離散的盤塊中，通過(guò)的盤塊中，通過(guò)鏈接指針鏈接指針 將這些離散的盤塊鏈成一個(gè)鏈表。將這些離散的盤塊鏈成一個(gè)鏈表。 鏈接的形式鏈接的形式1. 隱式鏈接隱式鏈接 2. 顯式鏈接顯式鏈接81. 隱式鏈接隱式鏈接n每個(gè)目錄項(xiàng)中，都須含有指向鏈接文件第一個(gè)盤每個(gè)目錄項(xiàng)中，都須含有指向鏈接文件第一個(gè)盤塊和最后一個(gè)盤塊的指針塊和最后一個(gè)盤塊的指針(圖6-8)n主要問(wèn)題：主要問(wèn)題：只適合順序訪問(wèn)，隨機(jī)訪問(wèn)極其低效只適合順序訪問(wèn)，隨機(jī)訪問(wèn)極其低效 如要訪問(wèn)文

5、件所在的第如要訪問(wèn)文件所在的第i i個(gè)盤塊，則必須先讀出個(gè)盤塊，則必須先讀出文件的第一個(gè)盤塊文件的第一個(gè)盤塊，這樣順序地查找直至第，這樣順序地查找直至第i i塊?？梢?jiàn)，隨機(jī)訪問(wèn)的速度相當(dāng)?shù)?。塊?？梢?jiàn)，隨機(jī)訪問(wèn)的速度相當(dāng)?shù)?。n可靠性較差可靠性較差。只要其中的任何一個(gè)指針出現(xiàn)問(wèn)。只要其中的任何一個(gè)指針出現(xiàn)問(wèn)題，都會(huì)導(dǎo)致整個(gè)鏈的斷開(kāi)。題，都會(huì)導(dǎo)致整個(gè)鏈的斷開(kāi)。TU8-225123056749101181314151217181916212223202526272429303128filestartendjeep925目錄101-116圖8-2磁盤空間的鏈接式分配（隱式） 9102. 顯式鏈接顯式鏈接

6、n把鏈接文件各物理塊的指針，把鏈接文件各物理塊的指針，顯式地存放在內(nèi)存的一顯式地存放在內(nèi)存的一張鏈接表張鏈接表中。該表在整個(gè)磁盤僅設(shè)置一張中。該表在整個(gè)磁盤僅設(shè)置一張(圖8-3所示)n表中凡是屬于某一文件的第一個(gè)盤塊號(hào)，均作為文件表中凡是屬于某一文件的第一個(gè)盤塊號(hào)，均作為文件地址被填入相應(yīng)文件的地址被填入相應(yīng)文件的FCB的的“物理地址物理地址”字段中。字段中。n顯著提高了檢索速度，大大減少了訪問(wèn)磁盤的次數(shù)。顯著提高了檢索速度，大大減少了訪問(wèn)磁盤的次數(shù)。n由于分配給文件的所有盤塊號(hào)都放在該表中，故該表由于分配給文件的所有盤塊號(hào)都放在該表中，故該表有稱為有稱為文件分配表(File Allocati

7、on Table)nMS-DOS的文件物理結(jié)構(gòu)(FAT)TU 8-3012345物理塊號(hào)2FCBFAT0451圖8-3顯式鏈接結(jié)構(gòu) 11128.1.3 FAT和和NTFS技術(shù)技術(shù)n早期MS-DOS的FAT文件系統(tǒng)引入“卷卷”，支持一個(gè)物理磁盤分成4個(gè)邏輯磁盤（卷、分區(qū)卷、分區(qū)），每個(gè)分區(qū)都是一個(gè)能夠被單獨(dú)格式化和使用的邏輯單元，供文件系統(tǒng)分配空間時(shí)使用n每個(gè)分區(qū)包含每個(gè)分區(qū)包含: :文件系統(tǒng)信息文件系統(tǒng)信息 + + 一組文件一組文件 + + 空閑空間，空閑空間，并有單獨(dú)存放目錄和并有單獨(dú)存放目錄和FATFAT表的區(qū)域表的區(qū)域1. FAT12 2. FAT16 3. FAT32 4. NTFS1

8、31. FAT121) 以以盤塊盤塊為基本分配單位為基本分配單位 早期MS-DOS使用FAT12文件系統(tǒng)，每個(gè)分區(qū)中配有兩張文件分配表FAT1FAT1和FAT2FAT2，F(xiàn)AT的每個(gè)表項(xiàng)中存放下一個(gè)盤塊號(hào)，通過(guò)它將文件的所有盤塊鏈接起來(lái)，而文件的第一個(gè)盤塊號(hào)放在FCB中。 MS-DOSMS-DOS的文件物理結(jié)構(gòu)的文件物理結(jié)構(gòu) 圖8-4 整個(gè)系統(tǒng)有一張文件分配表整個(gè)系統(tǒng)有一張文件分配表FAT TU8-46EOF11105EOF0123456789FATFCB A4FCB B9圖8-4MS-DOS的文件物理結(jié)構(gòu) 文件文件A A占占3 3個(gè)盤塊，盤個(gè)盤塊，盤塊號(hào)為塊號(hào)為4 4、6 6、1111；文件

9、文件B B則占用則占用9 9、1010及及5 5號(hào)號(hào)3 3個(gè)盤塊。個(gè)盤塊。每個(gè)文件的第一個(gè)盤每個(gè)文件的第一個(gè)盤塊號(hào)放在自己的塊號(hào)放在自己的FCBFCB中。中。14151. FAT12n對(duì)1.2MB的軟盤，盤塊大小為512B，F(xiàn)AT中共含有2.4K個(gè)表項(xiàng)，由于每個(gè)FAT表項(xiàng)占12位，故FAT表占用3.6KB的存儲(chǔ)空間n以盤塊為分配單位時(shí)最大磁盤容量問(wèn)題以盤塊為分配單位時(shí)最大磁盤容量問(wèn)題每個(gè)FAT表項(xiàng)1212位位，F(xiàn)AT表中最多允許有40964096項(xiàng)；盤塊大小是512B,每個(gè)磁盤分區(qū)的容量為2 MB(4096512B)。一個(gè)物理磁盤支持4個(gè)邏輯分區(qū)，相應(yīng)的磁盤最大容量?jī)H為8 MB。 8MB對(duì)最早

10、時(shí)期的硬盤還可應(yīng)付，但很快容量就超過(guò)了，F(xiàn)AT12FAT12還能繼續(xù)用還能繼續(xù)用? Yes.引入新的分配單位簇簇。161. FAT12例如例如: : 簇僅有一個(gè)扇區(qū)時(shí)，磁盤的最大容量為8 MB； 簇包含兩個(gè)扇區(qū)時(shí)，磁盤的最大容量可達(dá)16MB； 簇包含八個(gè)扇區(qū)時(shí)，磁盤的最大容量可達(dá)64MB。2)2) 簇簇的基本概念的基本概念進(jìn)行盤塊分配時(shí)，不再以盤塊而是以簇進(jìn)行盤塊分配時(shí)，不再以盤塊而是以簇( (cluster)cluster)為基為基本單位。本單位。簇是一組連續(xù)的扇區(qū)簇是一組連續(xù)的扇區(qū)，在FAT中它是作為一個(gè)虛擬扇區(qū)，簇的大小一般是2 2n n 個(gè)盤塊簇包含扇區(qū)的數(shù)量與磁盤容量的大小直接有關(guān)簇

11、包含扇區(qū)的數(shù)量與磁盤容量的大小直接有關(guān)171. FAT123) 3) FAT12FAT12存在的問(wèn)題存在的問(wèn)題所允許的磁盤容量存在著嚴(yán)重的限制所允許的磁盤容量存在著嚴(yán)重的限制，通常只能是幾十個(gè)M Megabytes，雖可繼續(xù)增加簇的大小來(lái)提高最大磁盤容量，但隨著支持的硬盤容量的增加，相應(yīng)的簇內(nèi)碎片也將隨之成倍地增加。只能支持只能支持8+38+3格式的文件名格式的文件名181616位位最大表項(xiàng)數(shù)最大表項(xiàng)數(shù)65536(265536(21616) )個(gè)，可將一個(gè)磁盤分區(qū)個(gè)，可將一個(gè)磁盤分區(qū)分為分為6553665536個(gè)簇。在個(gè)簇。在FAT16FAT16的每個(gè)簇中可以有的盤塊數(shù)的每個(gè)簇中可以有的盤塊數(shù)

12、為為4 4、8 8、1616、3232直到直到6464，由此得出，由此得出FAT16FAT16可以管理的最可以管理的最大分區(qū)空間為大分區(qū)空間為2 216166464512 = 2048 512 = 2048 MBMB。 2. FAT16問(wèn)題問(wèn)題 FAT12所存在的問(wèn)題的根本原因在于，F(xiàn)AT12表最多只允許4096個(gè)表項(xiàng)，亦即最多只能將一個(gè)磁盤分區(qū)分為4096個(gè)簇。隨著磁盤容量的增加，必定會(huì)引起簇的大隨著磁盤容量的增加，必定會(huì)引起簇的大小和簇內(nèi)碎片也隨之增加。小和簇內(nèi)碎片也隨之增加。解決方法解決方法 增加增加FATFAT表的表項(xiàng)數(shù)，即增加表的表項(xiàng)數(shù)，即增加FATFAT表的寬度表的寬度192. F

13、AT16有改善，但改善有限。有改善，但改善有限。當(dāng)磁盤容量較大時(shí)，使用當(dāng)磁盤容量較大時(shí)，使用FAT16FAT16，所形成的簇內(nèi)碎片所形成的簇內(nèi)碎片所造成的浪費(fèi)會(huì)很大所造成的浪費(fèi)會(huì)很大。例如例如 當(dāng)磁盤分區(qū)大小為8GB時(shí)，則每簇的大小達(dá)到128 KB，這意味著內(nèi)部零頭最大可達(dá)到128 KB。 一般對(duì)一般對(duì)1 14 4 GBGB的硬盤來(lái)說(shuō)，大約會(huì)浪費(fèi)的硬盤來(lái)說(shuō)，大約會(huì)浪費(fèi)10102020的空間。的空間。為了解決這一問(wèn)題，微軟推出了為了解決這一問(wèn)題，微軟推出了FAT32FAT32 20 FAT系列文件系統(tǒng)的最后一個(gè)產(chǎn)品。 FAT32文件系統(tǒng)的每一簇在FAT表中的表項(xiàng)占據(jù)4B(232)，F(xiàn)AT表可以表

14、示4 294 967 2964 294 967 296項(xiàng)。 FAT32FAT32中采用較小的簇中采用較小的簇，每個(gè)簇都固定為4 KB，每個(gè)盤塊仍為512B，F(xiàn)AT32分區(qū)格式可以管理的單個(gè)最大磁盤空間大到4KB232 = 16TB。實(shí)際上，實(shí)際上，F(xiàn)AT32FAT32僅使用僅使用2828位簇標(biāo)識(shí)符，位簇標(biāo)識(shí)符，在簇大小為在簇大小為4KB4KB時(shí)，時(shí)，最大磁盤空間大到最大磁盤空間大到1TB1TB，若簇大小為，若簇大小為8KB8KB，則最大，則最大可為可為2TB2TB。3. FAT3221三種三種FATFAT中簇大小與最大分區(qū)的對(duì)應(yīng)關(guān)系中簇大小與最大分區(qū)的對(duì)應(yīng)關(guān)系塊大小/KB FAT12/MB F

15、AT16/MB FAT32/TB 0.5 2 1 4 2 8 128 4 16 256 1 8 512 2 16 1024 2 32 2048 2 228.1.4 NTFS技術(shù)技術(shù)1) NTFS1) NTFS新特征新特征NTFS(New Technology File System)是一個(gè)專門為Windows NT開(kāi)發(fā)的、全新的文件系統(tǒng)，并適用于Windows 2000/XP/2003及后續(xù)使用使用64位磁盤地址位磁盤地址，理論上可支持支持2的的64次方次方字節(jié)的磁盤分區(qū)在NTFS中可以很好地支持長(zhǎng)文件名，單個(gè)文件名限制在255個(gè)字符以內(nèi)，全路徑名為32 767個(gè)字符；具有系統(tǒng)容錯(cuò)功能: 出現(xiàn)

16、故障或差錯(cuò)時(shí)，仍能保證系統(tǒng)正常運(yùn)行；提供了數(shù)據(jù)的一致性；提供了文件加密、壓縮等功能。 23NTFS2) 2) 磁盤組織磁盤組織NTFSNTFS也是以簇作為磁盤空間分配和回收的基本單位。也是以簇作為磁盤空間分配和回收的基本單位。一一個(gè)文件占用若干個(gè)簇，一個(gè)簇只屬于一個(gè)文件個(gè)文件占用若干個(gè)簇，一個(gè)簇只屬于一個(gè)文件通過(guò)簇間接管理磁盤，不需要知道扇區(qū)的大小，使NTFSNTFS具有與磁盤物理扇區(qū)大小無(wú)關(guān)的獨(dú)立性具有與磁盤物理扇區(qū)大小無(wú)關(guān)的獨(dú)立性，很容易支持扇區(qū)大小不是512字節(jié)的非標(biāo)準(zhǔn)磁盤，從而可以根據(jù)不同的磁盤選擇匹配的簇大小。 卷上簇的大小稱為“卷因子卷因子”，它是在磁盤格式化時(shí)確定的，其大小也是物

17、理磁盤扇區(qū)的整數(shù)倍，即一個(gè)簇包含2n個(gè)盤塊，簇的大可以為512B、1KB、2KB64 KB248.1.5 索引組織（索引組織（Index Allocation） 鏈接分配方式解決了連續(xù)分配方式存在的問(wèn)題，但出現(xiàn)鏈接分配方式解決了連續(xù)分配方式存在的問(wèn)題，但出現(xiàn)了另外兩個(gè)問(wèn)題：了另外兩個(gè)問(wèn)題：1 1、不支持直接存取、不支持直接存取(FAT中順序查找盤塊號(hào))2 2、FATFAT需占用較大的內(nèi)存空間需占用較大的內(nèi)存空間(只有將整個(gè)FAT調(diào)入內(nèi)存，才能保證在FAT中找到文件的所有盤塊號(hào))1.單級(jí)索引分配單級(jí)索引分配 2.多級(jí)索引分配多級(jí)索引分配 3.增量式分配方式增量式分配方式解決方法解決方法： FAT

18、部分部分調(diào)入內(nèi)存調(diào)入內(nèi)存（基于這種想法，形成索引分配方法）251. 單級(jí)索引分配單級(jí)索引分配 每個(gè)文件分配一個(gè)索引塊(表)，再把分配給該文件的所有盤塊號(hào)都記錄在該索引塊中，因而該索引塊是個(gè)數(shù)組。文件的目錄項(xiàng)中填上指向該索引塊的指針 (圖8-6) 支持高效的直接存取支持高效的直接存取(索引表)主要問(wèn)題：花費(fèi)較多的外存空間主要問(wèn)題：花費(fèi)較多的外存空間（小文件）TU8-6123056749101181314151217181916212223202526272429303128countfile塊序號(hào)jeep19目錄9161102511119圖8-6索引分配方式 26272. 多級(jí)索引分配多級(jí)索引分

19、配n當(dāng)文件盤塊號(hào)裝滿一個(gè)索引塊時(shí)，需要再分配另一個(gè)當(dāng)文件盤塊號(hào)裝滿一個(gè)索引塊時(shí)，需要再分配另一個(gè)索引塊，可通過(guò)索引塊，可通過(guò)鏈指針將各索引塊按序鏈接起來(lái)鏈指針將各索引塊按序鏈接起來(lái)。n當(dāng)文件太大，其索引塊太多，這種方法低效。當(dāng)文件太大，其索引塊太多，這種方法低效。n解決方法解決方法：為索引塊建立索引，稱為第一級(jí)索引，形成兩級(jí)索引分配方式。如果文件非常大時(shí)，還可用三級(jí)、四級(jí)索引分配方式(圖8-7) 例如：例如：盤塊大小盤塊大小1 1KBKB，每個(gè)盤塊號(hào)占每個(gè)盤塊號(hào)占4 4B B，那么一個(gè)索那么一個(gè)索引塊中可存放引塊中可存放256256個(gè)盤塊號(hào)。在兩級(jí)索引時(shí)，最多可個(gè)盤塊號(hào)。在兩級(jí)索引時(shí)，最多可存

20、放的盤塊號(hào)總數(shù)存放的盤塊號(hào)總數(shù)N = 256N = 256256 = 64K256 = 64K個(gè)，允許的文個(gè)，允許的文件最大長(zhǎng)度為件最大長(zhǎng)度為64 64 MBMB。 TU8-701210510625435635798510510625474035635711259853607401125主索引360第二級(jí)索引磁盤空間圖圖8 8- -7 7兩級(jí)索引分配兩級(jí)索引分配 28293. 增量式（混合）分配方式增量式（混合）分配方式多種索引分配方式相結(jié)合而形成的一種分配方多種索引分配方式相結(jié)合而形成的一種分配方式。式。例如例如：系統(tǒng)既采用直接地址，又采用一級(jí)索引分配，或兩系統(tǒng)既采用直接地址，又采用一級(jí)索引

21、分配，或兩 級(jí)索引分配，甚至還采用了三級(jí)索引分配方式。級(jí)索引分配，甚至還采用了三級(jí)索引分配方式。 這種混合索引分配方式在這種混合索引分配方式在UNIX系統(tǒng)中采用。在系統(tǒng)中采用。在UNIX System 的索引結(jié)點(diǎn)中，共設(shè)置了的索引結(jié)點(diǎn)中，共設(shè)置了13個(gè)地址個(gè)地址項(xiàng)，即項(xiàng)，即iaddr(0)iaddr(12) (圖圖8-8) 。在在BSD UNIX的的索引結(jié)點(diǎn)中，共設(shè)置了索引結(jié)點(diǎn)中，共設(shè)置了13個(gè)地址項(xiàng)，它們都把所有個(gè)地址項(xiàng)，它們都把所有的地址項(xiàng)分成兩類，即的地址項(xiàng)分成兩類，即直接地址直接地址和和間接地址間接地址 modeowners (2)time stamps (3)sizeblock co

22、unti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata圖8-8增量式（混合）索引方式 3031n直接地址：直接地址：在索引結(jié)點(diǎn)中可設(shè)置1010個(gè)直接地址項(xiàng)個(gè)直接地址項(xiàng)，即用iaddr(0)iaddr(9)來(lái)存放直接地址。假如盤塊大小為4KB，當(dāng)文件不大于40KB時(shí)，便可直接從索引結(jié)點(diǎn)中讀出該文件的全部盤塊號(hào)n一次間接地址：一次間接地址：利用索引結(jié)點(diǎn)中的地址項(xiàng)iaddr(10)來(lái)提供一次間接地址(同二級(jí)索引：每

23、個(gè)盤塊號(hào)占同二級(jí)索引：每個(gè)盤塊號(hào)占4B,盤塊盤塊個(gè)數(shù)個(gè)數(shù)1KB),。實(shí)質(zhì)就是一級(jí)索引分配方式（大、中型文件，文件長(zhǎng)達(dá)4 MB）n多次間接地址：多次間接地址：文件大于4MB+40KB時(shí)，須采用二次間址分配方式。地址項(xiàng)iaddr(11)提供二次間接地址，實(shí)質(zhì)是兩級(jí)索引分配方式，此時(shí)文件最大長(zhǎng)度可達(dá)4 GB。同理，地址項(xiàng)iaddr(12)作為三次間接地址，其所允許的文件最大長(zhǎng)度可達(dá)4 TB unix操作系統(tǒng)上，如果一個(gè)塊的大小是塊的大小是1KB ,一個(gè)盤塊號(hào)占盤塊號(hào)占4個(gè)字節(jié)個(gè)字節(jié)(一個(gè)盤塊有256個(gè)地址)。請(qǐng)把下面的文件字節(jié)偏移量轉(zhuǎn)換為物理地址：（1）9999 （2）18000 （3）140000

24、32P276，11 （1）9999邏輯塊號(hào)：邏輯塊號(hào)：9999/1024=9 塊內(nèi)偏移量為塊內(nèi)偏移量為: 9999-9*1024=783 邏輯塊號(hào)邏輯塊號(hào)10, 直接地址直接地址物理地址為物理地址為: inode9+783 modeowners (2)time stamps (3)sizeblock counti.addr (0)i.addr (1)direct blockssingle indirectdouble indirecttriple indirectdatadatadatadatadatadatadatadatadatadata圖8-8增量式（混合）索引方式 33n直接地址：直接

25、地址： 可設(shè)10個(gè)直接地址項(xiàng)n一次間接地址：一次間接地址：n多次間接地址：多次間接地址：34 （2）18000 邏輯塊號(hào)：邏輯塊號(hào)： 18000/1024=17 塊內(nèi)偏移量為塊內(nèi)偏移量為: 18000-17*1024=592 1017256+10, 一次間接地址一次間接地址,若一次間接盤塊號(hào)為若一次間接盤塊號(hào)為MM中第中第17-10=7項(xiàng)地址，即物理塊號(hào)為項(xiàng)地址，即物理塊號(hào)為M7物理地址為物理地址為: M7+592 35 （3） 140000 140000 邏輯塊號(hào)：邏輯塊號(hào)： 420000/1024=410 塊內(nèi)偏移量為塊內(nèi)偏移量為: 420000-410*1024=160 10+25641

26、065802,(65536+256+10) 二次間接盤塊號(hào)二次間接盤塊號(hào)若二次間接的盤快號(hào)為若二次間接的盤快號(hào)為M，由于一次間接快可容納，由于一次間接快可容納256個(gè)塊號(hào)，且個(gè)塊號(hào)，且410-256-10=144 所以該文件的物理塊號(hào)在：所以該文件的物理塊號(hào)在：M0所指示的間接快所指示的間接快N的的第第144項(xiàng)項(xiàng)中的數(shù)據(jù)，中的數(shù)據(jù)，該地址的第該地址的第160字節(jié)字節(jié)即位文件的物理地址即位文件的物理地址8.2 文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理 先要記住先要記住空閑存儲(chǔ)空間空閑存儲(chǔ)空間的情況。為此，設(shè)置的情況。為此，設(shè)置相應(yīng)的數(shù)據(jù)結(jié)構(gòu)；系統(tǒng)要提供對(duì)存儲(chǔ)空間相應(yīng)的數(shù)據(jù)結(jié)構(gòu)；系統(tǒng)要提供對(duì)存儲(chǔ)空間分

27、配和分配和回收回收的功能。的功能。 空閑表法空閑表法/空閑鏈表法空閑鏈表法2. 位示圖位示圖法法3.成組鏈接法成組鏈接法368.2.1 空閑表法和空閑鏈表法（空閑表法和空閑鏈表法（1）1. 空閑表法空閑表法n空閑表：空閑表：外存每個(gè)空閑區(qū)空閑區(qū)對(duì)應(yīng)一個(gè)空閑表項(xiàng)n空間的分配和回收（可采用多種方式，如首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等）序號(hào)序號(hào) 第一空閑盤塊表第一空閑盤塊表 空閑盤塊數(shù)空閑盤塊數(shù) 1242933155 空閑盤塊表空閑盤塊表37 8.2.2 位示圖法位示圖法1. 位示圖位示圖每一位表示一個(gè)塊/簇，值0和1分別表示空閑和占用占用空間少、容易找到相鄰的空閑盤塊382. 盤塊的分配盤塊的分配

28、(三步三步) 順序掃描位示圖，找出一個(gè)一個(gè)/組組值是0的二進(jìn)制位 將找到的二進(jìn)制位，轉(zhuǎn)換成對(duì)應(yīng)的盤塊號(hào) b = n(i-1) + jb = n(i-1) + j 修改位示圖修改位示圖 map i,j = 1map i,j = 1 393. 盤塊的回收盤塊的回收(2步步) 將盤塊號(hào)b b轉(zhuǎn)換成位于圖中的行號(hào)和列號(hào) i=(b-1) DIV n + 1 i=(b-1) DIV n + 1 j=(b-1) MOD n + 1 j=(b-1) MOD n + 1 修改位示圖 mapi,j= 0 mapi,j= 040 8.2.3 成組鏈接法成組鏈接法1. 空閑盤塊的組織空閑盤塊的組織（圖8-11） 空閑

29、盤塊號(hào)?？臻e盤塊號(hào)棧：存放當(dāng)前可用可用的一組空閑盤塊的盤塊號(hào)所有空閑盤塊，被所有空閑盤塊，被分成若干個(gè)組分成若干個(gè)組每組含有的盤塊總數(shù)每組含有的盤塊總數(shù)N + 該組所有的盤塊號(hào)，記入前一該組所有的盤塊號(hào)，記入前一組的組的第一個(gè)盤塊的第一個(gè)盤塊的S.free(0)S.free(99)中。中。第一組的盤塊總數(shù)和所有盤塊號(hào)，記入第一組的盤塊總數(shù)和所有盤塊號(hào)，記入空閑盤塊號(hào)?？臻e盤塊號(hào)棧最末一組只有最末一組只有99個(gè)盤塊，盤塊號(hào)記入其前一組第一盤塊個(gè)盤塊，盤塊號(hào)記入其前一組第一盤塊的的S.free(1)S.free(99)中。而在中。而在S.free(0)中存放中存放“0”，作為空閑盤塊鏈的作為空閑盤

30、塊鏈的結(jié)束標(biāo)志結(jié)束標(biāo)志。 41圖8-11空閑盤塊的成組鏈接法 1004003993013001003002992022012991004003992013019907999790179007899780179997901空閑盤塊號(hào)棧S.free01989942438.3.2 提高磁盤提高磁盤I/O速度的其它方法速度的其它方法1. 提前讀提前讀(Read-Ahead) 2. 延遲寫(xiě)延遲寫(xiě)3. 優(yōu)化物理塊的分布優(yōu)化物理塊的分布4. 虛擬盤虛擬盤441. 提前讀提前讀(Read-Ahead)進(jìn)程對(duì)文件進(jìn)行訪問(wèn)時(shí)，常采用順序訪問(wèn)的方式進(jìn)程對(duì)文件進(jìn)行訪問(wèn)時(shí)，常采用順序訪問(wèn)的方式 這種情況下，讀當(dāng)前塊時(shí)可

31、預(yù)測(cè)下一次要讀的盤塊，采這種情況下，讀當(dāng)前塊時(shí)可預(yù)測(cè)下一次要讀的盤塊，采取預(yù)先讀方式將下一個(gè)盤塊的數(shù)據(jù)也讀入緩沖區(qū)取預(yù)先讀方式將下一個(gè)盤塊的數(shù)據(jù)也讀入緩沖區(qū)( (提前讀)。 當(dāng)下次要讀該盤塊中的數(shù)據(jù)時(shí)，由于數(shù)據(jù)已被提前讀入當(dāng)下次要讀該盤塊中的數(shù)據(jù)時(shí)，由于數(shù)據(jù)已被提前讀入緩沖區(qū)，便可直接從緩沖區(qū)中取得下一盤塊的數(shù)據(jù)，而不需緩沖區(qū)，便可直接從緩沖區(qū)中取得下一盤塊的數(shù)據(jù)，而不需再去啟動(dòng)磁盤再去啟動(dòng)磁盤I/OI/O，大大減少了讀數(shù)據(jù)的時(shí)間。也就等效于提大大減少了讀數(shù)據(jù)的時(shí)間。也就等效于提高了磁盤高了磁盤I/OI/O的速度。的速度。 452. 延遲寫(xiě)延遲寫(xiě)延遲寫(xiě)延遲寫(xiě)：在緩沖區(qū)A中的數(shù)據(jù)，本應(yīng)寫(xiě)回磁盤，

32、但考慮到在不久之后可能還會(huì)再被訪問(wèn)，因而并不立即寫(xiě)入磁盤，而是將它掛在空閑緩沖區(qū)隊(duì)列的末尾空閑緩沖區(qū)隊(duì)列的末尾。隨著空閑緩沖區(qū)的使用，緩沖區(qū)緩緩?fù)耙苿?dòng)。隨著空閑緩沖區(qū)的使用，緩沖區(qū)緩緩?fù)耙苿?dòng)。 當(dāng)有進(jìn)當(dāng)有進(jìn)程申請(qǐng)到該緩沖區(qū)時(shí)，才將數(shù)據(jù)寫(xiě)入磁盤程申請(qǐng)到該緩沖區(qū)時(shí)，才將數(shù)據(jù)寫(xiě)入磁盤，把該緩沖，把該緩沖區(qū)作為空閑緩沖區(qū)分配出去區(qū)作為空閑緩沖區(qū)分配出去。當(dāng)該緩沖區(qū)A仍在隊(duì)列中時(shí)，任何進(jìn)程都可直接讀其中數(shù)據(jù)而不必訪問(wèn)磁盤。這樣，可進(jìn)一步減小等效的磁盤I/O時(shí)間。463. 優(yōu)化物理塊的分布優(yōu)化物理塊的分布 另一種提高磁盤I/O速度的措施是優(yōu)化文件物理優(yōu)化文件物理塊的分布，使磁頭的移動(dòng)距離最小塊的分布，

33、使磁頭的移動(dòng)距離最小。例如：例如：文件的第一個(gè)盤塊安排在最里的一條磁道上，文件的第一個(gè)盤塊安排在最里的一條磁道上，而第二個(gè)盤塊安排在最外的一條磁道上。如此，讀而第二個(gè)盤塊安排在最外的一條磁道上。如此，讀完第一個(gè)盤塊后讀第二個(gè)盤塊時(shí)，磁頭要從最里的完第一個(gè)盤塊后讀第二個(gè)盤塊時(shí)，磁頭要從最里的磁道移到最外的磁道上。若安排在同一條磁道，會(huì)磁道移到最外的磁道上。若安排在同一條磁道，會(huì)大大提高對(duì)這兩盤塊的訪問(wèn)速度大大提高對(duì)這兩盤塊的訪問(wèn)速度。474. 虛擬盤虛擬盤 所謂虛擬盤，是指利用內(nèi)存空間去仿真磁盤，所謂虛擬盤，是指利用內(nèi)存空間去仿真磁盤，又又稱為稱為RAMRAM盤。盤。該盤的設(shè)備驅(qū)動(dòng)程序也可以接受

34、所有標(biāo)準(zhǔn)的磁盤操作，但這些操作的執(zhí)行不是在磁盤上而是在內(nèi)存中。操作對(duì)用戶都是透明的。484. 虛擬盤虛擬盤虛擬盤的主要問(wèn)題虛擬盤的主要問(wèn)題 它是易失性存儲(chǔ)器，故一旦系統(tǒng)或電源發(fā)生故障，或系統(tǒng)再啟動(dòng)時(shí)，原來(lái)保存在虛擬盤中的數(shù)據(jù)將會(huì)丟失。虛擬盤與磁盤高速緩存的主要區(qū)別虛擬盤與磁盤高速緩存的主要區(qū)別 虛擬盤中的內(nèi)容完全由用戶控制，高速磁盤緩存中的虛擬盤中的內(nèi)容完全由用戶控制，高速磁盤緩存中的內(nèi)容則由內(nèi)容則由OSOS控制的?？刂频?。例如：例如：RAM盤在開(kāi)始時(shí)是空的，僅當(dāng)用戶(程序)在RAM盤中創(chuàng)建了文件后，RAM盤中才有內(nèi)容。 498.3.3 廉價(jià)磁盤冗余陣列廉價(jià)磁盤冗余陣列RAID1. 并行交叉存

35、取并行交叉存取2. RAID的分級(jí)的分級(jí)3. RAID的優(yōu)點(diǎn)的優(yōu)點(diǎn) 利用一臺(tái)磁盤陣列控制器，來(lái)統(tǒng)一管理和利用一臺(tái)磁盤陣列控制器，來(lái)統(tǒng)一管理和控制一組控制一組( (幾臺(tái)到幾十臺(tái)幾臺(tái)到幾十臺(tái)) )磁盤驅(qū)動(dòng)器，組成一磁盤驅(qū)動(dòng)器，組成一個(gè)大型磁盤系統(tǒng)。個(gè)大型磁盤系統(tǒng)。（Redundant Array of Inexpensive Disks）508.3.3 廉價(jià)磁盤冗余陣列廉價(jià)磁盤冗余陣列RAID并行交叉存取并行交叉存取N塊硬盤通過(guò)RAID Controller，結(jié)合成虛擬單塊大容量的硬盤使用，特色是：N塊硬盤同時(shí)讀取速度加快及提供容錯(cuò)性Fault TolerantTu5-29 在該系統(tǒng)中，有多臺(tái)磁盤

36、驅(qū)動(dòng)器，系統(tǒng)將每一盤塊中在該系統(tǒng)中，有多臺(tái)磁盤驅(qū)動(dòng)器，系統(tǒng)將每一盤塊中的數(shù)據(jù)分為若干個(gè)子盤塊數(shù)據(jù)，再把每一的數(shù)據(jù)分為若干個(gè)子盤塊數(shù)據(jù)，再把每一個(gè)子盤塊的數(shù)據(jù)個(gè)子盤塊的數(shù)據(jù)分別存儲(chǔ)到各個(gè)不同磁盤中的相同位置上分別存儲(chǔ)到各個(gè)不同磁盤中的相同位置上。 以后，當(dāng)要將一個(gè)盤塊的數(shù)據(jù)傳送到內(nèi)存時(shí)，采取以后，當(dāng)要將一個(gè)盤塊的數(shù)據(jù)傳送到內(nèi)存時(shí)，采取并并行傳輸行傳輸方式，將各個(gè)盤塊中的子盤塊數(shù)據(jù)同時(shí)向內(nèi)存中傳方式，將各個(gè)盤塊中的子盤塊數(shù)據(jù)同時(shí)向內(nèi)存中傳輸，從而使傳輸時(shí)間大大減少。輸，從而使傳輸時(shí)間大大減少。123N圖圖8 8- -1212磁盤并行交叉存取方式磁盤并行交叉存取方式 5152廉價(jià)磁盤冗余陣列廉價(jià)磁盤

37、冗余陣列RAIDlRAID 0 級(jí)：并行交叉存取lRAID 1 級(jí)：具有磁盤鏡像功能lRAID 2級(jí)：并行傳輸、奇偶校驗(yàn)功能lRAID 5 級(jí)：獨(dú)立傳送、獨(dú)立數(shù)據(jù)通道 、校驗(yàn)信息螺旋分布lRAID 6 級(jí)和 RAID 7 級(jí)2. RAID的分級(jí)的分級(jí)剛被推出時(shí)，分成剛被推出時(shí)，分成6級(jí)，即級(jí)，即RAID 0級(jí)至級(jí)至RAID 5級(jí)，后來(lái)又增加級(jí)，后來(lái)又增加RAID 6級(jí)和級(jí)和RAID 7級(jí)。級(jí)。535.6.5 廉價(jià)磁盤冗余陣列廉價(jià)磁盤冗余陣列RAIDl可靠性高可靠性高。采用容錯(cuò)技術(shù)容錯(cuò)技術(shù)（RAID 0級(jí)除外）。當(dāng)某一磁盤損壞時(shí)，不會(huì)造成數(shù)據(jù)的丟失，因?yàn)榭赏ㄟ^(guò)磁盤鏡像/磁盤雙工/其它冗余方式恢復(fù)

38、。l磁盤磁盤I/OI/O速度高速度高。采取并行交叉存取方式，可將磁盤I/O速度提高N-1倍(N為磁盤數(shù)目)。l性能性能/ /價(jià)格比高價(jià)格比高。利用RAID技術(shù)來(lái)實(shí)現(xiàn)大容量高速存儲(chǔ)器時(shí)，其體積與具有相同容量和速度的大型磁盤系統(tǒng)相比，只是后者的1/3，價(jià)格也只是后者的1/3，且可靠性高。3. RAID的優(yōu)點(diǎn)的優(yōu)點(diǎn)（Redundant Array of Independent Disk）8.5 數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制8.5.1 事務(wù)事務(wù) 8.5.2 檢查點(diǎn)檢查點(diǎn) 8.5. 3 并發(fā)控制并發(fā)控制 數(shù)據(jù)數(shù)據(jù)存儲(chǔ)到多個(gè)文件存儲(chǔ)到多個(gè)文件中，會(huì)出現(xiàn)一致性問(wèn)題。中，會(huì)出現(xiàn)一致性問(wèn)題。大多數(shù)大多數(shù)OSOS中有能確保中有能確保數(shù)據(jù)一致性的機(jī)制數(shù)據(jù)一致性的機(jī)制，用于保證文件系，用于保證文件系統(tǒng)中的數(shù)據(jù)一致性統(tǒng)中的數(shù)據(jù)一致性( (記憶狀態(tài)記憶狀態(tài)和恢復(fù)和恢復(fù)) )。需硬件支持，最重要的是需硬件支持，最重要的是存儲(chǔ)器系統(tǒng)。存儲(chǔ)器系統(tǒng)。548.5.1 事務(wù)事務(wù)1. 1. 事務(wù)事務(wù) 用于訪問(wèn)和修改各個(gè)數(shù)據(jù)項(xiàng)的一個(gè)程序單位訪問(wèn)和修改各個(gè)數(shù)據(jù)項(xiàng)的一個(gè)程序單位；被訪問(wèn)的數(shù)據(jù)可以分散在多個(gè)文件中，事務(wù)可看作是一系列事務(wù)可看作是一系列讀和寫(xiě)操作讀和寫(xiě)操作。 v當(dāng)這些操作全部完成時(shí)，再以當(dāng)這些操作全部完成時(shí)，再以托付操作托付操作來(lái)終止事務(wù)。來(lái)