10磁盘调度算法

1、操作系统实验报告实验题目磁盘调度算法学生姓名lee学 号专业班级指导教师院系名称计算机与信息学院2017年 10 月 30 日11 扫描 FAT12 文件系统管理的软盘1. 实验目的与要求通过学习EOS；现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机。观察EOS；现的FCFS SST舜口 SCA肱盘调度算法，了解常用的磁盘调度算法。编写CSCANN-Step-SCANW盘调度算法，加深对各种扫描算法的理解。2. 实验原理阅读本书第7章的第7.5 节， 并结合 io/block.c 文件中的 IopReceiveRequest 函数 （第 67行） 、IopProcessNextRequ

2、est 函数（第 181 行）、 IopDiskSchedule 函数（第378行）和IopReadWriteSector函数（第263行）的源代码，理解 EOS!如何实现磁盘调度算法的。阅读 ke/sysproc.c 文件中第 580 行的 ConsoleCmdDiskSchedule 函数及其调用的其它函数 （包括第 536 行的 NewThreadAccessCylinder 函数和第 499 行的 AccessCylinderThread 函数） ， 学 习 EOS 是如何测试磁盘调度算法的，并体会这种测试方法的优缺点。3. 实验内容6553.1 准备实验按照下面的步骤准备实验：1.

3、启动 OS Lab。2. 新建一个 EOS Kernel 项目。3.2 验证先来先服务（FCF9磁盘调度算法 按照下面的步骤进行验证：1 .在 项目管理器”窗口中双击ke文件夹中的sysproc.c文件，打开此文件。2 .在sysproc.c文件的第580行找到控制台命令ds”对应的函数 ConsoleCmdDiskSchedule 。“ds” 命令专门用来测试磁盘调度算法。阅读该函数中的源代码， 目前该函数使磁头初始停留在磁道 10，其它被阻塞的线程依次访问磁道8、 21、 9、 78、 0、 41、 10、 67、 12、 10。3 . 打开 io/block.c 文件，在第378行找到磁

4、盘调度算法函数IopDiskSchedule 。阅读该函数中的源代码，目前此函数实现了 FCFS1盘调度算法，其流程图可以参见图 18-1。4 .按F7生成项目，然后按F5启动调试。5 .待EOSB动完毕，在EO醛制台中输入命令 ds”后按回车。在EO醛制台中会首先显示磁头的起始位置是10磁道，然后按照线程被阻塞的顺序依次显示线程的信息（包括线程ID和访问的磁道号）。磁盘调度算法执行的过程中，在OS Lab的 输出 ” 窗口中也会首先显示磁头的起始位置， 然后按照线程被唤醒的顺序依次显示线程信息 （包 括线程 ID 、 访问的磁道号、磁头移动的距离和方向），并在磁盘调度结束后显示此次调度的统计

5、信息（包括总寻道数、寻道次数和平均寻道数）。对比EOS!制台和 输出”窗口中的内容，可以发现FCFS?法是根据线程访问磁盘的先后顺序进行调度的。图18-2显示了本次调度 执行时磁头移动的轨迹。可以在控制台中多次输入ds”命令，查看磁盘调度算法执行的情况。将 输出”窗口中的内容复制到一个文本文件中，然后结束此次调试。EOS操作系统实验教程北京海西慧学科技有限公司 177 lopDiskSchedule函数开始选择请求队列中的第一个请求返回选中的请求的指针注意，链表 头指向的下一个请求是请求队列中的第一个请求。注意.能表头指向的卜 二一个请求是清末队列申 "I的海一个请求.闻18-实现了

6、 FCFS算法儆lopDiskSchfdul#函效流程图18-2： FCFS算法诞头移动的轨遮f茗寻道数3珈寻道次数10平均寻追敝36）图1:实现了 FCFSf法的IopDiskSchedule函数流程图图2: FCFST法磁头移动的轨迹（总寻道数360寻道次数10平均寻道数36）3.3验证最短寻道时间优先（SSTF）磁盘调度算法使用OS Lab打开本实验文件夹中的 sstf.c文件（将sstf.c文件拖动到OS Lab窗口中释放即 可）。该文件提供的IopDiskSchedule函数实现了 SSTFB盘调度算法。在阅读此函数的源代 码的时，可以参考图18-3所示的流程图，并且应该特别注意下面

