《管理學第8章 湯小丹,計算機操作系統(tǒng),官方通用課件,第四版,計算機,操作系統(tǒng), 通用課件,》由會員分享，可在線閱讀，更多相關《管理學第8章 湯小丹,計算機操作系統(tǒng),官方通用課件,第四版,計算機,操作系統(tǒng), 通用課件,（83頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、1 1第八章 磁盤存儲器的管理第八章第八章 磁盤存儲器的管理磁盤存儲器的管理8.1 外存的組織方式8.2 文件存儲空間的管理8.3 提高磁盤I/O速度的途徑8.4 提高磁盤可靠性的技術(shù)8.5 數(shù)據(jù)一致性控制習題2 2第八章 磁盤存儲器的管理8.1 外存的組織方式如前所述，文件的物理結(jié)構(gòu)直接與外存的組織方式有關。對于不同的外存組織方式，將形成不同的文件物理結(jié)構(gòu)。目前常用的外存組織方式有：(1)連續(xù)組織方式。(2)鏈接組織方式。(3)索引組織方式。3 3第八章 磁盤存儲器的管理8.1.1 連續(xù)組織方式連續(xù)組織方式又稱連續(xù)分配方式，要求為每一個文件分配一組相鄰接的盤塊。例如，第一個盤塊的地址為b，則

2、第二個盤塊的地址為b+1，第三個盤塊的地址為b+2，。通常，它們都位于一條磁道上，在進行讀/寫時，不必移動磁頭。在采用連續(xù)組織方式時，可把邏輯文件中的記錄順序地存儲到鄰接的各物理盤塊中，這樣所形成的文件結(jié)構(gòu)稱為順序文件結(jié)構(gòu)，此時的物理文件稱為順序文件。4 4第八章 磁盤存儲器的管理圖8-1 磁盤空間的連續(xù)組織方式5 5第八章 磁盤存儲器的管理連續(xù)組織方式的主要優(yōu)點有：(1)順序訪問容易。(2)順序訪問速度快。6 6第八章 磁盤存儲器的管理連續(xù)組織方式的主要缺點如下：(1)要求為一個文件分配連續(xù)的存儲空間。(2)必須事先知道文件的長度。(3)不能靈活地刪除和插入記錄。(4)對于那些動態(tài)增長的文件

3、。7 7第八章 磁盤存儲器的管理8.1.2 鏈接組織方式如果可以將文件裝到多個離散的盤塊中，就可消除連續(xù)組織方式的上述缺點。在采用鏈接組織方式時，可為文件分配多個不連續(xù)的盤塊，再通過每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，由此所形成的物理文件稱為鏈接文件。鏈接組織方式的主要優(yōu)點是：(1)消除了磁盤的外部碎片，提高了外存的利用率。(2)對插入、刪除和修改記錄都非常容易。(3)能適應文件的動態(tài)增長，無需事先知道文件的大小。8 8第八章 磁盤存儲器的管理1.隱式鏈接在采用隱式鏈接組織方式時，在文件目錄的每個目錄項中，都須含有指向鏈接文件第一個盤塊和最后一個盤塊的指針。9

4、 9第八章 磁盤存儲器的管理圖8-2 磁盤空間的鏈接式分配10 10第八章 磁盤存儲器的管理2.顯式鏈接這是指把用于鏈接文件各物理塊的指針顯式地存放在內(nèi)存的一張鏈接表中。該表在整個磁盤中僅設置一張，如圖8-3所示。11 11第八章 磁盤存儲器的管理圖8-3 顯式鏈接結(jié)構(gòu)12 12第八章 磁盤存儲器的管理8.1.3 FAT技術(shù)1.FAT12 1)早期的FAT12文件系統(tǒng) FAT12是以盤塊為基本分配單位的。由于FAT是文件系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu)，為了安全起見，在每個分區(qū)中都配有兩張相同的文件分配表FAT1和FAT2。在FAT的每個表項中存放下一個盤塊號，它實際上是用于盤塊之間的鏈接的指針，通過它

