2022年磁盘调度算法 .pdf

《2022年磁盘调度算法 .pdf》由会员分享，可在线阅读，更多相关《2022年磁盘调度算法 .pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实验六磁盘调度算法【实验目的】通过这次实验， 加深对磁盘调度算法的理解， 进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环 SCAN 算法的实现方法。【实验内容】问题描述：设计程序模拟先来先服务FCFS、 最短寻道时间优先 SSTF、 SCAN和循环 SCAN 算法的工作过程。假设有n 个磁道号所组成的磁道访问序列，给定开始磁道号m 和磁头移动的方向（正向或者反向） ，分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。程序要求 ：1）利用先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环 SCAN 算法模拟磁道

2、访问过程。2）模拟四种算法的磁道访问过程，给出每个磁道访问的磁头移动距离。3）输入：磁道个数n 和磁道访问序列，开始磁道号m 和磁头移动方向（对SCAN 和循环 SCAN 算法有效），算法选择1-FCFS，2-SSTF，3-SCAN，4-循环 SCAN。4）输出：每种算法的平均寻道长度。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 24 页 - - - - - - - - - 实现提示：用 C+语言实现提示：1）程序中变量定义参考（根据需要可添加）如下：const in

3、t MaxNumber=100; int TrackOrderMaxNumber; int MoveDistanceMaxNumber; double AverageDistance; bool direction; 2）页面置换的实现过程如下：变量初始化；接收用户输入磁道个数n 和磁盘访问序列， 选择算法 1-FCFS，2-SSTF，3-SCAN，4-循环 SCAN，输入开始磁盘号m 和磁头移动方向；根据用户选择的算法进行磁道访问，输出磁盘调度算法的模拟过程；计算选择每次移动的磁头移动距离和算法的平均寻道长度；输出选择算法的平均寻道长度。实验要求：1）上机前认真复习磁盘调度算法，熟悉FCFS

4、、SSTF、SCAN和循环 SCAN 算法的过程；2）上机时独立编程、调试程序；3）根据具体实验要求，完成好实验报告（包括实验的目的、内名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 24 页 - - - - - - - - - 容、要求、源程序、实例运行结果截图、发现的问题以及解决方法）。【实验分析】需求分析：(1) 按提示输入磁道个数，不得大于MaxNum；依次输入磁盘访问序列；按提示输入开始磁道号，磁头移动方向（1为磁道号增加方向,0为磁道号减少方向）；根据提示输入

5、要进行的算法类型，1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。(2) 输出的形式：先输出每次访问的磁道号和移动的磁头移动距离，最后输出平均寻道长度。(3) 程序所能达到的功能：根据用户选择的算法进行磁道访问，输出磁盘调度算法的模拟过程， 输出每次移动的磁头移动距离和算法的平均寻道长度。(4) 测试数据：输入数据分别为： 9 55 58 39 18 90 160 150 38 184 100 1 输入： 1 输出：被访问的下一个磁道号55 移动距离（磁道数） 45 被访问的下一个磁道号 58 移动距离（磁道数） 3 被访问的下一个磁道号 39 移动距离（磁道数） 19 被访问的下

6、一个磁道号 18 移动距离（磁道数） 21 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 24 页 - - - - - - - - - 被访问的下一个磁道号 90 移动距离（磁道数） 72 被访问的下一个磁道号 160 移动距离（磁道数） 70 被访问的下一个磁道号 150 移动距离（磁道数） 10 被访问的下一个磁道号 38 移动距离（磁道数） 112 被访问的下一个磁道号 184 移动距离（磁道数） 146 平均寻道长度： 55.3333 输入： 2 输出：被访问的

7、下一个磁道号90 移动距离（磁道数） 10 被访问的下一个磁道号 58 移动距离（磁道数） 32 被访问的下一个磁道号 55 移动距离（磁道数） 3 被访问的下一个磁道号 39 移动距离（磁道数） 16 被访问的下一个磁道号 38 移动距离（磁道数） 1 被访问的下一个磁道号 18 移动距离（磁道数） 20 被访问的下一个磁道号 150 移动距离（磁道数） 132 被访问的下一个磁道号 160 移动距离（磁道数） 10 被访问的下一个磁道号 184 移动距离（磁道数） 24 平均寻道长度： 27.5556 输入： 3 输出：被访问的下一个磁道号150 移动距离（磁道数） 50 被访问的下一个磁

