操作系统实验磁盘调度算法

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

2、内容(1) 验证先来先服务(FCFS)磁盘调度算法；(2) 验证最短寻道时间优先(SSTF)磁盘调度算法；( 3)验证 SSTF 算法造成的线程“饥饿”现象；( 4)验证扫描( SCAN )磁盘调度算法；( 5)改写 SCAN 算法。二、实验环境在 OS Lab 实验环境的基础上， 利用 EOS 操作系统， 由汇编语言及 C 语言编写代码， 对需要的项目进行生成、调试、查看和修改，并通过EOS应用程序使内核从源代码变为可以在虚拟机上使用。三、实验过程1. 设计思路和流程图( 1 )改写 SCAN 算法在已有 SCAN 算法源代码的基础上进行改写，要求不再使用双重循环，而是只遍历 一次请求队列中

3、的请求，就可以选中下一个要处理的请求。算法流程图如下图所示。图 3.1.1 SCAN 算法 IopDiskSchedule 函数流程图(2)编写循环扫描(CSCAN)磁盘调度算法在已经完成的 SCAN 算法源代码的基础上进行改写，不再使用全局变量 ScanInside 确定磁头移动的方向，而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁 道时，磁头立即移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环， 进行扫描。算法流程图如下图所示。图 3.1.2 CSCAN 算法 IopDiskSchedule 函数流程图（3）编写 N-Step-SCAN 磁盘调度算法在已经完成的 S

4、CAN 算法源代码的基础上进行改写， 将请求队列分成若干个长度为 N 的子队列，调度程序按照 FCFS 原则依次处理这些子队列，而每处理一个子队列时， 又是按照 SCAN 算法。算法流程图如下图所示。图 3.1.3 N-Step-SCAN 算法 IopDiskSchedule 函数流程图2. 算法实现（1）改写 SCAN 算法 在一次遍历中，不再关心当前磁头移动的方向，而是同时找到两个方向上移动距离 最短的线程所对应的请求，这样就不再需要遍历两次。 在计算出线程要访问的磁道与当 前磁头所在磁道的偏移后，可以将偏移分为三种类型：偏移为0，表示线程要访问的磁道与当前磁头所在磁道相同，此情况应该优先

5、被调度，可立即返回 该线程对应的请求的指针；偏移大于 0，记录向内移动距离最短的线程对应的请求；偏 移小于 0，记录向外移动距离最短的线程对应的请求。循环结束后，根据当前磁头移动 的方向选择同方向移动距离最短的线程，如果在同方向上没有线程，就变换方向，选择 反方向移动距离最短的线程。（2）编写循环扫描（CSCAN）磁盘调度算法由于规定了磁头只能从外向内移动， 所以在每次遍历中， 总是同时找到向内移动距离 最短的线程和向外移动距离最长的线程。 注意，与 SCAN 算法查找向外移动距离最短线 程不同，这里查找向外移动距离最长的线程。在开始遍历前，可以将用来记录向外移动 最长距离的变量赋值为 0。在

6、计算出线程要访问的磁道与当前磁头所在磁道的偏移后， 同 样可以将偏移分为三种类型：偏移为 0，表示线程要访问的磁道与当前磁头所在磁道相 同，此情况应优先被调度，可立即返回该线程对应的请求的指针；偏移大于0，记录向内移动距离最短的线程对应的请求；偏移小于 0，记录向外移动距离最长的线程对应的 请求。循环结束后，选择向内移动距离最短的线程，如果没有向内移动的线程，就选择 向外移动距离最长的线程。（ 3）编写 N-Step-SCAN 磁盘调度算法在 block.c 文件中的第 360 行定义了一个宏 SUB_QUEUE_LENGTH ，表示子队列 的长度（即 N 值 ）。目前这个宏定义的值为 6。在

7、第 367 行定义了一个全局变量 SubQueueRemainLength表示第一个子队列剩余的长度，并初始化其值为 SUB_QUEUE_LENGTH 。在执行 N-Step-SCAN 算法时，要以第一个子队列剩余的长度 做为计数器，确保只遍历第一个子队列剩余的项。所以，结束遍历的条件就既包括第一 个子队列结束，又包括整个队列结束（如果整个队列的长度小于第一个子队列剩余的长 度）。注意，不要直接使用第一个子队列剩余的长度做为计数器，可以定义一个新的局 部变量来做为计数器。按照 SCAN 算法从第一个子队列剩余的项中选择一个合适的请求。最后，需要将第一个子队列剩余长度减少1 （SubQueueR

