磁盘移臂调度算法PPT学习课件

5.4.1磁盘移臂调度,磁盘是对被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，以使各进程对磁盘的平均访问（主要是寻道）时间最小。由于在访问磁盘的时间中、主要是寻道时间，因此，磁盘调度的目标应是使磁盘的平均寻道时间最少。常用的磁盘调度算法有：先来先服务；最短寻道时间优先；扫描算法；循环扫描算法等,1,一、先来先服务FCFS(First-Come,First-Served)这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。,在任何时候，都有许多I/O请求在排队等待。每次当调用进程从磁盘读出时，首先要把磁头定位到它所要求的正确磁道上。移动磁头所需时间取决于磁头必须移动多远的距离。下页表是一作用于等待的I/O进程请求其要求读出的磁道的分布情况。,2,其中进程是按其发出请求的先后顺序排列的。采用的是FCFS调度策略。完成这组I/O操作需移动磁头的总距离为1604磁道。优点：公平、简单，且每个进程的请求都能依次得到处理，不会出现某进程的请求长期得不到满足的情况。缺点：与后面讲的几种,调度算法相比，其平均寻道距离较大。故此算法仅适用于请求磁盘上的进程数较少的场合。,3,例：假定磁盘共有40个柱面，当前磁头正在第11道服务，等待服务的进程有6个，它们请求的柱面分别是：1,36,16,34,9和12(以请求时间先后为序)。,按FCFS算法：,移动为：111361634912,总移动柱面数：10+35+20+18+25+3=111,4,思考：假设磁盘访问序列：98,183,37,122,14,124,65,67读写头起始位置：53试安排磁头服务序列，并计算磁头移动总距离(道数),5,二、最短寻道时间优先SSTF(ShortsetSeekTimeFirst)第一种改进方法是：最短寻找时间优先(SSTF)的调度方法。采用这种调度策略，每当启动一个新的磁盘I/O操作时，首先查看这个等待请求的挂起队列，找出其中寻找时间最短的进程。按此策略完成这组I/O操作需移动磁头的总距离为700磁道。(如右图所示),6,该策略隐含有一个难以捉摸的问题：这就是有些进程将会“饿死”。如假定在进程9(要求读出磁道376上的信息)的请求得到服务之前的某段时间，系统又收到一个请求流，而且这些请求所要求移动的磁道数均小于376所移动的距离，因而进程9和进程3永远得不到服务。优点：改善了磁盘平均服务时间；缺点：造成某些访问请求长期等待得不到服务,7,例：假定磁盘共有40个柱面，当前磁头正在第11道服务，等待服务的进程有6个，它们请求的柱面分别是：1,36,16,34,9和12。,按SSTF算法：,移动为：111291613436,总移动柱面数：1+3+7+15+33+2=61由此可知总的柱面移动数为61，明显地优于FCFS。,8,思考：假设磁盘访问序列：98,183,37,122,14,124,65,67读写头起始位置：53试安排磁头服务序列，并计算磁头移动总距离(道数),9,三、扫描(SCAN)算法（电梯调度算法）具体做法：当设备无访问请求时，磁头不动；当有访问请求时，磁头按一个方向移动，在移动过程中对遇到的访问请求进行服务，然后判断该方向上是否还有访问请求，如果有则继续扫描；否则改变移动方向，并为经过的访问请求服务，如此反复.,10,按按此策略完成这组I/O操作需移动磁头的总距离为490磁道。(如右下图所示),该方法克服了最短寻道优先的缺点，既考虑了距离，同时又考虑了方向。但是，必须说明，这种修改的SCAN调度策略并不总是优于纯SSTF调度算法。由于这种算法中磁头移动的规律颇似电梯的运行，故又常称为电梯调度算法,11,例：假定磁盘共有40个柱面，当前磁头正在第11道服务，等待服务的进程有6个，它们请求的柱面分别是：1,36,16,34,9和12。,按SCAN算法：,移动为：111216343691,总移动柱面数：1+4+18+2+27+8=60尽管此例的平均寻道时间电梯算法优于SSF算法，但一般而言SSTF算法下平均寻道时间要优于电梯算法。从效率和公平性考虑，目前较多采用电梯调度算法。,12,思考：假设磁盘访问序列：98,183,37,122,14,124,65,67读写头起始位置：53试安排磁头服务序列，并计算磁头移动总距离(道数),13,四、循环扫描算法CSAN(CircularSCAN)（不考）SCAN算法存在这样的问题：当磁头刚从里向外移动过某一磁道时、恰有进程请求访问此磁道，这时该进程必须等待，待磁头从里向外然后再从外向里扫描完所有要访问的磁道后、才处理该进程的请求，致使该进程的请求被严重地推迟。为了减少这种延迟，SSTF的另一个修改版本是循环扫描法(CSAN)。该算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。即一个在磁道0上的I/O请求，将在磁道400上请求之后马上可以得到满足。,14,按按此策略完成这组I/O操作需移动磁头的总距离为642磁道。,CSCAN的优缺点的讨论作为一个习题留给读者,15,五、N-Step-SCAN和FSCAN调度算法（不考）1N-Step-SCAN算法在SSTF、SCAN及CSCAN几种调度算法中，都可能出现磁臂停留在某处不动的情况。例如，有一个或几个进程对某一磁道有着较高的访问频率，即他们反复请求对某一磁道进行I/O，从而垄断了整个磁盘设备。我们把这一现象称为磁臂粘着(Armstickiness)。在高密度盘上更容易出现此情况。N-Step-SCAN是将磁盘请求队列分成若干个长度为N的子队列，对一个队列处理完后又处理另一个队列，这样可避免出现粘着现象。当N很大时，会使N-Step-SCAN的性能，接近于SCAN算法的性能；当N=1时，N-Step-SCAN算法退化为FCFS算法。,16,2FSCAN算法FSCAN算法实质上是N-Step-SCAN算法的简化。它只将磁盘请求访问队列分成两个子队列。一是当前所有请求磁盘I/O的进程形成的队列，由磁盘调度按SCAN算法进行处理。另一个队列则是在扫描期间，新出现的所有请求磁盘I/O进程的队列，把它们排入另一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一次扫描时处理。,17,例1：假定某移动磁盘上，处理了访问56号柱面的请求后，现在正在70号柱面上读信息，目前有下面的请求访问磁盘柱面的序列：73,68,100,120,60,108,8,50请写出下列各小题的响应的次序及移动的柱面数。用最短查找时间优先算法电梯调度算法,解：用SSTF，响应的次序为70、68、73、60、50、8、100、108、120移动的柱面数：2+5+13+10+42+92+8+12=184用电梯调度算法，响应的次序为70、73、100、108、120、68、60、50、8移动的柱面数：3+27+8+12+52+8+10+42=162,18,例2：若干个等待访问磁盘者依次要访问的柱面为20,44,40,4,80,12,76。假设每移动一个柱面需要3毫秒时间，移动臂当前位于40号柱面，请按下列算法分别计算为完成上述各次访问总共花费的寻找时间。(1)先来先服务算法：(2)最短寻找时间优先算法。(3)电梯调度算法（分情况）,解：（1）先来先服务算法：402044404801276（20）（24）（4）（36）（76）（68）（64）共移动292柱面(20+24+4+36+76+68+64)*3=292*3=876ms（2）最短寻找时间算法：404044201247680（0）（4）（24）（8）（8）（72）（4）共移动120柱面(0+4+24+8+8+72+4)*3=120*3=360ms,19,（3）电梯调度算法：由于未指明开始移动的方向，分成