計(jì)算機(jī)操作系統(tǒng)（第二版）課件：磁盤調(diào)度

教學(xué)內(nèi)容：磁盤管理概述

磁盤調(diào)度算法

磁盤調(diào)度思考問(wèn)題：

從磁盤上讀一塊數(shù)據(jù)，大約需要多長(zhǎng)時(shí)間？所需時(shí)間主要包括哪幾部分？

當(dāng)同一時(shí)刻有多個(gè)磁盤訪問(wèn)請(qǐng)求時(shí)，如何安排訪問(wèn)順序,以得到相對(duì)較短的平均訪問(wèn)時(shí)間？有哪些方法可以縮短磁盤讀寫時(shí)間？6.6.1磁盤管理概述：盤面、磁道、扇區(qū)的概念盤面號(hào)（磁頭號(hào)）、柱面號(hào)（磁道號(hào)）、扇區(qū)號(hào)扇區(qū)兩種編址方式：CHS方式、LBA方式LBA與CHS之間的互相轉(zhuǎn)換磁盤訪問(wèn)時(shí)間：尋道時(shí)間、旋轉(zhuǎn)延遲時(shí)間、數(shù)據(jù)傳輸時(shí)間的含義、各與哪些因素有關(guān)？6.6磁盤調(diào)度

6.6.1磁盤管理概述1.數(shù)據(jù)組織和格式盤面號(hào)（磁頭號(hào)）：0～

M-1；柱面號(hào)（磁道號(hào)）：0～

L-1；扇區(qū)號(hào)：1～

N；

6.6磁盤調(diào)度扇區(qū)標(biāo)識(shí)符字段數(shù)據(jù)字段校驗(yàn)字段

6.6.1磁盤管理概述1.數(shù)據(jù)組織和格式

（1）扇區(qū)編址方式CHS（Cylinder/Head/Sector，柱面/磁頭/扇區(qū)）方式：

使用柱面號(hào)、磁頭號(hào)和扇區(qū)號(hào)表示每個(gè)扇區(qū)，DOS中稱

為“絕對(duì)扇區(qū)”表示法。

LBA（LogicalBlockAddressing，相對(duì)扇區(qū)號(hào)）方式：

相對(duì)扇區(qū)號(hào)標(biāo)識(shí)扇區(qū)，以磁盤第一個(gè)扇區(qū)（0柱面、0磁頭、

1扇區(qū)）作為L(zhǎng)BA的0扇區(qū)。6.6磁盤調(diào)度

1.數(shù)據(jù)組織和格式（2）LBA與CHS的轉(zhuǎn)換若L、M、N分別表示一個(gè)磁盤的柱面數(shù)（磁道數(shù)）、盤面數(shù)（磁頭數(shù)）、扇區(qū)數(shù)，則第i柱面、j磁頭、k扇區(qū)所對(duì)應(yīng)的LBA扇區(qū)號(hào)為：若知道LBA扇區(qū)號(hào)，則對(duì)應(yīng)的柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)分別是：6.6磁盤調(diào)度LBA=(i*M*N)+(j*N)+k-1

柱面號(hào)：i=int(LBA

/(M*N))

磁頭號(hào)：j=[LBAmod(M*N)]/N

扇區(qū)號(hào)：k=[LBAmod(M*N)]modN+1（3）存儲(chǔ)容量

=磁頭數(shù)×磁道（柱面）數(shù)×每道扇區(qū)數(shù)×每扇區(qū)字節(jié)數(shù)6.6.1磁盤管理概述

（4）LBA與CHS的轉(zhuǎn)換舉例6.6磁盤調(diào)度

假設(shè)一個(gè)磁盤共有100個(gè)柱面，每個(gè)柱面有8個(gè)磁道，每條磁道被分成4個(gè)扇區(qū)。若磁盤塊大小與扇區(qū)大小相等，柱面、磁道、扇區(qū)的編號(hào)均從“0”開始，現(xiàn)用字長(zhǎng)為16位的200個(gè)字（第0字到第199字）組成位示圖來(lái)管理磁盤空間。請(qǐng)問(wèn)：（1）文件系統(tǒng)發(fā)現(xiàn)位示圖中第15字第7位為0而準(zhǔn)備分配給某文件時(shí)，該文件會(huì)存放到磁盤的哪一塊上？此塊的物理位置（柱面號(hào)、磁頭號(hào)、扇區(qū)號(hào)）如何？（2）刪除某文件時(shí)，回收第56柱面第6盤面第3扇區(qū)的塊，此時(shí)，位示圖中第幾字第幾位應(yīng)該由“1”改為“0”？答案：（1）柱面號(hào)7，磁頭號(hào)5，扇區(qū)號(hào)3

