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

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