磁盤存儲管理

磁盤存儲管理第1頁，課件共57頁，創(chuàng)作于2023年2月9.1磁盤I/O磁盤I/O速度的高低，將直接影響文件系統(tǒng)的性能。提高磁盤I/O速度的主要途徑：選擇性能好的磁盤采用好的磁盤調(diào)度算法設(shè)置磁盤高速緩沖區(qū)第2頁，課件共57頁，創(chuàng)作于2023年2月直接（隨機(jī)）存取設(shè)備：存取磁盤上任一物理塊的時(shí)間不依賴于該物理塊所處的位置。一、數(shù)據(jù)的組織信息記錄在磁道上，多個(gè)盤片，正反兩面都用來記錄信息，每面一個(gè)磁頭,所有盤面中處于同一磁道號上的所有磁道組成一個(gè)柱面。磁道由若干個(gè)扇區(qū)組成，每個(gè)扇區(qū)的大小相當(dāng)于一個(gè)盤塊。物理地址形式：磁頭號（盤面號）磁道號（柱面號）扇區(qū)號9.1.1磁盤性能簡述第3頁，課件共57頁，創(chuàng)作于2023年2月磁道扇區(qū)第4頁，課件共57頁，創(chuàng)作于2023年2月柱面扇區(qū)磁臂磁頭第5頁，課件共57頁，創(chuàng)作于2023年2月二、磁盤的類型固定頭磁盤：每個(gè)磁道設(shè)置一個(gè)磁頭，變換磁道時(shí)不需要磁頭的機(jī)械移動，速度快但成本高移動頭磁盤：一個(gè)盤面只有一個(gè)磁頭，變換磁道時(shí)需要移動磁頭，速度慢但成本低磁盤系統(tǒng)由磁盤本身和驅(qū)動控制設(shè)備組成，實(shí)際存取讀寫的動作過程是由磁盤驅(qū)動控制設(shè)備按照主機(jī)要求完成的。一次訪盤請求：讀/寫，磁盤地址（設(shè)備號，柱面號，磁頭號，扇區(qū)號），內(nèi)存地址（源/目）9.1.1磁盤性能簡述第6頁，課件共57頁，創(chuàng)作于2023年2月磁盤訪問時(shí)間包括以下三個(gè)部分：尋道時(shí)間TS：磁頭移動定位到指定磁道。10-40msTS=m*n+s（m：常數(shù)，n:移動的磁道數(shù)，s:磁盤啟動時(shí)間）旋轉(zhuǎn)延遲時(shí)間TR：等待指定扇區(qū)旋轉(zhuǎn)到磁頭下。硬盤平均8.3ms,軟盤平均50-100ms數(shù)據(jù)傳輸時(shí)間TT：數(shù)據(jù)在磁盤與內(nèi)存之間的實(shí)際傳輸。TT=b/(r*N)(b:讀寫字節(jié)數(shù)r:磁盤轉(zhuǎn)速N:一個(gè)磁道上的字節(jié)數(shù)）分析：提高I/O效率的關(guān)鍵是什么？9.1.1磁盤性能簡述第7頁，課件共57頁，創(chuàng)作于2023年2月設(shè)計(jì)文件系統(tǒng)時(shí)應(yīng)盡可能減少磁盤訪問次數(shù)塊高速緩存系統(tǒng)在內(nèi)存中保存一些塊，邏輯上它們屬于磁盤，檢查所有的讀請求，看所需的塊是否在高速緩存中。如果在，則可直接進(jìn)行讀操作。否則，首先要將塊讀到高速緩存，再拷貝到所需的地方，如果高速緩存已滿，則需要進(jìn)行淘汰合理分配磁盤空間分配塊時(shí)，把有可能順序存取的塊放在一起，最好在同一柱面上，從而減少磁盤臂的移動次數(shù)好的磁盤調(diào)度算法9.1.1磁盤性能簡述第8頁，課件共57頁，創(chuàng)作于2023年2月9.1.2早期的磁盤調(diào)度算法磁盤調(diào)度：

當(dāng)多個(gè)訪盤請求在等待時(shí)，采用一定的策略，對這些請求的服務(wù)順序調(diào)整安排，旨在降低平均磁盤服務(wù)時(shí)間，達(dá)到公平、高效公平：一個(gè)I/O請求在有限時(shí)間內(nèi)滿足高效：減少設(shè)備機(jī)械運(yùn)動所帶來的時(shí)間浪費(fèi)，主要是使磁盤的平均尋道時(shí)間最短。第9頁，課件共57頁，創(chuàng)作于2023年2月一、先來先服務(wù)：按訪問請求到達(dá)的先后次序服務(wù)。優(yōu)點(diǎn)：簡單，公平；缺點(diǎn)：效率不高，相臨兩次請求可能會造成最內(nèi)到最外的柱面尋道，使磁頭反復(fù)移動，增加了服務(wù)時(shí)間，對機(jī)械也不利。例：假設(shè)磁盤訪問序列：98，183，37，122，14，124，65，67讀寫頭起始位置：53安排磁頭服務(wù)序列，計(jì)算磁頭移動總距離（道數(shù)）9.1.2早期的磁盤調(diào)度算法第10頁，課件共57頁，創(chuàng)作于2023年2月53：98，183，37，122，14，124，65，67總=640先來先服務(wù)第11頁，課件共57頁，創(chuàng)作于2023年2月二、最短尋道時(shí)間優(yōu)先：優(yōu)先選擇距當(dāng)前磁頭最近的訪問請求進(jìn)行服務(wù)，主要考慮尋道優(yōu)先。優(yōu)點(diǎn)：改善了磁盤平均服務(wù)時(shí)間；缺點(diǎn)：造成某些訪問請求長期等待得不到服務(wù)。9.1.2早期的磁盤調(diào)度算法第12頁，課件共57頁，創(chuàng)作于2023年2月53：98，183，37，122，14，124，65，67總=236最短尋道時(shí)間優(yōu)先第13頁，課件共57頁，創(chuàng)作于2023年2月一、掃描算法（電梯算法）克服了最短尋道優(yōu)先的缺點(diǎn)，既考慮了距離，同時(shí)又考慮了方向具體做法：當(dāng)設(shè)備無訪問請求時(shí)，磁頭不動；當(dāng)有訪問請求時(shí)，磁頭按一個(gè)方向移動，在移動過程中對遇到的訪問請求進(jìn)行服務(wù)，然后判斷該方向上是否還有訪問請求，如果有則繼續(xù)掃描；否則改變移動方向，并為經(jīng)過的訪問請求服務(wù)，如此反復(fù)9.1.3各種掃描算法第14頁，課件共57頁，創(chuàng)作于2023年2月第15頁，課件共57頁，創(chuàng)作于2023年2月53：98，183，37，122，14，124，65，67總=208本例所示的當(dāng)前移動方向?yàn)橄虼诺捞枩p少的方向電梯算法第16頁，課件共57頁，創(chuàng)作于2023年2月二、循環(huán)掃描算法循環(huán)掃描法也稱單向掃描，規(guī)定磁頭單向移動。例如：它對請求者的服務(wù)總是每次從０柱面號開始，然后移動至最大柱面。遇著訪問進(jìn)行服務(wù)。一次完后，磁頭再返回０號柱面，又重復(fù)上述步驟。9.1.3各種掃描算法第17頁，課件共57頁，創(chuàng)作于2023年2月第18頁，課件共57頁，創(chuàng)作于2023年2月例：假設(shè)磁盤訪問序列：98，183，37，122，14，124，65，67讀寫頭起始位置：53,移動方向是向磁道號增加的方向循環(huán)掃描算法：訪問序列：53，65，67，98，122，124，183，14，37總移動距離=3229.1.3各種掃描算法第19頁，課件共57頁，創(chuàng)作于2023年2月三、N步掃描和FSCAN算法

