計算機操作系統(tǒng) 第四版 湯小丹 梁紅兵 哲鳳屏第7章(2016-2017-1).ppt

1、第八章 磁盤存儲器的管理,8.1 外存的組織文件 8.2 文件存儲空間的管理 8.3 提高磁盤I/O速度的途徑 8.4 提高磁盤可靠性的技術(shù) 8.5 數(shù)據(jù)一致性控制,8.1 外存的組織方式,8.1.1 連續(xù)組織方式,文件的物理結(jié)構(gòu)直接與外存的組織方式有關(guān)；不同的外存組織方式，將形成不同的文件物理結(jié)構(gòu)。 連續(xù)組織方式形成順序式的文件結(jié)構(gòu)。,外存的組織方式：連續(xù)組織方式、鏈接組織方式、索引組織方式,1. 隱式鏈接,圖 8-2 磁盤空間的鏈接式分配,8.1.2 鏈接組織方式,幾個盤塊組成一個簇，以簇為單位進行分配。,2. 顯式鏈接,8.1.2 鏈接組織方式,文件分配表FAT(File Allocat

2、ion Table) 存放分配給文件的所有盤塊號。,8.1.5 索引組織方式,1. 單級索引組織方式,2. 多級索引組織方式,8.1.5 索引組織方式,2. 多級索引分配,兩級索引分配,圖 8-8 混合索引方式,3. 增量式索引組織方式,8.1.5 索引組織方式,(1) 直接地址。 為了提高對文件的檢索速度，在索引結(jié)點中可設(shè)置10個直接地址項，即用iaddr(0)iaddr(9)來存放直接地址。換言之，在這里的每項中所存放的是該文件數(shù)據(jù)的盤塊的盤塊號。假如每個盤塊的大小為 4 KB，當文件不大于40 KB時，便可直接從索引結(jié)點中讀出該文件的全部盤塊號。,3. 增量式索引組織方式,8.1.5 索

3、引組織方式,(2) 一次間接地址。 對于大、 中型文件， 只采用直接地址是不現(xiàn)實的。 為此，可再利用索引結(jié)點中的地址項iaddr(10)來提供一次間接地址。這種方式的實質(zhì)就是一級索引分配方式。圖中的一次間址塊也就是索引塊，系統(tǒng)將分配給文件的多個盤塊號記入其中。在一次間址塊中可存放1K個盤塊號， 因而允許文件長達4 MB。,3. 增量式索引組織方式,8.1.5 索引組織方式,(3) 多次間接地址。 當文件長度大于4 MB+40 KB時(一次間址與10個直接地址項)， 系統(tǒng)還須采用二次間址分配方式。這時，用地址項iaddr(11)提供二次間接地址。該方式的實質(zhì)是兩級索引分配方式。系統(tǒng)此時是在二次間

4、址塊中記入所有一次間址塊的盤號。在采用二次間址方式時，文件最大長度可達4 GB。 同理，地址項iaddr(12)作為三次間接地址， 其所允許的文件最大長度可達4 TB。,3. 增量式索引組織方式,8.1.5 索引組織方式,思考題1：請分別解釋在連續(xù)分配方式、隱式鏈接分配方式、顯式鏈接分配方式和索引分配方式中如何將文件的字節(jié)偏移量3500轉(zhuǎn)換為物理塊號和塊內(nèi)位移量（設(shè)盤塊大小為1KB，盤塊號需占4個字節(jié)）。,思考題2：存放在某個磁盤上的文件系統(tǒng)，采用混合索引分配方式，其FCB中共有13個地址項，第09個地址項為直接地址，第10個地址項為一次間接地址，第11個地址項為二次間接地址，第12個地址項為

5、三次間接地址。如果每個盤塊的大小為512字節(jié)，若盤塊號需要用3個字節(jié)來描述，而每個盤塊最多存放170個盤塊地址： （1）該文件系統(tǒng)允許文件的最大長度是多少？ （2）將字節(jié)的字節(jié)偏移量5000、15000轉(zhuǎn)換為物理塊號和塊內(nèi)偏移量。 （3）假設(shè)某個文件的FCB已在內(nèi)存，但其他信息均在外存，為了訪問該文件中某個位置的內(nèi)容，最少需要幾次訪問磁盤，最多需要幾次訪問磁盤？,8.2 文件存儲空間的管理,8.2.1 空閑表法和空閑鏈表法,1. 空閑表法,2. 空閑鏈表法,空閑鏈表法：將所有空閑盤區(qū)拉成一條空閑鏈。 根據(jù)構(gòu)成鏈鎖的基本元素，分空閑盤塊鏈、空閑盤區(qū)鏈,用于連續(xù)分配方式 分配算法？,8.2.2 位

