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

第8章磁盤存儲(chǔ)器管理外存組織方式方法空閑存儲(chǔ)空間的管理磁盤容錯(cuò)技術(shù)文件系統(tǒng)性能的改善數(shù)據(jù)一致性控制2023/2/428.1外存的組織方式連續(xù)組織方式鏈接(串聯(lián))組織方式索引組織方式常用的三種外存組織方式方式：2023/2/438.1.1連續(xù)組織方式連續(xù)組織方式：為每個(gè)文件組織方式相鄰的物理塊（數(shù)據(jù)塊/盤塊/扇區(qū)）。組織方式給文件的首物理塊的地址被登記在它的目錄項(xiàng)內(nèi)。由連續(xù)組織方式方式形成的文件物理結(jié)構(gòu)被稱為順序文件結(jié)構(gòu)，相應(yīng)的物理文件則稱為順序文件(SequentialFile)。2023/2/44

磁盤空間的連續(xù)組織方式012345678910111213141516171819202122232425262728293031文件名始址塊數(shù)count02tr143mail196list284f62文件目錄countftrmaillist2023/2/45連續(xù)組織方式優(yōu)缺點(diǎn)優(yōu)點(diǎn)(Strongpoint)

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

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

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

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

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

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

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

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

(1)將回收盤塊的盤塊號(hào)轉(zhuǎn)換成位示圖中的行號(hào)和列號(hào)。

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

令map［i,j］=0。

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

序號(hào)

柱面號(hào)

磁頭號(hào)

扇區(qū)號(hào)

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磁盤容錯(cuò)技術(shù)(1)通過存取控制機(jī)制來防止由人為因素所造成的文件不安全性。

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

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

事務(wù)名：

用于標(biāo)識(shí)該事務(wù)的惟一名字；數(shù)據(jù)項(xiàng)名：

它是被修改數(shù)據(jù)項(xiàng)的惟一名字；舊值：

修改前數(shù)據(jù)項(xiàng)的值；新值：

修改后數(shù)據(jù)項(xiàng)將具有的值。2023/2/4413.恢復(fù)算法

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

如果系統(tǒng)發(fā)生故障，

系統(tǒng)應(yīng)對(duì)以前所發(fā)生的事務(wù)進(jìn)行清理。

2023/2/4428.5.2檢查點(diǎn)檢查點(diǎn)：主要目的是使對(duì)事務(wù)記錄表中事務(wù)記錄的清理工作經(jīng)?；?。2023/2/443首先是將駐留在易失性存儲(chǔ)器(內(nèi)存)中的當(dāng)前事務(wù)記錄表中的所有記錄，輸出到穩(wěn)定存儲(chǔ)器中；其次是將駐留在易失性存儲(chǔ)器中的所有已修改數(shù)據(jù)，輸出到穩(wěn)定存儲(chǔ)器中；然后是將事務(wù)記錄表中的〈檢查點(diǎn)〉記錄，輸出到穩(wěn)定存儲(chǔ)器中；

最后是每當(dāng)出現(xiàn)一個(gè)〈檢查點(diǎn)〉記錄時(shí)，系統(tǒng)便執(zhí)行上小節(jié)所介紹的恢復(fù)操作，利用redo和undo過程實(shí)現(xiàn)恢復(fù)功能。2023/2/4448.5.3并發(fā)控制由信號(hào)量實(shí)現(xiàn)一個(gè)事務(wù)執(zhí)行完再執(zhí)行另一個(gè)事務(wù)，實(shí)現(xiàn)了事務(wù)的順序性。2023/2/4458.5.4重復(fù)數(shù)據(jù)的數(shù)據(jù)一致性問題1.重復(fù)文件的一致性

2023/2/4462.盤塊號(hào)一致性的檢查2023/2/4473.鏈接數(shù)一致性檢查配置一張計(jì)數(shù)器表，為每個(gè)文件建立一個(gè)表項(xiàng)，其中含有該索引結(jié)點(diǎn)號(hào)的計(jì)數(shù)值。

在進(jìn)行檢查時(shí)，從根目錄開始查找，每當(dāng)在目錄中遇到該索引結(jié)點(diǎn)號(hào)時(shí)，便在該計(jì)數(shù)器表中相應(yīng)文件的表項(xiàng)上加1。當(dāng)把所有目錄都檢查完后，便可將該計(jì)數(shù)器表中每個(gè)表項(xiàng)中的索引結(jié)點(diǎn)號(hào)計(jì)數(shù)值與該文件索引結(jié)點(diǎn)中的鏈接計(jì)數(shù)count值加以比較，如果兩者一致，表示是正確的；否則，便是發(fā)生了鏈接數(shù)據(jù)不一致的錯(cuò)誤。

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

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

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

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