操作系统实验十.docx

《操作系统实验十.docx》由会员分享，可在线阅读，更多相关《操作系统实验十.docx（18页珍藏版）》请在三一办公上搜索。

1、操作系统实验十操作系统 实 验 报 告 课程名称 实验项目名称 学号 姓名 学生所在学院 实验室名称地点 操作系统实验 磁盘调度算法 课程编号 0906553 年级 专业 指导教师 哈尔滨工程大学 计算机科学与技术学院 第一讲 磁盘调度算法 一、实验概述 1. 实验名称 磁盘调度算法 2. 实验目的 l 通过学习EOS实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机。 l 观察EOS实现的FCFS、SSTF和SCAN磁盘调度算法，了解常用的磁盘调度算法。 l 编写CSCAN和N-Step-SCAN磁盘调度算法，加深对各种扫描算法的理解。 3. 实验类型 验证，设计 4. 实验内容 4.

2、1 准备实验 4.2 验证先来先服务磁盘调度算法 4.3 验证最短寻道时间优先磁盘调度算法 4.4 验证SSTF算法造成的线程“饥饿”现象 4.5 验证扫描磁盘调度算法 4.6 改写SCAN算法 4.7 编写循环扫描磁盘调度算法 4.8 验证SSTF、SCAN及CSCAN算法中的“磁臂粘着”现象 4.9 编写N-Step-SCAN磁盘调度算法 二、实验环境 操作系统：Windows XP 编译器：Tevalation OS Lab 语言：C 三、实验过程 1. 设计思路和流程图 SCAN算法流程图： 1 SSTF算法流程图： 流程图： 2 算法调度： . 需要解决的问题及解答 在执行SCAN、

3、N-Step-SCAN 磁盘调度算法时，如果在EOS控制台中多次输入“ds”命令，调度的顺序会发生变化，说明造成这种现象的原因。尝试修改源代码，使这两种算法在多次执行时，都能确保调度的顺序一致。 答：ScanInside是一个全局变量，当第一次执行“ds”命令时，调用IopDiskSchedule 函数，ScanInside被修改了一次，再次执行“ds”命令时，ScanInside不会被重置，因此输出的结果会不一样。只需在for循环结束后添加如下代码，就能确保调度的顺序一致。 3 尝试在io/block.c文件中定义一个全局的函数指针变量DiskScheduleFunc，该函数指针初始指向实现

4、了FCFS算法的IopDiskSchedule函数。修改io/block.c文件中的IopProcessNextRequest函数，在该函数中不再直接调用IopDiskSchedule函数，而是调用函数指针DiskScheduleFunc指向的磁盘调度算法函数；ke/sysproc.c文件中的ConsoleCmdDiskSchedule函数中也不再直接调用IopDiskSchedule函数，也要修改为调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。最后，添加一个控制台命令“sstf”，该命令使函数指针DiskScheduleFunc指向实现了SSTF算法的函数。这样，在EO

5、S启动后默认会执行FCFS算法，执行控制台命令“sstf”后，会执行SSTF算法。按照这种方式依次实现“fcfs”、“scan”、“cscan”和“nstepscan”命令。说明这种在EOS运行时动态切换磁盘调度算法的好处。 答：首先在block.c 中定义一个全局的函数指针变量DiskScheduleFunc。 修改IopProcessNextRequest 函数和ConsoleCmdDiskSchedule 函数，使其不再直接调用IopDiskSchedule 函数而是调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。 调用函数前先声明。 添加一个控制台命令“sstf”，

6、该命令使函数指针DiskScheduleFunc 指向实现了 SSTF 算法的函数。 4 分析已经实现的各种磁盘调度算法的优缺点，尝试实现更多其它的磁盘调度算法。 答：先来先服务算法是一种比较简单的磁盘调度算法，它根据进程请求访问磁盘的先后次序进行调度，此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况，在对磁盘的访问请求比较多的情况下，致使平均寻道时间可能较长；最短寻道时间优先算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短，其缺点是在服务请

