操作系统实验磁盘调度

操作系统 实 验 报 告

课程名称 实验项目名称 学号 姓名 学生所在学院 实验室名称地点

操作系统实验 磁盘调度算法 课程编号 0906553 年级 专业 2012 计算机科学与技术 计算机科学与技术 指导教师 初妍 21B475 哈尔滨工程大学 计算机科学与技术学院

第六讲 磁盘调度算法

一、实验概述

1. 实验名称

磁盘调度算法 2. 实验目的

（1）通过学习EOS 实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机；

（2）观察 EOS 实现的FCFS、SSTF和 SCAN磁盘调度算法，了解常用的磁盘调度算法；

（3）编写 CSCAN和 N-Step-SCAN磁盘调度算法，加深对各种扫描算法的理解。 3. 实验类型

验证性和设计性实验 4. 实验内容

（1）验证先来先服务（FCFS）磁盘调度算法； （2）验证最短寻道时间优先（SSTF）磁盘调度算法； （3）验证SSTF算法造成的线程“饥饿”现象； （4）验证扫描（SCAN）磁盘调度算法； （5）改写SCAN算法。

二、实验环境

在OS Lab实验环境的基础上，利用EOS操作系统，由汇编语言及C语言编写代码，对需要的项目进行生成、调试、查看和修改，并通过EOS应用程序使内核从源代码变为可以在虚拟机上使用。 三、实验过程

1. 设计思路和流程图 （1）改写SCAN算法

在已有 SCAN 算法源代码的基础上进行改写，要求不再使用双重循环，而是只遍历一次请求队列中的请求，就可以选中下一个要处理的请求。算法流程图如下图所示。

1

图 3.1.1 SCAN算法IopDiskSchedule函数流程图

（2）编写循环扫描（CSCAN）磁盘调度算法

在已经完成的SCAN算法源代码的基础上进行改写，不再使用全局变量ScanInside确定磁头移动的方向，而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时，磁头立即移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环，进行扫描。算法流程图如下图所示。

图 3.1.2 CSCAN算法IopDiskSchedule函数流程图

（3）编写N-Step-SCAN磁盘调度算法

在已经完成的 SCAN 算法源代码的基础上进行改写，将请求队列分成若干个长度为 N 的子队列，调度程序按照 FCFS原则依次处理这些子队列，而每处理一个子队列时，又是按照SCAN算法。算法流程图如下图所示。

2

图 3.1.3 N-Step-SCAN算法IopDiskSchedule函数流程图

2. 算法实现

（1）改写SCAN算法

在一次遍历中，不再关心当前磁头移动的方向，而是同时找到两个方向上移动距离最短的线程所对应的请求，这样就不再需要遍历两次。 在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，可以将偏移分为三种类型：偏移为0， 表示线程要访问的磁道与当前磁头所在磁道相同，此情况应该优先被调度，可立即返回该线程对应的请求的指针；偏移大于 0，记录向内移动距离最短的线程对应的请求；偏移小于 0，记录向外移动距离最短的线程对应的请求。循环结束后，根据当前磁头移动的方向选择同方向移动距离最短的线程，如果在同方向上没有线程，就变换方向，选择反方向移动距离最短的线程。

（2）编写循环扫描（CSCAN）磁盘调度算法

由于规定了磁头只能从外向内移动，所以在每次遍历中，总是同时找到向内移动距离最短的线程和向外移动距离最长的线程。注意，与 SCAN 算法查找向外移动距离最短线程不同，这里查找向外移动距离最长的线程。在开始遍历前，可以将用来记录向外移动最长距离的变量赋值为0。在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，同样可以将偏移分为三种类型：偏移为 0，表示线程要访问的磁道与当前磁头所在磁道相同，此情况应优先被调度，可立即返回

3

该线程对应的请求的指针；偏移大于 0，记录向内移动距离最短的线程对应的请求；偏移小于 0，记录向外移动距离最长的线程对应的请求。循环结束后，选择向内移动距离最短的线程，如果没有向内移动的线程，就选择向外移动距离最长的线程。

（3）编写N-Step-SCAN磁盘调度算法

