磁盘移臂调度算法

《磁盘移臂调度算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5.4.1磁盘移臂调度磁盘是对被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，以使各进程对磁盘的平均访问（主要是寻道）时间最小。由于在访问磁盘的时间中、主要是寻道时间，因此，磁盘调度的目标应是使磁盘的平均寻道时间最少。常用的磁盘调度算法有：⑴先来先服务；⑵最短寻道时间优先；⑶扫描算法；⑷循环扫描算法等．一、先来先服务FCFS(First-Come,First-Served)这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。在任何时候，都有许多I/O请求在排队等待。每次当调用进程从磁盘读出时，首

2、先要把磁头定位到它所要求的正确磁道上。移动磁头所需时间取决于磁头必须移动多远的距离。下页表是一作用于等待的I/O进程请求其要求读出的磁道的分布情况。当前磁道=100进程号磁道号移动距离(磁道数)419819376357232051717134713418116225638141921363396204322936717326121916294021磁头移动的总距离=1604(磁道)其中进程是按其发出请求的先后顺序排列的。采用的是FCFS调度策略。完成这组I/O操作需移动磁头的总距离为1604磁道。优点：公平、简单，且每个进程的请求都能依次得到处

3、理，不会出现某进程的请求长期得不到满足的情况。缺点：与后面讲的几种调度算法相比，其平均寻道距离较大。故此算法仅适用于请求磁盘上的进程数较少的场合。例：假定磁盘共有40个柱面，当前磁头正在第11道服务，等待服务的进程有6个，它们请求的柱面分别是：1,36,16,34,9和12(以请求时间先后为序)。按FCFS算法：移动为：111361634912总移动柱面数：10+35+20+18+25+3=111思考：假设磁盘访问序列：98,183,37,122,14,124,65,67读写头起始位置：53试安排磁头服务序列，并计算磁头移动总距离(

4、道数)二、最短寻道时间优先SSTF(ShortsetSeekTimeFirst)第一种改进方法是：最短寻找时间优先(SSTF)的调度方法。采用这种调度策略，每当启动一个新的磁盘I/O操作时，首先查看这个等待请求的挂起队列，找出其中寻找时间最短的进程。按此策略完成这组I/O操作需移动磁头的总距离为700磁道。(如右图所示)当前磁道=100进程号磁道号移动距离(磁道数)713434141925823205132256149294016322911419101219034181173159376373339620磁头移动的总距离=700(磁道)该策略

5、隐含有一个难以捉摸的问题：这就是有些进程将会“饿死”。如假定在进程9(要求读出磁道376上的信息)的请求得到服务之前的某段时间，系统又收到一个请求流，而且这些请求所要求移动的磁道数均小于376所移动的距离，因而进程9和进程3永远得不到服务。优点：改善了磁盘平均服务时间；缺点：造成某些访问请求长期等待得不到服务例：假定磁盘共有40个柱面，当前磁头正在第11道服务，等待服务的进程有6个，它们请求的柱面分别是：1,36,16,34,9和12。按SSTF算法：移动为：111291613436总移动柱面数：1+3+7+15+33+2=61由此

6、可知总的柱面移动数为61，明显地优于FCFS。思考：假设磁盘访问序列：98,183,37,122,14,124,65,67读写头起始位置：53试安排磁头服务序列，并计算磁头移动总距离(道数)三、扫描(SCAN)算法（电梯调度算法）具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复.按按此策略完成这组I/O操作需移动磁头的总距离为490磁道。。(如右下图所示)当前磁道=100移动方向

7、=OUT(向0道)进程号磁道号移动距离(磁道数)225644294016322911419101219034181173157134131(移动方向=IN)141925823205139376171339620磁头移动的总距离=490(磁道)该方法克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向。但是，必须说明，这种修改的SCAN调度策略并不总是优于纯SSTF调度算法。由于这种算法中磁头移动的规律颇似电梯的运行，故又常称为电梯调度算法例：假定磁盘共有40个柱面，当前磁头正在第11道服务，等待服务的进程有6个，它们请求的柱面分别是：1,3

8、6,16,34,9和12。按SCAN算法：移动为：111216343691总移动柱面数：1+4+18+2+27+8=60尽管此例的平均寻道