7、几点：变量Offset是有符号的长整型，用来表示磁头的偏移（包括距离和方向）。 Offset大于0时表示磁头向内移动（磁道号增加）；小于0时表示磁头向外移动（磁道号减少）；等于 0时表示磁头没有移动。而名称以Distance 结尾的变量都是无符号长整型，只表示磁头移动的距离（无方向）。所以在比较磁头的偏移和距离时，或者在将偏移赋值给距离时，都要 取偏移的绝对值（调用C库函数abs）。本实验在实现其它磁盘调度算法时也同样遵守此约定。在开始遍历之前，将最小距离（ ShortestDistance ）初始化为最大的无符号长整型数， 这样，第一次计算的距离一定会小于最小距离，从而可以使用第一次计算的距

8、离来再次初始化最小距离。本实验在实现其它磁盘调度算法时也同样使用了此技巧。按照下面的步骤进行验证：1 .使用sstf.c 文件中IopDiskSchedule 函数的函数体，替换block.c文件中IopDiskSchedule 函数的函数体。2 .按F7生成项目，然后按F5启动调试。3 .待EOSB动完毕，在EO醛制台中输入命令ds后按回车。物出调国且3 入* Disk schedule start working * Start Cylinder: 10TID31 Cylinder8 Offset: 2 TID32 Cylinder21 Offset： 13 +TID33 Cylinder

9、9 Offset: 12 -TID34 Cylinder78 Offset: 6g +TID35 Cylinder0 Offset： 78 -T1D36 Cylinder41 Offset: 41 +TID37 Cylinder10 Offset: 31 -TID38 Cylinder67 Offset ： 57 +T1D39 Cylinder12 Offset: 55 -TID40 Cylinder10 Offset: 2 -Total offset: 360 Transfer tiroes: 10 Average offset: 36卜*:* Disk schedule stop work

10、ing *对比EOSS制台和 输出 窗口中的内容（特别是线程 ID的顺序），可以发现，SSTFT法唤醒线程的顺序与线程被阻塞的顺序是不同的。图18-4显示了本次调度执行时磁头移动的轨迹。对比SSTFI法与FCFST法在 输出 窗口中的内容，可以看出，SSTFI法的平均寻道数明显低于FCFS?法。但是，SSTFT法能保证平均寻道数最少吗？在后面的实验中会进行验证。可以在控制台中多次输入ds命令，查看磁盘调度算法执行的情况。将 输出 窗口中的内容复制到一个文本文件中，然后结束此次调试。 OS Lab PC - Iicrosoft Vxrtual PC 2007Action Edit CD Flop

11、py K«lpCONSOLE-1 (Press CtrHFl*F8 to switch console window.) Me leone to EOS shell >dsStart Cylinder： 10TID： 31 Cylinder： 8TID： 32 Cylinder： 21TID： 33 Cylinder： 3TID： 34 Cylinder： 78TID： 35 Cylinder： 0TID： 36 Cylinder： 41TID： 37 Cylinder： 16TID： 38 Cylinder： 67TID: 33 Cylinder： 12TID： 40 Cyl

12、inder： 16谓试, 1333当Disk schedule Start Cylinder： 10| TID: 37 Cylinder: 10 TID: 40 Cylinder： 10start working *Offset: 0 =Offset: 0 =TID： 33 Cylinder：TID: 31 Cylinder：TID： 39 Cylinder：TID: 32 Cylinder：TID: 36 Cylinder:TID： 38 Cylinder：TID: 34 Cylinder：TID: 35 Cylinder：9 Offset： 1 -8 Offset： 1 -12 Offse