8、emainLength减少1）,如果第一个子队列剩余长度变为 0，说明第一个子队列处理完毕，需要将子队列剩余的长 度重新变为 N（ SubQueueRemainLength 重新赋值为 SUB_QUEUE_LENGTH ），从而开 始处理下一个子队列。3. 需要解决的问题及解答（1）实验指导P176-3.2验证先来先服务（FCFS）磁盘调度算法，要求请给出在“输 出”窗口中的结果。答：先来先服务（FCFS）磁盘调度算法在“输出”窗口中的结果如下图所示。图 3.3.1（2） 实验指导P177-3.3验证验证最短寻道时间优先（SSTF）磁盘调度算法，要求请 给出在“输出”窗口中的结果。答：最短寻道

9、时间优先（SSTF）磁盘调度算法在“输出”窗口中的结果如下图所示。图 3.3.2（3）实验指导P178-3.4验证SSTF算法造成的线程“饥饿”现象，要求请给出在“输 出”窗口中的结果。答：SSTF算法造成的线程“饥饿”现象在“输出”窗口中的结果如下图所示。图 3.3.3（4）实验指导P179-3.5验证扫描（SCAN）磁盘调度算法，要求在非饥饿（即实验指导P176-3.2节中的数据）和饥饿（即实验指导P178-3.4节中的数据）请给出在“输出”窗口中的结果，并且要求在每次输入两次“ds”命令（注意不要连续输入，要等第一次“ ds”命令执行完，再输入第二次“ ds”命令），分析结果为什么不同。

10、答：在非饥饿情况下，“输出”窗口中的结果如下图所示。图 3.3.4在饥饿情况下，“输出”窗口中的结果如下图所示。图 3.3.5SCanlnSide是一个全局变量，当第一次执行“ ds”命令时，调用IOPDiSkSChedUIe函 数，SCanlnSide被修改了一次，再次执行“ ds”命令时，SCanlnSide不会被重置，因此输 出的结果会不一样。（5）在执行SCAN、N-SteP-SCAN磁盘调度算法时，如果在 EOS控制台中多次输 入“ds”命令，调度的顺序会发生变化，说明造成这种现象的原因（提示：注意这两种 算法使用的全局变量）。尝试修改源代码，使这两种算法在多次执行时，都能确保调度

11、的顺序一致（提示：可以参考 iO/bIOCk.C 文件中 lOPReCeiveRequest 函数和 IopProcessNextRequest函数判断磁盘调度算法开始工作和结束工作的方法）。答：SCanlnSide是一个全局变量，当第一次执行“ ds”命令时，调用IOPDiSkSCheduIe 函数，SCanlnSide被修改了一次，再次执行“ ds”命令时，SCanlnSide不会被重置，因此 输出的结果会不一样。只需在 fOr 循环结束后添加如下代码，就能确保调度的顺序一致。图 3.3.6（6）尝试在io/block.c文件中定义一个全局的函数指针变量DiSkSChedUIeFUnc该函

12、数指针初始指向实现了 FCFS 算法的 lOPDiSkSCheduIe 函数。修改 iO/bIOCk.C 文件中 的IopprocessNextRequest函数，在该函数中不再直接调用IoPDiSkSChedUIe函数，而是调用函数指针 DiSkSChedUleFUnC 指向的磁盘调度算法函数； ke/SySProC.C 文件中的 Con SoleCmdDiskSchedule函数中也不再直接调用IoPDiSkSChedUle函数，也要修改为调 用函数指针DiSkSChedUIeFUnc指向的磁盘调度算法函数。最后，添加一个控制台命令“sstf',该命令使函数指针 DiSkSChed

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

14、IeFUnc指向的磁盘调度算法函 数。图 3.3.8调用函数前先声明。图 3.3.9添加一个控制台命令“sstf”，该命令使函数指针DiSkSChedUIeFUnc指向实现了 SSTF 算法的函数。验证结果如下图所示。（7）分析已经实现的各种磁盘调度算法的优缺点，尝试实现更多其它的磁盘调度算 法。答： 先来先服务算法 是一种比较简单的磁盘调度算法，它根据进程请求访问磁盘的 先后次序进行调度，此算法的优点是公平、简单，且每个进程的请求都能依次得到处理， 不会出现某一进程的请求长期得不到满足的情况， 在对磁盘的访问请求比较多的情况下， 致使平均寻道时间可能较长； 最短寻道时间优先算法 选择这样的进

