当前位置：文档之家 › 磁盘调度算法实验报告

磁盘调度算法实验报告

  • 格式：docx
  • 大小：21.26 KB
  • 文档页数：11

操作系统实验报告哈尔滨工程大学计算机科学与技术学院磁盘调度算法一.实验概述：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 ）改写SCAN 算法；7 ）编写循环扫描（CSCAN 磁盘调度算法；8 ）验证SSTF SCAN 及 CSCAF 算法中的“磁臂粘着”现象； 9 ）编写N-Step-SCAN 磁盘调度算法。

二.实验环境操作系统：wi ndows XP 编译器：Tevalaton OS Lab 语言：C 三•实验过程1.设计思路和流程图： SCAN 算法流程图： SSTF 算法的流程图： csAcr 流程图：-------------- 循环结束后移录的线程移YES 动距离最短的线程和向外 移动距离最长的线程Kernel 项目；2） 在 文件中找到控制台命令“ ds ”对应的函数 ConsoleCmdDiskSchedule 。

“ ds ” 命令专门用来测试磁盘调度算法。

阅读该函数中的源代码，目前该函数使磁头初始停留在磁道10 ,其它被阻塞的线程依次访问磁道 8、21、9、78、0、41、10、67、12、10;3） 打开io/ 文件，在第378行找到磁盘调度算法函数lopDiskSchedule 。

阅读该函数中的源代码，目前此函数实现了FCFS 磁盘调度算法，流程图如下：4） 生成项目，启动调试，待 EOS 启动完毕，在 EOS 控制台中输入命令“ ds ”后按 回车；在EOS 控制台中会首先显示磁头的起始位置是 10磁道，然后按照线程被阻塞的顺序依次显示线程的信息（包括线程ID 和访问的磁道号）。

磁盘调度算法执行的过程中， 在OS Lab的“输出”窗口中也会首先显示磁头的起始位置，然后按照线程被唤醒的N-S 选择向SC 移动距法调丿2.实离最短的线程顺序依次显示线程信息（包括线程ID、访问的磁道号、磁头移动的距离和方向），并在磁盘调度结束后显示此次调度的统计信息（包括总寻道数、寻道次数和平均寻道数）。

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

下图显示了本次调度执行时磁头移动的轨迹：5）打开文件，该文件提供的IopDiskSchedule 函数实现了SSTF 磁盘调度算法，其中应注意：①变量Ofset 是有符号的长整型，用来表示磁头的偏移（包括距离和方向）。

Ofset 大于0 时表示磁头向内移动（磁道号增加）；小于0 时表示磁头向外移动（磁道号减少）；等于0 时表示磁头没有移动。

而名称以“ Distance ”结尾的变量都是无符号长整型，只表示磁头移动的距离（无方向）。

所以在比较磁头的偏移和距离时，或者在将偏移赋值给距离时，都要取偏移的绝对值（调用 C 库函数abs ）。

本实验在实现其它磁盘调度算法时也同样遵守此约定；②在开始遍历之前，将最小距离（ShortestDistance ）初始化为最大的无符号长整型数，这样，第一次计算的距离一定会小于最小距离，从而可以使用第一次计算的距离来再次初始化最小距离。

本实验在实现其它磁盘调度算法时也同样使用了此技巧。

6）生成项目，启动调试，待EOS启动完毕，在EOS控制台中输入命令“ ds ”后按回车；对比EOS 控制台和“输出” 窗口中的内容（特别是线程ID 的顺序），可以发现，SSTF 算法唤醒线程的顺序与线程被阻塞的顺序是不同的。

图18-4 显示了本次调度执行时磁头移动的轨迹。

对比SSTF算法与FCFS算法在“输出”窗口中的内容，可以看出，SSTF 算法的平均寻道数明显低于FCFS 算法。

7）验证SSTF算法造成的线程“饥饿现象”，使用SSTF算法时，如果不断有新线程要求访问磁盘，而且其所要访问的磁道与当前磁头所在磁道的距离较近，这些新线程的请求必然会被优先满足，而等待队列中一些老线程的请求就会被严重推迟，从而使老线程出现“饥饿”现象。

8）修改文件ConsoleCmdDiskSchedule 函数中的源代码，仍然使磁头初始停留在磁道10，而让其它线程依次访问磁道78 、21、9、8、11、41、10、67、12、10，生成项目，启动调试，待EOS启动完毕，在EOS控制台中输入命令“ ds ”后按回车；查看“输出”窗口中显示的内容，可以发现，虽然访问78 号磁道的线程的请求第一个被放入请求队列，但却被推迟到最后才被处理，出现了“饥饿”现象。

如果不断有新线程的请求到达并被优先满足，则访问78 号磁道的线程的“饥饿”情况就会更加严重；修改访问磁道顺序：修改后执行“ ds ”命令的结果：多次输入“ ds”命令：9）对SSTF 算法稍加改进后可以形成SCAN 算法，可防止老线程出现“饥饿”现象。