6、示圖法,1. 位示圖,2. 盤塊的分配,順序掃描位示圖, 找出一個或一組值為0的二進制。,將所找到的一個或一組二進制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號,修改位示圖,mapm ,n,3. 盤塊的回收,(1) 將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。 轉(zhuǎn)換公式為： i=(b-1)DIV n + 1 j=(b-1)MOD n + 1 (2) 修改位示圖。令 mapi,j=0。,8.2.2 位示圖法,8.2.3 成組鏈接法,2. 空閑盤塊的分配與回收 當系統(tǒng)要為用戶分配文件所需的盤塊時，盤塊分配過程首先檢查空閑盤塊號棧是否上鎖，如未上鎖，便從棧頂取出一空閑盤塊號，將與之對應(yīng)的盤塊分配給用戶，然后將棧頂指

7、針下移一格。若該盤塊號已是棧底，即S.free(0)，這是當前棧中最后一個可分配的盤塊號。由于在該盤塊號所對應(yīng)的盤塊中記有下一組可用的盤塊號，因此，須調(diào)用磁盤讀過程，將棧底盤塊號所對應(yīng)盤塊的內(nèi)容讀入棧中，作為新的盤塊號棧的內(nèi)容，并把原棧底對應(yīng)的盤塊分配出去(其中的有用數(shù)據(jù)已讀入棧中)。然后，再分配一相應(yīng)的緩沖區(qū)(作為該盤塊的緩沖區(qū))。最后，把棧中的空閑盤塊數(shù)減1并返回。,8.2.3 成組鏈接法,8.3 提高磁盤I/O速度的途徑,主要從下列三方面提高對文件的訪問速度：,改進文件的目錄結(jié)構(gòu)以及檢索目錄的方法來減少對目錄的查找時間； 選取好的文件存儲結(jié)構(gòu)，以提高對文件的訪問速度； 提高磁盤的I/O速

8、度，能將文件中的數(shù)據(jù)快速地從磁盤傳送到內(nèi)存中，或者相反。,8.3.1 磁盤高速緩存(Disk Cache),指利用內(nèi)存中的存儲空間，來暫存從磁盤中讀出的一系列盤塊中的信息。因此，高速緩存是一組在邏輯上屬于磁盤，而物理上是駐留在內(nèi)存中的盤塊。 高速緩存在內(nèi)存中有兩種形式：第一種是在內(nèi)存中開辟一個單獨的存儲空間來作為磁盤高速緩存，其大小是固定的；第二種是把所有未利用的內(nèi)存空間變?yōu)橐粋€緩沖池，供請求分頁系統(tǒng)和磁盤I/O時(作為磁盤高速緩存)共享。,1. 數(shù)據(jù)交付方式,數(shù)據(jù)交付就是將磁盤高速緩存中的數(shù)據(jù)傳送給請求者進程。系統(tǒng)可以采取兩種方式，將數(shù)據(jù)交付給請求進程： (1) 數(shù)據(jù)交付。這是直接將高速緩存

9、中的數(shù)據(jù)，傳送到請求者進程的內(nèi)存工作區(qū)中。 (2) 指針交付。只將指向高速緩存中某區(qū)域的指針，交付給請求者進程。,8.3.1 磁盤高速緩存(Disk Cache),2. 置換算法,當高速緩存中已裝滿盤塊數(shù)據(jù)時，需要運用置換算法將某些盤塊過的數(shù)據(jù)先換出問題。 目前，不少系統(tǒng)在設(shè)計其高速緩存的置換算法時，除了考慮到最近最久未使用這一原則外，還考慮了以下幾點： (1) 訪問頻率。 (2) 可預(yù)見性。 (3) 數(shù)據(jù)的一致性。,8.3.1 磁盤高速緩存(Disk Cache),3. 周期性地寫回磁盤,在UNIX系統(tǒng)中專門增設(shè)了一個修改(update)程序， 使之在后臺運行，該程序周期性地調(diào)用一個系統(tǒng)調(diào)用

10、SYNC。該調(diào)用的主要功能是強制性地將所有在高速緩存中已修改的盤塊數(shù)據(jù)寫回磁盤。一般是把兩次調(diào)用SYNC的時間間隔定為30s。這樣，因系統(tǒng)故障所造成的工作損失不會超過30s的勞動量。,8.3.1 磁盤高速緩存(Disk Cache),8.3.2 提高磁盤I/O速度的其它方法,1. 提前讀(Read-Ahead) 2. 延遲寫 3. 優(yōu)化物理塊的分布 4. 虛擬盤,8.3.3 廉價磁盤冗余陣列 (RAID),1. 并行交叉存取,RAID(Redundant Array of Inexpensive Disk) 系統(tǒng)利用一臺磁盤陣列控制器統(tǒng)一管理和控制一組磁盤驅(qū)動器，組成一個大型磁盤系統(tǒng)。,8.4

11、 提高磁盤可靠性的技術(shù),(1) 通過存取控制機制來防止由人為因素所造成的文件不安全性。 (2) 通過磁盤容錯技術(shù)，來防止由磁盤部分的故障所造成的文件不安全性。 (3) 通過“后備系統(tǒng)”來防止由自然因素所造成的不安全性。,為確保文件系統(tǒng)的安全性應(yīng)采取三方面措施：,8.4.1 第一級容錯技術(shù)SFT-( System Fault-Tolerance),1. 雙份目錄和雙份文件分配表 在不同的磁盤上或在磁盤的不同區(qū)域中，分別建立(雙份)目錄表和FAT。,2. 熱修復(fù)重定向和寫后讀校驗,熱修復(fù)重定向。系統(tǒng)將磁盤容量的很小一部分作為熱修復(fù)重定向區(qū)，用于存放當發(fā)現(xiàn)磁盤有缺陷時的待寫數(shù)據(jù)，并對寫入該區(qū)的所有數(shù)

