输入输出系统设备课件.ppt

系统往往采用一定的调度策略来决定各等待访问者的执行次序，这项工作称磁盘的“驱动调度”，采用的调度策略称“驱动调度算法”。 对磁盘来说，驱动调度有“移臂调度”和“旋转调度”两部分组成。 根据访问者指定的柱面位置来决定执行次序的调度称“移臂调度”，移臂调度的目的是尽可能地减少输入输出操作中的寻找时间。常用的移臂调度算法有先来先服务算法、最短寻找时间优先算法、电梯调度算法和单向扫描算法 （－）移臂调度 。 1．先来先服务调度算法 最简单的移臂调度算法是“先来先服务”调度算法，这个算法 实际上不考虑访问者要求访问的物理位置，而只是考虑访问者 提出访问请求的先后次序。 例如，现在读写磁头正在53号柱面上执行输入输出操作，而等待访问者依次要访问的柱面为98，183，37，122，14，124，65，67。 当53号柱面上的操作结束后，移动臂将按请求的先后次序先移到98号往面，最后到达67号柱面，如下页图所示。 其相应的臂的总移动量为： （98-53）+（183-98）+（183-37）+（122-37）+（122-14）+（124-14）+（124-65）+（67-65）= 45 + 85+146+85+108+110+59+2 = 496+144=640 cyl. 98，183，37，122，14，124，65，67 从图中可以看到采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂将来回地移动，读写磁头总共移动了640个柱面的距离。 先来先服务算法花费的寻找时间较长，于是，执行输入输出操作的总时间也很长。 2．最短寻道时间优先调度算法（SSTF） 总是从等待访问者中挑选寻找时间最短的那个请求先执行，而不管访问者到来的先后次序。 用同一个例子来讨论，现在当53号柱面的操作结束后， 应该先处理65号柱面的请求，然后到达67号柱面执行操作。随后 应处理37号柱面的请求（它与67号柱面相距30个柱面）而不是 98号柱面的请求（它与67号柱面相距31个柱面），后继操作的次序应该是14，98，122，124，183。如下页图所示。 采用最短寻找时间优先算法决定等待访问者执行输入输出操作的 次序时，读写磁头总共移动了236个柱面的距离。与先来先服务算法比较，大幅度地减少了寻找时间。因而缩短了为各请求访问者服务的平均时间，也就提高了系统效率。 现对需要存取得磁筒进行排序： 14，37，65，67 98，122，124，183。相对于53最近的磁筒为65。 余下的问题是在到达67后，下一个目标是？37，67，98其差为 30与31，所以下一个目标为37。 3．扫描算法，SCAN算法（电梯调度算法） “电梯调度”算法总是从移动臂当前位置开始沿着臂的移动方向 去选择离当前移动臂最近的那个柱面的访问者，如果沿臂的移动 方向无请求访问时，就改变臂的移动方向再选择。这好比乘电梯， 如果电梯已向上运动到4层时，依次有3位乘客A，B，C，他们的 要求是：A在2层等待去10层；B在5层等待去底层；C在8层等待上 15层。电梯管理员不是按照乘客来到的先后次序服务，而是考虑 电梯的效率。在这种情况下，沿电梯运动方向总是先把乘客C带到 15层，然后把乘客B带到底层，最后再把乘客A送到10层。 我们仍用同一例子来讨论采用“电梯调度”算法的情况，由于该 算法是与移动臂的方向有关，所以，应分两种情况来讨论。 （1）移动臂是向外移的。 当前正在53号柱面 ，在这种情况下为等待访问者服务的次序是： 37，14，65，67，98，122，124，183。 总的臂移动量为：(53 – 14）+ （183 – 14） = 208cyl. （2）移动臂是向里移的。 当前正在53号柱面 ，在这种情况下为等待访问者服务的次序是： 65，67，98，122，124，183，37，14。 总的臂移动量为： （183 – 53） + （183 – 14）= 299cyl. 怎样知道磁头当前移动方向？ 当前磁头所在磁道，刚刚访问完的磁道。 4．循环扫描（CSCAN）调度算法 “单向扫描”调度算法：不管等待访问者的先后次序，总是从0号 柱面开始向里扫描，按照各访问者所要访问的柱面位置的次序去 选择访问者。移动臂到达最后一个柱面后，立即带动读写磁头 快速返回到0号柱面，返回时不为任何的等待访问者服务，返回 后可再次从外向内扫描。 对相同的例子采用单向扫描调度算法的执行次序为： 65，67, 98，122，124，183 ， 此时移动臂继续向里移动，直到最内的柱面（图中为199号柱面） 后，再返回到0号柱面，重新扫描时依次为14，37柱面的访问者 服务。 总的臂移动量为： （199-53）+200+37 = 383 cyl。 5.NstepSCAN和FS