8、道号 160 移动距离（磁道数） 10 被访问的下一个磁道号 184 移动距离（磁道数） 24 被访问的下一个磁道号 90 移动距离（磁道数） 94 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 24 页 - - - - - - - - - 被访问的下一个磁道号 58 移动距离（磁道数） 32 被访问的下一个磁道号 55 移动距离（磁道数） 3 被访问的下一个磁道号 39 移动距离（磁道数） 16 被访问的下一个磁道号 38 移动距离（磁道数） 1 被访问的下一个磁道号

9、 18 移动距离（磁道数） 20 平均寻道长度： 27.7778 输入： 4 输出：被访问的下一个磁道号150 移动距离（磁道数） 50 被访问的下一个磁道号 160 移动距离（磁道数） 10 被访问的下一个磁道号 184 移动距离（磁道数） 24 被访问的下一个磁道号 18 移动距离（磁道数） 166 被访问的下一个磁道号 38 移动距离（磁道数） 20 被访问的下一个磁道号 39 移动距离（磁道数） 1 被访问的下一个磁道号 55 移动距离（磁道数） 16 被访问的下一个磁道号 58 移动距离（磁道数） 3 被访问的下一个磁道号 90 移动距离（磁道数） 32 平均寻道长度： 35.777

10、8 概要设计：(1) 本程序中用到的数据的定义： const int MaxNumber=100; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 24 页 - - - - - - - - - int TrackOrderMaxNumber;/存放磁盘访问序列int MoveDistanceMaxNumber;/存放每次的寻道长度int VisitOrderMaxNumber;/存放访问的顺序bool direction;/磁头移动方向int n;/磁道个数int m;/

11、开始磁道号(2) 主程序的流程 : 变量初始化 =用户选择执行的算法 =若不符合条件，则退出=若符合，执行算法 =输出结果(3) 各程序模块之间的层次 ( 调用) 关系。主程序调用初始化模块以及算法模块、输出模块详细设计实现程序模块的具体算法。#include using namespace std; const int MaxNumber=100; int TrackOrderMaxNumber;/存放磁盘访问序列int MoveDistanceMaxNumber;/存放每次的寻道长度int VisitOrderMaxNumber;/存放访问的顺序bool direction;/磁头移动方向

