第8章磁盤存儲器管理外存組織方式方法空閑存儲空間的管理磁盤容錯技術文件系統性能的改善數據一致性控制2023/2/428.1外存的組織方式連續組織方式鏈接(串聯)組織方式索引組織方式常用的三種外存組織方式方式：2023/2/438.1.1連續組織方式連續組織方式：為每個文件組織方式相鄰的物理塊（數據塊/盤塊/扇區）。組織方式給文件的首物理塊的地址被登記在它的目錄項內。由連續組織方式方式形成的文件物理結構被稱為順序文件結構，相應的物理文件則稱為順序文件(SequentialFile)。2023/2/44

磁盤空間的連續組織方式012345678910111213141516171819202122232425262728293031文件名始址塊數count02tr143mail196list284f62文件目錄countftrmaillist2023/2/45連續組織方式優缺點優點(Strongpoint)

：順序訪問容易順序存取速度快缺點(Disadvantage)：要求連續的存儲空間。易產生外存碎片，空間利用率降低須事先知道文件長度。不利于文件動態增長2023/2/468.1.2鏈接組織方式

(LinkedAllocation)一種離散組織方式方式。通過每個盤塊上的鏈接指針，將同一個文件的多個離散的盤塊鏈接成一個鏈表。可分為隱式鏈接和顯示鏈接兩種方式。1.隱式鏈接：將一文件離散地存放在外存上，并將下一個物理塊的地址登記在組織方式給它的前一個物理塊中。2023/2/47某個鏈接文件示意2023/2/48磁盤空間的鏈接式組織方式文件名始址末址jeep925文件目錄01234567891011121314151617181920212223242526272829303111016-1252023/2/49隱式鏈接優缺點優點：消除了外部碎片，提高利用率允許作業動態增長。缺點：可靠性差：一個指針出現問題，導致整個鏈斷開只適合于順序訪問，不適合隨機訪問。2023/2/4102.顯示鏈接將文件離散地存放，并將鏈接各個物理塊的指針顯式地登記在內存的一張文件組織方式表FAT(FileAllocationTable)中。2023/2/411顯示鏈接特點優點：顯著提高檢索速度缺點：不支持大文件隨機存取FAT需要占用較大的內存空間2023/2/412思考如果硬盤是16G空間，盤塊大小為4K，一個FAT表項占多少位？FAT表需占用多少空間？如果文件A占用硬盤的第11，12，16，14四個盤塊，試畫出文件A中各盤塊間的連接及FAT的情況。2023/2/4138.1.3索引組織方式也屬于離散組織方式方式，它在存放文件同時，為每個文件建立一個索引表（盤塊），以登記物理塊號，并在文件目錄項的地址字段中填上指向該索引表的指針。2023/2/414索引組織方式方式012345678910111213141516171819202122232425262728293031文件名索引表地址文件目錄Jeep1991611025-1-1-1192023/2/4158.1.3索引組織方式優缺點

(StrongpointandDisadvantage)優點：支持高效的隨機存取消除了外部碎片允許文件動態增長。缺點：索引表本身也要花費較多外存空間，造成外存空間浪費。2023/2/41601210510625435635798510510625474035635711259853607401125主索引360第二級索引磁盤空間2023/2/417總結三種外存組織方式連續組織方式鏈接組織方式索引組織方式思考題：各種組織方式方式的優缺點是什么？2023/2/4188.2文件存儲空間的管理為對文件存儲空間進行管理，常用以下幾種方法進行：空閑表法空閑鏈表法位示圖法成組鏈接法2023/2/4198.2.1空閑表法和空閑鏈表法空閑表法：屬于連續組織方式方式，為每個文件組織方式一塊連續空間。系統為外存上的所有區建立一張空閑表，每個空閑區對應一個空閑表項，每個表項包括表項序號、空閑區的第一個盤塊號和空閑區的盤塊數。優點：空閑區組織方式與回收容易。缺點：空閑表也會浪費很大存儲空間。2023/2/420序號第一空閑盤塊號空閑盤塊數1242933155………圖6-21空閑盤快表2023/2/4212空閑鏈表法：將文件存儲空間中的所有空閑區拉成一條空閑鏈表。根據構成鏈的基本元素是空閑盤塊或空閑盤區，再分為空閑盤塊鏈或空閑盤區鏈。2023/2/4228.2.2位示圖法位示圖法：利用二進制的一位來表示文件存儲空間中的一個盤塊的使用情況。其值為0表示空閑，為1表示組織方式，這樣由所有盤塊所對應的位構成一個集合，稱為位示圖。2023/2/4231.位示圖

