磁盤存儲管理

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

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

FSCAN算法：兩個隊列，一是當前請求I/O的磁盤請求隊列,二是在掃描期間新出現(xiàn)的所有磁盤請求組成的隊列。這樣，所有新到達的訪問請求本次不予訪問，留待下次再服務。9.1.3各種掃描算法第20頁，課件共57頁，創(chuàng)作于2023年2月FSCAN算法示意圖第21頁，課件共57頁，創(chuàng)作于2023年2月例：假設磁盤訪問序列：98，183，37，122，14，124，65，67新出現(xiàn)：45，7，30讀寫頭起始位置：53當前移動方向為向磁道號增加的方向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外存分配算法文件的物理結構：又稱為文件的存儲結構，是指文件在外存上的存儲組織形式，于存儲介質的特性有關。類型：順序結構（順序分配）鏈接結構（鏈接分配）索引結構（索引分配）第23頁，課件共57頁，創(chuàng)作于2023年2月9.2.1連續(xù)分配一個文件的信息存放在若干連續(xù)的物理塊中

優(yōu)點:

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

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

B不利于文件插入和刪除

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

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

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

91611025-1-1-119第32頁，課件共57頁，創(chuàng)作于2023年2月當索引表較大時，有如下幾種組織方式：鏈接模式:一個盤塊一個索引表,多個索引表鏈接起來多級索引:將一個大文件的所有索引表（二級索引)的地址放在另一個索引表（一級索引)中混合模式:UNIX文件系統(tǒng)采用的是多級索引結構(綜合模式)。每個文件的索引表為13個索引項，每項4個字節(jié)。最前面10項直接登記存放文件信息的物理塊號（直接尋址）9.2.3索引分配第33頁，課件共57頁，創(chuàng)作于2023年2月混合分配(假定每個盤塊大小為4KB）:1.直接地址:當文件不大于40KB時，可直接從索引結點中讀出全部盤塊號。2.一次間接地址iaddr(10):允許文件長達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空閑表法

將所有空閑塊記錄在一個表中，即空閑盤塊表（示意圖）特點:數(shù)據(jù)結構:空閑盤塊表(序號,第一空閑盤塊號,空閑盤塊數(shù))連續(xù)分配,分配和回收與內存管理的動態(tài)分區(qū)分配方法類似分配速度快,可減少訪盤頻率,用于小文件的分配和對換空間的管理第38頁，課件共57頁，創(chuàng)作于2023年2月序號第一空閑盤塊號空閑盤塊數(shù)12429331554----返回空閑盤塊表第39頁，課件共57頁，創(chuàng)作于2023年2月9.3.2空閑鏈表法把所有空閑盤塊鏈成一個空閑鏈,根據(jù)構成鏈的基本元素不同,可有兩種鏈表形式:空閑盤塊鏈:基本元素為盤塊。優(yōu)點：分配回收過程簡單缺點：空閑盤塊鏈可能很長空閑盤區(qū)鏈：基本元素為盤區(qū)（可包含若干個盤塊）特點：分配回收與動態(tài)分區(qū)類似說明：可用顯式鏈接方式提高檢索速度第40頁，課件共57頁，創(chuàng)作于2023年2月9.3.3位示圖法1.位示圖用一串二進制位反映磁盤空間中分配使用情況,每個物理塊對應一位,分配物理塊為1，否則為0。磁盤上的所有盤塊都有一個二進制位與之對應，由所有盤塊所對應的位組成的集合，稱為位示圖。Varmap:array[1…m,1…n]ofbit優(yōu)點：占用空間少，描述能力強，適合各種物理結構第41頁，課件共57頁，創(chuàng)作于2023年2月2.盤塊的分配（1）順序掃描位示圖，查找為0的一個或一組二進制位（2）返回對應盤塊號。假設位于位示圖的第i行，第j列，對應的盤塊為b=n(i-1)+j(n為每行的位數(shù)）（3）修改位示圖map[i,j]=13.盤塊的回收（1）將回收盤塊號b轉換成行號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成組鏈接法磁盤文件卷結構:超級塊：描述文件系統(tǒng)的狀態(tài)，包括磁盤空閑塊棧，空閑i結點棧i節(jié)點（inodelist）：存放文件說明信息，每項64字節(jié)目錄文件：每個目錄項16字節(jié)。文件名區(qū)分大小寫。文件分配：直接索引，一級、二級、三級間接索引第44頁，課件共57頁，創(chuàng)作于2023年2月空閑塊成組鏈接，建立空閑塊專用棧，空閑塊分配時按組進行，一組的空閑塊分配完了，再使用下一組；回收時次序相反，入棧一組空閑塊后，夠成一組。這種方法兼?zhèn)淞丝臻e空間表法和空閑塊鏈接法的優(yōu)點，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月下面演示分配過程的例子當前空閑塊棧中還有兩塊未分配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月下面演示回收過程的例子當前空閑塊棧中有99個空閑塊9.3.4成組鏈接法第52頁，課件共57頁，創(chuàng)作于2023年2月……s_nfree=99460299

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