在 block.c 文件中的第360 行定义了一个宏 SUB_QUEUE_LENGTH，表示子队列的长度（即N 值 ）。目前这个宏定义的值为6。在第 367行定义了一个全局变量SubQueueRemainLength，表示第一个子队列剩余的长度，并初始化其值为SUB_QUEUE_LENGTH。在执行 N-Step-SCAN算法时，要以第一个子队列剩余的长度做为计数器，确保只遍历第一个子队列剩余的项。所以，结束遍历的条件就既包括第一个子队列结束，又包括整个队列结束（如果整个队列的长度小于第一个子队列剩余的长度）。注意，不要直接使用第一个子队列剩余的长度做为计数器，可以定义一个新的局部变量来做为计数器。按照 SCAN 算法从第一个子队列剩余的项中选择一个合适的请求。最后，需要将第一个子队列剩余长度减少1（SubQueueRemainLength减少1），如果第一个子队列剩余长度变为 0，说明第一个子队列处理完毕，需要将子队列剩余的长度重新变为 N（SubQueueRemainLength 重新赋值为SUB_QUEUE_LENGTH），从而开始处理下一个子队列。

3. 需要解决的问题及解答

（1）实验指导P176-3.2验证先来先服务（FCFS）磁盘调度算法，要求请给出在“输出”窗口中的结果。

答：先来先服务（FCFS）磁盘调度算法在“输出”窗口中的结果如下图所示。

4

图 3.3.1

（2）实验指导P177-3.3验证验证最短寻道时间优先（SSTF）磁盘调度算法，要求请给出在“输出”窗口中的结果。

答：最短寻道时间优先（SSTF）磁盘调度算法在“输出”窗口中的结果如下图所示。

图 3.3.2

（3）实验指导P178-3.4验证SSTF算法造成的线程“饥饿”现象，要求请给出在“输出”窗口中的结果。

答：SSTF算法造成的线程“饥饿”现象在“输出”窗口中的结果如下图所示。

5

图 3.3.3

（4）实验指导P179-3.5验证扫描（SCAN）磁盘调度算法，要求在非饥饿（即《实验指导》P176-3.2节中的数据）和饥饿（即《实验指导》P178-3.4节中的数据）请给出在“输出”窗口中的结果，并且要求在每次输入两次“ds”命令（注意不要连续输入，要等第一次“ds”命令执行完，再输入第二次“ds”命令），分析结果为什么不同。

答：在非饥饿情况下，“输出”窗口中的结果如下图所示。

图 3.3.4

在饥饿情况下，“输出”窗口中的结果如下图所示。

6

图 3.3.5

ScanInside是一个全局变量，当第一次执行“ds”命令时，调用IopDiskSchedule 函数，ScanInside被修改了一次，再次执行“ds”命令时，ScanInside不会被重置，因此输出的结果会不一样。

（5）在执行 SCAN、N-Step-SCAN 磁盘调度算法时，如果在EOS控制台中多次输入“ds”命令，调度的顺序会发生变化，说明造成这种现象的原因（提示：注意这两种算法使用的全局变量）。尝试修改源代码，使这两种算法在多次执行时，都能确保调度的顺序一致（提示：可以参考 io/block.c 文件中IopReceiveRequest 函数和 IopProcessNextRequest 函数判断磁盘调度算法开始工作和结束工作的方法）。

答：ScanInside是一个全局变量，当第一次执行“ds”命令时，调用IopDiskSchedule 函数，ScanInside被修改了一次，再次执行“ds”命令时，ScanInside不会被重置，因此输出的结果会不一样。只需在for循环结束后添加如下代码，就能确保调度的顺序一致。

图 3.3.6

7

（6）尝试在 io/block.c 文件中定义一个全局的函数指针变量 DiskScheduleFunc，该函数指针初始指向实现了 FCFS 算法的 IopDiskSchedule 函数。修改 io/block.c 文件中的 IopProcessNextRequest 函数，在该函数中不再直接调用 IopDiskSchedule 函数，而是调用函数指针 DiskScheduleFunc 指向的磁盘调度算法函数；ke/sysproc.c 文件中的 ConsoleCmdDiskSchedule 函数中也不再直接调用IopDiskSchedule函数，也要修改为调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。最后，添加一个控制台命令“sstf”，该命令使函数指针 DiskScheduleFunc 指向实现了 SSTF 算法的函数。这样，在 EOS启动后默认会执行FCFS 算法，执行控制台命令“sstf”后，会执行SSTF算法。按照这种方式依次实现“fcfs”、“scan”、“cscan”和“nstepscan”命令。说明这种在EOS运行时动态切换磁盘调度算法的好处。

答：首先在block.c 中定义一个全局的函数指针变量 DiskScheduleFunc。

图 3.3.7

修改IopProcessNextRequest 函数和ConsoleCmdDiskSchedule 函数，使其不再直接调用 IopDiskSchedule 函数而是调用函数指针DiskScheduleFunc指向的磁盘调度算法函数。

图 3.3.8

调用函数前先声明。

图 3.3.9

8

添加一个控制台命令“sstf”，该命令使函数指针 DiskScheduleFunc 指向实现了 SSTF 算法的函数。

图 3.3.10