1234567891011121314151612345…1100011100100110000111111000011111100011111100002023/2/4242.盤塊的組織方式

(1)順序掃描位示圖，從中找出一個或一組其值為“0”的二進制位(“0”表示空閑時)。(2)將所找到的一個或一組二進制位，轉換成與之相應的盤塊號。假定找到的其值為“0”的二進制位，位于位示圖的第i行、第j列，則其相應的盤塊號應按下式計算：

b=n(i-1)+j式中，

n代表每行的位數。(3)修改位示圖，

令map［i,j］=1。2023/2/4253.盤塊的回收

(1)將回收盤塊的盤塊號轉換成位示圖中的行號和列號。

轉換公式為：i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示圖。

令map［i,j］=0。

2023/2/4278.2.3成組鏈接法UNIX系統中空閑盤塊管理方法將一個文件卷的所有空閑盤塊分成固定大小的組（如100個盤塊），將每一組的盤塊號和盤塊數記入前一組的最后一個盤塊中，第一組的盤塊數和盤塊號記入空閑盤塊棧中。2023/2/4282023/2/4308.3提高磁盤IO速度高速緩存。提前讀，延遲寫。優化物理塊分布虛擬盤。2023/2/431思考題2假設磁盤轉速為20ms/圈，磁盤格式化時每個磁道被劃分成10個扇區，今有10個邏輯記錄（每個記錄大小剛好與扇區大小相等）存放在同一條磁道上，處理程序每次從磁道讀出一個記錄要花費4ms進行處理，先要求順序處理這10個記錄，若磁頭現在處于首個邏輯記錄的起始位置。按逆時針安排10個邏輯記錄（磁盤順時針方向旋轉）處理程序處理完這10條記錄花費的時間是多少？按優化分布重新安排這10條記錄，計算所需要的時間2023/2/432思考題3假定磁盤的移動臂現在處于第8柱面，有如下6個請求者等待訪問磁盤，請你列出最省時間的響應次序：

序號

柱面號

磁頭號

扇區號

1

9

6

3

2

7

5

6

3

15

20

6

4

9

4

4

5

20

9

5

6

7

15

2

8.4磁盤容錯技術(1)通過存取控制機制來防止由人為因素所造成的文件不安全性。

(2)通過磁盤容錯技術，來防止由磁盤部分的故障所造成的文件不安全性。

(3)通過“后備系統”來防止由自然因素所造成的不安全性。1.第一級容錯技術SFT-Ⅰ1)雙份目錄和雙份文件組織方式表在磁盤上存放的文件目錄和文件組織方式表FAT，是文件管理所用的重要數據結構。如果這些表格被破壞，將導致磁盤上的部分或全部文件成為不可訪問的，因而也就等效于文件的丟失。為了防止這類情況發生，可在不同的磁盤上或在磁盤的不同區域中，分別建立(雙份)目錄表和FAT。其中，一份被稱為主目錄及主FAT；把另一份稱為備份目錄及備份FAT。2)熱修復重定向和寫后讀校驗熱修復重定向(Hot-Redirection)。(2)寫后讀校驗(ReadafterwriteVerification)方式。2.第二級容錯技術SFT-Ⅱ(1)磁盤鏡像(DiskMirroring)。圖6-26磁盤鏡像示意(2)磁盤雙工(DiskDuplexing)。圖6-27磁盤雙工示意2023/2/4388.5數據一致性一個數據同時出現在多個不同的對象中時，即可能會出現數據一致性問題。事務檢查點并發控制硬件穩定存儲器的支持2023/2/4398.5.1事務事務：它是一種原子性操作，是用于訪問和修改各種數據項的一個程序單位，可被看作一系列的讀和寫操作。事務的原子性操作須借助于存放在穩定存儲器中的事務記錄表（log)來實現，表中的每條記錄描述了事務運行中的重要操作，一旦出現錯誤，便立即回滾。2023/2/4402.事務記錄(TransactionRecord)