7、求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟；扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向，此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道；循环扫描算法是对扫描算法的改进，如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少；N-Step-SCAN算法是扫描算法和先来先服务算法的一个综合算法，将请求队列分成若干个长度为N 的子队列，调度程序按

8、照FCFS原则依次处理这些子队列，而每处理一个子队列时，又是按照SCAN算法，所以它是一种性能比较平均的算法。 EOS在块设备层实现了磁盘调度算法后，由于请求队列中的请求一定是被逐个处理的，所以并发的多个线程已经可以互斥的访问磁盘上的数据，那为什么在IopReadWriteSector函数中还要使用磁盘设备的互斥信号量进行互斥呢？ 答：如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据，那这个线程是不需要进行磁盘调度的，所以不会进入请求队列，但该线程同样需要与其它并发访问磁盘设备的线程进行互斥，这时就需要使用磁盘设备的互斥信号量进行互斥。 . 源程序并附上注释 改写算法： BOOL

9、ScanInside = TRUE; PREQUEST IopDiskSchedule( PLIST_ENTRY pListEntry; PREQUEST pRequest; 5 VOID ) LONG Offset; ULONG InsideShortestDistance = 0xFFFFFFFF; ULONG OutsideShortestDistance = 0xFFFFFFFF; PREQUEST pNextRequest; PREQUEST pNextRequestInside = NULL; PREQUEST pNextRequestOutside = NULL; /* 遍历请求

10、队列，计算磁道的偏移，如果 Offset=0 ，则不需要移动； Offset 0 & Offset InsideShortestDistance 则向内测移动并计下最短距离； Offset 0 & -Offset Cylinder - CurrentCylinder; if (Offset=0) pNextRequest = pRequest; goto RETURN; else if (Offset 0 & Offset Next) = CONTAINING_RECORD(pListEntry, REQUEST, else if (Offset 0 & -Offset 0 & Offset

11、InsideShortestDistance 则向内测移动并计下最短距离； Offset 0 & -Offset Next) pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry); Offset = pRequest-Cylinder - CurrentCylinder; if (Offset=0) 8 pNextRequest = pRequest; goto RETURN; else if (Offset 0 & Offset InsideShortestDistance) InsideShortestDistance =

12、 Offset; pNextRequestInside = pRequest; else if (Offset OutsideShortestDistance) OutsideShortestDistance = -Offset; pNextRequestOutside = pRequest; ; /* 判定移动方向，判定ScanInside是否为0,在判定pNextRequestInside、pNextRequestOutside是否为0，确定移动方向。 */ if(pNextRequestInside != NULL) pNextRequest = pNextRequestInside;

13、ScanInside = ScanInside; else pNextRequest = pNextRequestOutside; ScanInside = !ScanInside; RETURN: return pNextRequest; . 程序运行时的初值和运行结果 .1 准备实验 按照下面的步骤准备实验： 1. 启动OS Lab。 2. 新建一个EOS Kernel项目。 9 .2 验证先来先服务磁盘调度算法 按照下面的步骤进行验证： 1. 在“项目管理器”窗口中双击ke文件夹中的sysproc.c文件，打开此文件。 2. 在sysproc.c文件的第580行找到控制台命令“ds”对应

14、的函数ConsoleCmdDiskSchedule。“ds”命令专门用来测试磁盘调度算法。阅读该函数中的源代码，目前该函数使磁头初始停留在磁道10，其它被阻塞的线程依次访问磁道8、21、9、78、0、41、10、67、12、10。 3. 打开io/block.c文件，在第378行找到磁盘调度算法函数IopDiskSchedule。阅读该函数中的源代码，目前此函数实现了FCFS磁盘调度算法。 4. 按F7生成项目，然后按F5启动调试。 5. 待EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。 在EOS控制台中会首先显示磁头的起始位置是10磁道，然后按照线程被阻塞的顺序依次显示线程的信息

