第五章_磁盘移臂调度算法.ppt

《第五章_磁盘移臂调度算法.ppt》由会员分享，可在线阅读，更多相关《第五章_磁盘移臂调度算法.ppt（20页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、5.4.1 磁盘移臂调度磁盘移臂调度 磁盘是对被多个进程共享的设备。当有多个进磁盘是对被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，程都请求访问磁盘时，应采用一种适当的调度算法，以使各进程对磁盘的平均访问（主要是寻道）时间以使各进程对磁盘的平均访问（主要是寻道）时间最小。由于在访问磁盘的时间中、主要是寻道时间，最小。由于在访问磁盘的时间中、主要是寻道时间，因此，磁盘调度的目标应是使磁盘的平均寻道时间因此，磁盘调度的目标应是使磁盘的平均寻道时间最少。最少。常用的磁盘调度算法有：常用的磁盘调度算法有：先来先服务；先来先服务；最短寻道时间优先；最短寻道时间优先；扫描算

2、法；扫描算法；循环扫描算法循环扫描算法等等一、先来先服务一、先来先服务FCFS(First-Come,First-Served)这是一种最简单的磁盘调度算法。它根这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。据进程请求访问磁盘的先后次序进行调度。在任何时候，都有许多在任何时候，都有许多I/O请求在排队等请求在排队等待。每次当调用进程从磁盘读出时，首先要待。每次当调用进程从磁盘读出时，首先要把磁头定位到它所要求的正确磁道上。移动把磁头定位到它所要求的正确磁道上。移动磁头所需时间取决于磁头必须移动多远的距磁头所需时间取决于磁头必须移动多远的距离。下页表是一作用于等待的离。

3、下页表是一作用于等待的I/O进程请求其进程请求其要求读出的磁道的分布情况。要求读出的磁道的分布情况。当前磁道=100进程号 磁道号 移动距离(磁道数)4 19 81 9 376 357 23 205 171 7 134 71 34 18 116 22 56 38 14 192 136 3 396 204 32 29 367 17 3 26 12 19 16 29 40 21磁头移动的总距离=1604(磁道)其中进程是按其发出其中进程是按其发出请求的先后顺序排列的。请求的先后顺序排列的。采用的是采用的是FCFS调度策略。调度策略。完成这组完成这组I/O操作需移动操作需移动磁头的总距离为磁头的总距

4、离为1604磁道。磁道。优点：优点：公平、简单，且公平、简单，且每个进程的请求都能依次每个进程的请求都能依次得到处理，不会出现某进得到处理，不会出现某进程的请求长期得不到满足程的请求长期得不到满足的情况。的情况。缺点：缺点：与后面讲的几种与后面讲的几种调度算法相比，其平均寻道距离较大。故此算法仅调度算法相比，其平均寻道距离较大。故此算法仅适用于请求磁盘上的进程数较少的场合。适用于请求磁盘上的进程数较少的场合。例例：假定磁盘共有40个柱面，当前磁头正在第11道服务，等待服务的进程有6个，它们请求的柱面分别是：1,36,16,34,9 和 12(以请求时间先后为序)。按按FCFS算法：算法：移动为

5、：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)的调度方法的调度方法。采用这种调。采用这种调度策略，每当启动一个新度策略，每当启动一个新的磁盘的磁盘

6、 I/O操作时，首先操作时，首先查看这个等待请求的挂起查看这个等待请求的挂起队列，找出其中寻找时间队列，找出其中寻找时间最短的进程。最短的进程。按此策略完成这组按此策略完成这组I/O操作需移动磁头的总距离操作需移动磁头的总距离为为700磁道。磁道。(如右图所示如右图所示)当前磁道=100进程号 磁道号 移动距离(磁道数)7 134 34 14 192 58 23 205 13 22 56 149 29 40 16 32 29 11 4 19 10 12 19 0 34 18 1 17 3 15 9 376 373 3 396 20磁头移动的总距离=700(磁道)该策略隐含有一个难以捉摸的问题：

7、这该策略隐含有一个难以捉摸的问题：这就是有些进程将会就是有些进程将会“饿死饿死”。如假定在进程。如假定在进程9(要求读出磁道要求读出磁道376上的信息上的信息)的请求得到服的请求得到服务之前的某段时间，系统又收到一个请求流，务之前的某段时间，系统又收到一个请求流，而且这而且这些请求些请求所要求移动的磁道数均小于所要求移动的磁道数均小于376所移动的距离，因而进程所移动的距离，因而进程9和进程和进程3永远永远得不到服务。得不到服务。优点：优点：改善了磁盘平均服务时间；改善了磁盘平均服务时间；缺缺点点：造造成成某某些些访访问问请请求求长长期期等等待待得得不不到服务到服务例例：假定磁盘共有40个柱面

8、，当前磁头正在第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)算法算法（电梯调度算法）（电梯调度算法）具具体体做做法法：当当设设备备无

9、无访访问问请请求求时时，磁磁头头不不动动；当当有有访访问问请请求求时时，磁磁头头按按一一个个方方向向移移动动，在在移移动动过过程程中中对对遇遇到到的的访访问问请请求求进进行行服服务务，然然后后判判断断该该方方向向上上是是否否还还有有访访问问请请求求，如如果果有有则则继继续续扫扫描描；否否则则改改变移动方向，并为经过的访问请求服务，如此反复变移动方向，并为经过的访问请求服务，如此反复.按按按按此此策策略略完完成成这这组组I/O操操作作需需移移动动磁磁头头的的总总距距离为离为490磁道磁道。(如右下图所示如右下图所示)当前磁道=100 移动方向=OUT(向0道)进程号 磁道号 移动距离(磁道数)2

