第8章 磁盤存儲管理

1、12022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.1 外存的組織(zzh)方式8.2 文件存儲空間的管理8.3 提高磁盤I/O速度的途徑8.4 提高磁盤可靠性的技術(shù)8.5 數(shù)據(jù)一致性控制 主要任務(wù)和要求是：有效地利用存儲空間提高磁盤的I/O速度提高磁盤系統(tǒng)的可靠性第8章 磁盤存儲器的管理共四十五頁22022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院文件的物理結(jié)構(gòu)和外存分配方法有關(guān)連續(xù)分配方式 順序(shnx)式結(jié)構(gòu)鏈接分配方式 鏈接式結(jié)構(gòu)索引分配方式 索引式結(jié)構(gòu) 8.1.1 連續(xù)分配8.1.2 鏈接分配8.1.3 索引分配 8.1 外存組織方式共四十五頁32022/7/19阜

2、陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.1.1 連續(xù)(linx)分配優(yōu)點(diǎn)：順序訪問容易，支持隨機(jī)存??；存取速度很快缺點(diǎn)：分配連續(xù)的外存空間；事先知道文件的長度共四十五頁42022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.1.2 鏈接(lin ji)分配屬于離散分配方式采用鏈接分配方式時，可通過在每個盤塊上的鏈接指針，將同屬于一個文件的多個離散的盤塊鏈接成一個鏈表，把這樣形成的文件稱為鏈接文件。鏈接方式又可分為隱式鏈接和顯式鏈接兩種形式。共四十五頁52022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院隱式鏈接(lin ji)缺點(diǎn)：可靠性較差；不適合隨機(jī)訪問共四十五頁62022/7/

3、19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院顯式鏈接(lin ji)共四十五頁72022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院鏈?zhǔn)椒峙?fnpi)的優(yōu)缺點(diǎn)離散分配方式消除了外部碎片提高了外存空間利用率便于文件動態(tài)增長方便文件的增、刪、改不能支持高效的直接存取FAT需占用較大的內(nèi)存空間優(yōu)點(diǎn)：缺點(diǎn)：共四十五頁82022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院單級索引(suyn)方式8.1.5 索引組織方式每個文件一個索引塊不利于小文件（常采用鏈?zhǔn)剑┕菜氖屙?2022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院outer-index外部(wib)索引index table索引表

4、File文件多級索引方式共四十五頁102022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院混合(hnh)索引方式直接地址一次間接地址多次間接地址共四十五頁112022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院共四十五頁122022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院例題(lt)1設(shè)文件索引節(jié)點(diǎn)中有7個地址項，其中4個地址項為直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個文件的最大長度是：（ ）1057KB共四十五頁132022/7/19阜陽師范學(xué)院計算機(jī)與信息(x

5、nx)學(xué)院例題(lt)2 若某文件系統(tǒng)索引結(jié)點(diǎn)（inode）中有直接地址項和間接地址項，則下列選項中，與單個文件長度無關(guān)的因素是（ ）索引結(jié)點(diǎn)的總數(shù)間接地址索引的級數(shù)地址項的個數(shù)文件塊大小A共四十五頁142022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院例題(lt)3下列文件物理結(jié)構(gòu)中，適合隨機(jī)訪問且易于文件擴(kuò)展的是：連續(xù)結(jié)構(gòu)索引結(jié)構(gòu) 鏈?zhǔn)浇Y(jié)構(gòu) 順序結(jié)構(gòu)B共四十五頁152022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.2 文件(wnjin)存儲空間的管理8.2.1 空閑表法和空閑鏈表法8.2.2 位示圖法8.2.3 成組鏈接法共四十五頁162022/7/19阜陽師范學(xué)院計算機(jī)與

6、信息(xnx)學(xué)院8.2.1 空閑(kngxin)表法和空閑(kngxin)鏈表法序號第一空閑盤塊號空閑盤塊數(shù)12429331554共四十五頁172022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院存儲空間的分配(fnpi)與回收與內(nèi)存的動態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等內(nèi)存管理中雖然很少采用連續(xù)分配方式，然而在外存的管理中，由于它具有較高的分配速度，可減少訪問磁盤的I/O頻率，故它在諸多分配方式中仍占有一席之地共四十五頁182022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院空閑(kngxin)鏈表法空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成鏈所用基本元