5、可以將一個文件的所有的盤塊鏈接起來，而將文件的第一個盤塊號放在自己的FCB中。13 13第八章 磁盤存儲器的管理圖8-4 MS-DOS的文件物理結(jié)構(gòu)14 14第八章 磁盤存儲器的管理2)以簇為單位的FAT12文件系統(tǒng) 稍加分析便可看出，如果把每個盤塊(扇區(qū))的容量增大n倍，則磁盤的最大容量便可增加n倍。但要增加盤塊的容量是不方便和不靈活的。為此，引入了簇(cluster)的概念。15 15第八章 磁盤存儲器的管理2.FAT16 FAT12對磁盤容量限制的原因在于，F(xiàn)AT12表中的表項有限制，亦即最多只允許4096個。這樣，隨著磁盤容量的增加，必定會引起簇的大小和簇內(nèi)碎片也隨之增加。16 16第

6、八章 磁盤存儲器的管理3.FAT32由于FAT16表的長度只有65535項，隨著磁盤容量的增加，簇的大小也必然會隨之增加，為了減少簇內(nèi)零，也就應當增加FAT表的長度，為此需要再增加FAT表的寬度，這樣也就由FAT16演變?yōu)镕AT32。17 17第八章 磁盤存儲器的管理圖8-5 FAT中簇的大小與最大分區(qū)的對應關系18 18第八章 磁盤存儲器的管理8.1.4 NTFS的文件組織方式1.NTFS新特征NTFS(New Technology File System)是一個專門為Windows NT開發(fā)的、全新的文件系統(tǒng)，并適用于Windows 2000/XP及后續(xù)的Windows OS。19 19第

7、八章 磁盤存儲器的管理2.磁盤組織NTFS是以簇作為磁盤空間分配和回收的基本單位的。一個文件占用若干個簇，一個簇只屬于一個文件。這樣，在為文件分配磁盤空間時，就無須知道盤塊的大小，只要根據(jù)不同的磁盤容量，選擇相應大小的簇，即使NTFS具有了與磁盤物理塊大小無關的獨立性。2020第八章 磁盤存儲器的管理3.文件的組織在NTFS中，以卷為單位，將一個卷中的所有文件信息、目錄信息以及可用的未分配空間信息，都以文件記錄的方式記錄在一張主控文件表MFT(Master File Table)中，該表是NTFS卷結(jié)構(gòu)的中心，從邏輯上講，卷中的每個文件作為一條記錄，在MFT表中占有一行，其中還包括MFT自己的

8、這一行。每行大小固定為1KB，每行稱為該行所對應文件的元數(shù)據(jù)(metadata)，也稱為文件控制字。21 21第八章 磁盤存儲器的管理8.1.5 索引組織方式1.單級索引組織方式鏈接組織方式雖然解決了連續(xù)組織方式所存在的問題(即不便于隨機訪問)，但又出現(xiàn)了另外兩個問題，即：不能支持高效的直接存取，要對一個較大的文件進行存取，須在FAT中順序地查找許多盤塊號；FAT需占用較大的內(nèi)存空間，由于一個文件所占用盤塊的盤塊號是隨機地分布在FAT中的，因而只有將整個FAT調(diào)入內(nèi)存，才能保證在FAT中找到一個文件的所有盤塊號。2222第八章 磁盤存儲器的管理圖8-6 索引分配方式2323第八章 磁盤存儲器的

9、管理2.多級索引組織方式在為一個大文件分配磁盤空間時，如果所分配出去的盤塊的盤塊號已經(jīng)裝滿一個索引塊時，OS須再為該文件分配另一個索引塊，用于將以后繼續(xù)為之分配的盤塊號記錄于其中。依此類推，再通過鏈指針將各索引塊按序鏈接起來。2424第八章 磁盤存儲器的管理圖8-7 兩級索引分配2525第八章 磁盤存儲器的管理3.增量式索引組織方式1)增量式索引組織方式的基本思想為了能較全面地照顧到小、中、大及特大型作業(yè)，可以采取多種組織方式來構(gòu)成文件的物理結(jié)構(gòu)。如果盤塊的大小為1KB或4KB，對于小文件(如1KB10KB或4KB40KB)而言，最多只會占用10個盤塊，為了能提高對數(shù)量眾多的小型作業(yè)的訪問速度

