學(xué)習(xí)操作系統(tǒng)ch12disk os

第12章磁盤(pán)管理

（DiskManagement）主講教師:龐俊彪

郵件：junbiao_pang@辦公室:信息樓南412內(nèi)容回顧：磁盤(pán)塊的分配方法連續(xù)分配鏈?zhǔn)椒峙渌饕峙渲嫔葏^(qū)磁臂磁頭012345678910111213141516171819202122232425262728293031test.cftrmaillist如何管理這些磁盤(pán)塊？本章教學(xué)目標(biāo)磁盤(pán)結(jié)構(gòu)磁盤(pán)調(diào)度磁盤(pán)管理1.1磁盤(pán)的結(jié)構(gòu)1.2磁盤(pán)的調(diào)度磁盤(pán)管理1.1磁盤(pán)的結(jié)構(gòu)1.2磁盤(pán)的調(diào)度首先需要了解磁盤(pán)!直接（隨機(jī)）存取設(shè)備：存取磁盤(pán)上任一物理塊的時(shí)間不依賴于該物理塊所處的位置磁盤(pán)固定頭磁盤(pán)：每個(gè)磁道設(shè)置一個(gè)磁頭，變換磁道時(shí)不需要磁頭的機(jī)械移動(dòng)，速度快但成本高移動(dòng)頭磁盤(pán)：一個(gè)盤(pán)面只有一個(gè)磁頭，變換磁道時(shí)需要移動(dòng)磁頭，速度慢但成本低順序存取設(shè)備：只有在前面的物理塊被訪問(wèn)過(guò)之后，才能存取后續(xù)的物理塊的內(nèi)容磁帶磁盤(pán)結(jié)構(gòu)認(rèn)識(shí)一下磁盤(pán)磁道扇區(qū)盤(pán)面畫(huà)一個(gè)示意圖:看看俯視圖:磁盤(pán)的數(shù)據(jù)單位是扇區(qū)扇區(qū)大小：512字節(jié)扇區(qū)是磁盤(pán)的尋址單位、訪問(wèn)單位扇區(qū)的大小是傳輸時(shí)間和碎片浪費(fèi)的折衷所以，磁盤(pán)被稱為塊設(shè)備!柱面扇區(qū)磁臂磁頭尋道時(shí)間：磁頭定位磁道所需時(shí)間（或者稱柱面定位時(shí)間：磁頭移動(dòng)到指定柱面的機(jī)械運(yùn)動(dòng)時(shí)間）；旋轉(zhuǎn)延遲時(shí)間：磁盤(pán)旋轉(zhuǎn)到指定扇區(qū)的機(jī)械運(yùn)動(dòng)時(shí)間；它與磁盤(pán)轉(zhuǎn)速相關(guān)，如：軟盤(pán)轉(zhuǎn)速可為600rpm(每分鐘轉(zhuǎn)速)，硬盤(pán)可為5400-10000r/m傳送時(shí)間：從指定扇區(qū)讀寫(xiě)數(shù)據(jù)的時(shí)間。排隊(duì)延遲時(shí)間：發(fā)出I/O請(qǐng)求的進(jìn)程須首先在隊(duì)列中等待該設(shè)備可用磁盤(pán)結(jié)構(gòu)-幾個(gè)名詞磁盤(pán)的I/O總線控制器IDE控制器讓我們仔細(xì)想想磁盤(pán)如何讀/寫(xiě)1一個(gè)字節(jié)?(1)(2)(3)分析磁盤(pán)I/O的重點(diǎn)在于第2步!磁道內(nèi)存緩存讀出了一個(gè)字節(jié)寫(xiě)(修改)一個(gè)字節(jié)磁盤(pán)I/O:緩存隊(duì)列控制器尋道旋轉(zhuǎn)傳輸!旋轉(zhuǎn)型存儲(chǔ)設(shè)備上信息的優(yōu)化分布能減少I(mǎi)/O服務(wù)的總時(shí)間。例如，有10個(gè)記錄A，B，C，…,J在某磁盤(pán)的磁道上，假定這個(gè)磁道劃分為10個(gè)扇區(qū)，每個(gè)扇區(qū)存放一個(gè)記錄（如圖）。現(xiàn)在要從磁道上順序?qū)⒂涗汚，B，C，…,J讀出，如果磁盤(pán)轉(zhuǎn)速為20ms轉(zhuǎn)1周，處理程序每讀出一個(gè)記錄后花4ms進(jìn)行處理。試問(wèn)處理完10個(gè)記錄的總時(shí)間是多少（從找到A記錄開(kāi)始計(jì)算）？如何優(yōu)化存儲(chǔ)？扇區(qū)記錄ABCDEFGHIJ12345678910答：已知磁盤(pán)轉(zhuǎn)速為20ms轉(zhuǎn)1周，故讀取一個(gè)記錄花2ms，處理一個(gè)記錄為4ms。在讀取和處理記錄A時(shí)，由于磁盤(pán)已轉(zhuǎn)到記錄D的位置，為了順序處理記錄B，必讓磁盤(pán)再轉(zhuǎn)過(guò)8個(gè)記錄才能到達(dá)記錄B的開(kāi)始位置。