7、素的不同，可把鏈表分成兩種形式：（1）空閑盤塊鏈（2）空閑盤區(qū)鏈共四十五頁192022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院1101010000011000110111000011010100111 2 3 4 5 6 7 8 9 10 11 12123128.2.2 位示圖法(t f)位示圖位示圖是利用二進(jìn)制的一位來表示磁盤中一個盤塊的使用情況。0表示盤塊空閑，1表示已分配。 磁盤上所有盤塊所對應(yīng)的位構(gòu)成一個集合，稱為位示圖。 通常可用m*n個位數(shù)來構(gòu)成位示圖，并使m*n等于磁盤的總塊數(shù)。 如圖,可看成是二維數(shù)組map(m,n)。共四十五頁202022/7/19阜陽師范學(xué)院計算機(jī)與

8、信息(xnx)學(xué)院盤塊的分配(fnpi)和回收順序掃描位示圖，找到0二進(jìn)制位。將所找到的一個或一組二進(jìn)制位，轉(zhuǎn)換成與之對應(yīng)的盤塊號。 盤塊號=列數(shù)*（i-1）+j; （ i,j,b（盤塊號）都從1開始） 盤塊號=列數(shù)*i+j+1; （ i,j從0開始，b從1開始） 盤塊號=列數(shù)*i+j; （ i,j從0開始，b從0開始）3) 修改位示圖,令map(i,j)=1分配過程：1）將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。轉(zhuǎn)換公式為: i=(盤塊號-1)div列數(shù)+1 j=(盤塊號-1)mod列數(shù)+1（ i,j,b（盤塊號）都從1開始） i=(盤塊號-1)div列數(shù) j=(盤塊號-1)mod列數(shù)

9、（i,j從0開始，b從1開始） i=盤塊號div列數(shù) j=盤塊號mod列數(shù) （i,j從0開始，b從0開始）2）修改位示圖,令map(i,j)=0回收過程：共四十五頁212022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院例題(lt)4假定一個盤組共有100個盤面,每個盤面上有16個磁道,每個磁道分成4個扇區(qū),問:(1) 整個磁盤空間共有多少個存儲塊？(2) 如果用字長32位的單元來構(gòu)造位示圖,共需多少個字？(3) 位示圖中第18個字的第16位對應(yīng)的塊號是多少？ 分析：(1) 4*16*100=6400(2) 6400/32=200(3) (18-1)*32+16=560共四十五頁22202

10、2/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.2.3 成組鏈接(lin ji)法空閑表法和空閑鏈表法都不適用于大型文件系統(tǒng)，因?yàn)檫@會使空閑表或空閑鏈表太長。在UNIX系統(tǒng)中采用的是成組鏈接法是將上述兩種方法結(jié)合而形成的一種空閑盤塊管理方法，它兼?zhèn)淞松鲜龇椒ǖ膬?yōu)點(diǎn)而克服了表太長的缺點(diǎn)。共四十五頁232022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院空閑(kngxin)盤塊的成組鏈接法示意圖S.free(0)是棧底棧滿時棧頂為S.free(99)共四十五頁242022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院空閑(kngxin)盤塊的組織空閑盤塊號棧用來存放當(dāng)前可用的一組空閑盤

11、塊的盤塊號（最多含100個號），以及棧中尚有的空閑盤塊號數(shù)NN還兼作棧頂指針例如：當(dāng)N=100時，它指向S.free(99)，S.free(0)是棧底，棧滿時棧頂為S.free(99)。共四十五頁252022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院空閑(kngxin)盤塊的組織文件中的所有空閑盤塊，被分成若干個組。將每一組含有的盤塊總數(shù)N和該組的盤塊號，記入其前一組的第一個盤塊的S.free(0)S.free(99)中。這樣由各組的第一個盤塊形成了一條鏈。將第一組的盤塊總數(shù)和所有的盤塊號，記入空閑盤塊號棧中，作為當(dāng)前可供分配的空閑盤塊號。最末一組只有99個盤塊，在S.free(0)中則