13、t： 4 +21 Offset： 9 +41 Offset: 20 +67 Offset: 26 +78 Offset: 11 + 0 Offset： 78 -Total offset： 150 Transfer times： 10 Average offset： 15* Disk schedule stop working *M >W何 百7B(ffl 15-31 实现了 5STF 算法的 mpDi.k5cli.dul函«（流程图图SSTF算法磁头移动的轨迹（总各道数150字道次数10平均寻道里15）图18-3:实现了 SSTFT法的lopDiskSchedule函数流程图图

14、18-4： SSTFI法磁头移动的轨迹（总寻道数150寻道次数10平均寻道数15）3.4 验证SSTFT法造成的线程 饥饿”现象使用SSTFT法时，如果不断有新线程要求访问磁盘， 而且其所要访问的磁道与当前磁头所在 磁道的距离较近，这些新线程的请求必然会被优先满足，而等待队列中一些老线程的请求就会被严重推迟，从而使老线程出现 饥饿”现象。按照下面的步骤进行实验，观察这个现象：1 .修改sysproc.c文件ConsoleCmdDiskSchedule函数中的源代码，仍然使磁头初始停留在 磁道10,而让其它线程依次访问磁道78、21、9、8、11、41、10、67、12、10。修改代码：2.61

15、4i615'6166176186196201621|622623|62 4l625|626i按F7生成项目,N ewT hr eadAcc e s 式y 1 i nder (StdH andl 岛 NeThreadAccessyl inder (Si dHandl e* N ewThreadAcc e ssCyl inder (St dHandl e, N ewThreadAcc e s ?yli nder (St dHandl e, N ewThreadAcee ssCyl inder (S t dHandl ef NewThreadAcc e ssCyl inder (S t dH

16、andl e, NewThrea'dAccessCylinder (StdHandle, MewThreadAccrsylinder(StdHandle? NewThrfadAccessCylinder(StdHandle, II ewThr ea dAcc e s sCy 1 inder (St dHandl j78). 21);9)； S)；ID； 41); 10); 67); 12); 1削/w *4 *CE rt-nf > I工ell11sju_ > |i 干e 使士_I f_I ll然后按F5启动调试。3.待EOSB动完毕，在EO的制台中输入命令 ds”后按回车。

17、将“输出”窗口中的内容复制到一个文本文件中，然后结束此次调试。将ConsoleCmdDiskSchedule函数中线程访问的磁道号恢复到本实验3.2中的样子，在后面的实 验中还要使用这些数据。-r-rrf-fti-*+* Disk schedule start werkinsTID: 37 blinderTID： 40 CylinderT1D: 33 Cylindtr 71D: 34 Cylinder ?D: 15 ylin Irr TID: 39 Cylinhr TIDi 32 Cylinder TID： 36 CylinderTID: 38 CylTID： 31 Cylinder10 Of

18、fset： 0 -10 Offsets 0 =9 Offset: I -E Offset ： 1 -11 Of furl: 3 +12 Offset: 1 421 Offset: 9 +Offset： 20 +6T Offset： E6 + ?B Offset: 11 +Stjrt ?yllnJrr： 1UTotal offset： 72 Transfer tines： 10 Average jffaet： 7D"k schedule stop norkin£ <»*查看 输出”窗口中显示的内容， 可以发现，虽然访问78号磁道的线程的请求第一个被放入请 求队

19、列，但却被推迟到最后才被处理，出现了 饥饿”现象。如果不断有新线程的请求到达并被优先满足，则访问78号磁道的线程的 饥饿”情况就会更加严重。* Disk schedule start working *Stiti Cylinder: 10TID: 47 Cylinder:TID: 50 Cylinder:TID: 43 Cylinder:TID: 41 Cylinder：TID： 49 Cylinder：TID: 42 Cylinder：TID： 46 Cylinder：TID: 48 Cylinder:TID： 44 Cylinder:TID: 45 Cylinder:ITotal offs

20、et： 15010 Offset: 0 二 10 Off sei: 0 二9 Offset: 1 - S Offset: 1 - 12 Offset: 4 + 21 Offset: 9 + 41 Offset： 20 + 67 Offset: 26 + 78 Offset: 11 + 0 Offset: 78 -Trinsfer 1ines：10 Average offset:153.5 验证扫描（SCAN磁盘调度算法又SSTFf法稍加改进后可以形成 SCANT法，可防止老线程出现 饥饿”现象。使用OSLab打开 本实验文件夹中的scan.c文件，该文件提供的lopDiskSchedule函数

21、实现了 SCA瞰盘调度算 法。在阅读此函数的源代码的时，应该特别注意下面几点：在block.c文件中的第374行定义了一个布尔类型的全局变量ScanInside ,用于表示扫描算法中磁头移动的方向。该变量值为TRUE寸表示磁头向内移动（磁道号增加）；值为 FALSE时表示磁头向外移动（磁道号减少）。该变量初始化为TRUE表示SCANT法第一次执行时，磁头向内移动。在scan.c文件的IopDiskSchedule函数中使用了双重循环。第一次遍历队列时，查找指定方向上移动距离最短的线程，如果在指定方向上已经没有线程，就变换方向，进行第二次遍历，同样是查找移动距离最短的线程。在这两次遍历中一定能找

22、到合适的线程。按照下面的步骤进行验证：1 .使用scan.c文件中IopDiskSchedule 函数的函数体，替换block.c文件中IopDiskSchedule 函数的函数体。2 .按F7生成项目，然后按F5启动调试。3 .待EOSB动完毕，在EO醛制台中输入命令ds后按回车。帏出* Disk schedule start marking *7*Slart Cylinder: 10TID: 37 Cylinder: 10 Offset: 0 =TID： 40 Cylinder： 10 Offset： 0 -TID: 39 Cylinder: 12 Offset; 2 +TID: 32 C

23、ylinder: 21 Offset： 9 +TID: 36 Cylinder: 41 Offset ： 20 可TID: 38 Cylinder: 6T Offset! 26 +TID： 34 Cylinder: 73 Offset: 11 +TID: 33 Cylinder: 9 Offset: 69 -TID: 31 Cylinder： 8 Offset: 1 -TID: 35 Cylinder： 0 Offset: 8 -,Total offset ： 1r非 Transfer times： 10 Average offset： 14TID:47 Cylinder10 Offset:

24、0 =TID50 Cylinder10 Offset: 0 二TID:43 Cylinder9 Offset: 1 -TID41 Cylinder8 Offset: 1 -TID45 Cylinder0 Offset: 8 -TID49 Cylinder12 Offset: 12 +TID.42 Cylinder21 Offset ： 9 +TID46 Cylinder41 Offset： 20 +TID48 Cylinder67 Offset： 26 +TID44 Cylinder78 Offset: 11 +* Disk schedule start working *Start Cyli

25、nder： 10Total offset： 83Transfer times： 10 Average offset： 8对比SCA醇法与SSTFT法在 输出 窗口中的内容，可以看出，SCANT法的平均寻道数有可 能小于SSTFT法，所以说SSTFI法不能保证平均寻道数最少。图18-5显示了本次调度执行时磁头移动的轨迹。尝试在控制台中多次输入ds命令，查看磁盘调度算法执行的情况，说明为什么线程调度的顺序会发生变化。将 输出 窗口中的内容复制到一个文本文件中，然后结束此次调试。图18-5: SCA醇法磁头移动的轨迹（总寻道数 146寻道次数10平均寻道数14）使用SCA醇法调度在本实验3.4中产生

26、 饥饿 现象的数据，验证SCA醇法能够解决 饥饿 现象，并将 输出 窗口中的内容保存到一个文本文件中。最后将ConsoleCmdDiskSchedule 函数中线程访问的磁道号恢复到本实验3.2 中的样子，在后面的实验中还要使用这些数据。3.6改写SCANT法3.6.1 要求在已有SCANT法源代码的基础上进行改写，要求不再使用双重循环，而是只遍历一次请求队列中的请求， 就可以选中下一个要处理的请求。 由于线程和请求总是一一对应的， 为了使后面的内容更加简单易懂，有时就不再区分这两个概念。3.6.2 提示1. 在一次遍历中，不再关心当前磁头移动的方向，而是同时找到两个方向上移动距离最短的线程所

27、对应的请求，这样就不再需要遍历两次。2. 在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，可以将偏移分为三种类型：偏移为0，表示线程要访问的磁道与当前磁头所在磁道相同，此情况应该优先被调度，可立即返回该线程对应的请求的指针；偏移大于0 ，记录向内移动距离最短的线程对应的请求；偏移小于0，记录向外移动距离最短的线程对应的请求。3. 循环结束后，根据当前磁头移动的方向选择同方向移动距离最短的线程，如果在同方向上没有线程， 就变换方向， 选择反方向移动距离最短的线程。 具体逻辑可以参见图 18-6 所示 的流程图。SCA题写代码：PREQUEST IopDiskSchedule( VOID )P

28、LIST_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; /请求队列中的第一个请求是链表头

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

30、回。pNextRequest = pRequest; goto RETURN; else if (Offset<InsideShortestDistance && Offset > 0) / 记录向内移动距离最短的线程InsideShortestDistance = Offset;INpNextRequest = pRequest; else if (-Offset < OutsideShortestDistance && Offset < 0) / 记录向外移动距离最短的线程OutsideShortestDistance = -Offs

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

32、离最短的线程 ScanInside =!ScanInside;return INpNextRequest; RETURN:return pNextRequest; 修改完SCANT法后车入“ ds”命令：DDDD-DDDDDD I I I- I 1 1 I I I ITTTTTTTTTT* Disk schedule start workingSi art Cylinder： 1037 Cylinder： 10 Offset： 0 =40 Cylinder： 10 Offset： 0 39 Cylinder: 12 Offset; 2 +32 Cylinder: 21 Offset: 9 +3

33、6 Cylinder: 41 Offset: 20 +38 Cylinder： 67 Offset： 26 +34 Cylinder； 78 Offset; 11 +33 Cylinder: 9 Offset: 69 -31 Cylinder： E Offset： 1 -35 Cylinder： 0 Offset： 8 -Total offset： 146 Transfer times： 10 Average offset： 143.6.3测试方法使用本实验3.2中的数据进行测试，确保调度的结果与图18-5中显示的一致，也可以多准备几组测试数据，保证改写的SCANT法是正确的。测试成功后，将改

34、写的SCANT法源代码备份。循环结束:同酎记 录了两个方向上杼 动距离短的战程图18-6:循环结束后，根据磁头移动方向选择合适线程的流程图3.7编写循环扫描(CSCAN磁盘调度算法3.7.1 要求在已经完成的SCAN?法源代码的基础上进行改写，不再使用全局变量ScanInside确定磁头移 动的方向，而是规定磁头只能从外向内移动。 当磁头移动到最内的被访问磁道时， 磁头立即 移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环，进行扫描。由于磁头移动的方向被固定，也就不需要根据磁头移动的方向进行分类处理，所以CSCAN法的源代码会较SCANT法更加简单。3.7.2 提示1 .由于规定

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

36、移动的线程，就选择向外移 动距离最长的线程。CSCA修改代码：PREQUEST IopDiskSchedule( VOID ) PLIST_ENTRY pListEntry;PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL;LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0x00000000;PREQUEST pNextRequest = NULL;/ 需要遍历

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

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

39、; Offset < 0) / 记录向外移动距离最短的线程OutsideShortestDistance = -Offset;OUTpNextRequest = pRequest;/ 需要向内移动的线程是否存在if(INpNextRequest)/ 存在则返回向内移动的请求return INpNextRequest; else / 没有则返回向外移动的请求return OUTpNextRequest;RETURN: return pNextRequest;启动修改后的程序，输入“ ds ”命令：* Disk scheduleStart Cylinder: 10start working

40、*TID TID TID TID TID TID TID TID TID TID37403932363834353133Cylinder Cylinder Cylinder Cyl i nder Cylinder Cylinder Cyl inder Cylinder Cylinder CylinderTotal offset: 155101012214167780 8 9 Offset: Offset ： ：Offset 1Offset:Offset 1 Offset: i Offset ： Offset：Offset: Offset:0 二0 =2 +9 +20 +26 +11 +78 -

41、8 +1 +Transfer times: 10 Average offset: 15+* Disk schedule stop working *3.7.3测试方法使用本实验3.2中的数据进行测试，确保调度的结果与图18-7中显示的一致。可以在控制台中多次输入ds”命令，查看磁盘调度算法执行的情况。测试成功后，将输出”窗口中的内容观察执行SSTF SCA阪CSCANT法时磁头移动的轨迹（图 18-4、图18-5和图18-7 ）,可以看到，在开始时磁头都停留在 10磁道不动，这就是 磁臂粘着”现象。为了更加明显的观察该现 象，按照下面的步骤进行实验：1.修改sysproc.c文件Console

42、CmdDiskSchedule函数中的源代码，仍然使磁头初始停留在磁道10,而让其它线程依次访问磁道78、10、10、10、10、10、10、10、10、10。NewThreadAccessCylinder (StdHandl e, 78);MewThreadAccessCyl inder (StdHandle, 10);NewThreadAccessCyl inder (StdHandle, 10);WewThreadAccessCylinder (StdHandl e3 10);NeffThrcadAccessCyl inder (StdHandle, 10);NewThreadAcces

43、sCylinder CStdHandle? 10);MewThreadAccessCylinder (StdRandle1 10);NewThreadAccessCyl inder (St dHandle, 10);MewThreadAccessCylinder tStdHandle, 10):NewThreadAccessCyl inder (St dHandle, 10);JF J2.分别使用SSTR SCAND CSCAN法调度这组数据。查看各种算法在 输出”窗口中显示的内容， 可以发现，虽然访问78号磁道的线程的请求第一个被放入请求队列，但却被推迟到最后才被处理，出现了磁臂粘着”现象。