定位記錄B花8x2ms=16ms,讀出記錄B花2ms，處理記錄B花4ms，總共22ms。這種情況對(duì)于B-J均出現(xiàn)，故讀取和處理B-J總時(shí)間=22msx9=198ms,再加上讀取和處理記錄A的時(shí)間6ms，總計(jì)為204ms。例題扇區(qū)記錄AHEBIFCJGD12345678910優(yōu)化后的存儲(chǔ)位置，只需要6msX10=60ms磁盤(pán)管理1.1磁盤(pán)的結(jié)構(gòu)1.2磁盤(pán)的調(diào)度磁盤(pán)I/O的分析可以整理磁盤(pán)I/O的過(guò)程：進(jìn)程請(qǐng)求隊(duì)列磁盤(pán)控制器磁盤(pán)我們最關(guān)心的磁盤(pán)什么時(shí)候讀/寫(xiě)完?磁盤(pán)訪問(wèn)延遲=隊(duì)列時(shí)間+控制器時(shí)間+

尋道時(shí)間+旋轉(zhuǎn)時(shí)間+傳輸時(shí)間扇區(qū)磁道Head12msto8ms(半周):8msto4ms50M/秒約0.25ms前兩項(xiàng)可以忽略!關(guān)鍵所在:最小化尋道時(shí)間和旋轉(zhuǎn)延遲!I/O過(guò)程是解開(kāi)許多磁盤(pán)問(wèn)題的鑰匙分析磁盤(pán)扇區(qū)尺寸：磁盤(pán)訪問(wèn)延遲=隊(duì)列時(shí)間+控制器時(shí)間+

尋道時(shí)間+旋轉(zhuǎn)時(shí)間+傳輸時(shí)間12msto8ms8msto4ms約0.25ms前兩項(xiàng)可以忽略!扇區(qū)尺寸為1byte：沒(méi)有碎片；傳輸速度100byte/秒(尋道時(shí)間10ms)扇區(qū)尺寸1KByte：碎片0.5K；傳輸100KByte/秒扇區(qū)尺寸1MByte：碎片0.5M；傳輸4Mbyte/秒扇區(qū)大小空間利用率傳輸速度I/O過(guò)程是解開(kāi)許多磁盤(pán)問(wèn)題的鑰匙磁盤(pán)調(diào)度：磁盤(pán)訪問(wèn)延遲=隊(duì)列時(shí)間+控制器時(shí)間+