15、程，其要求访问的磁 道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好 的吞吐量，但却不能保证平均寻道时间最短，其缺点是在服务请求很多的情况下，对内 外边缘磁道的请求将会无限期的被延迟； 扫描算法 不仅考虑到欲访问的磁道与当前磁道 的距离，更优先考虑的是磁头的当前移动方向，此算法基本上克服了最短寻道时间优先 算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算 法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被 访问的频率仍低于中间磁道； 循环扫描算法 是对扫描算法的改进，如果对磁道的访问请 求是均匀分布的，当磁头到达

16、磁盘的一端，并反向运动时落在磁头之后的访问请求相对 较少； N-Step-SCAN 算法是扫描算法和先来先服务算法的一个综合算法，将请求队列分 成若干个长度为 N 的子队列，调度程序按照 FCFS 原则依次处理这些子队列，而每处 理一个子队列时，又是按照 SCAN 算法，所以它是一种性能比较平均的算法。（6）EOS 在块设备层实现了磁盘调度算法后， 由于请求队列中的请求一定是被逐个 处理的，所以并发的多个线程已经可以互斥的访问磁盘上的数据，那为什么在 IopReadWriteSector 函数中还要使用磁盘设备的互斥信号量进行互斥呢？ （提示：如果一 个线程只是要获取磁盘设备的状态而不是要访问

17、磁盘上的数据，是否需要对该线程进行 磁盘调度？该线程是否要与其它并发访问磁盘设备的线程进行互斥？）答：如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据， 那这个线 程是不需要进行磁盘调度的，所以不会进入请求队列，但该线程同样需要与其它并发访 问磁盘设备的线程进行互斥，这时就需要使用磁盘设备的互斥信号量进行互斥。4. 源程序并附上注释（1）改写 SCAN 算法BOOL ScanInside = TRUE;PREQUESTIopDiskSchedule（VOID）PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextReque

18、st = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;/ 需要遍历请求队列一次或两次for （pListEntry = RequestListHead.Next; / 请求队列中的第一个请求是链表头指 / 向的下一个请求。pListEntry != &RequestListHead; / 遍历到请求队列头时结

19、束循环。pListEntry = pListEntry->Next） / 根据链表项获得请求的指针pRequest = CONTAINING_RECORD（pListEntry, REQUEST, ListEntry）;/ 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移(方向由正负表示)Offset = pRequest->Cylinder - CurrentCylinder;if (0 = Offset) / 如果线程要访问的磁道与当前磁头所在磁道相同，可立即返回。 pNextRequest = pRequest;goto RETURN; else if ( Offset

20、 > 0 && Offset < InsideShortestDistance ) / 记录向内移动距离最短的线程InsideShortestDistance = Offset; INpNextRequest = pRequest; else if ( Offset < 0 && -Offset < OutsideShortestDistance ) / 记录向外移动距离最短的线程OutsideShortestDistance = -Offset; OUTpNextRequest = pRequest;/判断磁头移动方向，若向内移动if(

21、 ScanInside)/判断是否有向内移动的线程if(INpNextRequest)/有则选择该线程return INpNextRequest;else/没有则修改磁头方向，选择向外移动距离最短的线程ScanInside = !ScanInside;return OUTpNextRequest;/如果向外移动else/判断是否有向外移动的线程if(OUTpNextRequest)/有则选择该线程return OUTpNextRequest;else/没有则修改词头方向，选择向内移动距离最短的线程ScanInside = !ScanInside;return INpNextRequest;RE

22、TURN: return pNextRequest;(2) 编写循环扫描(CSCAN)磁盘调度算法PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0x00000000;PREQUEST pNextRequest

23、 = NULL;/ 需要遍历请求队列一次或两次for (pListEntry = RequestListHead.Next; /请求队列中的第一个请求是链表头指/向的下一个请求。pListEntry != &RequestListHead;/ 遍历到请求队列头时结束循环。pListEntry = pListEntry->Next) / 根据链表项获得请求的指针pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移(方向由正负表示) Offset = pRe