15、。磁盘调度算法执行的过程中，在OS Lab的“输出”窗口中也会首先显示磁头的起始位置，然后按照线程被唤醒的顺序依次显示线程信息，并在磁盘调度结束后显示此次调度的统计信息。对比EOS控制台和“输出”窗口中的内容，可以发现FCFS算法是根据线程访问磁盘的先后顺序进行调度的。图18-2显示了本次调度执行时磁头移动的轨迹。 可以在控制台中多次输入“ds”命令，查看磁盘调度算法执行的情况。将“输出”窗口中的内容复制到一个文本文件中，然后结束此次调试。 .3 验证最短寻道时间优先磁盘调度算法 使用OS Lab打开本实验文件夹中的sstf.c文件。该文件提供的IopDiskSchedule函数实现了SSTF

16、磁盘调度算法。在阅读此函数的源代码的时，可以参考图18-3所示的流程图，并且应该特别注意下面几点： l 变量Offset是有符号的长整型，用来表示磁头的偏移。Offset大于0时表示磁头向内移动；小于0时表示磁头向外移动；等于0时表示磁头没有移动。而名称以“Distance”结尾的变量都是无符号长整型，只表示磁头移动的距离。所以在比较磁头的偏移和距离时，或者在将偏移赋值给距离时，都要取偏移的绝对值。本实验在实现其它磁盘调度算法时也同样遵守此约定。 l 在开始遍历之前，将最小距离初始化为最大的无符号长整型数，这样，第一次计算的距离一定会小于最小距离，从而可以使用第一次计算的距离来再次初始化最小距

17、离。本实验在实现其它磁盘调度算法时也同样使用了此技巧。 按照下面的步骤进行验证： 1. 使用sstf.c文件中IopDiskSchedule函数的函数体，替换block.c文件中11 IopDiskSchedule函数的函数体。 2. 按F7生成项目，然后按F5启动调试。 3. 待EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。 对比EOS控制台和“输出”窗口中的内容，可以发现，SSTF算法唤醒线程的顺序与线程被阻塞的顺序是不同的。图18-4显示了本次调度执行时磁头移动的轨迹。对比SSTF算法与FCFS算法在“输出”窗口中的内容，可以看出，SSTF算法的平均寻道数明显低于FCFS算法

18、。但是，SSTF算法能保证平均寻道数最少吗？在后面的实验中会进行验证。 可以在控制台中多次输入“ds”命令，查看磁盘调度算法执行的情况。将“输出”窗口中的内容复制到一个文本文件中，然后结束此次调试。 .4 验证SSTF算法造成的线程“饥饿”现象 使用SSTF算法时，如果不断有新线程要求访问磁盘，而且其所要访问的磁道与当前磁头所在磁道的距离较近，这些新线程的请求必然会被优先满足，而等待队列中一些老线程的请求就会被严重推迟，从而使老线程出现“饥饿”现象。 按照下面的步骤进行实验，观察这个现象： 1. 修改sysproc.c文件ConsoleCmdDiskSchedule函数中的源代码，仍然使磁头初

19、始停留在磁道10，而让其它线程依次访问磁道78、21、9、8、11、41、10、67、12、10。 2. 按F7生成项目，然后按F5启动调试。 3. 待EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。 查看“输出”窗口中显示的内容，可以发现，虽然访问78号磁道的线程的请求第一个被放入请求队列，但却被推迟到最后才被处理，出现了“饥饿”现象。如果不断有新线程的请求到达并被优先满足，则访问78号磁道的线程的“饥饿”情况就会更加严重。 将“输出”窗口中的内容复制到一个文本文件中，然后结束此次调试。将ConsoleCmdDiskSchedule函数中线程访问的磁道号恢复到本实验3.2中的样子，