验证结果如下图所示。

图 3.3.11

图 3.3.12

9

（7）分析已经实现的各种磁盘调度算法的优缺点，尝试实现更多其它的磁盘调度算法。

答：先来先服务算法是一种比较简单的磁盘调度算法，它根据进程请求访问磁盘的先后次序进行调度，此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况，在对磁盘的访问请求比较多的情况下，致使平均寻道时间可能较长；最短寻道时间优先算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短，其缺点是在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟；扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向，此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道；循环扫描算法是对扫描算法的改进，如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少；N-Step-SCAN算法是扫描算法和先来先服务算法的一个综合算法，将请求队列分成若干个长度为 N 的子队列，调度程序按照 FCFS原则依次处理这些子队列，而每处理一个子队列时，又是按照SCAN算法，所以它是一种性能比较平均的算法。

（6）EOS 在块设备层实现了磁盘调度算法后，由于请求队列中的请求一定是被逐个处理的，所以并发的多个线程已经可以互斥的访问磁盘上的数据，那为什么在 IopReadWriteSector 函数中还要使用磁盘设备的互斥信号量进行互斥呢？（提示：如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据，是否需要对该线程进行磁盘调度？该线程是否要与其它并发访问磁盘设备的线程进行互斥？）

答：如果一个线程只是要获取磁盘设备的状态而不是要访问磁盘上的数据，那这个线程是不需要进行磁盘调度的，所以不会进入请求队列，但该线程同样需要与其它并发访问磁盘设备的线程进行互斥，这时就需要使用磁盘设备的互斥信号量进行互斥。

10

4. 源程序并附上注释 （1）改写SCAN算法

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

11

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

//判断磁头移动方向，若向内移动 if( ScanInside) {

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

12

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

RETURN: return pNextRequest; }

（2）编写循环扫描（CSCAN）磁盘调度算法

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;

13

// // 需要遍历请求队列一次或两次 // 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 > 0 && Offset < InsideShortestDistance ) { // // 记录向内移动距离最短的线程 // InsideShortestDistance = Offset; INpNextRequest = pRequest; } else if ( Offset < 0 && -Offset > OutsideShortestDistance ) { // // 记录向外移动距离最长的线程 //

14

OutsideShortestDistance = -Offset; OUTpNextRequest = pRequest; } } //需要向内移动的线程是否存在 if( INpNextRequest ) { //存在则返回向内移动的请求 return INpNextRequest; } else { //否则返回向外移动的请求 return OUTpNextRequest; } RETURN: return pNextRequest;

}

（3）编写N-Step-SCAN磁盘调度算法

//

// N-Step-SCAN 磁盘调度算法使用的子队列长度N //

#define SUB_QUEUE_LENGTH 6 //

// 记录N-Step-SCAN 磁盘调度算法第一个子队列剩余的长度。

// 子队列初始长度为N，每执行一次磁盘调度算法会从子队列中移除一个请求，子队列 // 长度就要减少1，待长度变为0 时，再将长度重新变为N，开始处理下一个子队列。 //

ULONG SubQueueRemainLength = SUB_QUEUE_LENGTH; //

// 扫描算法中磁头移动的方向。操作系统启动时初始化为磁头向内移动。 // TRUE，磁头向内移动，磁道号增加。 // FALSE，磁头向外移动，磁道号减少。

15

//

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; ULONG counter; // // 需要遍历请求队列一次或两次 // //计数器记录一个子队列剩余的长度 counter = SubQueueRemainLength; //没调度一次子队列剩余的长度减 SubQueueRemainLength--; //如果子队列剩余的长度为，则重置为子队列原长度 if(SubQueueRemainLength == 0) SubQueueRemainLength = SUB_QUEUE_LENGTH; for (pListEntry = RequestListHead.Next; // 请求队列中的第一个请求是链表头指向的下一个请求。 pListEntry != &RequestListHead && counter>0; // 遍历到请求队列头时结束循环或子队列结束。 pListEntry = pListEntry->Next) { // // 根据链表项获得请求的指针 // pRequest = CONTAINING_RECORD(pListEntry, REQUEST, ListEntry); //

16

表示）

// 计算请求对应的线程所访问的磁道与当前磁头所在磁道的偏移（方向由正负//

Offset = pRequest->Cylinder - CurrentCylinder;

if (0 == Offset) { // // 如果线程要访问的磁道与当前磁头所在磁道相同，可立即返回。 // pNextRequest = pRequest; return pNextRequest;

} else if ( Offset > 0 && Offset < InsideShortestDistance ) { // // 记录向内移动距离最短的线程 // InsideShortestDistance = Offset; INpNextRequest = pRequest;

} else if ( Offset < 0 && -Offset < OutsideShortestDistance ) { // // 记录向外移动距离最短的线程 // OutsideShortestDistance = -Offset; OUTpNextRequest = pRequest; }

counter--; }