12、存放0，作為空閑盤塊鏈的結(jié)束標(biāo)志。共四十五頁8.3 提高磁盤I/O速度(sd)的途徑磁盤高速緩存(Disk Cache)提高(t go)磁盤I/O速度的其它方法廉價磁盤冗余陣列 (RAID)262022/7/19阜陽師范學(xué)院計算機(jī)與信息學(xué)院共四十五頁272022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院 指利用內(nèi)存中的存儲空間，來暫存從磁盤中讀出的一系列盤塊中的信息。因此，它是一組在邏輯上屬于(shy)磁盤，而物理上是駐留在內(nèi)存中的盤塊。8.3.1 磁盤高速緩存(Disk Cache)1. 磁盤高速緩存的形式 指將磁盤高速緩存中的數(shù)據(jù)傳送給請求者進(jìn)程。系統(tǒng)可以采取兩種方式，將數(shù)據(jù)交付給請

13、求進(jìn)程： (1) 數(shù)據(jù)交付 (2) 指針交付2. 數(shù)據(jù)交付方式共四十五頁282022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院 磁盤緩存的調(diào)度算法(sun f)很類似存儲調(diào)度算法(sun f)，但由于磁盤的區(qū)別，通常比虛擬存儲復(fù)雜。除了考慮到最近最久未使用這一原則外，還考慮了以下幾點(diǎn)： 訪問頻率、 可預(yù)見性、數(shù)據(jù)的一致性。3. 置換算法4. 周期性地寫回磁盤8.3.1 磁盤高速緩存(Disk Cache)共四十五頁292022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院1. 提前(tqin)讀(Read-Ahead) 2. 延遲寫 3. 優(yōu)化物理塊的分布 4. 虛擬盤 8.3.2 提

14、高磁盤I/O速度的其它方法共四十五頁302022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.3.3 廉價磁盤(c pn)冗余陣列 (RAID)1. 并行交叉存取是利用一臺磁盤陣列控制器，來統(tǒng)一管理和控制一組磁盤驅(qū)動器，從而組成一個高度可靠的快速的大容量磁盤系統(tǒng)。OS將RAID中一組物理磁盤驅(qū)動器看作是一個單個的邏輯磁盤驅(qū)動器，用戶和系統(tǒng)數(shù)據(jù)可分布在陣列的所有磁盤中，并可采取并行傳輸方式。2. RAID的分級RAID的另一特點(diǎn)是高可靠性，可分成RAID0 RAID7幾級，除了RAID0外，其它各級都采用了容錯技術(shù)。共四十五頁312022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院影響

15、文件安全性的主要因素及采取(ciq)的措施：人為因素：采取存取控制機(jī)制系統(tǒng)因素：通過磁盤容錯技術(shù)自然因素：通過后備系統(tǒng)8.4 提高磁盤可靠性的技術(shù)共四十五頁322022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院容錯技術(shù)： 通過在系統(tǒng)中設(shè)置冗余部件的辦法(bnf)，提高系統(tǒng)可靠性的一種技術(shù)。磁盤容錯技術(shù)（系統(tǒng)容錯技術(shù)SFTSystem Fault Tolerance）則是通過增加冗余的磁盤驅(qū)動器、磁盤控制器等方法，來提高磁盤系統(tǒng)可靠性的一種技術(shù)。8.4 提高磁盤可靠性的技術(shù)共四十五頁332022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院磁盤容錯技術(shù)： SFT-1：低級磁盤容錯技術(shù)，主

16、要用于防止磁盤表面發(fā)生缺陷所引起的數(shù)據(jù)丟失(dis)； SFT-2：中級磁盤容錯技術(shù)，主要用于防止磁盤驅(qū)動器和磁盤控制器故障引起的系統(tǒng)不能正常工作； SFT-3：高級磁盤容錯技術(shù)，它基于集群技術(shù)實(shí)現(xiàn)容錯。8.4 提高磁盤可靠性的技術(shù)共四十五頁342022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院第一級容錯(rn cu)技術(shù)(SFT-1)常用的措施有：雙份目錄和雙份文件分配表（FAT）在不同的磁盤上或磁盤的不同區(qū)域中，分別建立兩份目錄表和FAT熱修復(fù)重定向和寫后讀校驗(yàn)熱修復(fù)重定向?qū)懞笞x校驗(yàn)共四十五頁352022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院 第二級容錯(rn cu)技術(shù)(

17、SFT-2) 磁盤鏡像（Disk Mirroring） 磁盤雙工（Disk Duplexing）共四十五頁362022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院主 機(jī)磁 盤 控 制 器通道磁盤驅(qū)動器磁盤鏡像（Disk Mirroring）磁盤驅(qū)動器故障的容錯 在同一磁盤控制器控制下，增設(shè)一個完全相同的磁盤驅(qū)動器,如下圖。 每次將數(shù)據(jù)寫主磁盤時，都需要采用寫后檢驗(yàn)方式，同時將數(shù)據(jù)也寫入到備份磁盤。 主磁盤驅(qū)動器發(fā)生故障時，則啟動備份驅(qū)動器，并立即發(fā)出(fch)警告，盡快修復(fù)。不足之處：磁盤利用率為50%共四十五頁372022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院磁盤(c pn)雙