20、在后面的实验中还要使用这些数据。 .5 验证扫描磁盘调度算法 对SSTF算法稍加改进后可以形成SCAN算法，可防止老线程出现“饥饿”现象。使用OS Lab打开本实验文件夹中的scan.c文件，该文件提供的IopDiskSchedule函数实现了SCAN磁盘调度算法。在阅读此函数的源代码的时，应该特别注意下面几点： l 在block.c文件中的第374行定义了一个布尔类型的全局变量ScanInside，用于表示扫描算法中磁头移动的方向。该变量值为TRUE时表示磁头向内移动；值为FALSE时表示磁头向外移动。该变量初始化为TRUE，表示SCAN算法第一次执行时，磁头向内移动。 l 在scan.c文

21、件的IopDiskSchedule函数中使用了双重循环。第一次遍历队列时，查找指定方向上移动距离最短的线程，如果在指定方向上已经没有线程，就变换方向，进行第二次遍历，同样是查找移动距离最短的线程。在这两次遍历中一定能找到合适的线程。 按照下面的步骤进行验证： 1. 使用scan.c文件中IopDiskSchedule函数的函数体，替换block.c文件中IopDiskSchedule函数的函数体。 2. 按F7生成项目，然后按F5启动调试。 3. 待EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。 对比SCAN算法与SSTF算法在“输出”窗口中的内容，可以看出，SCAN算法的平均寻道

22、数有可12 能小于SSTF算法，所以说SSTF算法不能保证平均寻道数最少。图18-5显示了本次调度执行时磁头移动的轨迹。尝试在控制台中多次输入“ds”命令，查看磁盘调度算法执行的情况，说明为什么线程调度的顺序会发生变化。将“输出”窗口中的内容复制到一个文本文件中，然后结束此次调试。 使用SCAN算法调度在本实验3.4中产生“饥饿”现象的数据，验证SCAN算法能够解决“饥饿”现象，并将“输出”窗口中的内容保存到一个文本文件中。最后将ConsoleCmdDiskSchedule函数中线程访问的磁道号恢复到本实验3.2中的样子，在后面的实验中还要使用这些数据。 .6 改写SCAN算法 .6.1 要求

23、 在已有SCAN算法源代码的基础上进行改写，要求不再使用双重循环，而是只遍历一次请求队列中的请求，就可以选中下一个要处理的请求。由于线程和请求总是一一对应的，为了使后面的内容更加简单易懂，有时就不再区分这两个概念。 .6.2 提示 1. 在一次遍历中，不再关心当前磁头移动的方向，而是同时找到两个方向上移动距离最短的线程所对应的请求，这样就不再需要遍历两次。 2. 在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，可以将偏移分为三种类型：偏移为0，表示线程要访问的磁道与当前磁头所在磁道相同，此情况应该优先被调度，可立即返回该线程对应的请求的指针；偏移大于0，记录向内移动距离最短的线程对应的请求

24、；偏移小于0，记录向外移动距离最短的线程对应的请求。 3. 循环结束后，根据当前磁头移动的方向选择同方向移动距离最短的线程，如果在同方向上没有线程，就变换方向，选择反方向移动距离最短的线程。具体逻辑可以参见图18-6所示的流程图。 13 制作软盘镜像. 正在启动 Virtual PC. 开始调试. * Disk schedule start working * Start Cylinder: 10 TID: 37 Cylinder: 10 Offset: 0 = TID: 40 Cylinder: 10 Offset: 0 = TID: 39 Cylinder: 12 Offset: 2 +

25、TID: 32 Cylinder: 21 Offset: 9 + TID: 36 Cylinder: 41 Offset: 20 + TID: 38 Cylinder: 67 Offset: 26 + TID: 34 Cylinder: 78 Offset: 11 + TID: 33 Cylinder: 9 Offset: 69 - TID: 31 Cylinder: 8 Offset: 1 - TID: 35 Cylinder: 0 Offset: 8 - Total offset: 146 Transfer times: 10 Average offset: 14 * Disk sched

