磁盘调度算法实验报告.doc
21页
操作系统实验报告课程名称操作系统实验课程编号0906553实验项目名称磁盘调度算法学号年级姓名专业计算机科学与技术学生所在学院计算机科学与技术学院指导教师实验室名称地点哈尔滨工程大学计算机科学与技术学院磁盘调度算法一. 实验概述：1. 实验名称：磁盘调度算法2. 实验目的:1）通过学习 EOS 实现磁盘调度算法的机制，掌握磁盘调度算法执行 的条件和时机；2）观察 EOS 实现的 FCFS、SSTF 和 SCAN 磁盘调度算法，了解常用 的磁盘调度算法；3）编写CSCAN和N-Step-SCAN磁盘调度算法，加深对各种扫描算法 的理解3. 实验类型： 验证、设计4. 实验内容：1 ）准备实验，创建一个 EOS Kernel 项目；2 ）验证先来先服务（FCFS磁盘调度算法；3 ）验证最短寻道时间优先（SSTF磁盘调度算法；4 ）验证SSTF算法造成的线程“饥饿现象”；5 ）验证扫描（SCAN磁盘调度算法；6 ）改写SCANS法；7 ）编写循环扫描（ CSCAN 磁盘调度算法；8 ）验证SSTF SCAN及 CSCAI算法中的“磁臂粘着”现象；9 ）编写N-Step-SCAN磁盘调度算法二．实验环境操作系统： windows XP编译器： Tevalaton OS Lab语言： C三．实验过程1. 设计思路和流程图:SCAN算法流程图：SSTF算法的流程图:CSAC流程图：YES仃循环结束后记录了向内移 动距离最短移动程线程外 移动距离最长的线程选择向内移动距n-STEP线SCai算法调度:选择向外移动距离最长的线程 nO2. 实验过程:1） 新建一个EOS Kernel项目；2） 在sysproc.c 文件中找到控制台命令“ ds”对应的函数ConsoleCmdDiskSchedule。
ds ” 命令专门用来测试磁盘调度算法阅读该函数中的源代码，目前该函数使磁头初始停留在磁道 10,其它被阻塞的线程依次访问磁道 8、21、9、78、0、41、10、67、12、10；3） 打开io/block.c 文件，在 第378行找到磁盘调度算法函数IopDiskSchedule阅读该函数中的源代码，目前此函数实现了 FCFS磁 盘调度算法，流程图如下：4） 生成项目，启动调试，待 EOS启动完毕，在EOS控制台中输入 命令“ ds”后按回车；在EOS控制台中会首先显示磁头的起始位置是 10磁道，然后按照 线程被阻塞的顺序依次显示线程的 信息（包括线程ID和访问的磁道 号）磁盘调度算法执行的过程中，在 OS Lab的“输出”窗口中也会 首 先显示磁头的起始位置，然后按照线程被唤醒的顺序依次显示线程 信息（包括线程 ID 、访问的磁道号、磁 头移动的距离和方向） ，并在 磁盘调度结束后显示此次调度的统计信息（包括总寻道数、寻道次数和 平均 寻道数）对比 EOS 控制台和“输出”窗口中的内容，可以发现 FCFS 算法是根据线程访问磁盘的先后顺序 进行调度的 下图显示了本 次调度执行时磁头移动的轨迹：5）打开 sstf.c 文件，该文件提供的 IopDiskSchedule 函数实现了 SSTF 磁盘调度算法，其中应注意：① 变量 Offset 是有符号的长整型，用来表示磁头的偏移（包括距离 和方向）。
Offset大于0时表示 磁头向内移动（磁道号增加）；小于0 时表示磁头向外移动（磁道号减少） ；等于 0 时表示磁头没 有移动 而名称以“ Distance ”结尾的变量都是无符号长整型，只表示磁头移动 的距离（无方向） 所以在比较磁头的偏移和距离时，或者在将偏移赋 值给距离时，都要取偏移的绝对值（调用 C 库 函数 abs ）本实验在 实现其它磁盘调度算法时也同样遵守此约定；② 在开始遍历之前，将最小距离（ShortestDista nee ）初始化为最大 的无符号长整型数，这样，第 一次计算的距离一定会小于最小距离， 从而可以使用第一次计算的距离来再次初始化最小距离 本实验在实 现其它磁盘调度算法时也同样使用了此技巧6）生成项目启动调试，待EOS启动完毕，在EOS控制台中输入命 令“ ds ”后按回车；对比 EOS 控制台和“输出”窗口中的内容 （特别是线程 ID 的顺序）， 可以发现， SSTF 算法唤醒线程的 顺序与线程被阻塞的顺序是不同的图18-4显示了本次调度执行时磁头移动的轨迹 对比SSTF算法与FCFS 算法在“输出”窗口中的内容，可以看出， SSTF 算法的平均寻道数明 显低于 FCFS 算法。
7） 验证SSTF算法造成的线程“饥饿现象”，使用SSTF算法时，如 果不断有新线程要求访问磁盘， 而且其所要访问的磁道与当前磁头所在 磁道的 距离较近，这些新线程的请求必然会被优先满足，而等待队列 中一些老线程的请求就会被严重推迟，从而 使老线程出现“饥饿”现 象8） 修改 sysproc.c 文件 ConsoleCmdDiskSchedule 函数中的源代码， 仍然使磁头初始停留在磁道 10，而让其它线程依次访问磁道 78 、21 、9、 8、11、41 、10、67、12、10，生成项目，启动调试，待 EOS 启动完毕， 在EOS控制台中输入命令“ ds”后按回车；查看“输出”窗口中显示的内容，可以发现，虽然访问 78 号磁道的 线程的请求第一个被放入请求队 列，但却被推迟到最后才被处理，出 现了“饥饿”现象如果不断有新线程的请求到达并被优先满足， 则 访 问 78 号磁道的线程的“饥饿”情况就会更加严重；修改访问磁道顺序：修改后执行“ ds ”命令的结果：多次输入“ ds”命令：9） 对 SSTF 算法稍加改进后可以形成 SCAN 算法，可防止老线程出 现“饥饿”现象打开 scan.c 文件，该文件提供的 IopDiskSchedule 函 数实现了 SCAN 磁盘调度算法。
其中应注意下面几点：①在 block.c 文件中的第 374 行定义了一个布尔类型的全局变量 ScanInside ，用于表示扫描算法中 磁头移动的方向该变量值为 TRUE 时表示磁头向内移动（磁道号增加） ；值为 FALSE 时表示磁头 向外移 动（磁道号减少）该变量初始化为TRUE表示SCAN算法第一次执行 时，磁头向内移动；②在 scan.c 文件的 IopDiskSchedule 函数中使用了双重循环第 一次遍历队列时，查找指定方向 上移动距离最短的线程，如果在指定 方向上已经没有线程，就变换方向，进行第二次遍历，同样 是查找移 动距离最短的线程在这两次遍历中一定能找到合适的线程10） 使用 scan.c 文件中 IopDiskSchedule 函数的函数体，替换 block.c 文件中 IopDiskSchedule 函 数的函数体，生成项目，启动调 试，待EOS启动完毕，在EOS控制台中输入命令“ ds”后按回车；对比 SCAN 算法与 SSTF 算法在“输出”窗口中的内容，可以看出，SCAN算法的平均寻道数有可能小于 SSTF算法，所以说SSTF算法不 能保证平均寻道数最少。
下图显示了本次调度执行时磁头移动的轨迹：11） 改写SCAN算法，算法提示：① 在一次遍历中，不再关心当前磁头移动的方向，而是同时找到两个 方向上移动距离最短的线程所 对应的请求， 这样就不再需要遍历两次；② 在计算出线程要访问的磁道与当前磁头所在磁道的偏移后， 可以将偏移分为三种类型：偏移为 0 ，表示线程要访问的磁道与当前磁头所在 磁道相同，此情况应该优先被调度，可立即返回该线程对应的请求的指针；偏移大于 0 ，记录向内移动距离最短的线程对应的请求；偏移小于0，记录向 外移动距离最短的线程对应的请求；③ 循环结束后， 根据当前磁头移动的方向选择同方向移动距离最短的 线程，如果在同方向上没有线 程，就变换方向，选择反方向移动距离 最短的线程；流程如下所示：scAr改写代码：PREQUESTIopDiskschedule(VOID){PLIsT_ENTRY pListEntry;PREQUEsT pRequest;PREQUEsT INpNextRequest = NULL;PREQUEsT OUTpNextRequest = NULL;LONG Offset;ULONG InsideshortestDistance = 0xFFFFFFFF;ULONG OutsideshortestDistance = 0xFFFFFFFF;PREQUEsT pNextRequest = NULL;// 需要遍历请求队列一次或两次for (pListEntry = RequestListHead.Next; // 请 求 队 列 中的第一个请求是链表头指向的下一个请求。
pListEntry != &RequestListHead; // 遍历到请求队列头时结束循环pListEntry = pListEntry->Next) {// 根据链表项获得请求的指针pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);// 计算请求对应的线程所访问的磁道与当前磁头所在磁 道的偏移(方向由正负表示)Offset = pRequest->Cylinder - CurrentCylinder;if (0 == Offset) {// 如果线程要访问的磁道与当前磁头所在磁道相同， 可立即返回pNextRequest = pRequest;goto RETURN;} else if (Offset