44、将 输出“窗口中的内容复制到一个文本文件中后，将ConsoleCmdDiskSchedule函数中线程访问的磁道号恢复到本实验 3.2中的样子，在后面的实验中还要使用这些数据。SCANT法测试：* an-DDDDDnDDD* tlllll-IIIII* s T T T T T T _T T T T* *L10 Offset:78 Offset:I 二二二二二二二一二8 0000000006Total oftscT: 68* Disk schedule stooTiines ： 10 Average offset ： 6*4orkinst * * * *CSCAN算法测试:* Disk sche

45、duleStart Cylinder： 10:32 Cylinder: 1033 Cylinder: 1034 Cylinder: 1035 Cylinder： 1036 Cylinder: 1037 Cylinder： 1038 Cylinder: 1039 Cylinder: 1040 Cylinder： 1031 Cylinder： 78DDDDDDDDDDstart working *Offset Offset Offset Offset Offset Offset Offset Offset Offset Offset一二二二二-1T -= 0 0000000068Total off

46、set： 68 Transfer times： 10 Average offset： 6* Disk schedule stop working *SST嗡法测试:* Disk scheduleStart Cylinder: 10start working *DDDDDDDDDD32 Cylinder: 10 Offset0 =33 Cylinder: 10 Offset0 =34 Cylinder: 10 Offset0 =35 Cylinder: 10 Offset0 =36 Cylinder: 10 Offset0 =37 Cylinder: 10 Offset0 =38 Cylinde