26、ule stop working * 14 * Disk schedule start working * Start Cylinder: 10 TID: 47 Cylinder: 10 Offset: 0 = TID: 50 Cylinder: 10 Offset: 0 = TID: 43 Cylinder: 9 Offset: 1 - TID: 41 Cylinder: 8 Offset: 1 - TID: 45 Cylinder: 0 Offset: 8 - TID: 49 Cylinder: 12 Offset: 12 + TID: 42 Cylinder: 21 Offset: 9

27、+ TID: 46 Cylinder: 41 Offset: 20 + TID: 48 Cylinder: 67 Offset: 26 + TID: 44 Cylinder: 78 Offset: 11 + Total offset: 88 Transfer times: 10 Average offset: 8 * Disk schedule stop working * .6.3 测试方法 使用本实验3.2中的数据进行测试，确保调度的结果与图18-5中显示的一致，也可以多准备几组测试数据，保证改写的SCAN算法是正确的。测试成功后，将改写的SCAN算法源代码备份。 .7 编写循环扫描磁盘调

28、度算法 .7.1 要求 在已经完成的SCAN算法源代码的基础上进行改写，不再使用全局变量ScanInside确定磁头移动的方向，而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时，磁头立即移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环，进行扫描。 由于磁头移动的方向被固定，也就不需要根据磁头移动的方向进行分类处理，所以CSCAN算法的源代码会较SCAN算法更加简单。 .7.2 提示 1. 由于规定了磁头只能从外向内移动，所以在每次遍历中，总是同时找到向内移动距离最短的线程和向外移动距离最长的线程。注意，与SCAN算法查找向外移动距离最短线程不同，这里查找向外移动距离最

29、长的线程。在开始遍历前，可以将用来记录向外移动最长距离的变量赋值为0。 2. 在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，同样可以将偏移分为三种类型：偏移为0，表示线程要访问的磁道与当前磁头所在磁道相同，此情况应优先被调度，可立即返回该线程对应的请求的指针；偏移大于0，记录向内移动距离最短的线程对应的请求；偏移小于0，记录向外移动距离最长的线程对应的请求。 3. 循环结束后，选择向内移动距离最短的线程，如果没有向内移动的线程，就选择向外移动距离最长的线程。 .7.3 测试方法 使用本实验3.2中的数据进行测试，。可以在控制台中多次输入“ds”命令，查看磁盘调度算法执行的情况。测试成功后

30、，将“输出”窗口中的内容复制到一个文本文件中，并将编写的CSCAN算法源代码备份。 15 制作软盘镜像. 正在启动 Virtual PC. 开始调试. * Disk schedule start working * Start Cylinder: 10 TID: 37 Cylinder: 10 Offset: 0 = TID: 40 Cylinder: 10 Offset: 0 = TID: 39 Cylinder: 12 Offset: 2 + TID: 32 Cylinder: 21 Offset: 9 + TID: 36 Cylinder: 41 Offset: 20 + TID: 38

31、 Cylinder: 67 Offset: 26 + TID: 34 Cylinder: 78 Offset: 11 + TID: 35 Cylinder: 0 Offset: 78 - TID: 31 Cylinder: 8 Offset: 8 + TID: 33 Cylinder: 9 Offset: 1 + Total offset: 155 Transfer times: 10 Average offset: 15 * Disk schedule stop working * 16 * Disk schedule start working * Start Cylinder: 10 T

32、ID: 47 Cylinder: 10 Offset: 0 = TID: 50 Cylinder: 10 Offset: 0 = TID: 49 Cylinder: 12 Offset: 2 + TID: 42 Cylinder: 21 Offset: 9 + TID: 46 Cylinder: 41 Offset: 20 + TID: 48 Cylinder: 67 Offset: 26 + TID: 44 Cylinder: 78 Offset: 11 + TID: 45 Cylinder: 0 Offset: 78 - TID: 41 Cylinder: 8 Offset: 8 + TI