24、quest->Cylinder - CurrentCylinder;if (0 = Offset) / 如果线程要访问的磁道与当前磁头所在磁道相同，可立即返回。 pNextRequest = pRequest;goto RETURN; else if ( Offset > 0 && Offset < InsideShortestDistance ) / 记录向内移动距离最短的线程 InsideShortestDistance = Offset; INpNextRequest = pRequest; else if ( Offset < 0 &&a

25、mp; -Offset > OutsideShortestDistance ) / 记录向外移动距离最长的线程OutsideShortestDistance = -Offset;OUTpNextRequest = pRequest; /需要向内移动的线程是否存在 if( INpNextRequest )/存在则返回向内移动的请求 return INpNextRequest;else/否则返回向外移动的请求return OUTpNextRequest;RETURN:return pNextRequest;(3) 编写 N-Step-SCAN 磁盘调度算法/ N-Step-SCAN 磁盘调度

26、算法使用的子队列长度 N#define SUB_QUEUE_LENGTH 6/ 记录 N-Step-SCAN 磁盘调度算法第一个子队列剩余的长度。/ 子队列初始长度为 N ，每执行一次磁盘调度算法会从子队列中移除一个请求，子队列/ 长度就要减少 1，待长度变为 0 时，再将长度重新变为 N ，开始处理下一个子队列 ULONG SubQueueRemainLength = SUB_QUEUE_LENGTH;/ 扫描算法中磁头移动的方向。操作系统启动时初始化为磁头向内移动。/ TRUE ，磁头向内移动，磁道号增加。/ FALSE ，磁头向外移动，磁道号减少。BOOL ScanInside = TR

27、UE;PREQUESTIopDiskSchedule(VOID)PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;ULONG counter;/ 需要遍历请求队列一次或两次/计数器记录一个子

28、队列剩余的长度counter = SubQueueRemainLength;/没调度一次子队列剩余的长度减SubQueueRemainLength-;/如果子队列剩余的长度为，则重置为子队列原长度 if(SubQueueRemainLength = 0)SubQueueRemainLength = SUB_QUEUE_LENGTH;/向的下一个/束循环或for (pListEntry = RequestListHead.Next; / 请求队列中的第一个请求是链表头指 请求。pListEntry != &RequestListHead && counter>0;

29、/ 遍历到请求队列头时结 子队列结束。pListEntry = pListEntry->Next) / 根据链表项获得请求的指针pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry);/ 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移(方向由正负表示)Offset = pRequest->Cylinder - CurrentCylinder;if (0 = Offset) / 如果线程要访问的磁道与当前磁头所在磁道相同，可立即返回。 pNextRequest = pRequest;return pNextRe

30、quest; else if ( Offset > 0 && Offset < InsideShortestDistance ) / 记录向内移动距离最短的线程 InsideShortestDistance = Offset; INpNextRequest = pRequest; else if ( Offset < 0 && -Offset < OutsideShortestDistance ) / 记录向外移动距离最短的线程OutsideShortestDistance = -Offset; OUTpNextRequest = pRe

31、quest;counter-;if( ScanInside )if(INpNextRequest)return INpNextRequest;elseScanInside = !ScanInside;return OUTpNextRequest;elseif(OUTpNextRequest)return OUTpNextRequest;elseScanInside = !ScanInside;return INpNextRequest;5. 程序运行时的初值和运行结果（1）验证先来先服务（FCFS）磁盘调度算法新建一个EoS Kemel项目，双击ke文件夹中的SySPrOc.c文件，阅读函数C

32、onsoleCmdDiskSchedue目前该函数使磁头初始停留在磁道 10，其它被阻塞的线程依 次访问磁道 8、21、9、78、0、41、10、67、12、10。按F5调试项目，待EOS启动完毕，在EOS控制台中输入命令“ ds”后按回车。控 制台和输出窗口显示内容如下图所示。图 3.5.2图 3.5.3对比EOS控制台和“输出”窗口中的内容，可以发现FCFS算法是根据线程访问磁盘的先后顺序进行调度的。（2）验证最短寻道时间优先（SSTF）磁盘调度算法使用 sstf.c 文件中 IoPDiskSchedule 函数的函数体，替换 block.c 文件中IoPDiSkSChedUIe函数的函数体。按 F7生成项目，然后按F5启动调试。待EOS启动完 毕，在EOS控制台中输入命令“ ds”后按回车。输出窗口输出结果如下图所示。图 3.5.4（3）验证SSTF算法造成的线程“饥饿”现象修改SySProc.c文件ConSOIeCmdDiSkSChedUle函数中的源代码，仍然使磁头初始停留 在磁道 10，而让其它线程依次访问磁道 78、21、9、8、11、41、10、67、12、10。按 F7生成项目，然后按F5启动调试。 待EOS启动完毕，在EOS控制台中输