磁盤管理概述

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

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

M-1；柱面號（磁道號）：0～

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

N；

6.6磁盤調(diào)度

6.6.1磁盤管理概述1.數(shù)據(jù)組織和格式（1）扇區(qū)編址方式CHS（Cylinder/Head/Sector，柱面/磁頭/扇區(qū)）方式：

使用柱面號、磁頭號和扇區(qū)號表示每個扇區(qū)，DOS中稱為

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

LBA（LogicalBlockAddressing，相對扇區(qū)號）方式：

相對扇區(qū)號標(biāo)識扇區(qū)，以磁盤第一個扇區(qū)（0柱面、0磁頭、

1扇區(qū)）作為LBA的0扇區(qū)。6.6磁盤調(diào)度

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

柱面號：i=int(LBA

/(M*N))

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

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

=磁頭數(shù)×磁道（柱面）數(shù)×每道扇區(qū)數(shù)×每扇區(qū)字節(jié)數(shù)

6.6.1磁盤管理概述2.磁盤訪問時間：移動頭磁盤（1）尋道時間

磁頭從當(dāng)前位置移動到指定磁道所需要的時間Ts=m*n+s

其中s是啟動磁臂的時間；m是磁頭每移動一條磁道所需要的時間；n是移動的磁道數(shù)。m：一般磁盤：0.2～0.3；高速磁盤：m≤0.1S：磁臂啟動時間，約為2ms～3ms

6.6磁盤調(diào)度

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

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

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

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

rNbrTTsa++=212r1Tr=

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

磁盤是多個進(jìn)程可以共享的設(shè)備。當(dāng)有大量磁盤I/O請求時，

應(yīng)該恰當(dāng)選擇調(diào)度順序，以降低完成這些磁盤I/O服務(wù)的總時間。

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

旋轉(zhuǎn)調(diào)度：當(dāng)一條磁道上有多個扇區(qū)訪問請求時，確定扇區(qū)訪問順序，以減少旋轉(zhuǎn)延遲時間6.6磁盤調(diào)度

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

移臂調(diào)度算法（1）先來先服務(wù)（FCFS，F(xiàn)irstComeFirstServed）算法

它按照進(jìn)程請求訪問磁盤的先后次序進(jìn)行調(diào)度。（2）最短尋道時間優(yōu)先（SSTF，ShortestSeekTimeFirst）算法

總是選擇與當(dāng)前磁道距離最短的磁道訪問請求。（3）掃描（SCAN）算法（又稱為電梯算法）

總是從磁頭當(dāng)前移動方向上，選擇與當(dāng)前磁道距離最近的磁道訪問請求，如果

沿磁頭的移動方向無訪問請求時，就改變磁頭的反方向再選擇。（4）循環(huán)掃描（CSAN，CircularSCAN）算法CSCAN算法是對SCAN算法的改進(jìn)，它規(guī)定磁頭單向移動。

6.6磁盤調(diào)度

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

移臂調(diào)度算法（5）N-Step-SCAN算法將當(dāng)前的磁盤請求隊列分成若干個長度為N的子隊列，磁盤調(diào)度將按FCFS算法依次處理這些子隊列；而在處理每個子隊列時又采用SCAN算法。（6）FSCAN（FairSCAN）算法實質(zhì)上是N-Step-SCAN算法的簡化，它只將磁盤請求隊列分成兩個子隊列。當(dāng)前所有磁盤訪問請求組織在一個隊列中，由磁盤調(diào)度按SCAN算法進(jìn)行處理；在掃描處理過程中，對新出現(xiàn)的所有磁盤I/O請求，放入另一個等待處理的請求隊列，等上一個隊列處理完成后，再來處理這個隊列中的I/O請求。6.6磁盤調(diào)度

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

移臂調(diào)度算法舉例假設(shè)當(dāng)前磁道在100號磁道，磁頭正向磁道號增加的方向（由外向里）移動。現(xiàn)依次有如下磁盤請求隊列：23，376，205，132，61，190，29，4，40，求幾種移臂調(diào)度算法的磁盤調(diào)度順序和尋道距離。（1）FCFS磁盤調(diào)度順序：23，376，205，132，61，190，29，4，40尋道距離Ts：（100-23）+（376-23）+（376-205）+（205-132）+（132-61）+（190-61）+（190-29）+（29-4）+（40-4）=1096平均尋道距離：Ts/9=121.78（2）SSTF磁盤調(diào)度順序：132，190，205，61，40，29，23，4，376尋道距離Ts：（132-100）+（190-132）+（205-190）+（205-61）+（61-40）+（40-29）+（29-23）+（23-4）+（376-4）=678平均尋道距離：Ts/9=75.336.6磁盤調(diào)度

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

移臂調(diào)度算法舉例（3）SCAN磁盤調(diào)度順序：132，190，205，376，61，40，29，23，4尋道距離Ts：（132-100）+（190-132）+（205-190）+（376-205）+（376-61）+（61-40）+（40-29）+（29-23）+（23-4）=648平均尋道距離：Ts/9=72（4）CSCAN磁盤調(diào)度順序：132，190，205，376，4，23，29，40，61尋道距離Ts：（132-100）+（190-132）+（205-190）+（376-205）+（376-4）+（23-4）+（29-23）+（40-29）+（61-40）=705平均尋道距離：Ts/9=78.336.6磁盤調(diào)度

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

移臂調(diào)度算法舉例（5）N-Step_SCAN若子隊列長度N=4，則磁盤請求分成3個隊列：23，376，205，132；61，190，29，40；4三個隊列按FCFS處理；每個隊列內(nèi)部按SCAN算法處理：磁盤調(diào)度順序：132，205，376，23，29，40，61，190，4尋道距離Ts：（132-100）+（205-132）+（376-205）+（376-23）+（29-23）+（40-29）+（61-40）+（190-61）+（190-4）=982平均尋道距離：Ts/9=109.11（6）FSCAN這里沒有新到達(dá)的磁盤請求，因此磁盤調(diào)度順序和平均尋道距離與SCAN算法一致。6.6磁盤調(diào)度

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

當(dāng)同一磁道（柱面）上有多個扇區(qū)請求時，總是選取與當(dāng)前讀寫頭最近的那

個I/O請求，使旋轉(zhuǎn)圈數(shù)最少。旋轉(zhuǎn)調(diào)度算法舉例對磁盤訪問的5個請求如圖所示，若此時磁頭在1號柱面，且移臂調(diào)度算法采用SCAN算法，確定調(diào)度順序。6.6磁盤調(diào)度柱面號盤面號塊號

2775215355384063柱面號盤面號塊號

52153853540632