10、，最好能將它們的每一個盤塊地址都直接放入文件控制塊FCB(或索引結(jié)點)中，這樣就可以直接從FCB中獲得該文件的盤塊地址。2626第八章 磁盤存儲器的管理2)UNIX System V的組織方式在UNIX System V的索引結(jié)點中設有13個地址項，即i.addr(0)i.addr(12)，如圖8-8所示。(1)直接地址。(2)一次間接地址。(3)多次間接地址。2727第八章 磁盤存儲器的管理圖8-8 混合索引方式2828第八章 磁盤存儲器的管理8.2 文件存儲空間的管理8.2.1 空閑表法和空閑鏈表法1.空閑表法1)空閑表空閑表法屬于連續(xù)分配方式，它與內(nèi)存的動態(tài)分配方式雷同，它為每個文件分配

11、一塊連續(xù)的存儲空間。即系統(tǒng)也為外存上的所有空閑區(qū)建立一張空閑表，每個空閑區(qū)對應于一個空閑表項，其中包括表項序號、該空閑區(qū)的第一個盤塊號、該區(qū)的空閑盤塊數(shù)等信息。再將所有空閑區(qū)按其起始盤塊號遞增的次序排列，形成空閑盤塊表，如圖8-9所示。2929第八章 磁盤存儲器的管理圖8-9 空閑盤塊表3030第八章 磁盤存儲器的管理2)存儲空間的分配與回收空閑盤區(qū)的分配與內(nèi)存的分區(qū)(動態(tài))分配類似，同樣是采用首次適應算法和最佳適應算法等，它們對存儲空間的利用率大體相當，都優(yōu)于最壞適應算法。在系統(tǒng)為某新創(chuàng)建的文件分配空閑盤塊時，先順序地檢索空閑表的各表項，直至找到第一個其大小能滿足要求的空閑區(qū)，再將該盤區(qū)分配

12、給用戶(進程)，同時修改空閑表。31 31第八章 磁盤存儲器的管理2.空閑鏈表法1)空閑盤塊鏈這是將磁盤上的所有空閑空間以盤塊為單位拉成一條鏈，其中的每一個盤塊都有指向后繼盤塊的指針。2)空閑盤區(qū)鏈這是將磁盤上的所有空閑盤區(qū)(每個盤區(qū)可包含若干個盤塊)拉成一條鏈。在每個盤區(qū)上除含有用于指示下一個空閑盤區(qū)的指針外，還應有能指明本盤區(qū)大小(盤塊數(shù))的信息。3232第八章 磁盤存儲器的管理8.2.2 位示圖法1.位示圖位示圖是利用二進制的一位來表示磁盤中一個盤塊的使用情況。當其值為“0”時，表示對應的盤塊空閑；為“1”時，表示已分配。有的系統(tǒng)把“0”作為盤塊已分配的標志，把“1”作為空閑標志。(它們

13、在本質(zhì)上是相同的，都是用一位的兩種狀態(tài)來標志空閑和已分配兩種情況。)磁盤上的所有盤塊都有一個二進制位與之對應，這樣，由所有盤塊所對應的位構(gòu)成一個集合，稱為位示圖。3333第八章 磁盤存儲器的管理圖8-10 位示圖3434第八章 磁盤存儲器的管理2.盤塊的分配根據(jù)位示圖進行盤塊分配時，可分三步進行：(1)順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位(“0”表示空閑時)。(2)將所找到的一個或一組二進制位轉(zhuǎn)換成與之相應的盤塊號。假定找到的其值為“0”的二進制位位于位示圖的第i行、第j列，則其相應的盤塊號應按下式計算：b=n(i-1)+j式中，n代表每行的位數(shù)。(3)修改位示圖，令map

14、i,j=1。3535第八章 磁盤存儲器的管理3.盤塊的回收盤塊的回收分兩步：(1)將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。轉(zhuǎn)換公式為：i=(b-1)DIV n+1j=(b-1)MOD n+1(2)修改位示圖。令mapi,j=0。3636第八章 磁盤存儲器的管理8.2.3 成組鏈接法1.空閑盤塊的組織(1)空閑盤塊號棧，用來存放當前可用的一組空閑盤塊的盤塊號(最多含100個號)，以及棧中尚有的空閑盤塊(號)數(shù)N。順便指出，N還兼作棧頂指針用。3737第八章 磁盤存儲器的管理圖8-11 空閑盤塊的成組鏈接法3838第八章 磁盤存儲器的管理(2)文件區(qū)中的所有空閑盤塊被分成若干個組，比如，將每

