《操作系统实验第五讲磁盘调度算法》由会员分享，可在线阅读，更多相关《操作系统实验第五讲磁盘调度算法（33页珍藏版）》请在金锄头文库上搜索。
1、word操作系统实 验 报 告课程名称操作系统实验实验项目名称磁盘调度算法学号班级20120616某某专业计算机科学与技术学生所在学院计算机科学与技术学院指导教师初妍实验室名称地点21#428某某工程大学计算机科学与技术学院第六讲 磁盘调度算法一、实验概述1. 实验名称磁盘调度算法2. 实验目的1通过学习EOS 实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机； 2观察 EOS 实现的FCFS、SSTF和 SCAN磁盘调度算法，了解常用的磁盘调度算法； 3编写 CSCAN和 N-Step-SCAN磁盘调度算法，加深对各种扫描算法的理解。3. 实验类型验证性+设计性实验4. 实验内容1验
2、证先来先服务FCFS磁盘调度算法； 2验证最短寻道时间优先SSTF磁盘调度算法； 3验证SSTF算法造成的线程“饥饿现象； 4验证扫描SCAN磁盘调度算法； 5改写SCAN算法。 二、实验环境在OS Lab实验环境的根底上，利用EOS操作系统，由汇编语言与C语言编写代码，对需要的项目进展生成、调试、查看和修改，并通过EOS应用程序使内核从源代码变为可以在虚拟机上使用。三、实验过程1. 设计思路和流程图1改写SCAN算法在已有 SCAN 算法源代码的根底上进展改写，要求不再使用双重循环，而是只遍历一次请求队列中的请求，就可以选中下一个要处理的请求。算法流程图如如下图所示。图 3.1.1 SCAN
3、算法IopDiskSchedule函数流程图（2） 编写循环扫描CSCAN磁盘调度算法在已经完成的SCAN算法源代码的根底上进展改写，不再使用全局变量ScanInside确定磁头移动的方向，而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时，磁头立即移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环，进展扫描。算法流程图如如下图所示。图 3.1.2 CSCAN算法IopDiskSchedule函数流程图（3） 编写N-Step-SCAN磁盘调度算法在已经完成的 SCAN 算法源代码的根底上进展改写，将请求队列分成假如干个长度为 N 的子队列，调度程序按照 FCFS原如此依
4、次处理这些子队列，而每处理一个子队列时，又是按照SCAN算法。算法流程图如如下图所示。图 3.1.3 N-Step-SCAN算法IopDiskSchedule函数流程图2. 算法实现1改写SCAN算法在一次遍历中，不再关心当前磁头移动的方向，而是同时找到两个方向上移动距离最短的线程所对应的请求，这样就不再需要遍历两次。 在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，可以将偏移分为三种类型：偏移为0，表示线程要访问的磁道与当前磁头所在磁道一样，此情况应该优先被调度，可立即返回该线程对应的请求的指针；偏移大于 0，记录向内移动距离最短的线程对应的请求；偏移小于 0，记录向外移动距离最短的线程
5、对应的请求。循环完毕后，根据当前磁头移动的方向选择同方向移动距离最短的线程，如果在同方向上没有线程，就变换方向，选择反方向移动距离最短的线程。（2） 编写循环扫描CSCAN磁盘调度算法由于规定了磁头只能从外向内移动，所以在每次遍历中，总是同时找到向内移动距离最短的线程和向外移动距离最长的线程。注意，与 SCAN 算法查找向外移动距离最短线程不同，这里查找向外移动距离最长的线程。在开始遍历前，可以将用来记录向外移动最长距离的变量赋值为0。在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，同样可以将偏移分为三种类型：偏移为 0，表示线程要访问的磁道与当前磁头所在磁道一样，此情况应优先被调度，可立
6、即返回该线程对应的请求的指针；偏移大于 0，记录向内移动距离最短的线程对应的请求；偏移小于 0，记录向外移动距离最长的线程对应的请求。循环完毕后，选择向内移动距离最短的线程，如果没有向内移动的线程，就选择向外移动距离最长的线程。3编写N-Step-SCAN磁盘调度算法在 block.c 文件中的第360 行定义了一个宏 SUB_QUEUE_LENGTH，表示子队列的长度即N 值 。目前这个宏定义的值为6。在第 367行定义了一个全局变量SubQueueRemainLength，表示第一个子队列剩余的长度，并初始化其值为SUB_QUEUE_LENGTH。在执行 N-Step-SCAN算法时，要以
7、第一个子队列剩余的长度做为计数器，确保只遍历第一个子队列剩余的项。所以，完毕遍历的条件就既包括第一个子队列完毕，又包括整个队列完毕如果整个队列的长度小于第一个子队列剩余的长度。注意，不要直接使用第一个子队列剩余的长度做为计数器，可以定义一个新的局部变量来做为计数器。按照 SCAN 算法从第一个子队列剩余的项中选择一个适宜的请求。最后，需要将第一个子队列剩余长度减少1SubQueueRemainLength减少1，如果第一个子队列剩余长度变为 0，说明第一个子队列处理完毕，需要将子队列剩余的长度重新变为 NSubQueueRemainLength 重新赋值为SUB_QUEUE_LENGTH，从而
8、开始处理下一个子队列。 3. 需要解决的问题与解答（1） 实验指导P176-3.2验证先来先服务FCFS磁盘调度算法，要求请给出在“输出窗口中的结果。答：先来先服务FCFS磁盘调度算法在“输出窗口中的结果如如下图所示。（2） 实验指导P177-3.3验证验证最短寻道时间优先SSTF磁盘调度算法，要求请给出在“输出窗口中的结果。答：最短寻道时间优先SSTF磁盘调度算法在“输出窗口中的结果如如下图所示。（3） “饥饿现象，要求请给出在“输出窗口中的结果。答：SSTF算法造成的线程“饥饿现象在“输出窗口中的结果如如下图所示。（4） 实验指导P179-3.5验证扫描SCAN磁盘调度算法，要求在非饥饿即
9、实验指导P176-3.2节中的数据和饥饿即实验指导P178-3.4节中的数据请给出在“输出窗口中的结果，并且要求在每次输入两次“ds命令注意不要连续输入，要等第一次“ds命令执行完，再输入第二次“ds命令，分析结果为什么不同。 答：在非饥饿情况下，“输出窗口中的结果如如下图所示。在饥饿情况下，“输出窗口中的结果如如下图所示。ScanInside是一个全局变量，当第一次执行“ds命令时，调用IopDiskSchedule 函数，ScanInside被修改了一次，再次执行“ds命令时，ScanInside不会被重置，因此输出的结果会不一样。5在执行 SCAN、N-Step-SCAN 磁盘调度算法时
10、，如果在EOS控制台中屡次输入“ds命令，调度的顺序会发生变化，说明造成这种现象的原因提示：注意这两种算法使用的全局变量。尝试修改源代码，使这两种算法在屡次执行时，都能确保调度的顺序一致提示：可以参考 io/block.c 文件中IopReceiveRequest 函数和 IopProcessNextRequest 函数判断磁盘调度算法开始工作和完毕工作的方法。 答：ScanInside是一个全局变量，当第一次执行“ds命令时，调用IopDiskSchedule 函数，ScanInside被修改了一次，再次执行“ds命令时，ScanInside不会被重置，因此输出的结果会不一样。只需在for循
11、环完毕后添加如下代码，就能确保调度的顺序一致。6尝试在 io/block.c 文件中定义一个全局的函数指针变量 DiskScheduleFunc，该函数指针初始指向实现了 FCFS 算法的 IopDiskSchedule 函数。修改 io/block.c 文件中的 IopProcessNextRequest 函数，在该函数中不再直接调用 IopDiskSchedule 函数，而是调用函数指针 DiskScheduleFunc 指向的磁盘调度算法函数；ke/sysproc.c 文件中的 ConsoleCmdDiskSchedule 函数中也不再直接调用IopDiskSchedule函数，也要修改
12、为调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。最后，添加一个控制台命令“sstf，该命令使函数指针 DiskScheduleFunc 指向实现了 SSTF 算法的函数。这样，在 EOS启动后默认会执行FCFS 算法，执行控制台命令“sstf后，会执行SSTF算法。按照这种方式依次实现“fcfs、“scan、“cscan和“nstepscan命令。说明这种在EOS运行时动态切换磁盘调度算法的好处。答：首先在block.c 中定义一个全局的函数指针变量 DiskScheduleFunc。修改IopProcessNextRequest 函数和ConsoleCmdDiskSch
13、edule 函数，使其不再直接调用 IopDiskSchedule 函数而是调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。调用函数前先声明。添加一个控制台命令“sstf，该命令使函数指针 DiskScheduleFunc 指向实现了 SSTF 算法的函数。验证结果如如下图所示。7分析已经实现的各种磁盘调度算法的优缺点，尝试实现更多其它的磁盘调度算法。 答：先来先服务算法是一种比拟简单的磁盘调度算法，它根据进程请求访问磁盘的先后次序进展调度，此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况，在对磁盘的访问请求比拟多的情况
14、下，致使平均寻道时间可能较长；最短寻道时间优先算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比拟好的吞吐量，但却不能保证平均寻道时间最短，其缺点是在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟；扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向，此算法根本上克制了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比拟大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道；循环扫描算法是对扫描算法的改良，如果对
15、磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少；N-Step-SCAN算法是扫描算法和先来先服务算法的一个综合算法，将请求队列分成假如干个长度为 N 的子队列，调度程序按照 FCFS原如此依次处理这些子队列，而每处理一个子队列时，又是按照SCAN算法，所以它是一种性能比拟平均的算法。6EOS 在块设备层实现了磁盘调度算法后，由于请求队列中的请求一定是被逐个处理的，所以并发的多个线程已经可以互斥的访问磁盘上的数据，那为什么在 IopReadWriteSector 函数中还要使用磁盘设备的互斥信号量进展互斥呢？提示：如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据，是否需要对该线程进展磁盘调度？该线程是否要与其它并发访问磁盘设备的线程进展互斥？答：如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据，那这个线程是不需要进展磁盘调度的，所以不会进入请求队列，但该线程同样需要与其它并发访问磁盘设备的线程进展互斥，这
