磁盘调度算法文档.docVIP

磁盘调度算法文档 磁盘调度算法文档 PAGE 磁盘调度算法文档 《操作系统原理及应用》课程设计报告 磁盘调度算法 学院（系）： 计算机科学与工程学院 班 级： 37-5 学号 学生姓名： 时间： 从 2013 年 12 月16日 到 2013 年12月20日 1、课程设计的目的 本课程设计是学生学习完《操作系统原理及应用》课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。 2、课程设计的内容及要求 编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度： 要求设计主界面以灵活选择某算法，且以下算法都要实现 1、先来先服务算法（FCFS） 2、最短寻道时间优先算法（SSTF） 3、扫描算法（SCAN） 4、循环扫描算法（CSCAN） 3、实现原理 磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有先来先服务、最短寻道时间优先、扫描和循环扫描等算法。 其中，平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N 其中Mi为磁头从上一各磁道到这个磁道所需移动的距离。 4、算法 1.先来先服务算法（FCFS） 这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法只考虑访问者提出访问请求的先后次序，按照先后次序依次访问磁道号。移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。 2.短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，而不管访问者到来的先后次序。实现时可以先对磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，选择离自己最近的访问，每比较一次，当前磁道号也跟着变化，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当数组里的最大值小于当前磁道号时，就逆序访问，此时移动距离的和就等于当前磁道号减去数组中最小数；当数组中最小的数大于当前磁道号时，就正序访问，此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。 3.扫描算法（SCAN） SCAN 算法又称电梯调度算法。该算法先考虑磁头的移动方向，再考虑距离近的访问。所以可以对即将访问的磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，当磁头移动方向向磁道号增加的方向移动时，就先依次访问比当前磁道号大的数，再逆向访问比自己小的数；当磁头移动方向是向磁道号减小的方向时就先访问比自己的小的，然后逆向访问比自己大的，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当数组里的最大值小于当前磁道号时，两种方向都是逆序对磁道号访问，此时移动距离的和就等于当前磁道号减去数组中最小数；当数组中最小的数大于当前磁道号时，两种方向都是正序对磁道号访问，此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。 4.循环扫描算法（CSCAN） CSCAN算法是在SCAN算法的基础上规定磁头单向移动，即扫描时要么向磁道号增加的方向的访问，要么向磁道号减小的方向访问。所以可以对即将访问的磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，当磁头移动方向向磁道号增加的方向移动时，就先依次访问比当前磁道号大的数，再返回磁道最里面朝增加的方向访问比自己小的数；当磁头移动方向是向磁道号减小的方向时就先访问比自己的小的，然后返回到磁道最外层访问比自己大的，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当向磁道号增加的方向时，数组里的最大值小于当前磁道号或数组中最小的数大于当前磁道号时，都是正序访问；而当向磁道号减小的方向时，数组里的最大值小于当前磁道号或数组中最小的数大于当前磁道号时，都是逆序访问；此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。 5、程序中使用的数据结构及使用的变量说明和作用 int[] cidao = new int[1000];ET程序设计基础教程，清华大学出版社，