15、100個盤塊作為一組。假定盤上共有10000個盤塊，每塊大小為1 KB，其中第2017999號盤塊用于存放文件，即作為文件區(qū)，這樣，該區(qū)的最末一組盤塊號應為79017999；次末組為78017900，倒數(shù)第二組的盤塊號為301400；第一組為201300，如圖8-11所示。(3)將每一組含有的盤塊總數(shù)N和該組所有的盤塊號記入其前一組的第一個盤塊的S.free(0)S.free(99)中。這樣，由各組的第一個盤塊可鏈成一條鏈。3939第八章 磁盤存儲器的管理(4)將第一組的盤塊總數(shù)和所有的盤塊號記入空閑盤塊號棧中，作為當前可供分配的空閑盤塊號。(5)最末一組只有99個盤塊，其盤塊號分別記入其前一

16、組的S.free(1)S.free(99)中，而在S.free(0)中則存放“0”，作為空閑盤塊鏈的結(jié)束標志。(注：最后一組的盤塊數(shù)應為99，不應是100，因為這是指可供使用的空閑盤塊。其編號應為(199)，0號中放空閑盤塊鏈的結(jié)尾標志。)4040第八章 磁盤存儲器的管理2.空閑盤塊的分配與回收當系統(tǒng)要為用戶分配文件所需的盤塊時，須調(diào)用盤塊分配過程來完成。該過程首先檢查空閑盤塊號棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號，將與之對應的盤塊分配給用戶，然后將棧頂指針下移一格。若該盤塊號已是棧底，即S.free(0)，這是當前棧中最后一個可分配的盤塊號。41 41第八章 磁盤存儲器的管理8.3

17、 提高磁盤I/O速度的途徑(1)改進文件的目錄結(jié)構(gòu)以及檢索目錄的方法來減少對目錄的查找時間；(2)選取好的文件存儲結(jié)構(gòu)，以提高對文件的訪問速度；(3)提高磁盤的I/O速度，能將文件中的數(shù)據(jù)快速地從磁盤傳送到內(nèi)存中，或者相反。其中的第1和第2點已在上一章或本章作了較詳細的闡述，本節(jié)主要對如何提高磁盤的I/O速度作一簡單介紹。4242第八章 磁盤存儲器的管理8.3.1 磁盤高速緩存(Disk Cache)在設計磁盤高速緩存時需要考慮的問題有：(1)如何將磁盤高速緩存中的數(shù)據(jù)傳送給請求進程；(2)采用什么樣的置換策略；(3)已修改的盤塊數(shù)據(jù)在何時被寫回磁盤。4343第八章 磁盤存儲器的管理1.數(shù)據(jù)交

18、付(Data Delivery)方式如果I/O請求所需要的數(shù)據(jù)能從磁盤高速緩存中獲取，此時就需要將磁盤高速緩存中的數(shù)據(jù)傳送給請求進程。所謂的數(shù)據(jù)交付就是指將磁盤高速緩存中的數(shù)據(jù)傳送給請求者進程。系統(tǒng)可以采取兩種方式將數(shù)據(jù)交付給請求進程：(1)數(shù)據(jù)交付(2)指針交付 4444第八章 磁盤存儲器的管理2.置換算法現(xiàn)在不少系統(tǒng)在設計其高速緩存的置換算法時，除了考慮到最近最久未使用這一原則外，還考慮了以下幾點：(1)訪問頻率。(2)可預見性。(3)數(shù)據(jù)的一致性。4545第八章 磁盤存儲器的管理3.周期性地寫回磁盤還有一種情況值得注意，那就是根據(jù)LRU算法，那些經(jīng)常要被訪問的盤塊數(shù)據(jù)可能會一直保留在高速

