第8章磁盤存儲管理

12023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.1外存的組織方式8.2文件存儲空間的管理8.3提高磁盤I/O速度的途徑8.4提高磁盤可靠性的技術(shù)8.5數(shù)據(jù)一致性控制

主要任務(wù)和要求是：有效地利用存儲空間提高磁盤的I/O速度提高磁盤系統(tǒng)的可靠性第8章磁盤存儲器的管理22023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院文件的物理結(jié)構(gòu)和外存分配方法有關(guān)連續(xù)分配方式順序式結(jié)構(gòu)鏈接分配方式鏈接式結(jié)構(gòu)索引分配方式索引式結(jié)構(gòu)

8.1.1連續(xù)分配8.1.2鏈接分配8.1.3索引分配8.1外存組織方式32023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.1.1連續(xù)分配優(yōu)點(diǎn)：順序訪問容易，支持隨機(jī)存取；存取速度很快缺點(diǎn)：分配連續(xù)的外存空間；事先知道文件的長度42023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.1.2鏈接分配屬于離散分配方式采用鏈接分配方式時(shí)，可通過在每個(gè)盤塊上的鏈接指針，將同屬于一個(gè)文件的多個(gè)離散的盤塊鏈接成一個(gè)鏈表，把這樣形成的文件稱為鏈接文件。鏈接方式又可分為隱式鏈接和顯式鏈接兩種形式。52023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院隱式鏈接缺點(diǎn)：可靠性較差；不適合隨機(jī)訪問62023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院顯式鏈接72023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院鏈?zhǔn)椒峙涞膬?yōu)缺點(diǎn)離散分配方式消除了外部碎片提高了外存空間利用率便于文件動(dòng)態(tài)增長方便文件的增、刪、改不能支持高效的直接存取FAT需占用較大的內(nèi)存空間優(yōu)點(diǎn)：缺點(diǎn)：82023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院單級索引方式8.1.5索引組織方式每個(gè)文件一個(gè)索引塊不利于小文件（常采用鏈?zhǔn)剑?2023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院outer-index外部索引indextable索引表File文件多級索引方式102023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院混合索引方式直接地址一次間接地址多次間接地址112023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院122023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院例題1設(shè)文件索引節(jié)點(diǎn)中有7個(gè)地址項(xiàng)，其中4個(gè)地址項(xiàng)為直接地址索引，2個(gè)地址項(xiàng)是一級間接地址索引，1個(gè)地址項(xiàng)是二級間接地址索引，每個(gè)地址項(xiàng)大小為4字節(jié)，若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個(gè)文件的最大長度是：（）1057KB132023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院例題2若某文件系統(tǒng)索引結(jié)點(diǎn)（inode）中有直接地址項(xiàng)和間接地址項(xiàng)，則下列選項(xiàng)中，與單個(gè)文件長度無關(guān)的因素是（）索引結(jié)點(diǎn)的總數(shù)間接地址索引的級數(shù)地址項(xiàng)的個(gè)數(shù)文件塊大小A142023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院例題3下列文件物理結(jié)構(gòu)中，適合隨機(jī)訪問且易于文件擴(kuò)展的是：連續(xù)結(jié)構(gòu)索引結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)順序結(jié)構(gòu)B152023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.2文件存儲空間的管理8.2.1空閑表法和空閑鏈表法8.2.2位示圖法8.2.3成組鏈接法162023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.2.1空閑表法和空閑鏈表法序號第一空閑盤塊號空閑盤塊數(shù)12429331554——172023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院存儲空間的分配與回收與內(nèi)存的動(dòng)態(tài)分配類似，同樣是采用首次適應(yīng)算法、循環(huán)首次適應(yīng)算法等內(nèi)存管理中雖然很少采用連續(xù)分配方式，然而在外存的管理中，由于它具有較高的分配速度，可減少訪問磁盤的I/O頻率，故它在諸多分配方式中仍占有一席之地182023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院空閑鏈表法空閑鏈表法是將所有空閑盤區(qū)拉成一條空閑鏈。根據(jù)構(gòu)成鏈所用基本元素的不同，可把鏈表分成兩種形式：（1）空閑盤塊鏈（2）空閑盤區(qū)鏈192023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院110101000001100011011100001101010011123456789101112123………128.2.2

位示圖法——位示圖位示圖是利用二進(jìn)制的一位來表示磁盤中一個(gè)盤塊的使用情況。0表示盤塊空閑，1表示已分配。

磁盤上所有盤塊所對應(yīng)的位構(gòu)成一個(gè)集合，稱為位示圖。通?？捎胢*n個(gè)位數(shù)來構(gòu)成位示圖，并使m*n等于磁盤的總塊數(shù)。如圖,可看成是二維數(shù)組map(m,n)。202023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院盤塊的分配和回收順序掃描位示圖，找到0二進(jìn)制位。將所找到的一個(gè)或一組二進(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ù)+1j=(盤塊號-1)mod列數(shù)+1（i,j,b（盤塊號）都從1開始）