尋道時(shí)間+旋轉(zhuǎn)時(shí)間+傳輸時(shí)間12msto8ms8msto4ms約0.25ms前兩項(xiàng)可以忽略!多個(gè)磁盤(pán)訪問(wèn)請(qǐng)求出現(xiàn)在請(qǐng)求隊(duì)列怎么辦?調(diào)度調(diào)度的目標(biāo)是什么?調(diào)度時(shí)主要考察什么?目標(biāo)當(dāng)然是平均訪問(wèn)延遲小!尋道時(shí)間是主要矛盾!磁盤(pán)調(diào)度:輸入多個(gè)磁道請(qǐng)求，給出服務(wù)順序!所以，磁盤(pán)調(diào)度策略當(dāng)多個(gè)訪盤(pán)請(qǐng)求在等待時(shí)，采用一定的策略，對(duì)這些請(qǐng)求的服務(wù)順序調(diào)整安排，旨在降低平均磁盤(pán)服務(wù)時(shí)間，達(dá)到公平、高效：公平：一個(gè)I/O請(qǐng)求在有限時(shí)間內(nèi)滿足高效：減少設(shè)備機(jī)械運(yùn)動(dòng)所帶來(lái)的時(shí)間浪費(fèi)磁盤(pán)調(diào)度考慮的問(wèn)題：一次訪盤(pán)時(shí)間=尋道時(shí)間+旋轉(zhuǎn)延遲時(shí)間+傳送時(shí)間(1)減少尋道時(shí)間（活動(dòng)頭磁盤(pán)）(2)減少延遲時(shí)間（固定頭磁盤(pán)）磁盤(pán)調(diào)度策略－減少尋道時(shí)間由于尋道(柱面定位時(shí)間）時(shí)間占主要部分，合理組織磁盤(pán)數(shù)據(jù)的存儲(chǔ)位置可提高磁盤(pán)I/O性能。磁盤(pán)系統(tǒng)通常以柱面為單位供用戶記錄文件信息（磁盤(pán)空間是以“柱面”劃分和使用的）若將信息連續(xù)地存儲(chǔ)在一個(gè)“柱面”上，則針對(duì)一次I/O請(qǐng)求只需移動(dòng)一次磁頭，定位相應(yīng)柱面，然后根據(jù)不同盤(pán)面上的讀/寫(xiě)磁頭進(jìn)行連續(xù)讀/寫(xiě)。OS可通過(guò)合理調(diào)度它們對(duì)磁盤(pán)的使用順序，達(dá)到減少磁盤(pán)平均服務(wù)時(shí)間的目的。磁盤(pán)調(diào)度策略例子：讀一個(gè)128KB大小的文件：(1)文件由8個(gè)連續(xù)磁道(每個(gè)磁道32個(gè)扇區(qū))上的256個(gè)扇區(qū)構(gòu)成：20ms+(7.3ms+16.7ms)*8=220ms;其中，柱面定位時(shí)間為20ms，旋轉(zhuǎn)延遲時(shí)間為7.3ms，32扇區(qū)數(shù)據(jù)傳送時(shí)間為16.7ms；(2)文件由256個(gè)隨機(jī)分布的扇區(qū)構(gòu)成：(20ms+7.3ms+0.5ms)*256=7373ms;其中，1扇區(qū)數(shù)據(jù)傳送時(shí)間為0.5ms；隨機(jī)分布時(shí)的訪問(wèn)時(shí)間為連續(xù)分布時(shí)的33.5倍。磁盤(pán)調(diào)度策略O(shè)S為每個(gè)I/O設(shè)備維護(hù)一條請(qǐng)求隊(duì)列。對(duì)于磁盤(pán)，隊(duì)列中可能有來(lái)自多個(gè)進(jìn)程的許多I/O請(qǐng)求（讀或?qū)懀?。調(diào)度方法如下：隨機(jī)調(diào)度RSS:性能差，可以用來(lái)評(píng)估其它技術(shù)先來(lái)先服務(wù)（FCFS）短查找時(shí)間優(yōu)先算法（SSTF）掃描(SCAN)算法循環(huán)掃描(C-SCAN)算法LOOK算法FCFS磁盤(pán)調(diào)度（先來(lái)先服務(wù)）最直觀、最公平的調(diào)度：一個(gè)實(shí)例:磁頭開(kāi)始位置=53；請(qǐng)求隊(duì)列=98,183,37,122,14,124,65,670143753656798122124183199磁頭在長(zhǎng)途奔襲!FCFS:磁頭共移動(dòng)640磁道!在移動(dòng)過(guò)程中把經(jīng)過(guò)的請(qǐng)求處理了!SSTF磁盤(pán)調(diào)度