19、緩存中，長期不會被寫回磁盤。4646第八章 磁盤存儲器的管理8.3.2 提高磁盤I/O速度的其它方法能有效地提高磁盤I/O速度的方法還有許多，如提前讀、延遲寫等，現(xiàn)介紹如下：1.提前讀2.延遲寫3.優(yōu)化物理塊的分布4747第八章 磁盤存儲器的管理4.虛擬盤由于訪問內(nèi)存的速度遠高于訪問磁盤的速度，于是有人試圖利用內(nèi)存空間去仿真磁盤，形成所謂虛擬盤，又稱為RAM盤。該盤的設備驅(qū)動程序也可以接受所有標準的磁盤操作，但這些操作的執(zhí)行不是在磁盤上而是在內(nèi)存中。這對用戶都是透明的。4848第八章 磁盤存儲器的管理8.3.3 廉價磁盤冗余陣列(RAID)1.并行交叉存取這是把在大、中型機中，用于提高訪問內(nèi)存

20、速度的并行交叉存取技術(shù)應用到磁盤存儲系統(tǒng)中，以提高對磁盤的I/O速度。在該系統(tǒng)中，有多臺磁盤驅(qū)動器，系統(tǒng)將每一盤塊中的數(shù)據(jù)分為若干個子盤塊數(shù)據(jù)，再把每一個子盤塊的數(shù)據(jù)分別存儲到各個不同磁盤中的相同位置上。以后當要將一個盤塊的數(shù)據(jù)傳送到內(nèi)存時，采取并行傳輸方式，將各個盤塊中的子盤塊數(shù)據(jù)同時向內(nèi)存中傳輸，從而使傳輸時間大大減少。4949第八章 磁盤存儲器的管理圖8-12 磁盤并行交叉存取方式5050第八章 磁盤存儲器的管理2.RAID的分級RAID在剛被推出時，是分成6級的，后來又增加了RAID 6級和RAID 7級。(1)RAID 0級。(2)RAID 1級。(3)RAID 3級。(4)RAID

21、 5級。(5)RAID 6級和RAID 7級。51 51第八章 磁盤存儲器的管理3.RAID的優(yōu)點(1)可靠性高，除了RAID 0級外，其余各級都采用了容錯技術(shù)。當陣列中某一磁盤損壞時，并不會造成數(shù)據(jù)的丟失。此時可根據(jù)其它未損壞磁盤中的信息來恢復已損壞的盤中的信息。其可靠性比單臺磁盤機高出一個數(shù)量級。(2)磁盤I/O速度高，由于采取了并行交叉存取方式，可使磁盤I/O速度提高N-1倍。(3)性能/價格比高，RAID的體積與具有相同容量和速度的大型磁盤系統(tǒng)相比，只是后者的1/3，價格也只是后者的1/3，且可靠性高。換言之，它僅以犧牲1/N的容量為代價，換取了高可靠性。5252第八章 磁盤存儲器的管

22、理8.4 提高磁盤可靠性的技術(shù)8.4.1 第一級容錯技術(shù)SFT-第一級容錯技術(shù)(SFT-)是最基本的一種磁盤容錯技術(shù)，主要用于防止因磁盤表面缺陷所造成的數(shù)據(jù)丟失。它包含雙份目錄、雙份文件分配表及寫后讀校驗等措施。5353第八章 磁盤存儲器的管理1.雙份目錄和雙份文件分配表在磁盤上存放的文件目錄和文件分配表FAT，是文件管理所用的重要數(shù)據(jù)結(jié)構(gòu)。為了防止這些表格被破壞，可在不同的磁盤上或在磁盤的不同區(qū)域中分別建立(雙份)目錄表和FAT。其中一份為主目錄及主FAT，另一份為備份目錄及備份FAT。一旦由于磁盤表面缺陷而造成主文件目錄或主FAT的損壞時，系統(tǒng)便自動啟用備份文件目錄及備份FAT，從而可以保

23、證磁盤上的數(shù)據(jù)仍是可訪問的。5454第八章 磁盤存儲器的管理2.熱修復重定向和寫后讀校驗由于磁盤價格昂貴，在磁盤表面有少量缺陷的情況下，則可采取某種補救措施后繼續(xù)使用。一般主要采取以下兩個補救措施：(1)熱修復重定向。(2)寫后讀校驗方式。5555第八章 磁盤存儲器的管理8.4.2 第二級容錯技術(shù)SFT-1.磁盤鏡像(Disk Mirroring)為了避免磁盤驅(qū)動器發(fā)生故障而丟失數(shù)據(jù)，便增設了磁盤鏡像功能。為實現(xiàn)該功能，須在同一磁盤控制器下，再增設一個完全相同的磁盤驅(qū)動器，如圖8-13所示。5656第八章 磁盤存儲器的管理2.磁盤雙工(Disk Duplexing)如果控制這兩臺磁盤驅(qū)動器的磁