i=(盤塊號-1)div列數(shù)

j=(盤塊號-1)mod列數(shù)（i,j從0開始，b從1開始）i=盤塊號div列數(shù)

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

分析：(1)4*16*100=6400(2)6400/32=200(3)(18-1)*32+16=560222023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.2.3成組鏈接法空閑表法和空閑鏈表法都不適用于大型文件系統(tǒng)，因?yàn)檫@會使空閑表或空閑鏈表太長。在UNIX系統(tǒng)中采用的是成組鏈接法是將上述兩種方法結(jié)合而形成的一種空閑盤塊管理方法，它兼?zhèn)淞松鲜龇椒ǖ膬?yōu)點(diǎn)而克服了表太長的缺點(diǎn)。232023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院空閑盤塊的成組鏈接法示意圖S.free(0)是棧底棧滿時(shí)棧頂為S.free(99)242023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院空閑盤塊的組織空閑盤塊號棧用來存放當(dāng)前可用的一組空閑盤塊的盤塊號（最多含100個(gè)號），以及棧中尚有的空閑盤塊號數(shù)NN還兼作棧頂指針例如：當(dāng)N=100時(shí)，它指向S.free(99)，S.free(0)是棧底，棧滿時(shí)棧頂為S.free(99)。252023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院空閑盤塊的組織文件中的所有空閑盤塊，被分成若干個(gè)組。將每一組含有的盤塊總數(shù)N和該組的盤塊號，記入其前一組的第一個(gè)盤塊的S.free(0)~S.free(99)中。這樣由各組的第一個(gè)盤塊形成了一條鏈。將第一組的盤塊總數(shù)和所有的盤塊號，記入空閑盤塊號棧中，作為當(dāng)前可供分配的空閑盤塊號。最末一組只有99個(gè)盤塊，在S.free(0)中則存放0，作為空閑盤塊鏈的結(jié)束標(biāo)志。8.3提高磁盤I/O速度的途徑磁盤高速緩存(DiskCache)提高磁盤I/O速度的其它方法廉價(jià)磁盤冗余陣列(RAID)262023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院272023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院

指利用內(nèi)存中的存儲空間，來暫存從磁盤中讀出的一系列盤塊中的信息。因此，它是一組在邏輯上屬于磁盤，而物理上是駐留在內(nèi)存中的盤塊。8.3.1磁盤高速緩存(DiskCache)1.磁盤高速緩存的形式

指將磁盤高速緩存中的數(shù)據(jù)傳送給請求者進(jìn)程。系統(tǒng)可以采取兩種方式，將數(shù)據(jù)交付給請求進(jìn)程：

(1)數(shù)據(jù)交付(2)指針交付2.數(shù)據(jù)交付方式282023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院

磁盤緩存的調(diào)度算法很類似存儲調(diào)度算法，但由于磁盤的區(qū)別，通常比虛擬存儲復(fù)雜。除了考慮到最近最久未使用這一原則外，還考慮了以下幾點(diǎn)：訪問頻率、可預(yù)見性、數(shù)據(jù)的一致性。3.置換算法4.周期性地寫回磁盤8.3.1磁盤高速緩存(DiskCache)292023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院1.提前讀(Read-Ahead)2.延遲寫3.優(yōu)化物理塊的分布4.虛擬盤8.3.2提高磁盤I/O速度的其它方法302023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.3.3廉價(jià)磁盤冗余陣列(RAID)1.并行交叉存取是利用一臺磁盤陣列控制器，來統(tǒng)一管理和控制一組磁盤驅(qū)動(dòng)器，從而組成一個(gè)高度可靠的快速的大容量磁盤系統(tǒng)。OS將RAID中一組物理磁盤驅(qū)動(dòng)器看作是一個(gè)單個(gè)的邏輯磁盤驅(qū)動(dòng)器，用戶和系統(tǒng)數(shù)據(jù)可分布在陣列的所有磁盤中，并可采取并行傳輸方式。2.RAID的分級RAID的另一特點(diǎn)是高可靠性，可分成RAID0－RAID7幾級，除了RAID0外，其它各級都采用了容錯(cuò)技術(shù)。312023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院影響文件安全性的主要因素及采取的措施：人為因素：——采取存取控制機(jī)制系統(tǒng)因素：——通過磁盤容錯(cuò)技術(shù)自然因素：——通過后備系統(tǒng)8.4提高磁盤可靠性的技術(shù)322023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院容錯(cuò)技術(shù)：通過在系統(tǒng)中設(shè)置冗余部件的辦法，提高系統(tǒng)可靠性的一種技術(shù)。磁盤容錯(cuò)技術(shù)（系統(tǒng)容錯(cuò)技術(shù)SFT——SystemFaultTolerance）則是通過增加冗余的磁盤驅(qū)動(dòng)器、磁盤控制器等方法，來提高磁盤系統(tǒng)可靠性的一種技術(shù)。8.4提高磁盤可靠性的技術(shù)332023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院磁盤容錯(cuò)技術(shù)：