12、據(jù)進行登記。 (2) 寫后讀校驗方式。每次向磁盤中寫入一個數(shù)據(jù)塊后，又立即寫入另一緩沖區(qū)，并將這兩個緩沖區(qū)的內(nèi)容進行比較，以保證它們的一致。,8.4.2 第二級容錯技術(shù)SFT-,(1) 磁盤鏡像(Disk Mirroring),主要用于防止由磁盤驅(qū)動器和磁盤控制器故障所導(dǎo)致的系統(tǒng)不能正常工作。,(2) 磁盤雙工(Disk Duplexing)。,8.4.2 第二級容錯技術(shù)SFT-,8.5 數(shù)據(jù)一致性控制,8.5.1 事務(wù),1. 事務(wù)的定義 事務(wù)是用于訪問和修改各種數(shù)據(jù)項的一個程序單位，是一系列相關(guān)讀和寫操作。只有對分布在不同位置的同一數(shù)據(jù)所進行的讀和寫(含修改)操作全部完成時，才能再以托付操作

13、(Commit Operation)來終止事務(wù)。只要有一個讀、寫或修改操作失敗，便須執(zhí)行夭折操作(Abort Operation)，也稱為回滾操作或取消操作。一個事務(wù)在對一批數(shù)據(jù)執(zhí)行修改操作時，應(yīng)該是要么全部完成，并用修改后的數(shù)據(jù)去代替原來的數(shù)據(jù)，要么一個也不修改。這體現(xiàn)了事務(wù)具有原子性。,2. 事務(wù)記錄(Transaction Record),事務(wù)名：用于標識該事務(wù)的惟一名字； 數(shù)據(jù)項名：它是被修改數(shù)據(jù)項的惟一名字； 舊值 ; 新值,8.5.1 事務(wù),3. 恢復(fù)算法,(1) undo。把所有被事務(wù)Ti修改過的數(shù)據(jù)恢復(fù)為修改前的值 (2) redo。把所有被事務(wù)Ti修改過的數(shù)據(jù)設(shè)置為新值.,原

14、子操作借助于稱為事務(wù)記錄的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。用來記錄在事務(wù)運行時數(shù)據(jù)項修改的信息，稱為運行記錄(Log).,8.5.2 檢查點,1. 檢查點(Check Points)的作用,使對事務(wù)記錄表中事務(wù)記錄的清理工作經(jīng)?；?，即每隔一定時間便做一次下述工作：首先是將駐留在易失性存儲器(內(nèi)存)中的當前事務(wù)記錄表中的所有記錄，輸出到穩(wěn)定存儲器中；其次是將駐留在易失性存儲器中的所有已修改數(shù)據(jù)，輸出到穩(wěn)定存儲器中；然后是將事務(wù)記錄表中的記錄，輸出到穩(wěn)定存儲器中；最后是每當出現(xiàn)一個記錄時，系統(tǒng)便執(zhí)行上小節(jié)所介紹的恢復(fù)操作，利用redo和undo過程實現(xiàn)恢復(fù)功能。,2. 新的恢復(fù)算法,恢復(fù)例程首先查找事務(wù)記錄表，確

15、定在最近檢查點以前開始執(zhí)行的最后的事務(wù)Ti。在找到這樣的事務(wù)后，再返回去搜索事務(wù)記錄表，便可找到第一個檢查點記錄，恢復(fù)例程便從該檢查點開始，返回搜索各個事務(wù)的記錄，并利用redo和undo過程對它們進行處理。 如果把所有在事務(wù)Ti以后開始執(zhí)行的事務(wù)表示為事務(wù)集T， 則新的恢復(fù)操作要求是：對所有在T中的事務(wù)TK, 如果在事務(wù)記錄表中出現(xiàn)了記錄，則執(zhí)行redo操作； 反之，如果在事務(wù)記錄表中并未出現(xiàn)記錄，則執(zhí)行undo操作。,8.5.2 檢查點,8.5.3 并發(fā)控制,1. 利用互斥鎖實現(xiàn)“順序性” 2. 利用互斥鎖和共享鎖實現(xiàn)順序性,由于事務(wù)具有原子性，各個事務(wù)的執(zhí)行必然是按某種次序一次進行的，只有在一個事務(wù)執(zhí)行完后，才允許另一事務(wù)執(zhí)行。這種特性稱為順序性，實現(xiàn)事務(wù)順序性的技術(shù)稱為并發(fā)控制。,8.5.4 重復(fù)數(shù)據(jù)的數(shù)據(jù)一致性問題,1. 重復(fù)文件的一致性,為了保證數(shù)據(jù)的安全性，一般把關(guān)鍵文件或