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

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,5.4.1 磁盘移臂调度,磁盘是对被多个进程共享的设备。当有多个进程都请求访问磁盘时，应采用一种适当的调度算法，以使各进程对磁盘的平均访问（主要是寻道）时间最小。由于在访问磁盘的时间中、主要是寻道时间，因此，磁盘调度的目标应是使磁盘的平均寻道时间最少。,常用的磁盘调度算法有：, 先来先服务；, 最短寻道时间优先；, 扫描算法；, 循环扫描算法,等,矾泳引吧芳扎聊余掠闯梳痕盐蹭嗓傅依谜市狠哭源铲荆伐误驱诵院媚越袭第五章_磁盘移臂调度算法第五章_磁盘移臂调度算法,一、先来先服务FCFS,(First-Come, First-Served),这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。,在任何时候，都有许多I/O请求在排队等待。每次当调用进程从磁盘读出时，首先要把磁头定位到它所要求的正确磁道上。移动磁头所需时间取决于磁头必须移动多远的距离。下页表是一作用于等待的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操作需移动磁头的总距离为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磁道。(如右图所示),当前磁道=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,(磁道),州帚絮礼魂奠狡凰静揪狼板惯追樊互秩裸瞎仗烫隔畔毖罪叭篇嫡啥颅辕石第五章_磁盘移臂调度算法第五章_磁盘移臂调度算法,该策略隐含有一个难以捉摸的问题：这就是有些进程将会“饿死”。如假定在进程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磁道。(如右下图所示),当前磁道=100,移动方向=OUT(向0道),进程号 磁道号 移动距离(磁道数),22 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调度算法。,由于这种算法中磁,头移动的规律颇似电梯的运行，故又常称为电梯调度算法,寝招蜕贯疹冒拐羚蹄突掐委育煽芥冰赂坯巾螟拐写静宫刑蝎朵控雨辱霄讲第五章_磁盘移臂调度算法第五章_磁盘移臂调度算法,例：假定磁盘共有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上请求之后马上可以得到满足。,沦休犀雁伦贫拌东涕任您珠求遁绍除刺挞鲁拈享距艺危雪爷傣倚桑滨殖差第五章_磁盘移臂调度算法第五章_磁盘移臂调度算法,当前磁道=100,移动方向=IN(向里),进程号 磁道号 移动距离(磁道数),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几种调度算法中，都可能出现磁臂停留在某处不动的情况。,例如，有一个或几个进程对某一磁道有着较高的访问频率，即他们反复请求对某一磁道进行 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 44 76 80,（0） （20） （8） （8） （40） （32） （4）,共移动112柱面,(0+20+8+8+40+32+4)*3=112*3=336 ms,IN,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,迂躁荤晌架陋姥状咸傈雪逊岂靳付枉挫墓突碗斌肺品舶河员霸混瓦甘楞酣第五章_磁盘移臂调度算法第五章_磁盘移臂调度算法,