SFT-1：低級磁盤容錯(cuò)技術(shù)，主要用于防止磁盤表面發(fā)生缺陷所引起的數(shù)據(jù)丟失；

SFT-2：中級磁盤容錯(cuò)技術(shù)，主要用于防止磁盤驅(qū)動(dòng)器和磁盤控制器故障引起的系統(tǒng)不能正常工作；

SFT-3：高級磁盤容錯(cuò)技術(shù)，它基于集群技術(shù)實(shí)現(xiàn)容錯(cuò)。8.4提高磁盤可靠性的技術(shù)342023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院第一級容錯(cuò)技術(shù)(SFT-1)常用的措施有：雙份目錄和雙份文件分配表（FAT）在不同的磁盤上或磁盤的不同區(qū)域中，分別建立兩份目錄表和FAT熱修復(fù)重定向和寫后讀校驗(yàn)熱修復(fù)重定向?qū)懞笞x校驗(yàn)352023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院

第二級容錯(cuò)技術(shù)(SFT-2)磁盤鏡像（DiskMirroring）磁盤雙工（DiskDuplexing）362023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院主機(jī)磁盤控制器通道磁盤驅(qū)動(dòng)器磁盤鏡像（DiskMirroring）磁盤驅(qū)動(dòng)器故障的容錯(cuò)在同一磁盤控制器控制下，增設(shè)一個(gè)完全相同的磁盤驅(qū)動(dòng)器,如下圖。每次將數(shù)據(jù)寫主磁盤時(shí)，都需要采用寫后檢驗(yàn)方式，同時(shí)將數(shù)據(jù)也寫入到備份磁盤。主磁盤驅(qū)動(dòng)器發(fā)生故障時(shí)，則啟動(dòng)備份驅(qū)動(dòng)器，并立即發(fā)出警告，盡快修復(fù)。不足之處：磁盤利用率為50%372023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院磁盤雙工（DiskDuplexing）主機(jī)通道磁盤驅(qū)動(dòng)器

磁盤控制器通道

磁盤控制器

磁盤控制器或控制器與CPU之間的通道故障的容錯(cuò)。將兩臺磁盤驅(qū)動(dòng)器分別接到兩個(gè)磁盤控制器上,如下圖。兩個(gè)磁盤上的數(shù)據(jù)完全相同。每個(gè)磁盤都有自己的獨(dú)立通道382023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.5數(shù)據(jù)一致性控制

8.5.1事務(wù)8.5.2檢查點(diǎn)8.5.3并發(fā)控制392023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院8.5.1事務(wù)1、事務(wù)（Transaction）的定義當(dāng)一個(gè)數(shù)據(jù)被分散地存放在一個(gè)文件的不同記錄或多個(gè)文件中，可采用事務(wù)來保證該數(shù)據(jù)的一致性事務(wù)是用于訪問和修改各種數(shù)據(jù)項(xiàng)的一個(gè)程序單位。只有對分布在不同位置的同一個(gè)數(shù)據(jù)所進(jìn)行的讀和寫（含修改）操作全部完成時(shí)，才執(zhí)行托付操作。只要有一讀、寫或修改操作失敗，便執(zhí)行夭折操作，須將事務(wù)內(nèi)剛被修改的數(shù)據(jù)項(xiàng)恢復(fù)成原來的情況。事務(wù)具有原子性：事務(wù)的操作要么全部完成，要么一個(gè)也不做。402023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院2、事務(wù)記錄事務(wù)操作的原子性須借助于存放在穩(wěn)定存儲器中的事務(wù)記錄表來實(shí)現(xiàn)記錄事務(wù)運(yùn)行時(shí)所有對數(shù)據(jù)項(xiàng)的修改信息——又稱運(yùn)行日志（Log）。該記錄包括：事務(wù)名（事務(wù)的唯一標(biāo)識）、數(shù)據(jù)項(xiàng)名（被修改的數(shù)據(jù)項(xiàng)標(biāo)識）、舊值、新值當(dāng)一個(gè)事務(wù)提交時(shí)，將一個(gè)提交記錄<Ti托付>也寫入事務(wù)記錄表中。412023/2/6阜陽師范學(xué)院計(jì)算機(jī)與信息學(xué)院3、恢復(fù)算法當(dāng)系統(tǒng)發(fā)生故障后，利用事務(wù)記錄進(jìn)行故障恢復(fù)。搜索整個(gè)事務(wù)記錄表：對于已經(jīng)提交了的事務(wù)，若在事務(wù)記錄表中既包括<Ti開始>，又包括<Ti托付>記錄，則執(zhí)行redo<Ti>操作，設(shè)置為新值對于未提交事務(wù)，只有<Ti開始>，而無<Ti