磁盘移臂调度算法.ppt

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