事務名：

用于標識該事務的惟一名字；數據項名：

它是被修改數據項的惟一名字；舊值：

修改前數據項的值；新值：

修改后數據項將具有的值。2023/2/4413.恢復算法

恢復算法可利用以下兩個過程：(1)undo〈Ti〉。該過程把所有被事務Ti修改過的數據，恢復為修改前的值。(2)redo〈Ti〉。該過程能把所有被事務Ti修改過的數據，設置為新值。

如果系統發生故障，

系統應對以前所發生的事務進行清理。

2023/2/4428.5.2檢查點檢查點：主要目的是使對事務記錄表中事務記錄的清理工作經?；?023/2/443首先是將駐留在易失性存儲器(內存)中的當前事務記錄表中的所有記錄，輸出到穩定存儲器中；其次是將駐留在易失性存儲器中的所有已修改數據，輸出到穩定存儲器中；然后是將事務記錄表中的〈檢查點〉記錄，輸出到穩定存儲器中；

最后是每當出現一個〈檢查點〉記錄時，系統便執行上小節所介紹的恢復操作，利用redo和undo過程實現恢復功能。2023/2/4448.5.3并發控制由信號量實現一個事務執行完再執行另一個事務，實現了事務的順序性。2023/2/4458.5.4重復數據的數據一致性問題1.重復文件的一致性

2023/2/4462.盤塊號一致性的檢查2023/2/4473.鏈接數一致性檢查配置一張計數器表，為每個文件建立一個表項，其中含有該索引結點號的計數值。

在進行檢查時，從根目錄開始查找，每當在目錄中遇到該索引結點號時，便在該計數器表中相應文件的表項上加1。當把所有目錄都檢查完后，便可將該計數器表中每個表項中的索引結點號計數值與該文件索引結點中的鏈接計數count值加以比較，如果兩者一致，表示是正確的；否則，便是發生了鏈接數據不一致的錯誤。

2023/2/448習題1請分別解釋在連續組織方式、鏈接組織方式、索引組織方式方式中如何將文件的字節偏移量3500轉換為物理塊號和塊內位移量(假設盤塊大小為1KB，盤塊號需占4個字節)2023/2/449習題2存放在某個磁盤上的文件系統采用混合索引組織方式方式，其FCB中共有13個地址項，第0-9個地址項為直接地址，第10個地址項為一次間址，第11個地址項為二次間址，第12個地址項為三次間址。如果每個盤塊的大小為512字節，若盤塊號需要3個字節描述，每個盤塊最多存放170個盤塊地址，則（1）該文件系統允許文件的最大長度？（2）將文件的字節偏移量5000、15000、150000轉換為物理塊號和塊內偏移？（3）假設文件的FCB已經在內存，但其他信息均在外存，為了訪問該文件中某個位置的內容，最少需要幾次訪問磁盤，最多幾次訪問磁盤？2023/2/450習題3某系統采用成組鏈接法管理磁盤的空閑空間，目前磁盤的狀態如圖所示。（1）該磁盤中目前還有多少個空閑盤塊（2）簡述磁盤的組織方式過程（3）在為某個文件組織方式3個盤塊后，系統要刪除另一個文件，并回收他的5個盤塊，他們的盤塊號依次為700、711、703、788、701清畫出回收后的盤塊鏈接圖五、例

