操作系统课设 磁盘调度算法程序设计

1、题目磁盘调度算法程序设计课程名称操作系统课程设计一、程序设计的目的和要求磁盘是经常使用的一个外设，对磁盘数据的寻道时间的长短直接影响机器的 整体运行速度，本设计要求用C语言（或高级语言）编写程序模拟实现磁盘调度的 常用算法。以加深对磁盘调度常用算法的理解和实现技巧。二、课程设计环境要求1、硬件环境Intel Croe 2 Duo CPU2、软件环境Windows? Turbo C 2.0三、设计任务介绍及系统需求分析1、系统分析设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的 分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效 率通常是由于磁盘类旋转设备使

2、用不当造成的。操作系统中，对磁盘的访问要求 来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直 接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构 成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间， 其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再 优化旋转等待策略。2、系统设计：（1）先来先服务.（First-Come，First-Served，FCFS）:这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调 度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出 现某一进程的请

3、求长期得不到满足的情况。但此算法由于未对寻道进行优化，致 使平均寻道时间可能较长。最短寻道时间优先(ShortestSeekTimeFirst，SSTF):该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最 近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。扫描(SCAN)算法：SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁 头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下 一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自 里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这

4、 时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内， 从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行， 故又称为电梯调度算法。四、概要设计本系统划分为三个模块：先来先服务算法模块void FCFS(int array,int m)、 最短寻道时间优先算法模块void SSTF(int array,int m)、扫描算法模块void SCAN(int array,int m)。系统模块图磁盘调度模拟系统先 来 先 服 务 算 法最 短 寻 时 间 优 先扫 描 算 法五、详细设计1、先来先服务(FCFS)这是一种简单的磁盘调度算法。它根据进程请求访问磁

5、盘的先后次序进行调 度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出 现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致 使平均寻道时间可能较长。先来先服务算法(FCFS)流程图:2、最短寻道时间优先(SSTF)该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近， 以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。最短寻道时间优先流程图:3、扫描算法(SCAN)SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁 头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下 一个访问对象应是其

6、欲访问的磁道既在当前磁道之外，又是距离最近的。这样自 里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这 时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内， 从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行， 故又称为电梯调度算法。J六、测试数据和结果1、先来先服务调度(FCFS)输入起始磁道(你可以输入50)，点确定，进入第二个界面，再输入你要输入的 最大磁道(你可以输入100)，然后点确定。选择磁盘调度算法1 2 3中的任意一 个，若选择1后确认，则随机输出10个小于100的磁道数(41 67 34 0 69 24 78 58

7、62 64)，则先来先服务调度(FCFS)输出：(41 67 34 0 69 24 78 58 62 64)，在选择1 或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度运行结果图：+是否继续技。结束，技1继续?+ FCFS 访问顺序为： 4167340692478586264+整动故ii薮X 296+平均寻道长度= *29-60*+需要寻找的磁道号：416734 Q 692478586264请输入初始的磁道数泻。e C: Docu*ent s and Sett ingskAdninist r at or 桌面 豆件 test, exes s 00CFW-1 F tL -z di.-

8、 ewn mCA 的直道法 寻先 入着描 肇最扫14-1 2 3 12、最短寻道时间优先调度(SSTF)输入起始磁道(你可以输入50)，点确定，进入第二个界面，再输入你要输 入的最大磁道(你可以输入100)，然后点确定。选择磁盘调度算法1 2 3中的任 意一个，若选择2后确认，则随机输出10个小于100的磁道数(41 67 34 0 69 24 78 58 62 64)，则最短寻道时间优先调度(SSTF)： (58 62 64 67 69 78 41 34 24 0)。 在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度运行结果图:m C: Docu*ents and Set

9、tingsAdiLiiiistrator桌面，豆件 test, exe请输入初始的磁道数:酣*12 3 28法CFW rnCA 的费道法 寻先 入来.一 I H,短描64 |x|+需要寻找的磁道号：416734 Q 6924785862+ SSTF 访问顺序为： 586264676978413424+侵动磁ii数X 106 +平均寻道长度= *10-60*+是否继续技。结束，按1继续?3、扫描调度算法(SCAN)输入起始磁道(你可以输入50),点确定，进入第二个界面，再输入你要输 入的最大磁道(你可以输入100)，然后点确定。选择磁盘调度算法1 2 3中的任 意一个，若选择3后确认，则随机输出

10、10个小于100的磁道数：(41 67 34 0 69 24 78 58 62 64)，则扫描调度算法(SCAN)： (58 62 64 67 69 78 41 34 24 0)。C: Docuents and SettingsAdtaiiiiistrator桌面豆件 test, exe请输入初始的磁道数：弱F TS S 丽CFW- 1 F t -c di/ bwn mCA 的 s 董道法 寻先入来短描 取扫 +需要寻找的磁道号=416?340692478586264访磁寻由AN动置序:65536)printf(超出磁道范围!)；elseprintf(1.先来先服务算法(FCFS )n);pr

