最短寻道时间优先算法(SSTF)

it2026-03-12  2

SSTF问题描述:

SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。当然,总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。

优点

改善了磁盘平均服务时间。

缺点

优先级低的进程会发生“饥饿”现象。因为新进程请求到达,且其所要访问的磁道与磁头当前所在的磁道距离较近,必先优先满足。

思想:

本算法是对输入的磁道首先进行非递减排序,然后判断当前磁头所在的磁道是否在将要寻找的磁道中,分别进行最短寻道时间计算。(如下图示,表示SSTF示意图)

不是最优的例子:

若干个等待访问磁盘者依次要访问的磁道为 100,142,150,155,170,300,当前磁头位于 150 号柱面,若用最短寻道时间优先磁盘调度算法,则访问序列为 [ 150 , 155 , 142 , 170 , 100 , 300 ] [150,155,142,170,100,300] [150,155,142,170,100,300]


根据最短寻道时间优先磁盘调度算法,每次在寻找下一个磁道时,都要选择离自己最近的,所以当前磁头位于40号,下一道选择与40绝对值最小的,即40,再下一道选择43,差值为3,以此类推,最后的访问序列应该为, [ 150 , 155 , 142 , 170 , 100 , 300 ] [150,155,142,170,100,300] [150,155,142,170,100,300]

SSTF

[ 150 , 155 , 142 , 170 , 100 , 300 ] [150,155,142,170,100,300] [150,155,142,170,100,300] 磁 头 移 动 总 距 离 = ∣ 150 − 150 ∣ + ∣ 155 − 150 ∣ + ∣ 142 − 150 ∣ + ∣ 170 − 142 ∣ + ∣ 100 − 170 ∣ + ∣ 300 − 100 ∣ = 311 ( 磁 道 ) 磁头移动总距离=|150-150|+|155-150|+|142-150|+|170-142|+|100-170|+|300-100|=311(磁道) =150150+155150+142150+170142+100170+300100=311

更优的抉择

[ 150 , 142 , 100 , 155 , 170 , 300 ] [150,142,100,155,170,300] [150,142,100,155,170,300] 磁 头 移 动 总 距 离 = ∣ 40 − 40 ∣ + ∣ 43 − 40 ∣ + ∣ 76 − 43 ∣ + ∣ 79 − 76 ∣ + ∣ 19 − 79 ∣ + ∣ 11 − 19 ∣ + ∣ 4 − 11 ∣ = 250 ( 磁 道 ) 磁头移动总距离=|40-40|+|43-40|+|76-43|+|79-76|+|19-79| +|11-19|+|4-11|=250(磁道) =4040+4340+7643+7976+1979+1119+411=250

SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。当然,总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。

简单想:

可以想象这样一个序列,磁头目前在最中间。

第一次寻道,离磁头最近磁道的在中点的左边,磁头移动到该位置。第二次寻道,离磁头最近磁道的在中点的右边,磁头移动到该位置。第三次寻道,离磁头最近磁道的在中点的左边,磁头移动到该位置。…

如此,磁头一直在中点往复,显然不如寻完一侧的磁道再寻另一侧更优。

最新回复(0)