24、盤控制器發(fā)生故障，或主機到磁盤控制器之間的通道發(fā)生故障，磁盤鏡像功能便起不到數(shù)據(jù)保護的作用。因此，在第二級容錯技術(shù)中，又增加了磁盤雙工功能，即將兩臺磁盤驅(qū)動器分別接到兩個磁盤控制器上，同樣使這兩臺磁盤機鏡像成對，如圖8-14所示。5757第八章 磁盤存儲器的管理圖8-13 磁盤鏡像示意圖 5858第八章 磁盤存儲器的管理圖8-14 磁盤雙工示意圖 5959第八章 磁盤存儲器的管理8.4.3 基于集群技術(shù)的容錯功能1.雙機熱備份模式如圖8-15所示，在這種模式的系統(tǒng)中，備有兩臺服務器，兩者的處理能力通常是完全相同的，一臺作為主服務器，另一臺作為備份服務器。6060第八章 磁盤存儲器的管理圖8-1

25、5 雙機熱備份模式61 61第八章 磁盤存儲器的管理2.雙機互為備份模式在雙機互為備份模式中，平時，兩臺服務器均為在線服務器，它們各自完成自己的任務，例如，一臺作為數(shù)據(jù)庫服務器，另一臺作為電子郵件服務器。為了實現(xiàn)兩者互為備份的功能，在兩臺服務器之間，應通過某種專線將其連接起來。如果希望兩臺服務器之間能相距較遠，最好利用FDDI單模光纖來連接兩臺服務器。在此情況下，最好再通過路由器將兩臺服務器互連起來，作為備份通信線路。圖8-16示出了雙機互為備份系統(tǒng)的情況。6262第八章 磁盤存儲器的管理圖8-16 雙機互為備份系統(tǒng)的示意圖6363第八章 磁盤存儲器的管理3.公用磁盤模式為了減少信息復制的開銷

26、，可以將多臺計算機連接到一臺公共的磁盤系統(tǒng)上去。該公共磁盤被劃分為若干個卷。每臺計算機使用一個卷。如果某臺計算機發(fā)生故障，此時系統(tǒng)將重新進行配置，根據(jù)某種調(diào)度策略來選擇另一臺替代機器，后者對發(fā)生故障的機器的卷擁有所有權(quán)，從而可接替故障計算機所承擔的任務。這種模式的優(yōu)點是消除了信息的復制時間，因而減少了網(wǎng)絡和服務器的開銷。6464第八章 磁盤存儲器的管理8.4.4 后備系統(tǒng)1.磁帶機它是最早作為計算機系統(tǒng)的外存儲器。但由于它只適合存儲順序文件，故現(xiàn)在主要把它作為后備設備。磁盤機的主要優(yōu)點是容量大，一般可達數(shù)GB至數(shù)十GB，且價格便宜，故在許多大、中型系統(tǒng)中都配置了磁帶機。其缺點是只能順序存取且速

27、度也較慢，為數(shù)百KB到數(shù)MB，為了將一個大容量磁盤上的數(shù)據(jù)拷貝到磁帶上，需要花費很多時間。6565第八章 磁盤存儲器的管理2.硬盤(1)移動磁盤。(2)固定硬盤驅(qū)動器。6666第八章 磁盤存儲器的管理圖8-17 利用大容量硬盤兼做后備系統(tǒng)6767第八章 磁盤存儲器的管理3.光盤驅(qū)動器光盤驅(qū)動器是現(xiàn)在最流行的多媒體設備，可將它們分為如下兩類：(1)只讀光盤驅(qū)動器CD-ROM和DVD-ROM。(2)可讀寫光盤驅(qū)動器。6868第八章 磁盤存儲器的管理8.5 數(shù)據(jù)一致性控制在實際應用中，經(jīng)常會在多個文件中都含有同一個數(shù)據(jù)。所謂數(shù)據(jù)一致性問題是指，保存在多個文件中的同一數(shù)據(jù)，在任何情況下都必需能保證相同

