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

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

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

3、skSchedule函数流程图(2)编写循环扫描(CSCAN磁盘调度算法在已经完成的SCAN算法源代码的基础上进行改写，不再使用全局变量ScanInside确定磁头移动的方向，而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时，磁头立即移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环，进行扫描。算法流程图如下图所示。图3.1.2CSCAN算法lopDiskSchedule函数流程图（3）编写N-Step-SCAN磁盘调度算法在已经完成的SCAN算法源代码的基础上进行改写，将请求队列分成若干个长度为N的子队列，调度程序按照FCFS原则依次处理这些子队列，而每处理一个子队列

4、时，又是按照SCANT法。算法流程图如下图所示。图3.1.3N-Step-SCAN算法IopDiskSchedule函数流程图2 .算法实现（1）改写scant法在一次遍历中，不再关心当前磁头移动的方向，而是同时找到两个方向上移动距离最短的线程所对应的请求，这样就不再需要遍历两次。在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，可以将偏移分为三种类型：偏移为0,表示线程要访问的磁道与当前磁头所在磁道相同，此情况应该优先被调度，可立即返回该线程对应的请求的指针；偏移大于0,记录向内移动距离最短的线程对应的请求；偏移小于0,记录向外移动距离最短的线程对应的请求。循环结束后，根据当前磁头移动的方

5、向选择同方向移动距离最短的线程，如果在同方向上没有线程，就变换方向，选择反方向移动距离最短的线程。（2）编写循环扫描（CSCAN磁盘调度算法由于规定了磁头只能从外向内移动，所以在每次遍历中，总是同时找到向内移动距离最短的线程和向外移动距离最长的线程。注意，与SCAN算法查找向外移动距离最短线程不同，这里查找向外移动距离最长的线程。在开始遍历前，可以将用来记录向外移动最长距离的变量赋值为00在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，同样可以将偏移分为三种类型：偏移为0,表示线程要访问的磁道与当前磁头所在磁道相同，此情况应优先被调度，可立即返回该线程对应的请求的指针；偏移大于0,记录向内

6、移动距离最短的线程对应的请求；偏移小于0,记录向外移动距离最长的线程对应的请求。循环结束后，选择向内移动距离最短的线程，如果没有向内移动的线程，就选择向外移动距离最长的线程。（3）编写N-Step-SCAN磁盘调度算法在block.c文件中的第360行定义了一个宏SUB_QUEUE_LENGTH示子队列的长度（即N值）。目前这个宏定义的值为6。在第367行定义了一个全局变量SubQueueRemainLength,表示第一个子队列剩余的长度，并初始化其值为SUB_QUEUE_LENGTH执行N-Step-SCAN算法时，要以第一个子队列剩余的长度做为计数器，确保只遍历第一个子队列剩余的项。所以

7、，结束遍历的条件就既包括第一个子队列结束，又包括整个队列结束（如果整个队列的长度小于第一个子队列剩余的长度）。注意，不要直接使用第一个子队列剩余的长度做为计数器，可以定义一个新的局部变量来做为计数器。按照SCAN算法从第一个子队列剩余的项中选择一个合适的请求。最后，需要将第一个子队列剩余长度减少1(SubQueueRemainLengt曦少1),如果第一个子队列剩余长度变为0,说明第一个子队列处理完毕，需要将子队列剩余的长度重新变为N(SubQueueRemainLength重新赋值为SUB_QUEUE_LENGTH而开始处理下一个子队列。3 .需要解决的问题及解答(1)实验指导P176-3.

8、2验证先来先服务(FCFS磁盘调度算法，要求请给出在“输出”窗口中的结果。答：先来先服务(FCFS磁盘调度算法在“输出”窗口中的结果如下图所示。图3.3.1(2)实验指导P177-3.3验证验证最短寻道时间优先(SSTF磁盘调度算法，要求请给出在“输出”窗口中的结果。答：最短寻道时间优先(SSTF磁盘调度算法在“输出”窗口中的结果如下图所示。图3.3.2(3)实验指导P178-3.4验证SSTF算法造成的线程“饥饿”现象，要求请给出在“输出”窗口中的结果。答：SSTF算法造成的线程“饥饿”现象在“输出”窗口中的结果如下图所示。图3.3.3(4)实验指导P179-3.5验证扫描(SCAN磁盘调度

9、算法，要求在非饥饿(即实验指导P176-3.2节中的数据)和饥饿(即实验指导P178-3.4节中的数据)请给出在“输出”窗口中的结果，并且要求在每次输入两次“ds”命令(注意不要连续输入，要等第一次“ds”命令执行完，再输入第二次“ds”命令)，分析结果为什么不同。答：在非饥饿情况下，“输出”窗口中的结果如下图所示。图3.3.4在饥饿情况下，“输出”窗口中的结果如下图所示。图3.3.5ScanInside是一个全局变量，当第一次执行“ds”命令时，调用IopDiskSchedule函数，ScanInside被修改了一次，再次执行“ds”命令时，ScanInside不会被重置，因此输出的结果会不

10、一样。(5)在执行SCANN-Step-SCAN磁盘调度算法时，如果在EOS空制台中多次输入“ds”命令，调度的顺序会发生变化，说明造成这种现象的原因(提示：注意这两种算法使用的全局变量)。尝试修改源代码，使这两种算法在多次执行时，都能确保调度的顺序一致(提示：可以参考io/block.c文件中lopReceiveRequest函数和lopProcessNextRequest函数判断磁盘调度算法开始工作和结束工作的方法)。答：Scanlnside是一个全局变量，当第一次执行“ds”命令时，调用IopDiskSchedule函数，ScanInside被修改了一次，再次执行“ds”命令时，Scan

11、Inside不会被重置，因此输出的结果会不一样。只需在for循环结束后添加如下代码，就能确保调度的顺序一致。图3.3.6(6)尝试在io/block.c文件中定义一个全局的函数指针变量DiskScheduleFunc,该函数指针初始指向实现了FCFS算法的IopDiskSchedule函数。修改io/block.c文件中的IopProcessNextRequest函数，在该函数中不再直接调用IopDiskSchedule函数,而是调用函数指针DiskScheduleFunc指向的磁盘调度算法函数；ke/sysproc.c文件中的ConsoleCmdDiskSchedule函数中也不再直接调用I

12、opDiskSchedule函数，也要修改为调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。最后，添加一个控制台命令"sstf"，该命令使函数指针DiskScheduleFunc指向实现了SSTF算法的函数。这样，在EOS启动后默认会执行FCFS算法，执行控制台命令“sstf”后，会执行SSTF算法。按照这种方式依次实现“fcfs”、“scan”、“cscan”和“nstepscan”命令。说明这种在EOSg行时动态切换磁盘调度算法的好处。答：首先在block.c中定义一个全局的函数指针变量DiskScheduleFunc。图3.3.7修改IopProc

13、essNextRequest函数和ConsoleCmdDiskSchedule函数，使其不再直接调用IopDiskSchedule函数而是调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。图3.3.8调用函数前先声明。图3.3.9添加一个控制台命令“sstf"，该命令使函数指针DiskScheduleFunc指向实现了SSTF算法的函数。验证结果如下图所示。(7)分析已经实现的各种磁盘调度算法的优缺点，尝试实现更多其它的磁盘调度算法。答：先来先服务算法是一种比较简单的磁盘调度算法，它根据进程请求访问磁盘的先后次序进行调度，此算法的优点是公平、简单，且每个进程的请求都

14、能依次得到处理，不会出现某一进程的请求长期得不到满足的情况，在对磁盘的访问请求比较多的情况下，致使平均寻道时间可能较长；最短寻道时间优先算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短，其缺点是在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟；扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向，此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆

15、动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道；循环扫描算法是对扫描算法的改进，如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少；N-Step-SCAN算法是扫描算法和先来先服务算法的一个综合算法，将请求队列分成若干个长度为N的子队列，调度程序按照FCFS原则依次处理这些子队列，而每处理一个子队列时，又是按照SCANT法，所以它是一种性能比较平均的算法。(6)EOS在块设备层实现了磁盘调度算法后，由于请求队列中的请求一定是被逐个处理的，所以并发的多个线程已经可以互斥的访问磁盘上的数据，那为什么在lopReadWriteSector函数中还要

16、使用磁盘设备的互斥信号量进行互斥呢？(提示：如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据，是否需要对该线程进行磁盘调度？该线程是否要与其它并发访问磁盘设备的线程进行互斥？)答：如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据，那这个线程是不需要进行磁盘调度的，所以不会进入请求队列，但该线程同样需要与其它并发访问磁盘设备的线程进行互斥，这时就需要使用磁盘设备的互斥信号量进行互斥。4.源程序并附上注释(1)改写scant法BOOLScanInside=TRUE;PREQUESTIopDiskSchedule(VOID)PLIST_ENTRYpListEntry;PREQ

17、UESTpRequest;PREQUESTINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0xFFFFFFFF;ULONGOutsideShortestDistance=0xFFFFFFFF;PREQUESTpNextRequest=NULL;/需要遍历请求队列一次或两次for(pListEntry=RequestListHead.Next;/请求队列中的第一个请求是链表头指向的下一个请求。pListEntry!=&RequestListHead;/遍历到请求

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

19、<InsideShortestDistance)(/记录向内移动距离最短的线程InsideShortestDistance=Offset;INpNextRequest=pRequest;elseif(Offset<0&&-Offset<OutsideShortestDistance)(/记录向外移动距离最短的线程OutsideShortestDistance=-Offset;OUTpNextRequest=pRequest;/判断磁头移动方向，若向内移动if(ScanInside)(/判断是否有向内移动的线程if(INpNextRequest)(/有则选择该线

20、程returnINpNextRequest;else(/没有则修改磁头方向，选择向外移动距离最短的线程ScanInside=!ScanInside;returnOUTpNextRequest;)/如果向外移动else(/判断是否有向外移动的线程if(OUTpNextRequest)(/有则选择该线程returnOUTpNextRequest;)else(/没有则修改词头方向，选择向内移动距离最短的线程ScanInside=!ScanInside;returnINpNextRequest;)RETURN:returnpNextRequest;)(2)编写循环扫描(CSCAN磁盘调度算法PREQU

21、ESTIopDiskSchedule(VOID)PLIST_ENTRYpListEntry;PREQUESTpRequest;PREQUESTINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0xFFFFFFFF;ULONGOutsideShortestDistance=0x00000000;PREQUESTpNextRequest=NULL;/请求队列中的第/向的下一个请/需要遍历请求队列一次或两次for(pListEntry=RequestListHead.Next

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

23、quest;gotoRETURN;elseif(Offset>0&&Offset<InsideShortestDistance)/记录向内移动距离最短的线程InsideShortestDistance=Offset;INpNextRequest=pRequest;elseif(Offset<0&&-Offset>OutsideShortestDistance)/记录向外移动距离最长的线程OutsideShortestDistance="Offset;OUTpNextRequest=pRequest;)/需要向内移动的线程是否存在

24、if(INpNextRequest)(/存在则返回向内移动的请求returnINpNextRequest;)else(/否则返回向外移动的请求returnOUTpNextRequest;)RETURN:returnpNextRequest;)(3)编写N-Step-SCAN磁盘调度算法/N-Step-SCAN磁盘调度算法使用的子队列长度N#defineSUB_QUEUE_LENGTH6/记录N-Step-SCAN磁盘调度算法第一个子队列剩余的长度/子队列初始长度为N,每执行一次磁盘调度算法会从子队列中移除一个请求，子队列/长度就要减少1,待长度变为0时，再将长度重新变为N,开始处理下一个子队列

25、。ULONGSubQueueRemainLength=SUB_QUEUE_LENGTH;/扫描算法中磁头移动的方向。操作系统启动时初始化为磁头向内移动。/TRUE,磁头向内移动，磁道号增加。/FALSE,磁头向外移动，磁道号减少。BOOLScanInside=TRUE;PREQUESTIopDiskSchedule(VOID)PLIST_ENTRYpListEntry;PREQUESTpRequest;PREQUESTINpNextRequest=NULL;PREQUESTOUTpNextRequest=NULL;LONGOffset;ULONGInsideShortestDistance=0

26、xFFFFFFFF;ULONGOutsideShortestDistance=0xFFFFFFFF;PREQUESTpNextRequest=NULL;ULONGcounter;/需要遍历请求队列一次或两次/计数器记录一个子队列剩余的长度counter=SubQueueRemainLength;/没调度一次子队列剩余的长度减SubQueueRemainLength-;/如果子队列剩余的长度为，则重置为子队列原长度if(SubQueueRemainLength=0)SubQueueRemainLength=SUB_QUEUE_LENGTH;for(pListEntry=RequestListHe

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

28、set)/如果线程要访问的磁道与当前磁头所在磁道相同，可立即返回。pNextRequest=pRequest;returnpNextRequest;elseif(Offset>0&&Offset<InsideShortestDistance)/记录向内移动距离最短的线程InsideShortestDistance=Offset;INpNextRequest=pRequest;elseif(Offset<0&&-Offset<OutsideShortestDistance)/记录向外移动距离最短的线程OutsideShortestDista

29、nce=-Offset;OUTpNextRequest=pRequest;counter-;if(ScanInside)if(INpNextRequest)(returnINpNextRequest;)else(ScanInside=!ScanInside;returnOUTpNextRequest;)else(if(OUTpNextRequest)(returnOUTpNextRequest;)else(ScanInside=!ScanInside;returnINpNextRequest;)5.程序运行时的初值和运行结果(1)验证先来先服务(FCFS磁盘调度算法新建一个EOSKernel项

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