磁盤管理概述

磁盤調度算法6.6磁盤調度

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

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

L-1；扇區號：1～

N；

6.6磁盤調度

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

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

“絕對扇區”表示法。

LBA（LogicalBlockAddressing，相對扇區號）方式：

相對扇區號標識扇區，以磁盤第一個扇區（0柱面、0磁頭、

1扇區）作為LBA的0扇區。6.6磁盤調度

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

柱面號：i=int(LBA

/(M*N))

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

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

=磁頭數×磁道（柱面）數×每道扇區數×每扇區字節數

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

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

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

6.6磁盤調度

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

欲訪問扇區旋轉到磁頭下面所需要的時間，粗略的認為是磁盤旋轉半周的時間

這里r表示旋轉速度（3）傳輸時間Tt

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

rNbrTTsa++=212r1Tr=

6.6.2磁盤調度算法

磁盤是多個進程可以共享的設備。當有大量磁盤I/O請求時，

應該恰當選擇調度順序，以降低完成這些磁盤I/O服務的總時間。

移臂調度：當同時有多條磁道訪問請求時，確定磁道訪問順序，以減少平均尋道時間

旋轉調度：當一條磁道上有多個扇區訪問請求時，確定扇區訪問順序，以減少旋轉延遲時間6.6磁盤調度

6.6.2磁盤調度算法

移臂調度算法（1）先來先服務（FCFS，FirstComeFirstServed）算法

它按照進程請求訪問磁盤的先后次序進行調度。（2）最短尋道時間優先（SSTF，ShortestSeekTimeFirst）算法

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

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

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

6.6磁盤調度

6.6.2磁盤調度算法

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

6.6.2磁盤調度算法

移臂調度算法舉例假設當前磁道在100號磁道，磁頭正向磁道號增加的方向（由外向里）移動。現依次有如下磁盤請求隊列：23，376，205，132，61，190，29，4，40，求幾種移臂調度算法的磁盤調度順序和尋道距離。（1）FCFS磁盤調度順序：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磁盤調度順序：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磁盤調度

6.6.2磁盤調度算法

移臂調度算法舉例（3）SCAN磁盤調度順序：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磁盤調度順序：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磁盤調度

6.6.2磁盤調度算法

移臂調度算法舉例（5）N-Step_SCAN若子隊列長度N=4，則磁盤請求分成3個隊列：23，376，205，132；61，190，29，40；4三個隊列按FCFS處理；每個隊列內部按SCAN算法處理：磁盤調度順序：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這里沒有新到達的磁盤請求，因此磁盤調度順序和平均尋道距離與SCAN算法一致。6.6磁盤調度

6.6.2磁盤調度算法

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

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

2775215355384063柱面號盤面號塊號

52153853540632