引入目的：避免磁臂粘連。

N步掃描：將磁盤請求隊(duì)列分成若干個(gè)長度為N的子隊(duì)列，磁盤調(diào)度將按FCFS算法依次處理這些子隊(duì)列，對每個(gè)隊(duì)列的處理用SCAN方法。注意：N的選取。

FSCAN算法：兩個(gè)隊(duì)列，一是當(dāng)前請求I/O的磁盤請求隊(duì)列,二是在掃描期間新出現(xiàn)的所有磁盤請求組成的隊(duì)列。這樣，所有新到達(dá)的訪問請求本次不予訪問，留待下次再服務(wù)。9.1.3各種掃描算法第20頁，課件共57頁，創(chuàng)作于2023年2月FSCAN算法示意圖第21頁，課件共57頁，創(chuàng)作于2023年2月例：假設(shè)磁盤訪問序列：98，183，37，122，14，124，65，67新出現(xiàn)：45，7，30讀寫頭起始位置：53當(dāng)前移動方向?yàn)橄虼诺捞栐黾拥姆较騈步掃描（N=3)：分組序列：(98,183,37)，(122，14，124)，(65，67,45)，（7，30）訪問序列：(98,183,37)，(14，122，124)，(67，65,45)，（30，7）總移動距離=?FSCAN算法：訪問序列（65，67，98，122，124，183，37，14）（7，30，45）總移動距離=?9.1.3各種掃描算法526344第22頁，課件共57頁，創(chuàng)作于2023年2月9.2外存分配算法文件的物理結(jié)構(gòu)：又稱為文件的存儲結(jié)構(gòu)，是指文件在外存上的存儲組織形式，于存儲介質(zhì)的特性有關(guān)。類型：順序結(jié)構(gòu)（順序分配）鏈接結(jié)構(gòu)（鏈接分配）索引結(jié)構(gòu)（索引分配）第23頁，課件共57頁，創(chuàng)作于2023年2月9.2.1連續(xù)分配一個(gè)文件的信息存放在若干連續(xù)的物理塊中