一個文件系統中有一個20MB大文件和一個20KB小文件,當分別采用連續、鏈接、單級索引、二級索引和UNIXSytemV組織方式方案時(每塊大小為4096B,每塊地址用4B表示)，問:1.各文件系統管理的最大的文件是多少?2.每種方案對大、小二文件各需要多少專用塊來記錄文件的物理地址(說明各塊的用途)?3．如需要讀大文件前面第5.5KB和后面（16M＋5.5KB）信息，則每個方案各需要多少次盤I/O操作?這個范例是幫助讀者深入比較文件物理組織的各種方案：順序文件的連續組織方式、鏈接文件的鏈接組織方式、二級索引組織方式、鏈接索引組織方式和UNIX的直接間接混合組織方式，明確各種組織方式方案的優缺點和UNIX組織方式方案的設計特點。例-解答1.各種組織方式方案的文件系統可管理的最大文件連續組織方式：不受限制，可大到整個磁盤文件區。鏈接組織方式：同上。單級索引：同上。二級索引：由于盤塊大小為4KB，每個地址用4B表示，一個盤塊可存1K個索引表目，二級索引可管理的最大文件容量為4KB×1K×1K＝4GB，如要管理更大的文件需采用三索引，它可管理4TB大小文件。

UNIX混合組織方式：可管理的最大文件為40KB＋4MB+4GB＋4TB。2.每種組織方式方案對20MB大文件和20KB小文件各需要多少專用塊來記錄文件的物理地址?連續組織方式：對大小二個文件都只需在文件控制塊FCB中設二項，一是首塊物理塊塊號，另一是文件總塊數，不需專用塊來記錄文件的物理地址。例-解答鏈接組織方式：對大小二個文件都只需在文件控制塊FCB中設二項，一是首塊物理塊塊號，另一是文件總塊數；同時在每塊存文件的物理塊中設置存貯下一塊塊號的指針。單級索引：對20KB小文件只有5個物理塊大小，所以只需一塊專用物理塊來作索引塊，用來保存文件的各塊物理塊塊號。對于20MB大文件有5K個物理塊大小，由于鏈接索引的每個索引塊只能保存（1K－1）個物理塊塊號（還有一個表目作索引塊鏈接指針），所以它需要6塊專用物理塊來作鏈接索引塊，用于保存文件各塊的物理地址。二級索引：對大小文件都固定要用二級索引，對20KB小文件，用一塊作第一級索引，用另一塊作二級索引，共用二塊專用物理塊作索引塊，對于20MB大文件，用一塊作第一級索引，用5塊作第二級索引，共用六塊專用物理塊作索引塊。范例-解答

UNIX的混合組織方式：對20KB小文件只需在文件控制塊FCB的i_addr[13]中使用前5個表目存放文件的物理塊號，不需專用物理塊。對20MB大文件，FCB的i_addr[13]中使用前10個表目存放大文件前10塊物理塊塊號，用一級索引塊一塊保存大文件接著的1K塊塊號，還要用二級索引存大文件以后的塊號，二級索引使用第一級索引1塊，第二級索引4塊?？偣惨残枰?塊專用物理塊來存放文件物理地址。3.為讀大文件前面第5.5KB和后面（16M＋5.5KB）信息需要多少次盤I/O操作?連續組織方式：為讀大文件前面和后面信息都需先計算信息在文件中相對塊數，前面信息相對邏輯塊號為5.5K／4K=1，后面信息相對邏輯塊號為（16M＋5.5K）/4K=4097。再計算物理塊號＝文件首塊號＋相對邏輯塊號，最后化一次盤I/O操作讀出該塊信息。例-解答鏈接組織方式：為讀大文件前面5.5.KB的信息，只需先讀一次文件頭塊得到信息所在塊的塊號，再讀一次第1號邏輯塊得到所需信息。而讀大文件后面16MB＋5.5KB的信息，要先把該信息所在塊前面塊順序讀出，共化費4097次盤I／O操作，才能得到信息所在