磁盘调度算法

2017年9月23日20:39:32磁盘调度算法已关闭评论 397

 

转自网页

一次磁盘读写操作的时间由寻找(寻道)时间、延迟时间和传输时间决定:

1) 寻找时间Ts:活动头磁盘在读写信息前,将磁头移动到指定磁道所需要的时间。这个时间除跨越n条磁道的时间外,还包括启动磁臂的时间s,即:Ts = m * n + s。式中,m是与磁盘驱动器速度有关的常数,约为0.2ms,磁臂的启动时间约为2ms。

2)延迟时间Tr:磁头定位到某一磁道的扇区(块号)所需要的时间,设磁盘的旋转速度为r,则:Tr = 1 / (2 * r)。对于硬盘,典型的旋转速度为5400r/m,相当于一周11.1ms,则Tr为5.55ms;对于软盘,其旋转速度在300~600r/m之间,则Tr为50~100ms。

3) 传输时间Tt:从磁盘读出或向磁盘写入数据所经历的时间,这个时间取决于每次所读/写的字节数b和磁盘的旋转速度:Tt = b / (r * N)。式中,r为磁盘每秒钟的转数;N为一个磁道上的字节数。

在磁盘存取时间的计算中,寻道时间与磁盘调度算法相关,下面将会介绍分析几种算法,而延迟时间和传输时间都与磁盘旋转速度相关,且为线性相关,所以在硬件上,转速是磁盘性能的一个非常重要的参数。
总平均存取时间Ta可以表示为:Ta = Ts + Tr + Tt。

(1)先来先服务(FCFS)
按请求者的先后次序启动磁盘驱动器,而不考虑它们要访问的物理位置。
FCFS算法根据进程请求访问磁盘的先后顺序进行调度,这是一种最简单的调度算法。该算法的优点是具有公平性。如果只有少量进程需要访问,且大部分请求都是访问簇聚的文件扇区,则有望达到较好的性能;但如果有大量进程竞争使用磁盘,那么这种算法在性能上往往接近于随机调度。所以,实际磁盘调度中考虑一些更为复杂的调度算法。
1、算法思想:按访问请求到达的先后次序服务。
2、优点:简单,公平。
3、缺点:效率不高,相邻两次请求可能会造成最内到最外的柱面寻道,使磁头反复移动,增加了服务时间,对机械也不利。
4、例子:
假设磁盘访问序列:98,183,37,122,14,124,65,67。读写头起始位置:53。求:磁头服务序列和磁头移动总距离(道数)。
由题意和先来先服务算法的思想,得到下图所示的磁头移动轨迹。由此:
磁头服务序列为:98,183,37,122,14,124,65,67
磁头移动总距离=(98-53)+(183-98)+|37-183|+(122-37)+|14-122|+(124-14)+|65-124|+(67-65)=640(磁道)
磁盘调度算法

(2)最短寻道时间优先(SSTF)
SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。当然,总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。
1、算法思想:优先选择距当前磁头最近的访问请求进行服务,主要考虑寻道优先。
2、优点:改善了磁盘平均服务时间。
3、缺点:造成某些访问请求长期等待得不到服务,即出现“饥饿”现象。
4、例子:对上例的磁盘访问序列,可得磁头移动的轨迹如下图。
磁头服务序列为:65,67,37,14,98,122,124,183
磁头移动总距离=12 + 2 + 30 +23 + 84 + 24 + 2 + 59 = 236 (磁道)
磁盘调度算法

(3)扫描算法(SCAN)或电梯调度算法
SCAN算法在磁头当前移动方向上选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象。由于磁头移动规律与电梯运行相似,故又称为电梯调度算法。SCAN算法对最近扫描过的区域不公平,因此,它在访问局部性方面不如FCFS算法和SSTF算法好。
算法思想:当设备无访问请求时,磁头不动;当有访问请求时,磁头按一个方向移动,在移动过程中对遇到的访问请求进行服务,然后判断该方向上是否还有访问请求,如果有则继续扫描;否则改变移动方向,并为经过的访问请求服务,如此反复。
扫描算法(电梯算法)的磁头移动轨迹
优点:克服了最短寻道优先的缺点,既考虑了距离,同时又考虑了方向
缺点:存在一个请求刚好被错过而需要等待较长时间的问题。
上例中,假设磁头朝0方向移动
磁头服务序列为:37,14,65,67,98,122,124,183
磁头移动总距离=16 + 23 + 51 + 2 + 31 + 24 + 2 + 59 = 208 (磁道)
磁盘调度算法

(4)循环扫描算法(CSCAN)
循环扫描调度算法是在扫描算法的基础上改进的,为了减少延迟,规定磁头单向移动,例如,只是自里向外移动,从当前位置开始沿磁头的移动方向去选择离当前磁头最近的那个柱面访问,如果沿磁头的方向无请求时,磁头立即返回到最里面的欲访问的柱面,再亦即将最小柱面号紧接着最大柱面号构成循环。
优点:兼顾较好的寻道性能和防止饥饿现象,同时减少一个请求可能等待的最长时间。
缺点:可能出现磁头停留在某处不动的情况(磁臂黏着)
上例中,假设磁头移动的方向是从柱面0到柱面199方向。
磁头服务序列为:65,67,98,122,124,183,14,37
磁头移动总距离=12 + 2 + 31 + 24 + 2 + 59 + 169 + 23= 298 (磁道)
磁盘调度算法