優(yōu)點(diǎn):

簡單支持順序存取和隨機(jī)存取順序存取速度快所需的磁盤尋道次數(shù)和尋道時(shí)間最少

缺點(diǎn):A文件不能動態(tài)增長預(yù)留空間:浪費(fèi)重新分配和移動

B不利于文件插入和刪除

C外部碎片問題:存儲壓縮技術(shù)第24頁，課件共57頁，創(chuàng)作于2023年2月012345678910111213141516171819202122232425262728293031文件名始址塊數(shù)count02tr143mail196list284f62文件目錄countftrmaillist第25頁，課件共57頁，創(chuàng)作于2023年2月9.2.2鏈接分配一個(gè)文件的信息存放在若干不連續(xù)的物理塊中，各塊之間通過指針連接，前一個(gè)物理塊指向下一個(gè)物理塊。

優(yōu)點(diǎn)：提高了磁盤空間利用率,不存在外部碎片問題;有利于文件插入和刪除;有利于文件動態(tài)擴(kuò)充。鏈接方式分為:隱式鏈接顯式鏈接

第26頁，課件共57頁，創(chuàng)作于2023年2月一、隱式鏈接在文件目錄的每個(gè)目錄項(xiàng)中，都須含有鏈接文件第一個(gè)盤塊和最后一個(gè)盤塊的指針。缺點(diǎn)：存取速度慢，不適于隨機(jī)存取可靠性問題，如指針出錯更多的尋道次數(shù)和尋道時(shí)間鏈接指針占用一定的空間改進(jìn)：將幾個(gè)盤塊組成一個(gè)簇，以簇為單位分配盤塊，文件的每一個(gè)元素也以簇為單位。9.2.2鏈接分配第27頁，課件共57頁，創(chuàng)作于2023年2月文件名始址末址jeep925文件目錄01234567891011121314151617181920212223242526272829303111016-125第28頁，課件共57頁，創(chuàng)作于2023年2月二、顯式鏈接整個(gè)磁盤設(shè)置一張鏈接表（FAT)，每個(gè)文件的FCB表的“物理地址”中存放鏈?zhǔn)字羔?。?yōu)點(diǎn)：減少訪盤次數(shù)，提高檢索速度。9.2.2鏈接分配第29頁，課件共57頁，創(chuàng)作于2023年2月文件卷中的每個(gè)簇均對應(yīng)一個(gè)FAT表項(xiàng)，文件分配采用鏈?zhǔn)椒峙浞椒?。MS-DOSFAT第30頁，課件共57頁，創(chuàng)作于2023年2月9.2.3索引分配一個(gè)文件的信息存放在若干不連續(xù)物理塊中，系統(tǒng)為每個(gè)文件建立一個(gè)專用數(shù)據(jù)結(jié)構(gòu)--索引表，并將這些塊的塊號存放在一個(gè)索引表中。一個(gè)索引表就是磁盤塊地址數(shù)組,其中第i個(gè)條目指向文件的第i塊。優(yōu)點(diǎn)：保持了鏈接結(jié)構(gòu)的優(yōu)點(diǎn),又解決了其缺點(diǎn)，即能順序存取,又能隨機(jī)存取，滿足了文件動態(tài)增長、插入刪除的要求，也能充分利用外存空間缺點(diǎn)：較多的尋道次數(shù)和尋道時(shí)間索引表本身帶來了系統(tǒng)開銷如：內(nèi)外存空間，存取時(shí)間第31頁，課件共57頁，創(chuàng)作于2023年2月012345678910111213141516171819202122232425262728293031文件名索引表地址文件目錄Jeep19