打开文件，该文件提供的IopDiskSchedule 函数实现了SCAN 磁盘调度算法。

其中应注意下面几点：①在文件中的第374 行定义了一个布尔类型的全局变量ScanInside ，用于表示扫描算法中磁头移动的方向。

该变量值为TRUE 时表示磁头向内移动（磁道号增加）；值为FALSE时表示磁头向外移动（磁道号减少）。

该变量初始化为TRUE,表示SCAN算法第一次执行时，磁头向内移动；②在文件的IopDiskSchedule 函数中使用了双重循环。

第一次遍历队列时，查找指定方向上移动距离最短的线程，如果在指定方向上已经没有线程，就变换方向，进行第二次遍历，同样是查找移动距离最短的线程。

在这两次遍历中一定能找到合适的线程。

10)使用文件中IopDiskSchedule 函数的函数体，替换文件中IopDiskSchedule 函数的函数体，生成项目，启动调试，待EOS 启动完毕，在EOS 控制台中输入命令“ ds ”后按回车；对比SCAN算法与SSTF算法在“输出”窗口中的内容，可以看出，SCAN算法的平均寻道数有可能小于SSTF 算法，所以说SSTF 算法不能保证平均寻道数最少。

下图显示了本次调度执行时磁头移动的轨迹：11)改写SCAN算法，算法提示：①在一次遍历中，不再关心当前磁头移动的方向，而是同时找到两个方向上移动距离最短的线程所对应的请求，这样就不再需要遍历两次；②在计算出线程要访问的磁道与当前磁头所在磁道的偏移后，可以将偏移分为三种类型：偏移为0 ，表示线程要访问的磁道与当前磁头所在磁道相同，此情况应该优先被调度，可立即返回该线程对应的请求的指针；偏移大于0，记录向内移动距离最短的线程对应的请求；偏移小于0，记录向外移动距离最短的线程对应的请求；③循环结束后，根据当前磁头移动的方向选择同方向移动距离最短的线程，如果在同方向上没有线程，就变换方向，选择反方向移动距离最短的线程；流程如下所示：SCAN改写代码：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 = ; // 请求队列中的第一个请求是链表头指向的下一个请求。

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<InsideShortestDistance && Offset > 0) {// 记录向内移动距离最短的线程InsideShortestDistance = Offset; INpNextRequest = pRequest;} else if (-Offset < OutsideShortestDistance && Offset < 0) {// 记录向外移动距离最短的线程OutsideShortestDistance = -Offset;OUTpNextRequest = pRequest;}}// 判断磁头移动方向，若向内移动if(ScanInside){// 判断是否有向内移动的线程if(INpNextRequest){// 有则原则该进程return INpNextRequest;}else{// 没有则修改磁头方向，选择向外移动距离最短的线程ScanInside=!ScanInside;return OUTpNextRequest;}}// 如果向外移动else{// 判断是否有向外移动的线程if(OUTpNextRequest){// 有则选择该进程return OUTpNextRequest;}else{// 没有则修改磁头的方向，选择向内移动距离最短的线程ScanInside =!ScanInside;return INpNextRequest;}}RETURN:return pNextRequest;}修改完SCAN算法后输入“ ds ”命令：12) 在已经完成的SCAN 算法源代码的基础上进行改写，不再使用全局变量ScanInside 确定磁头移动的方向，而是规定磁头只能从外向内移动。

合集下载

操作系统磁盘调度算法实验报告及代码

操作系统磁盘调度算法实验报告及代码

操作系统磁盘调度算法实验报告及代码一、实验目的通过实验掌握磁盘调度算法的实现过程，了解各种不同磁盘调度算法的特点和优缺点，并比较它们的性能差异。

二、实验原理磁盘调度是操作系统中的重要内容，其主要目的是提高磁盘的利用率和系统的响应速度。

常见的磁盘调度算法有：FCFS（先来先服务）、SSTF （最短寻道时间）、SCAN（扫描）、C-SCAN（循环扫描）等。

三、实验过程1.编写代码实现磁盘调度算法首先，我们需要定义一个磁盘请求队列，其中存放所有的IO请求。

然后，根据所选的磁盘调度算法，实现对磁盘请求队列的处理和IO请求的调度。

最后，展示运行结果。

以FCFS算法为例，伪代码如下所示：```diskQueue = new DiskQueue(; // 创建磁盘请求队列while (!diskQueue.isEmpty()request = diskQueue.dequeue(; // 取出队列头的IO请求//处理IO请求displayResult(; // 展示运行结果```2.运行实验并记录数据为了验证各种磁盘调度算法的性能差异，我们可以模拟不同的场景，例如，随机生成一批磁盘IO请求，并使用不同的磁盘调度算法进行处理。

记录每种算法的平均响应时间、平均等待时间等指标。

3.撰写实验报告根据实验数据和结果，撰写实验报告。

实验报告通常包括以下内容：引言、实验目的、实验原理、实验步骤、实验结果、实验分析、结论等。

四、实验结果与分析使用不同的磁盘调度算法对磁盘IO请求进行处理，得到不同的实验结果。

通过对比这些结果，我们可以看出不同算法对磁盘IO性能的影响。

例如，FCFS算法对于请求队列中的请求没有排序，可能会导致一些请求等待时间过长。

而SSTF算法通过选择离当前磁道最近的请求进行处理，能够减少平均寻道时间，提高磁盘性能。

五、实验总结通过本次实验，我们学习了操作系统中磁盘调度算法的原理和实现过程。

不同的磁盘调度算法具有不同的优缺点，我们需要根据实际情况选择合适的算法。

操作系统课程设计磁盘调度报告

操作系统课程设计磁盘调度报告

题目：磁盘调度一．设计目的本课程设计是学习完《计算机操作系统》课程后，进行的一次全面的综合训练，通过课程设计，我们更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强了动手能力。

二．课程设计内容和要求编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度，要求设计主界面以灵活选择某算法，且以下算法都要实现：1、先来先服务算法（FCFS）2、最短寻道时间优先算法（SSTF）3、扫描算法（SCAN）4、循环扫描算法（CSCAN）三．算法及数据结构3.1算法的总体思想设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。

常用的分配策略有先请求先分配、优先级高者先分配等策略。

在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。

操作系统中，对磁盘的访问要求来自多方面，常常需要排队。

这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。

访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。

因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。

平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+……+Mi+……+MN）/N其中Mi为所需访问的磁道号所需移动的磁道数。

启动磁盘执行输入输出操作时，要把移动臂移动到指定的柱面，再等待指定扇区的旋转到磁头位置下，然后让指定的磁头进行读写，完成信息传送。

因此，执行一次输入输出所花的时间有：寻找时间——磁头在移动臂带动下移动到指定柱面所花的时间。

延迟时间——指定扇区旋转到磁头下所需的时间。

传送时间——由磁头进程读写完成信息传送的时间。

其中传送信息所花的时间，是在硬件设计就固定的。

而寻找时间和延迟时间是与信息在磁盘上的位置有关。

为了减少移动臂进行移动花费的时间，每个文件的信息不是按盘面上的磁道顺序存放满一个盘面后，再放到下一个盘面上。

实验报告六 磁盘调度算法

实验报告六 磁盘调度算法

实验报告六磁盘调度算法班级：软技2班学号：201467003084 姓名：刘道林一．实验内容：熟悉磁盘的结构以及磁盘的驱动调度算法的模拟，编程实现简单常用的磁盘驱动调度算法先来先服务（FIFO）、电梯调度算法、最短寻找时间优先算法、扫描（双向扫描）算法、单向扫描（循环扫描）算法等。

编程只需实现两个算法。

题目可以选取教材或习题中的相关编程实例。

编程语言建议采用c/c++或Java。

模拟程序鼓励采用随机数技术、动态空间分配技术，有条件的最好能用图形界面展现甚至用动画模拟。

实验性质：验证型。

二．实验目的和要求1）掌握使用一门语言进行磁盘驱动调度算法的模拟；2）编写程序将磁盘驱动调度算法的过程和结果能以较简明直观的方式展现出来。

三．实验原理、方法和步骤1. 实验原理磁盘驱动调度对磁盘的效率有重要影响。

磁盘驱动调度算法的好坏直接影响辅助存储器的效率，从而影响计算机系统的整体效率。

常用的磁盘驱动调度算法有：最简单的磁盘驱动调度算法是先入先出（FIFO）法。

这种算法的实质是，总是严格按时间顺序对磁盘请求予以处理。

算法实现简单、易于理解并且相对公平，不会发生进程饿死现象。

但该算法可能会移动的柱面数较多并且会经常更换移动方向，效率有待提高。

最短寻找时间优先算法：总是优先处理最靠近的请求。

该算法移动的柱面距离较小，但可能会经常改变移动方向，并且可能会发生进程饥饿现象。

电梯调度：总是将一个方向上的请求全部处理完后，才改变方向继续处理其他请求。

扫描（双向扫描）：总是从最外向最里进行扫描，然后在从最里向最外扫描。

该算法与电梯调度算法的区别是电梯调度在没有最外或最里的请求时不会移动到最外或最里柱面，二扫描算法总是移到最外、最里柱面。

两端的请求有优先服被务的迹象。

循环扫描（单向扫描）：从最外向最里进行柱面请求处理，到最里柱面后，直接跳到最外柱面然后继续向里进行处理。

该算法与扫描算法的区别是，回来过程不处理请求，基于这样的事实，因为里端刚被处理。

磁盘调度算法实验设计报告

磁盘调度算法实验设计报告

实验五磁盘调度算法班级： xxxxxxxxxxxx姓名：xxxxxxxx学号：xxxxxxxxxxxxxxxxxxxxx上级日期：2018年11月成绩：___________________________一、实验目的:通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易理解，使磁盘调度的特点更简单明了，加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解二、实验内容1、程序流程图模块调用关系图模块程序流程图FCFS算法（先来先服务）流程图SSTF（最短寻道时间优先算法）流程图SCAN算法（扫描算法）流程图CSCAN算法（循环扫描算法）流程图2、程序源码1.#include<stdio.h>2.#include<stdlib.h>3.#include<iostream>4.#include<math.h>ing namespace std;6.#define maxsize 10007./*********************判断输入数据是否有效**************************/8.int decide(char str[]) //判断输入数据是否有效9.{10.int i = 0;11.while (str[i] != '\0')12. {13.if (str[i]<'0' || str[i]>'9')14. {15.return 0;16.break;17. }18. i++;19. }20.return i;21.}22./******************将字符串转换成数字***********************/23.int trans(char str[], int a) //将字符串转换成数字24.{25.int i;26.int sum = 0;27.for (i = 0; i<a; i++)28. {29. sum = sum + (int)((str[i] - '0')*pow(10, a - i - 1));30. }31.return sum;32.}33./*********************冒泡排序算法**************************/34.int *bubble(int cidao[], int m)35.{36.int i, j;37.int temp;38.for (i = 0; i<m; i++) //使用冒泡法按从小到大顺序排列39.for (j = i + 1; j<m; j++)40. {41.if (cidao[i]>cidao[j])42. {43. temp = cidao[i];44. cidao[i] = cidao[j];45. cidao[j] = temp;46. }47. }48. cout << "排序后的磁盘序列为：";49.for (i = 0; i<m; i++) //输出排序结果50. {51. cout << cidao[i] << " ";52. }53. cout << endl;54.return cidao;55.}56./*********************先来先服务调度算法************************/57.void FCFS(int cidao[], int m) //磁道号数组，个数为m58.{59.int now;//当前磁道号60.int sum = 0; //总寻道长度61.int j, i;62.int a;63.char str[100];64.float ave; //平均寻道长度65. cout << "磁盘请求序列为：";66.for (i = 0; i<m; i++) //按先来先服务的策略输出磁盘请求序列67. {68. cout << cidao[i] << " ";69. }70. cout << endl;71. cout << "请输入当前的磁道号：";72.B: cin >> str; //对输入数据进行有效性判断73. a = decide(str);74.if (a == 0)75. {76. cout << "输入数据的类型错误,请重新输入！" << endl;77.goto B;78. }79.else80. now = trans(str, a); //输入当前磁道号81. sum += abs(cidao[0] - now);82. cout << "磁盘扫描序列为：";83.for (i = 0; i<m; i++) //输出磁盘扫描序列84. {85. cout << cidao[i] << " ";86. }87.for (i = 0, j = 1; j<m; i++, j++) //求平均寻道长度88. {89. sum += abs(cidao[j] - cidao[i]);90. ave = (float)(sum) / (float)(m);91. }92. cout << endl;93. cout << "平均寻道长度：" << ave << endl;94.}95./**********************最短寻道时间优先调度算法********************/96.void SSTF(int cidao[], int m)97.{98.int k = 1;99.int now, l, r;100.int i, j, sum = 0;101.int a;102.char str[100];103.float ave;104. cidao = bubble(cidao, m); //调用冒泡排序算法排序105. cout << "请输入当前的磁道号：";106.C: cin >> str; //对输入数据进行有效性判断107. a = decide(str);108.if (a == 0)109. {110. cout << "输入数据的类型错误,请重新输入！" << endl;111.goto C;112. }113.else114. now = trans(str, a); //输入当前磁道号115.if (cidao[m - 1] <= now) //若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务116. {117. cout << "磁盘扫描序列为：";118.for (i = m - 1; i >= 0; i--)119. cout << cidao[i] << " ";120. sum = now - cidao[0];121. }122.if (cidao[0] >= now) //若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务123. {124. cout << "磁盘扫描序列为：";125.for (i = 0; i<m; i++)126. cout << cidao[i] << " ";127. sum = cidao[m - 1] - now;128. }129.if (now>cidao[0] && now<cidao[m - 1]) //若当前磁道号大于请求序列中最小者且小于最大者130. {131. cout << "磁盘扫描序列为：";132.while (cidao[k]<now) //确定当前磁道在已排的序列中的位置，后面的算法都用到了，可以直接复制后少量修改，节省时间。