12、int n;/磁道个数int m;/开始磁道号名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 24 页 - - - - - - - - - void init()/变量初始化cout 输入磁道个数 n; cout 磁盘访问序列 endl; for(int i=0;iTrackOrderi; cout 输入开始磁道号 m; cout 输入磁头移动方向 ,1 为磁道号增加方向 ,0 为磁道号减少方向 direction; void fcfs() for(int i=0;in;

13、+i) VisitOrderi=i; if(i=0) MoveDistancei=m-TrackOrderi; else MoveDistancei=TrackOrderVisitOrderi-1-TrackOrderi;/按输入的磁盘访问序列寻道， 寻道长度为前一个访问的磁道号减名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 24 页 - - - - - - - - - 当前访问的 void shunxu()/排序，从小到大排列磁盘访问序列for(int i=1;in;

14、+i) for(int j=0;jTrackOrderj+1) int temp=TrackOrderj+1; TrackOrderj+1=TrackOrderj; TrackOrderj=temp;/冒泡排序 void sstf() shunxu(); int i; int temp; for(i=0;im) temp=i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 24 页 - - - - - - - - - break; / 找到小于开始磁道号的最后一个元素i

15、f(abs(TrackOrdertemp-m)abs(TrackOrdertemp+1-m)/ 比较小于开始磁道号的最后一个元素和下一个元素哪个离开始磁道号远VisitOrder0=temp+1; MoveDistance0=TrackOrdertemp+1-m; temp=temp+1; else VisitOrder0=temp; MoveDistance0=TrackOrdertemp-m; / 取距离小的那个为第一个访问的元素int h=temp-1; int k=temp+1; i=1; while(h-1&kabs(TrackOrderk-TrackOrderVisitOrderi

16、-1) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 24 页 - - - - - - - - - VisitOrderi=k; MoveDistancei=TrackOrderVisitOrderi-1-TrackOrderk; +i; k+; else VisitOrderi=h; MoveDistancei=TrackOrderVisitOrderi-1-TrackOrderh; +i; h-; if(h=-1) for(;k-1;-h) VisitOrderi=

17、h; MoveDistancei=TrackOrderVisitOrderi-1-TrackOrderh; +i; void scan() shunxu(); int k,i; k=1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 24 页 - - - - - - - - - int temp; if(direction)/若向磁道号增加方向访问for(i=0;i100)/找到第一个大于开始磁道号的元素temp=i; VisitOrder0=i; MoveDista

18、nce0=TrackOrderi-100; break; +i; while(i-1) VisitOrderk=i; MoveDistancek=TrackOrderVisitOrderk-1-TrackOrderi; -i; +k; else/若向磁道号减小方向访问for(i=0;i100)/找到最后一个小于磁道号的元素temp=i; VisitOrder0=i; MoveDistance0=TrackOrderi-100; break; -i;/向前遍历while(i-1) VisitOrderk=i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

19、- - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 24 页 - - - - - - - - - MoveDistancek=TrackOrderVisitOrderk-1-TrackOrderi; -i; +k; i=temp+1;/遍历完后，回到刚刚最后一个小于开始磁道号的元素的后一个向后遍历while(in) VisitOrderk=i; MoveDistancek=TrackOrderVisitOrderk-1-TrackOrderi; +i; +k; void cscan() 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

20、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 24 页 - - - - - - - - - shunxu(); int k,i; k=1; int temp; if(direction)/若向磁道号增加方向访问for(i=0;i100)/找到第一个大于开始磁道号的元素temp=i; VisitOrder0=i; MoveDistance0=TrackOrderi-100; break; +i; while(in)/向后遍历VisitOrderk=i; MoveDistancek=TrackOrderVisitOrderk-1-TrackO

21、rderi; +i; +k; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 24 页 - - - - - - - - - i=0;/遍历完再从第一个元素开始遍历while(itemp) VisitOrderk=i; MoveDistancek=TrackOrderVisitOrderk-1-TrackOrderi; +i; +k; else/若向磁道号减小方向访问for(i=0;i100)/找到最后一个小于磁道号的元素temp=i; VisitOrder0=i; Mo

22、veDistance0=TrackOrderi-100; break; -i;/向前遍历名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 24 页 - - - - - - - - - while(i-1) VisitOrderk=i; MoveDistancek=TrackOrderVisitOrderk-1-TrackOrderi; -i; +k; i=n-1;/遍历完后从最后一个元素向前遍历while(itemp) VisitOrderk=i; MoveDistanc

23、ek=TrackOrderVisitOrderk-1-TrackOrderi; -i; +k; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 24 页 - - - - - - - - - void output() int sum=0;/求磁道数总和for(int i=0;in;+i) cout被访问的下一个磁道号TrackOrderVisitOrderi 移动距离（磁道数）abs(MoveDistancei)endl; sum=sum+abs(MoveDistanc

24、ei); cout 平均寻道长度：double(sum)/nendl;/输出平均寻道长度 void main() init(); int a; cout 选 择 算 法 ， 1-FCFS， 2-SSTF， 3-SCAN， 4- 循 环SCANa; switch(a) case(1): fcfs();break; case(2): 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 24 页 - - - - - - - - - sstf();break; case(3): s

25、can();break; case(4): cscan();break; / 根据用户选择的算法进行磁盘调度算法output(); 调试分析1、执行算法前，要先申请变量。2、执行后面三种算法时，要注意先将磁道序列从小到大排序。3、执行 SSTF算法时，先找到小于开始磁道号的最后一个元素，以此元素为分割点，向前和向后遍历序列，每次移动一个，比较出离前一个访问的磁道号近的访问。4、执行 SCAN 和 CSCAN 算法时，要先判断用户输入的是向磁道号增加的方向执行还是向磁道号减少的方向执行。5、时间的复杂度是 O(n). 用户使用说明按提示输入磁道个数，不得大于MaxNum；依次输入磁盘访问序列；按

26、提示输入开始磁道号， 磁头移动方向 （1为磁道号增加方向 ,0为磁道号减少方向）；根据提示输入要进行的算法类型，1-FCFS，2-SSTF，3-SCAN，4-循环SCAN。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 24 页 - - - - - - - - - 测试结果输入数据分别为： 9 55 58 39 18 90 160 150 38 184 100 1 输入： 1 输出：被访问的下一个磁道号55 移动距离（磁道数） 45 被访问的下一个磁道号 58 移动距离

27、（磁道数） 3 被访问的下一个磁道号 39 移动距离（磁道数） 19 被访问的下一个磁道号 18 移动距离（磁道数） 21 被访问的下一个磁道号 90 移动距离（磁道数） 72 被访问的下一个磁道号 160 移动距离（磁道数） 70 被访问的下一个磁道号 150 移动距离（磁道数） 10 被访问的下一个磁道号 38 移动距离（磁道数） 112 被访问的下一个磁道号 184 移动距离（磁道数） 146 平均寻道长度： 55.3333 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20

28、 页，共 24 页 - - - - - - - - - 输入： 2 输出：被访问的下一个磁道号90 移动距离（磁道数） 10 被访问的下一个磁道号 58 移动距离（磁道数） 32 被访问的下一个磁道号 55 移动距离（磁道数） 3 被访问的下一个磁道号 39 移动距离（磁道数） 16 被访问的下一个磁道号 38 移动距离（磁道数） 1 被访问的下一个磁道号 18 移动距离（磁道数） 20 被访问的下一个磁道号 150 移动距离（磁道数） 132 被访问的下一个磁道号 160 移动距离（磁道数） 10 被访问的下一个磁道号 184 移动距离（磁道数） 24 名师资料总结 - - -精品资料欢迎下

29、载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 24 页 - - - - - - - - - 平均寻道长度： 27.5556 输入： 3 输出：被访问的下一个磁道号150 移动距离（磁道数） 50 被访问的下一个磁道号 160 移动距离（磁道数） 10 被访问的下一个磁道号 184 移动距离（磁道数） 24 被访问的下一个磁道号 90 移动距离（磁道数） 94 被访问的下一个磁道号 58 移动距离（磁道数） 32 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

30、- - - - - 名师精心整理 - - - - - - - 第 22 页，共 24 页 - - - - - - - - - 被访问的下一个磁道号 55 移动距离（磁道数） 3 被访问的下一个磁道号 39 移动距离（磁道数） 16 被访问的下一个磁道号 38 移动距离（磁道数） 1 被访问的下一个磁道号 18 移动距离（磁道数） 20 平均寻道长度： 27.7778 输入： 4 输出：被访问的下一个磁道号150 移动距离（磁道数） 50 被访问的下一个磁道号 160 移动距离（磁道数） 10 被访问的下一个磁道号 184 移动距离（磁道数） 24 名师资料总结 - - -精品资料欢迎下载 -

31、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 23 页，共 24 页 - - - - - - - - - 被访问的下一个磁道号 18 移动距离（磁道数） 166 被访问的下一个磁道号 38 移动距离（磁道数） 20 被访问的下一个磁道号 39 移动距离（磁道数） 1 被访问的下一个磁道号 55 移动距离（磁道数） 16 被访问的下一个磁道号 58 移动距离（磁道数） 3 被访问的下一个磁道号 90 移动距离（磁道数） 32 平均寻道长度： 35.7778 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 24 页，共 24 页 - - - - - - - - -