91611025-1-1-119第32頁，課件共57頁，創(chuàng)作于2023年2月當(dāng)索引表較大時(shí)，有如下幾種組織方式：鏈接模式:一個(gè)盤塊一個(gè)索引表,多個(gè)索引表鏈接起來多級索引:將一個(gè)大文件的所有索引表（二級索引)的地址放在另一個(gè)索引表（一級索引)中混合模式:UNIX文件系統(tǒng)采用的是多級索引結(jié)構(gòu)(綜合模式)。每個(gè)文件的索引表為13個(gè)索引項(xiàng)，每項(xiàng)4個(gè)字節(jié)。最前面10項(xiàng)直接登記存放文件信息的物理塊號（直接尋址）9.2.3索引分配第33頁，課件共57頁，創(chuàng)作于2023年2月混合分配(假定每個(gè)盤塊大小為4KB）:1.直接地址:當(dāng)文件不大于40KB時(shí)，可直接從索引結(jié)點(diǎn)中讀出全部盤塊號。2.一次間接地址iaddr(10):允許文件長達(dá)4MB3.多次間接地址：Iaddr(11):兩次,4GBIaddr(12):三次,4TB9.2.3索引分配第34頁，課件共57頁，創(chuàng)作于2023年2月第35頁，課件共57頁，創(chuàng)作于2023年2月第36頁，課件共57頁，創(chuàng)作于2023年2月9.3空閑存儲空間的管理9.3.1空閑表法9.3.2空閑鏈表法9.3.3位示圖法9.3.4成組鏈接法第37頁，課件共57頁，創(chuàng)作于2023年2月9.3.1空閑表法

將所有空閑塊記錄在一個(gè)表中，即空閑盤塊表（示意圖）特點(diǎn):數(shù)據(jù)結(jié)構(gòu):空閑盤塊表(序號,第一空閑盤塊號,空閑盤塊數(shù))連續(xù)分配,分配和回收與內(nèi)存管理的動態(tài)分區(qū)分配方法類似分配速度快,可減少訪盤頻率,用于小文件的分配和對換空間的管理第38頁，課件共57頁，創(chuàng)作于2023年2月序號第一空閑盤塊號空閑盤塊數(shù)12429331554----返回空閑盤塊表第39頁，課件共57頁，創(chuàng)作于2023年2月9.3.2空閑鏈表法把所有空閑盤塊鏈成一個(gè)空閑鏈,根據(jù)構(gòu)成鏈的基本元素不同,可有兩種鏈表形式:空閑盤塊鏈:基本元素為盤塊。優(yōu)點(diǎn)：分配回收過程簡單缺點(diǎn)：空閑盤塊鏈可能很長空閑盤區(qū)鏈：基本元素為盤區(qū)（可包含若干個(gè)盤塊）特點(diǎn)：分配回收與動態(tài)分區(qū)類似說明：可用顯式鏈接方式提高檢索速度第40頁，課件共57頁，創(chuàng)作于2023年2月9.3.3位示圖法1.位示圖用一串二進(jìn)制位反映磁盤空間中分配使用情況,每個(gè)物理塊對應(yīng)一位,分配物理塊為1，否則為0。磁盤上的所有盤塊都有一個(gè)二進(jìn)制位與之對應(yīng)，由所有盤塊所對應(yīng)的位組成的集合，稱為位示圖。Varmap:array[1…m,1…n]ofbit優(yōu)點(diǎn)：占用空間少，描述能力強(qiáng)，適合各種物理結(jié)構(gòu)第41頁，課件共57頁，創(chuàng)作于2023年2月2.盤塊的分配（1）順序掃描位示圖，查找為0的一個(gè)或一組二進(jìn)制位（2）返回對應(yīng)盤塊號。假設(shè)位于位示圖的第i行，第j列，對應(yīng)的盤塊為b=n(i-1)+j(n為每行的位數(shù)）（3）修改位示圖map[i,j]=13.盤塊的回收（1）將回收盤塊號b轉(zhuǎn)換成行號i和列號ji=(b-1)DIVn+1;j=(b-1)MODn+1（2）修改位示圖：map[i,j]=09.3.3位示圖法第42頁，課件共57頁，創(chuàng)作于2023年2月已知塊號，則磁盤地址：

柱面號＝[塊號/（磁頭數(shù)×扇區(qū)數(shù)）]

磁頭號＝[（塊號mod（磁頭數(shù)×扇區(qū)數(shù)））/扇區(qū)數(shù)]

扇區(qū)號＝（塊號mod（磁頭數(shù)×扇區(qū)數(shù)））mod扇區(qū)數(shù)已知磁盤地址：塊號＝柱面號×（磁頭數(shù)×扇區(qū)數(shù)）＋磁頭號×扇區(qū)數(shù)＋扇區(qū)號9.3.3位示圖法第43頁，課件共57頁，創(chuàng)作于2023年2月9.3.4成組鏈接法磁盤文件卷結(jié)構(gòu):超級塊：描述文件系統(tǒng)的狀態(tài)，包括磁盤空閑塊棧，空閑i結(jié)點(diǎn)棧i節(jié)點(diǎn)（inodelist）：存放文件說明信息，每項(xiàng)64字節(jié)目錄文件：每個(gè)目錄項(xiàng)16字節(jié)。文件名區(qū)分大小寫。文件分配：直接索引，一級、二級、三級間接索引第44頁，課件共57頁，創(chuàng)作于2023年2月空閑塊成組鏈接，建立空閑塊專用棧，空閑塊分配時(shí)按組進(jìn)行，一組的空閑塊分配完了，再使用下一組；回收時(shí)次序相反，入棧一組空閑塊后，夠成一組。這種方法兼?zhèn)淞丝臻e空間表法和空閑塊鏈接法的優(yōu)點(diǎn)，UNIX系統(tǒng)使用這種空閑塊管理策略。9.3.4成組鏈接法第45頁，課件共57頁，創(chuàng)作于2023年2月s-nfree空閑塊數(shù);s_free[100]空閑塊塊號;s_flock鎖位9.3.4成組鏈接法第46頁，課件共57頁，創(chuàng)作于2023年2月下面演示分配過程的例子當(dāng)前空閑塊棧中還有兩塊未分配9.3.4成組鏈接法第47頁，課件共57頁，創(chuàng)作于2023年2月……s_nfree=2300299012s_free…99100400399…301…299#300#100500499…401…400#...9907999…7001…7900#399#…301#...7999#…7001#第48頁，課件共57頁，創(chuàng)作于2023年2月……s_nfree=130001s_free…99100400399…301…分配299#300#100500499…401…400#...9907999…7001…7900#399#…301#...7999#…7001#第49頁，課件共57頁，創(chuàng)作于2023年2月……s_nfree=03000s_free…99100400399…301…100500499…401…400#...9907999…7001…7900#399#…301#...7999#…7001#300#分配第50頁，課件共57頁，創(chuàng)作于2023年2月……s_nfree=100400399…30101…99100500499…401…400#...9907999…7001…7900#399#…301#...7999#…7001#s_free300#分配第51頁，課件共57頁，創(chuàng)作于2023年2月下面演示回收過程的例子當(dāng)前空閑塊棧中有99個(gè)空閑塊9.3.4成組鏈接法第52頁，課件共57頁，創(chuàng)作于2023年2月……s_nfree=99460299

…350012…9899100700899…601…299#460#1005067099…4010…700#...990799…910…506#899