18、工（Disk Duplexing）主 機(jī)通道磁盤驅(qū)動器 磁 盤控制器通道 磁 盤控制器 磁盤控制器或控制器與CPU之間的通道故障的容錯。 將兩臺磁盤驅(qū)動器分別接到兩個磁盤控制器上,如下圖。 兩個磁盤上的數(shù)據(jù)完全相同。 每個磁盤都有自己的獨(dú)立通道共四十五頁382022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.5 數(shù)據(jù)(shj)一致性控制 8.5.1 事務(wù)8.5.2 檢查點(diǎn)8.5.3 并發(fā)控制共四十五頁392022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.5.1 事務(wù)(shw)1、事務(wù)（Transaction）的定義 當(dāng)一個數(shù)據(jù)被分散地存放在一個文件的不同記錄或多個文件中，可采

19、用事務(wù)來保證該數(shù)據(jù)的一致性事務(wù)是用于訪問和修改各種數(shù)據(jù)項的一個程序單位。只有對分布在不同位置的同一個數(shù)據(jù)所進(jìn)行的讀和寫（含修改）操作全部完成時，才執(zhí)行托付操作。只要有一讀、寫或修改操作失敗，便執(zhí)行夭折操作，須將事務(wù)內(nèi)剛被修改的數(shù)據(jù)項恢復(fù)成原來的情況。事務(wù)具有原子性：事務(wù)的操作要么全部完成，要么一個也不做。共四十五頁402022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院2、 事務(wù)(shw)記錄事務(wù)操作的原子性須借助于存放在穩(wěn)定存儲器中的事務(wù)記錄表來實(shí)現(xiàn)記錄事務(wù)運(yùn)行時所有對數(shù)據(jù)項的修改信息又稱運(yùn)行日志（Log）。該記錄包括：事務(wù)名（事務(wù)的唯一標(biāo)識）、數(shù)據(jù)項名（被修改的數(shù)據(jù)項標(biāo)識）、舊值、新值

20、當(dāng)一個事務(wù)提交時，將一個提交記錄也寫入事務(wù)記錄表中。共四十五頁412022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院3、 恢復(fù)(huf)算法當(dāng)系統(tǒng)發(fā)生故障后，利用事務(wù)記錄進(jìn)行故障恢復(fù)。搜索整個事務(wù)記錄表：對于已經(jīng)提交了的事務(wù)，若在事務(wù)記錄表中既包括，又包括記錄，則執(zhí)行redo 操作，設(shè)置為新值對于未提交事務(wù)，只有，而無記錄，執(zhí)行undo 操作共四十五頁422022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.5.2 檢查點(diǎn)1、檢查點(diǎn) （Check points）的作用系統(tǒng)每隔一段時間便寫一條檢查點(diǎn)記錄到事務(wù)記錄表，并進(jìn)行恢復(fù)(huf)工作，即：對已經(jīng)提交的事務(wù)執(zhí)行redo，未提交的事務(wù)執(zhí)行undo。 這樣在檢查點(diǎn)這個時刻，系統(tǒng)中數(shù)據(jù)的一致性和完整性肯定能得到保證。2、新的恢復(fù)算法 在引入檢查點(diǎn)后，當(dāng)發(fā)生故障后，只需對最后一個檢查點(diǎn)以后開始的事務(wù)執(zhí)行恢復(fù)工作。共四十五頁432022/7/19阜陽師范學(xué)院計算機(jī)與信息(xnx)學(xué)院8.5.3 并發(fā)(bngf)控制在多進(jìn)程或