33、D: 43 Cylinder: 9 Offset: 1 + Total offset: 155 Transfer times: 10 Average offset: 15 * Disk schedule stop working * .8 验证SSTF、SCAN及CSCAN算法中的“磁臂粘着”现象 观察执行SSTF、SCAN及CSCAN算法时磁头移动的轨迹，可以看到，在开始时磁头都停留在10磁道不动，这就是“磁臂粘着”现象。为了更加明显的观察该现象，按照下面的步骤进行实验： 1. 修改sysproc.c文件ConsoleCmdDiskSchedule函数中的源代码，仍然使磁头初始停留在磁道10

34、，而让其它线程依次访问磁道78、10、10、10、10、10、10、10、10、10。 2. 分别使用SSTF、SCAN和CSCAN算法调度这组数据。 查看各种算法在“输出”窗口中显示的内容，可以发现，虽然访问78号磁道的线程的请求第一个被放入请求队列，但却被推迟到最后才被处理，出现了“磁臂粘着”现象。 将“输出”窗口中的内容复制到一个文本文件中后，将ConsoleCmdDiskSchedule函数中线程访问的磁道号恢复到本实验3.2中的样子，在后面的实验中还要使用这些数据。 .9 编写N-Step-SCAN磁盘调度算法 .9.1 要求 在已经完成的SCAN算法源代码的基础上进行改写，将请求队

35、列分成若干个长度为N的子队列，调度程序按照FCFS原则依次处理这些子队列，而每处理一个子队列时，又是按照SCAN算法。 .9.2 提示 1. 在block.c文件中的第360行定义了一个宏SUB_QUEUE_LENGTH，表示子队列的长度。目前这个宏定义的值为6。在第367行定义了一个全局变量SubQueueRemainLength，表示第一个子队列剩余的长度，并初始化其值为SUB_QUEUE_LENGTH。 2. 在执行N-Step-SCAN算法时，要以第一个子队列剩余的长度做为计数器，确保只遍历17 第一个子队列剩余的项。所以，结束遍历的条件就既包括第一个子队列结束，又包括整个队列结束。注

36、意，不要直接使用第一个子队列剩余的长度做为计数器，可以定义一个新的局部变量来做为计数器。 3. 按照SCAN算法从第一个子队列剩余的项中选择一个合适的请求。最后，需要将第一个子队列剩余长度减少1，如果第一个子队列剩余长度变为 0，说明第一个子队列处理完毕，需要将子队列剩余的长度重新变为 N，从而开始处理下一个子队列。 .9.3 测试方法 使用本实验3.2中的数据进行测试，。尝试在控制台中多次输入“ds”命令，查看磁盘调度算法执行的情况，说明为什么调度的顺序会发生变化。将“输出”窗口中的内容复制到一个文本文件中，然后结束此次调试。 将宏定义SUB_QUEUE_LENGTH的值修改为100，算法性

37、能接近于SCAN算法的性能，此时调度的结果应该与图18-5中显示的一致；将宏定义SUB_QUEUE_LENGTH的值修改为1，算法退化为FCFS算法。 使用本实验中的数据验证N-Step-SCAN算法可以避免磁臂粘着现象。测试成功后，将编写的N-Step-SCAN算法源代码备份。 四、实验体会 通过本次实验的具体操作，了解了磁盘调度的SSTF算法、SCAN算法、CSCAN算法以及N-STEP-SCAN算法的具体代码和实现过程，掌握了不同的调度算法的各自特点，并与具体的理论知识相比较与验证，对掌握的理论知识有了更准确的理解。本次实验，是最后一次操作系统实验，在这门课的学习期间，我了解了很多有关于操作系统中的如进程调度，存储器管理等问题的知识，我感觉这门课会在今后的学习生活中起到很大的帮助，甚至在将来的工作中也会大量运用这门课的大量知识点，总之这是一门非常值得学习，对计算机专业的学生有非常大意义的学科，尤为感谢刘刚老师能够为我们耐心讲解以及在实验中给我们提供帮助的学长，希望将来有机会还能上刘刚老师您的课，最后，祝老师工作顺利，身体健康！ 18