（選擇距當(dāng)前磁頭位置最短尋道時(shí)間的請(qǐng)求）Shortest-seek-timeFirst：繼續(xù)該實(shí)例:磁頭開(kāi)始位置=53；請(qǐng)求隊(duì)列=98,183,37,122,14,124,65,670143753656798122124183199如果在處理183之前又來(lái)一些中間磁道的請(qǐng)求，則…SSTF:磁頭共移動(dòng)236(4+53+169)磁道，要少很多!SSTF存在饑餓問(wèn)題SCAN磁盤(pán)調(diào)度

（磁盤(pán)一端向另一端移動(dòng)，當(dāng)移動(dòng)過(guò)每個(gè)柱面時(shí)，處理位于該柱面上的服務(wù)請(qǐng)求）SSTF+中途不回折：每個(gè)請(qǐng)求都有處理機(jī)會(huì)繼續(xù)該實(shí)例:磁頭開(kāi)始位置=53；請(qǐng)求隊(duì)列=98,183,37,122,14,124,65,670143753656798122124183199這些請(qǐng)求的等待時(shí)間較長(zhǎng)，只因所在方向不夠幸運(yùn)!根據(jù)其特征，SCAN也被稱為電梯算法!SCAN:磁頭共移動(dòng)53+183=236磁道，和SSTF一樣!SCAN導(dǎo)致延遲不均C-SCAN磁盤(pán)調(diào)度

（SCAN+將柱面當(dāng)做一個(gè)環(huán)鏈）SCAN+直接移到另一端：兩端請(qǐng)求都能很快處理繼續(xù)該實(shí)例:磁頭開(kāi)始位置=53；請(qǐng)求隊(duì)列=98,183,37,122,14,124,65,670143753656798122124183199CSCAN中的C是環(huán)的意思!CSCAN:磁頭共移動(dòng)188+200磁道!其中200會(huì)較快!140(183199)沒(méi)有必要C-LOOK磁盤(pán)調(diào)度

SCAN（C-SCAN）+磁頭只移動(dòng)到一個(gè)方向上的最遠(yuǎn)的請(qǐng)求為止。接著馬上回頭，而不是繼續(xù)到磁盤(pán)的盡頭。繼續(xù)該實(shí)例:磁頭開(kāi)始位置=53；請(qǐng)求隊(duì)列=98,183,37,122,14,124,65,670143753656798122124183199LOOK和C-LOOK是比較合理的缺省算法操作系統(tǒng)中所有的算法都要因地制宜!I/O過(guò)程是解開(kāi)許多磁盤(pán)問(wèn)題的鑰匙磁盤(pán)尋址：對(duì)于內(nèi)存，我們往往更關(guān)心存放內(nèi)容的地址實(shí)際上就是扇區(qū)怎么編址?顯然這個(gè)地址是(盤(pán)面?,磁道?,扇區(qū)?)尋道和旋轉(zhuǎn)費(fèi)時(shí)多花最少時(shí)間訪問(wèn)最多扇區(qū)的方案:磁臂不動(dòng)、磁盤(pán)旋轉(zhuǎn)一周，訪問(wèn)磁頭遇到的所有扇區(qū)。磁臂讓這些扇區(qū)的編址鄰近:因?yàn)榫植啃?柱面!扇區(qū)編址(1):CHS(Cylinder/Head/Sector)扇區(qū)編址(2):扇區(qū)編號(hào)扇區(qū)編號(hào)—現(xiàn)代磁盤(pán)的常見(jiàn)尋址方式磁臂扇區(qū)編號(hào)，按照(C,H,S)將扇區(qū)形成一維扇區(qū)數(shù)組，數(shù)組索引就是扇區(qū)編號(hào)柱面1柱面2柱面n…整個(gè)磁盤(pán)磁道1磁道2磁道k…一個(gè)柱面扇區(qū)1扇區(qū)2扇區(qū)p…一個(gè)磁道0kp(k+1)p(k+2)p…體現(xiàn)了局部性!將整個(gè)過(guò)程貫穿在一起第1步：得到要訪問(wèn)的扇區(qū)的編號(hào)；得到讀的源(或?qū)懙哪繕?biāo))內(nèi)存地址算法輸入!第