28、。6969第八章 磁盤存儲器的管理8.5.1 事務1.事務的定義事務是用于訪問和修改各種數(shù)據(jù)項的一個程序單位。事務也可以被看做是一系列相關讀和寫操作。7070第八章 磁盤存儲器的管理2.事務記錄(Transaction Record)為了實現(xiàn)上述的原子修改，通常須借助于稱為事務記錄的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。這些數(shù)據(jù)結(jié)構(gòu)被放在一個非常可靠的存儲器(又稱穩(wěn)定存儲器)中，用來記錄在事務運行時數(shù)據(jù)項修改的全部信息，故又稱為運行記錄(Log)。71 71第八章 磁盤存儲器的管理3.恢復算法由于一組被事務Ti修改的數(shù)據(jù)以及它們被修改前和修改后的值都能在事務記錄表中找到，因此，利用事務記錄表系統(tǒng)能處理任何故障而不致

29、使故障造成非易失性存儲器中信息的丟失?；謴退惴衫靡韵聝蓚€過程：(1)undoTi。該過程把所有被事務Ti修改過的數(shù)據(jù)恢復為修改前的值。(2)redoTi。該過程能把所有被事務Ti修改過的數(shù)據(jù)設置為新值。7272第八章 磁盤存儲器的管理8.5.2 檢查點1.檢查點(Check Points)的作用如前所述，當系統(tǒng)發(fā)生故障時，必須去檢查整個Log表，以確定哪些事務需要利用redoTi過程去設置新值，而哪些事務又需要利用undoTi過程去恢復數(shù)據(jù)的舊值。由于在系統(tǒng)中可能存在著許多并發(fā)執(zhí)行的事務，因而在事務記錄表中就會有許多事務執(zhí)行操作的記錄。隨著時間的推移，記錄的數(shù)據(jù)也會愈來愈多。因此，一旦系統(tǒng)

30、發(fā)生故障，在事務記錄表中的記錄清理起來就非常費時。7373第八章 磁盤存儲器的管理2.新的恢復算法在引入檢查點后，可以大大減少恢復處理的開銷。因為在發(fā)生故障后，并不需要對事務記錄表中的所有事務記錄進行處理，而只需對最后一個檢查點之后的事務記錄進行處理。因此，恢復例程首先查找事務記錄表，確定在最近檢查點以前開始執(zhí)行的最后的事務Ti。在找到這樣的事務后，再返回去搜索事務記錄表，便可找到第一個檢查點記錄，恢復例程便從該檢查點開始返回搜索各個事務的記錄，并利用redo和undo過程對它們進行處理。7474第八章 磁盤存儲器的管理8.5.3 并發(fā)控制(Concurrent Control)1.利用互斥鎖

31、實現(xiàn)“順序性”實現(xiàn)順序性的一種最簡單的方法，是設置一種用于實現(xiàn)互斥的鎖，簡稱為互斥鎖(Exclusive Lock)。在利用互斥鎖實現(xiàn)順序性時，應為每一個共享對象設置一把互斥鎖。當某一事務Ti要去訪問某對象時，應先獲得該對象的互斥鎖。若成功，便用該鎖將該對象鎖住，于是事務T便可對該對象執(zhí)行讀或?qū)懖僮?；而其它事務由于未能獲得該鎖，因而不能訪問該對象。如果Ti需要對一批對象進行訪問，則為了保證事務操作的原子性，Ti應先獲得這一批對象的互斥鎖，以將這些對象全部鎖住。7575第八章 磁盤存儲器的管理2.利用互斥鎖和共享鎖實現(xiàn)順序性利用互斥鎖實現(xiàn)順序性的方法簡單易行。目前有不少系統(tǒng)都是采用這種方法來保證