47、r: 10 Offset0 =39 Cylin<ier: 10 Offset0 =40 Cylinder: 10 Offset0 =31 Cylinder 1 78 Offset68 +Total offset: 68Tresnsfer times 1 10 Average offset: 6* Disk schedule stop working *3.9编写N-Step-SCANB盘调度算法3.9.1 要求在已经完成的SCAN?法源代码的基础上进行改写，将请求队列分成若干个长度为 N的子队列， 调度程序按照FCFSM则依次处理这些子队列，而每处理一个子队列时，又是按照SCANT法。3

48、.9.2 提示1 .在block.c文件中的第360行定义了一个宏SUB_QUEUE_LENGTH示子队列的长度(即 N 值)。目前这个宏定义的值为 6。在第367行定义了一个全局变量 SubQueueRemainLength,表 示第一个子队列剩余的长度，并初始化其值为SUB_QUEUE_LENGTH2 .在执行N-Step-SCAN算法时，要以第一个子队列剩余的长度做为计数器，确保只遍历第一个子队列剩余的项。所以，结束遍历的条件就既包括第一个子队列结束，又包括整个队列结束(如果整个队列的长度小于第一个子队列剩余的长度)。注意，不要直接使用第一个子队列剩余的长度做为计数器，可以定义一个新的局

