浅谈磁盘调度算法.ppt

浅谈磁盘调度算法 2024/5/22 周三1一 目录1.常用调度算法概述2.各类调度算法对比3.例题展示4.小结2024/5/22 周三2二 常用调度算法概述1.先来先服务算法（FCFS）First Come First Service 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2024/5/22 周三3二 常用调度算法概述2.最短寻道时间优先算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。2024/5/22 周三4二 常用调度算法概述3、扫描算法（SCAN）电梯调度 磁臂从磁盘的一端向另一端移动，同时当磁头移过每个柱面时，处理位于该柱面上的服务请求。当到达另一端时，磁头改变移动方向，处理继续，磁头在磁盘上来回扫描。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。2024/5/22 周三5二 常用调度算法概述4、循环扫描算法（CSCAN）C-SCAN调度是SCAN调度的变种，主要提供一个更为均匀的等待时间。与SCAN一样，C-SCAN将磁头从磁盘一端移到磁盘的另一端，随着移动不断地处理请求。不过，当磁头移到另一端时，它会马上返回到磁盘开始，返回时并不处理请求。2024/5/22 周三6二 常用调度算法概述 5.LOOK调度&C-LOOK调度 与SCAN和C-SCAN相似，但是磁头只移动到一个方向上最远的请求为止，接着，它马上回头，而不是继续到磁盘的尽头。因为它们在朝一个方向移动会看（look）是否有请求，故以此命名。2024/5/22 周三7三 例题展示 假设移动头磁盘有200个磁道(从0号到199号)。目前正在处理143号磁道上的请求，而刚刚处理结束的请求是125号，如果下面给出的顺序是按FIFO排成的等待服务队列顺序：86，147，91，177，94，150，102，175，130.那么，用下列各种磁盘调度算法来满足这些请求所需的总磁头移动量是多少?(1)FCFS；(2)SSTF；(3)SCAN；(4)LOOK;(5)C-SCAN?2024/5/22 周三8三 例题展示（1）FCFS:143,86，147，91，177，94，150，102，175，130.总移动量：565（2）SSTF:143，147,150,130,102,94,91,86,175,177 总移动量：162（3）SCAN:143,147，150,175,177,199,130,102,94,91,86 总移动量：169（4）C-SCAN:143,147,150,175,177,199,0,86,91,94,102,130 总移动量：385（5）LOOK:143,147,150,175,177,130,102,94,91,86 总移动量：1252024/5/22 周三9四 小结 面对如此多的磁盘调度算法，如何选择最佳的呢？SSTF较为普通且很有吸引力，因为它比FCFS的性能要好。SCAN和C-SCAN对于磁盘负荷较大的系统会执行得更好，因为它不可能产生饿死问题。对于一个特定请求队列，可以定义一个最佳的执行顺序，但是查找最佳调度的所需时间有可能大于SSTF或SCAN节省的时间。对于任何调度算法，其性能主要依赖于请求的数量和类型。2024/5/22 周三10 谢谢观看！2024/5/22 周三112024/5/22 周三122024/5/22 周三13