（2）字號(hào)113，位號(hào)11

（4）LBA與CHS的轉(zhuǎn)換討論題解答：6.6磁盤調(diào)度

（1）塊號(hào)=15*字長(zhǎng)+7=15*16+7=247柱面號(hào)=INT(塊號(hào)/每個(gè)柱面的扇區(qū)數(shù)=INT(247/(4*8))=7磁頭號(hào)=INT((塊號(hào)MOD每個(gè)柱面的扇區(qū)數(shù))/每條磁道扇區(qū)數(shù)）=INT((247MOD32)/4)=5扇區(qū)號(hào)=(塊號(hào)MOD每個(gè)柱面扇區(qū)數(shù))MOD每條磁道扇區(qū)數(shù)=（247MOD32）MOD4=3（2）塊號(hào)=柱面號(hào)*每個(gè)柱面的扇區(qū)數(shù)+盤面號(hào)*每條磁道扇區(qū)數(shù)+扇區(qū)號(hào)=56*32+6*4+3=1819

字號(hào)=INT(塊號(hào)/字長(zhǎng)）=INT(1819/16)=113

位號(hào)=塊號(hào)MOD字長(zhǎng)=1819MOD16=11

6.6.1磁盤管理概述2.磁盤訪問(wèn)時(shí)間：移動(dòng)頭磁盤（1）尋道時(shí)間

磁頭從當(dāng)前位置移動(dòng)到指定磁道所需要的時(shí)間Ts=m*n+ss：?jiǎn)?dòng)磁臂的時(shí)間，2ms～3msm：磁頭每移動(dòng)一條磁道所需要的時(shí)間一般磁盤：0.2～0.3；高速磁盤：m≤0.1n：移動(dòng)的磁道數(shù)。6.6磁盤調(diào)度

6.6.1磁盤管理概述2.磁盤訪問(wèn)時(shí)間：移動(dòng)頭磁盤（2）旋轉(zhuǎn)延遲時(shí)間Tr

欲訪問(wèn)扇區(qū)旋轉(zhuǎn)到磁頭下面所需要的時(shí)間，粗略的認(rèn)為是磁盤旋轉(zhuǎn)半周的時(shí)間：

Tr

=1/2r

這里r表示旋轉(zhuǎn)速度（3）傳輸時(shí)間Tt：

把數(shù)據(jù)從磁盤讀出或向磁盤寫入所需要的時(shí)間6.6磁盤調(diào)度rNbTt=可將磁盤訪問(wèn)時(shí)間Ta表示為：

rNbrTTsa++=21

6.6.2磁盤調(diào)度算法

當(dāng)有大量磁盤I/O請(qǐng)求時(shí)，降低磁盤I/O服務(wù)的總時(shí)間

移臂調(diào)度：當(dāng)同時(shí)有多條磁道訪問(wèn)請(qǐng)求時(shí)，確定磁道訪問(wèn)順序，以減少平均尋道時(shí)間

旋轉(zhuǎn)調(diào)度：當(dāng)一條磁道上有多個(gè)扇區(qū)訪問(wèn)請(qǐng)求時(shí)，確定扇區(qū)訪問(wèn)順序，以減少旋轉(zhuǎn)延遲時(shí)間6.6磁盤調(diào)度移臂調(diào)度算法（1）先來(lái)先服務(wù)算法（FCFS）（2）最短尋道時(shí)間優(yōu)先算法（SSTF）（3）掃描算法（SCAN算法，又稱為電梯算法）（4）循環(huán)掃描算法（CSCAN）（5）N-Step-SCAN算法（6）FSCAN算法（FairSCAN）6.6磁盤調(diào)度6.6.2磁盤調(diào)度算法基本概念實(shí)現(xiàn)思路性能分析如何改進(jìn)（1）先來(lái)先服務(wù)FCFS(First-Come,FirstServed)

假設(shè)當(dāng)前磁道在100號(hào)磁道，磁頭正向磁道號(hào)增加的方向（由外向里）移動(dòng)。現(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：23，376，205，132，61，190，29，4，40則磁盤調(diào)度順序和尋道距離為：23，376，205，132，61，190，29，4，40Ts=(100-23)+(376-23)+(376-205)+(205-132)+(132-61)+(190-61)+(190-29)+(29-4)+(40-4)平均尋道距離=Ts/96.6.2磁盤調(diào)度算法6.6磁盤調(diào)度假設(shè)當(dāng)前磁道在100號(hào)磁道，磁頭正向磁道號(hào)增加的方向（由外向里）移動(dòng)?，F(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：23，376，205，132，61，190，29，4，40,則磁盤調(diào)度順序和尋道距離為：23，376，205，132，61，190，29，4，40Ts=(132-100)+(190-132)+(205-190)+(205-61)+(61-40)+(40-29)+(29-23)+(23-4)+(376-4)問(wèn)題：（1）不能保證平均尋道距離最短；（2）會(huì)產(chǎn)生饑餓現(xiàn)象；（3）影響磁盤的機(jī)械壽命。（2）最短尋道時(shí)間優(yōu)先算法SSTF6.6.2磁盤調(diào)度算法6.6磁盤調(diào)度（3）掃描(SCAN)算法：（又稱為電梯算法）（1）磁頭當(dāng)前的移動(dòng)方向；（2）欲訪問(wèn)磁道與當(dāng)前磁道的距離。假設(shè)當(dāng)前磁道在100號(hào)磁道，磁頭正向磁道號(hào)增加的方向（由外向里）移動(dòng)。現(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：23，376，205，132，61，190，29，4，40,則磁盤調(diào)度順序和尋道距離為：23，376，205，132，61，190，29，4，40Ts=(132-100)+(190-132)+(205-190)+(376-205)+(376-61)+(61-40)+(40-29)+(29-23)+(23-4)6.6.2磁盤調(diào)度算法6.6磁盤調(diào)度（4）循環(huán)掃描(CSCAN)算法：（1）磁頭單向移動(dòng)方向訪問(wèn)磁道；如從外往里（2）欲訪問(wèn)磁道與當(dāng)前磁道的距離。假設(shè)當(dāng)前磁道在100號(hào)磁道，磁頭正向磁道號(hào)增加的方向（由外向里）移動(dòng)?，F(xiàn)依次有如下磁盤請(qǐng)求隊(duì)列：23，376，205，132，61，190，29，4，406.6.2磁盤調(diào)度算法6.6磁盤調(diào)度132,190,205,376，4,23,29,40,61（5）N-Step-SCAN算法

“磁臂粘著”現(xiàn)象算法思想：將磁盤請(qǐng)求隊(duì)列分成若干個(gè)長(zhǎng)度為N的子隊(duì)列；按FCFS算法依次處理子隊(duì)列；每個(gè)子隊(duì)列采用SCAN算法。例如：23，376，205，132，61，190，29，4，40若子隊(duì)列長(zhǎng)度N=4，則分成3個(gè)隊(duì)列：23,376,205,13261,190,29,404FCFSSCAN6.6.2磁盤調(diào)度算法6.6磁盤調(diào)度隊(duì)列數(shù)量不固定；每個(gè)隊(duì)列長(zhǎng)度固定（6）FSCAN算法將磁盤請(qǐng)求隊(duì)列分成兩個(gè)子隊(duì)列：

①隊(duì)列1：由當(dāng)前所有磁盤請(qǐng)求形成的隊(duì)列，采用SCAN算法處理

②隊(duì)列2：處理隊(duì)列1期間，新出現(xiàn)的磁盤請(qǐng)求

23,376,205,132，61,190,29，40,4

6.6.2磁盤調(diào)度算法6.6磁盤調(diào)度隊(duì)列數(shù)量固定：兩個(gè)每個(gè)隊(duì)列長(zhǎng)度不固定13當(dāng)同一磁道（柱面）上有多個(gè)扇區(qū)請(qǐng)求時(shí)，總是選取與當(dāng)前讀寫頭最近的I/O請(qǐng)求，使旋轉(zhuǎn)圈數(shù)最少。例：對(duì)磁盤訪問(wèn)的5個(gè)請(qǐng)求，若磁頭在1號(hào)柱面，先按SCAN算法做移臂調(diào)度，再進(jìn)行旋轉(zhuǎn)調(diào)度，則調(diào)度順序如下：柱面號(hào)盤面號(hào)扇區(qū)號(hào)

27753852153540636.6.3旋轉(zhuǎn)調(diào)度算法：減少旋轉(zhuǎn)延遲時(shí)間柱面號(hào)盤面號(hào)扇區(qū)號(hào)

5215385354063277柱面號(hào)盤面號(hào)扇區(qū)號(hào)

27752153853540636.6磁盤調(diào)度移臂調(diào)度旋轉(zhuǎn)調(diào)度13思考題：假定磁盤的存取臂現(xiàn)在處于6#柱面上，有如表所示的6個(gè)請(qǐng)求等待訪問(wèn)磁盤，試列出最省時(shí)間的響應(yīng)順序。6.6.3旋轉(zhuǎn)調(diào)度算法：6.6磁盤調(diào)度序號(hào)柱面號(hào)磁頭號(hào)塊號(hào)17632