49、部变量来做为计数器。3 .按照SCANT法从第一个子队列剩余的项中选择一个合适的请求。最后，需要将第一个子 队列剩余长度减少1 (SubQueueRemainLength减少1),如果第一个子队列剩余长度变为0,说明第一个子队列处理完毕，需要将子队列剩余的长度重新变为N (SubQueueRemainLength重新赋值为SUB_QUEUE_LENGTH从而开始处理下一个子队列。ULONG SubQueueRemainLength = SUB_QUEUE_LENGTH;/扫描算法中磁头移动的方向。操作系统启动时初始化为磁头向内移动。/ TRUE ,磁头向内移动，磁道号增加。 FALSE ,磁头

50、向外移动，磁道号减少。BOOL ScanInside = TRUE; PREQUEST IopDiskSchedule( VOID ) PLIST_ENTRY pListEntry; PREQUEST pRequest;PREQUEST INpNextRequest = NULL;PREQUEST OUTpNextRequest = NULL; LONG Offset;ULONG InsideShortestDistance = 0xFFFFFFFF;ULONG OutsideShortestDistance = 0xFFFFFFFF;PREQUEST pNextRequest = NULL;

51、ULONG counter;/需要遍历请求队列一次或两次/计数器记录一个子队列剩余的长度 counter=SubQueueRemainLength ;/每调度一次子队列剩余的长度减一SubQueueRemainLength- ；/ 如果子队列剩余长度为0 ，则重置为子队列原长度if(SubQueueRemainLength=0)SubQueueRemainLength=SUB_QUEUE_LENGTH;for (pListEntry = RequestListHead.Next;/ 请求队列中的第一个请求是链表头指向的下一个请求。pListEntry != &RequestListHe

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

53、st = pRequest; goto RETURN; else if (Offset<InsideShortestDistance && Offset > 0) / 记录向内移动距离最短的线程InsideShortestDistance = Offset;INpNextRequest = pRequest;else if (-Offset < OutsideShortestDistance && Offset < 0) / 记录向外移动距离最短的线程OutsideShortestDistance = -Offset;OUTpNextRe

54、quest = pRequest; counter-; /判断磁头移动方向，若向内移动if(ScanInside) / 判断是否有向内移动的线程if(INpNextRequest)/有则原则该进程return INpNextRequest; else / 没有则修改磁头方向，选择向外移动距离最短的线程ScanInside=!ScanInside;return OUTpNextRequest; /如果向外移动else / 判断是否有向外移动的线程if(OUTpNextRequest) / 有则选择该进程return OUTpNextRequest; else / 没有则修改磁头的方向，选择向内移动距离最短的线程ScanInside =!ScanInside;return INpNextRequest; 3.9.3 测试方法使用本实验3.2 中的数据进行测试，确保调度的结果与图 18-8 中显示的一致。尝试在控制台中多次输入ds”命令，查看磁盘调度算法执行的情况，说明为什么调度的顺序会发生变化。将 “输出 ”窗口中的内容复制到