10、2 56 44 29 40 16 32 29 11 4 19 10 12 19 0 34 18 1 17 3 15 7 134 131(移动方向=IN)14 192 58 23 205 13 9 376 171 3 396 20磁头移动的总距离=490(磁道)该方法克服了最短该方法克服了最短寻道优先的缺点，既考寻道优先的缺点，既考虑了距离，同时又考虑虑了距离，同时又考虑了方向。了方向。但是，必须说明，但是，必须说明，这种修改的这种修改的SCAN调度调度策略并不总是优于纯策略并不总是优于纯SSTF调度算法。调度算法。由于这种算法中磁由于这种算法中磁头移动的规律颇似电梯头移动的规律颇似电梯的运行，

11、故又常称为的运行，故又常称为电电梯调度算法梯调度算法例例：假定磁盘共有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试安排磁头服务序

12、列，并计算磁头移动总距离试安排磁头服务序列，并计算磁头移动总距离(道数道数)四、循环扫描算法四、循环扫描算法CSAN(Circular SCAN)（不考）（不考）SCAN算法存在这样的问题：当磁头刚从里向外算法存在这样的问题：当磁头刚从里向外移动过某一磁道时、恰有进程请求访问此磁道，这移动过某一磁道时、恰有进程请求访问此磁道，这时该进程必须等待，待磁头从里向外然后再从外时该进程必须等待，待磁头从里向外然后再从外向里扫描完所有要访问的磁道后、才处理该进程的向里扫描完所有要访问的磁道后、才处理该进程的请求，致使该进程的请求被严重地推迟。为了减少请求，致使该进程的请求被严重地推迟。为了减少这种延迟，

13、这种延迟，SSTF的另一个修改版本是循环扫描法的另一个修改版本是循环扫描法(CSAN)。该该算法规定磁头单向移动。例如，只自里算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。即一个在磁道着最大磁道号构成循环，进行扫描。即一个在磁道0上的上的I/O请求，将在磁道请求，将在磁道400上请求之后马上可以得上请求之后马上可以得到满足。到满足。当前磁道=100 移动方向=IN(向里)进程号 磁道号 移动距离(磁道

14、数)7 134 34 14 192 58 23 205 13 9 376 171 3 396 20 17 3 393 34 18 15 12 19 1 4 19 0 32 29 10 29 40 11 22 56 16磁头移动的总距离=642(磁道)按按此策略完成按按此策略完成这组这组I/O操作需移动操作需移动磁头的总距离为磁头的总距离为642磁道。磁道。CSCAN的优缺点的优缺点的讨论作为一个习题留的讨论作为一个习题留给读者给读者五、五、N-Step-SCAN和和FSCAN调度算法（不考）调度算法（不考）1 N-Step-SCAN算法算法 在在 SSTF、SCAN及及CSCAN几种调度算法中

15、，都几种调度算法中，都可能出现磁臂停留在某处不动的情况。可能出现磁臂停留在某处不动的情况。例如，有一个或几个进程对某一磁道有着较高例如，有一个或几个进程对某一磁道有着较高的访问频率，即他们反复请求对某一磁道进行的访问频率，即他们反复请求对某一磁道进行 I/O，从而垄断了整个磁盘设备。我们把这一现象称为从而垄断了整个磁盘设备。我们把这一现象称为磁磁臂粘着臂粘着(Armstickiness)。在高密度盘上更容易出现在高密度盘上更容易出现此情况。此情况。N-Step-SCAN是将磁盘请求队列分成若干是将磁盘请求队列分成若干个长度为个长度为N的子队列，对一个队列处理完后又处理另的子队列，对一个队列处理

16、完后又处理另一个队列，这样可避免出现粘着现象。一个队列，这样可避免出现粘着现象。当当N很大时，会使很大时，会使N-Step-SCAN的性能，接近于的性能，接近于 SCAN算法的性能；当算法的性能；当 N=1时，时，N-Step-SCAN算法算法退化为退化为FCFS算法。算法。2 FSCAN算法算法 FSCAN算法算法实质上是实质上是N-Step-SCAN算法算法的简化。它只将磁盘请求访问队列分成两个的简化。它只将磁盘请求访问队列分成两个子队列。子队列。一是当前所有请求磁盘一是当前所有请求磁盘I/O的进程形成的的进程形成的队列，由磁盘调度按队列，由磁盘调度按SCAN算法进行处理。算法进行处理。另

17、一个队列则是在扫描期间，新出现的另一个队列则是在扫描期间，新出现的所有请求磁盘所有请求磁盘I/O进程的队列，把它们排入另进程的队列，把它们排入另一个等待处理的请求队列。一个等待处理的请求队列。这样，所有的新请求都将被推迟到下一这样，所有的新请求都将被推迟到下一次扫描时处理。次扫描时处理。例例1：假定某移动磁盘上，处理了访问假定某移动磁盘上，处理了访问56号柱面的请号柱面的请求后，现在正在求后，现在正在70号柱面上读信息，目前有下面的请号柱面上读信息，目前有下面的请求访问磁盘柱面的序列：求访问磁盘柱面的序列：73,68,100,120,60,108,8,50请写出下请写出下列各小题的响应的次序及

18、移动的柱面数。列各小题的响应的次序及移动的柱面数。用最短查找时间优先算法用最短查找时间优先算法电梯调度算法电梯调度算法解：解：用用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

19、,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+6

20、4)*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 44 76 80 （0）（20）（8）（8）（40）（32）（4）共移动共移动112柱面柱面 (0+20+8+8+40+32+4)*3=112*3=336 msIN 40 40 44 76 80 20 12 4 （0）（4）（32）（4）（60）（8）（8）共移动共移动116柱面柱面 (0+4+32+4+60+8+8)*3=116*3=348 ms