11、intf(吃.最短寻道时间优先算法(SSTF)n);printf(3.扫描算法(SCAN)n);scanf(%d,&n);if(n=0) exit(0);printf(n);switch(n)case 1:SetDI(DiscLine); 随机生成磁道数FCFS(Hand,DiscLine); / 先来先服务算法(FCFS) break;case 2:SetDI(DiscLine); /随机生成磁道数SSTF(Hand,DiscLine); 最短寻道时间优先算法(SSTF) break;case 3:SetDI(DiscLine); /随机生成磁道数SCAN(Hand,DiscLine,0,9

12、); 扫描算法(SCAN) break;SetDI(DiscLine); /随机生成磁道数FCFS(Hand,DiscLine); / 先来先服务算法(FCFS)SSTF(Hand,DiscLine); 最短寻道时间优先算法(SSTF)SCAN(Hand,DiscLine,0,9);/ 扫描算法(SCAN)printf(nn+是否继续(按0结束,按1继续)?);scanf(%5d,&Con);数组Sour复制到数组Dist，复制到x个数void CopyL(int Sour,int Dist ,int x)int i;for(i=0;i=x;i+)Disti=Souri;打印输出数组Privo

13、id Print(int Pri,int x)int i;for(i=0;i=x;i+)printf(%5d,Prii);随机生成磁道数void SetDI(int DiscL)int i;for(i=0;i=9;i+)DiscLi=rand()%Limit;随机生成 10 个磁道号printf(+需要寻找的磁道号:，Print(DiscL,9); 输出随机生成的磁道号printf(n);数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不 变(即会出现2个y)void DelInq(int Sour,int x,int y)int i;for(i=x;iy;i+)Souri=

14、Souri+1;x+;先来先服务算法(FCFS)void FCFS(int Han,int DiscL)int RLine10; 将随机生成的磁道数数组Discl复制给数组RLineint i,k,All,Temp; /Temp是计算移动的磁道距离的临时变量All=0; 统计全部的磁道数变量k=9; 限定10个的磁道数CopyL(DiscL,RLine,9); 复制磁道号到临时数组RLineprintf(n+ FCFS 访问顺序为:)；All=Han-RLine0;for(i=0;i=9;i+)Temp=RLine0-RLine1;/求出移动磁道数，前一个磁道数减去后一个磁道 数得出临时的移动

15、距离if(Temp0)Temp=(-Temp);/移动磁道数为负数时,算出相反数作为移动磁道数printf(%5d,RLine0);All=Temp+All;/求全部磁道数的总和DelInq(RLine,0,k);/每个磁道数向前移动一位k-;BestJage1=All;/Best1存放移动磁道数BestJage0=1; /Best 0存放算法的序号为:1Jage+;/排序的序号加1Aver=(float) All)/10;/求平 均寻道次数printf(n+ 移动磁道数: ,All);printf(n+ 平均寻道长度:*%0.2f* ,Aver);最短寻道时间优先算法(SSTF)void S

16、STF(int Han,int DiscL)int i,j,k,h,All;int Temp; /Temp是计算移动的磁道距离的临时变量int RLine10;将随机生成的磁道数数组Discl复制给数组RLineint Min;All=0; 统计全部的磁道数变量k=9; 限定10个的磁道数CopyL(DiscL,RLine,9); 复制磁道号到临时数组RLineprintf(n+ SSTF 访问顺序为:)；for(i=0;i=9;i+)Min=64000;for(j=0;jHan) 如果第一个随机生成的磁道号大于当前的磁道号，执 行下一句Temp=RLinej-Han; 求出临时的移动距离el

17、seTemp=Han-RLinej; /求出临时的移动距离if(TempMin) 如果每求出一次的移动距离小于Min，执行下一句Min=Temp; /Temp 临时值赋予 Minh=j; 把最近当前磁道号的数组下标赋予hAll=All+Min; 统计一共移动的距离printf(%5d,RLineh);Han=RLineh;DelInq(RLine,h,k); 每个磁道数向前移动一位k-;BestJage1=All;/Best1存放移动磁道数BestJage0=2;/Best0存放算法的序号为:2Jage+;/排序序号加1Aver=(float)All)/10;/求平 均寻道次数printf(n

18、+ 移动磁道数: ,All);printf(n+ 平均寻道长度:*%0.2f* ,Aver);扫描算法(SCAN)int SCAN(int Han,int DiscL,int x,int y)int t=0;int Temp;int Min;int RLine10; /将随机生成的磁道数数组Discl复制给数组RLineint Order;Order=1;k=y;m=2; 控制while语句的执行，即是一定要使当前磁道向内向外都要扫描 到All=0; 统计全部的磁道数变量CopyL(DiscL,RLine,9); 复制磁道号到临时数组RLineprintf(n+ SCAN 访问顺序为:)；Min=64000;for(j=x;jHan) 如果第一个随机生成的磁道号大于当前的磁道号，执 行下一句Temp=RLinej-Han; 求出临时的移动距离elseTemp=Han-RLinej; 求出临时的移动距离if(Temp=Han) 判动方向，即是由里向外还是由外向里断磁道的移Order=0;t=1；Han=RLineh;DelInq(RLine,h,k); 每个磁道数向前移动一位k-;while(m0)if(Order=1) /order是判断磁盘扫描的方向标签，order是1的话，