32、事務操作的順序性，但這卻存在著效率不高的問題。因為一個共享文件雖然只允許一個事務去寫，但卻允許多個事務同時去讀；而在利用互斥鎖來鎖住文件后，則只允許一個事務去讀。為了提高運行效率而又引入了另一種形式的鎖共享鎖(Shared Lock)。共享鎖與互斥鎖的區(qū)別在于：互斥鎖僅允許一個事務對相應對象執(zhí)行讀或?qū)懖僮?，而共享鎖則允許多個事務對相應對象執(zhí)行讀操作，但不允許其中任何一個事務對對象執(zhí)行寫操作。7676第八章 磁盤存儲器的管理8.5.4 重復數(shù)據(jù)的數(shù)據(jù)一致性問題1.重復文件的一致性我們以UNIX類型的文件系統(tǒng)為例來說明如何保證重復文件的一致性問題。對于通常的UNIX文件目錄，其每個目錄項中含有一個

33、ASCII碼的文件名和一個索引結(jié)點號，后者指向一個索引結(jié)點。當有重復文件時，一個目錄項可由一個文件名和若干個索引結(jié)點號組成，每個索引結(jié)點號都是指向各自的索引結(jié)點。圖8-18示出了UNIX類型的目錄和具有重復文件的目錄。7777第八章 磁盤存儲器的管理圖8-18 UNIX類型的目錄7878第八章 磁盤存儲器的管理2.鏈接數(shù)一致性檢查在UNIX類型的文件目錄中，其每個目錄項內(nèi)都含有一個索引結(jié)點號，用于指向該文件的索引結(jié)點。對于一個共享文件，其索引結(jié)點號會在目錄中出現(xiàn)多次。7979第八章 磁盤存儲器的管理習 題 1.目前常用的外存有哪幾種組織方式?2.由連續(xù)組織方式所形成的順序文件的主要優(yōu)缺點是什么

34、?它主要應用于何種場合?3.在鏈接式文件中常用哪種鏈接方式?為什么?4.在文件分配表中為什么要引入“簇”的概念?以“簇”為基本的分配單位有什么好處?5.簡要說明為什么要從FAT12發(fā)展為FAT16?又進一步要發(fā)展為FAT32?8080第八章 磁盤存儲器的管理6.試解釋邏輯簇號和虛擬簇號這兩個名詞，NTFS是如何將它們映射到文件的物理地址上的?7.在MS-DOS中有兩個文件A和B，A占用11、12、16和14四個盤塊；B占用13、18和20三個盤塊。試畫出在文件A和B中各盤塊間的鏈接情況及FAT的情況。8.NTFS文件系統(tǒng)中的文件所采用的是什么樣的物理結(jié)構(gòu)?9.假定一個文件系統(tǒng)的組織方式與MS-

35、DOS相似，在FAT中可有64K個指針，磁盤的盤塊大小為512B，試問該文件系統(tǒng)能否指引一個512MB的磁盤?81 81第八章 磁盤存儲器的管理10.為了快速訪問，又易于更新，當數(shù)據(jù)為以下形式時，應選用何種文件組織方式?(1)不經(jīng)常更新，經(jīng)常隨機訪問；(2)經(jīng)常更新，經(jīng)常按一定順序訪問；(3)經(jīng)常更新，經(jīng)常隨機訪問。11.在UNIX 中，如果一個盤塊的大小為1KB，每個盤塊號占4 個字節(jié)，即每塊可放256個地址。請轉(zhuǎn)換下列文件的字節(jié)偏移量為物理地址：(1)9999；(2)18000；(3)420000。12.什么是索引文件?為什么要引入多級索引?13.試說明增量式索引組織方式。8282第八章 磁盤存儲器的管理14.有一計算機系統(tǒng)利用圖8-19所示的位示圖來管理空閑盤塊。盤塊的大小為1KB，現(xiàn)要為某文件分配兩個盤塊，試說明盤塊的具體分配過程。圖8-19 某計算機系統(tǒng)的位示圖8383第八章 磁盤存儲器的管理15.某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長為32位的位示圖管理盤空間，試問：(1)位示圖需多少個字?(2)第i字第j位對應的塊號是多少?(3)給出申請/歸還一塊的工作流程。16.對空閑磁盤空間的管理常采用哪幾種分配方式?在UNIX系統(tǒng)中是采用何種分配方式?17.可從哪幾方面來提高對文件的訪問速度?18.何謂磁盤高速緩存?在設計磁盤高速緩存時需要考慮哪些問題?