if( ScanInside ) { if(INpNextRequest) { return INpNextRequest; } else {

17

}

ScanInside = !ScanInside; return OUTpNextRequest; } } else { if(OUTpNextRequest) { return OUTpNextRequest; } else { ScanInside = !ScanInside; return INpNextRequest; } }

5. 程序运行时的初值和运行结果

（1）验证先来先服务（FCFS）磁盘调度算法

新建一个 EOS Kernel项目，双击ke文件夹中的sysproc.c文件，阅读函数ConsoleCmdDiskSchedule，目前该函数使磁头初始停留在磁道10，其它被阻塞的线程依次访问磁道8、21、9、78、0、41、10、67、12、10。如下图所示。

图 3.5.1

按F5调试项目，待 EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。控制台和输出窗口显示内容如下图所示。

18

图 3.5.2

图 3.5.3

对比EOS控制台和“输出”窗口中的内容，可以发现FCFS算法是根据线程访问磁盘的先后顺序进行调度的。

（2）验证最短寻道时间优先（SSTF）磁盘调度算法

使用 sstf.c 文件中 IopDiskSchedule 函数的函数体，替换 block.c 文件中 IopDiskSchedule 函数的函数体。按 F7生成项目，然后按F5 启动调试。待 EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。输出窗口输出结果如下图所示。

19

图 3.5.4

（3）验证SSTF算法造成的线程“饥饿”现象

修改sysproc.c文件ConsoleCmdDiskSchedule函数中的源代码，仍然使磁头初始停留在磁道10，而让其它线程依次访问磁道78、21、9、8、11、41、10、67、12、10。按 F7生成项目，然后按F5 启动调试。 待 EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。输出窗口输出结果如下图所示。

图 3.5.5

（4）验证扫描（SCAN）磁盘调度算法

20

使用 scan.c 文件中 IopDiskSchedule 函数的函数体，替换 block.c 文件中 IopDiskSchedule 函数的函数体。按 F7生成项目，然后按F5 启动调试。 待 EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。输出窗口输出内容如下图所示。

图 3.5.6

再次输入“ds”命令，输出窗口输出内容如下图所示。

图 3.5.7

（5）改写SCAN算法

修改完代码后，按 F7生成项目，然后按F5 启动调试。待 EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。输出窗口输出内容如下图所示。

图 3.5.8

21

调试结果与预期一致，说明算法改写正确。

图 3.5.9

（6）编写循环扫描（CSCAN）磁盘调度算法

修改完代码后，按 F7生成项目，然后按F5 启动调试。待 EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。输出窗口输出内容如下图所示。

图 3.6.10

调试结果与预期一致，说明算法改写正确

图 3.5.11

22

（7）验证SSTF、SCAN 及 CSCAN算法中的“磁臂粘着”现象

修改sysproc.c文件ConsoleCmdDiskSchedule函数中的源代码，仍然使磁头初始停留在磁道10，而让其它线程依次访问磁道78、10、10、10、10、10、10、10、10、10。 分别使用SSTF、SCAN 和CSCAN算法调度这组数据。输出窗口输出内容如下图所示。

SSTF“磁臂粘着”现象：

图 3.5.12

SCAN“磁臂粘着”现象：

图 3.5.13

CSCAN“磁臂粘着”现象：

图 3.5.14

23

（8）编写N-Step-SCAN磁盘调度算法

修改完代码后，按 F7生成项目，然后按F5 启动调试。待 EOS启动完毕，在EOS控制台中输入命令“ds”后按回车。输出窗口输出内容如下图所示。

图 3.5.15

调试结果与预期一致，说明算法改写正确。

图 3.5.16

四、实验体会

本实验通过学习EOS实现磁盘调度算法的机制，对磁盘调度算法执行的条件和时机有了一定的掌握。同时通过实验操作观察了EOS实现的FCFS、SSTF和SCAN磁盘调度算法，了解了常用的磁盘调度算法。本次实验设计部分不是太难，主要是针对不同磁盘调度算法的特点改写代码，通过设计SCAN、CSCAN和N-STEP-SCAN算法，也让我感受到了每个算法所具有的特点。本次实验也是最后一次实验，通过本学期的实验学习对操作系统的知识有了更切实的了解，也让自己的编程能力有所锻炼。最后感谢王老师一学期以来的指导，让我在很多细节的方面能有所认识和提高。

24

本文来源：https://www.bwwdw.com/article/k6y.html