磁盘驱动调度算法.doc

操作系统课程设计操作系统课程设计 题 目： 磁盘驱动调度算法模拟 班 级: 姓 名： 学 号： 指导教师: 成 绩: 2014年6月1、 课程设计目标1进一步加深对磁盘驱动调度算法的理解。2编程实现“先来先服务”、“最短寻道时间优先”、“电梯调度”、“循环扫描”算法。二、课题内容1假设一个磁盘具有4个盘片，每个盘片有100个磁道，每道有8个扇区，模拟格式化时对柱面和扇区进行编号的过程。2设计若干磁道访问请求，要求用户输入线性块号，系统能将其转换为对应的磁道号（柱面号），并计算出分别采用“先来先服务”、“最短寻道时间优先”、“电梯调度”、“循环扫描”算法的寻道总长度。3提供可视化且简洁清晰的用户界面，能直观且动态地描述磁头移动。三、设计思路（一）系统概要设计 1.整体模块设计图磁盘驱动调度算法模拟CSCAN算法SSTF算法SCAN算法FCFS算法菜单显示沿磁道减小方向沿磁道增加方向沿磁道减小方向沿磁道增加方向2. 相关知识 磁盘调度：当有多个进程都请求访问磁盘时，采用一种适当的驱动调度算法，使各进程对磁盘的平均访问（主要是寻道）时间最小。目前常用的磁盘调度算法有：1）先来先服务2）最短寻道时间优先3）扫描算法4）循环扫描算法等3.算法思想介绍（1） 先来先服务算法（FCFS） 即先来的请求先被响应。FCFS策略看起来似乎是相当公平的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候FCFS也被看作是最简单的磁盘调度算法。（2） 最短寻道时间优先算法（SSTF） 最短时间优先算法选择这样的进程。要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。（3） 电梯调度算法（SCAN） 电梯（SCAN）调度算法:该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像。（4） 循环扫描算法（CSCAN） 循环扫描（CSCAN）算法：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。但本实验已完全能演示循环扫描的全过程。（2） 系统详细设计 1.数据结构设计 本系统采用数组a3200保存用户输入的线性块号，用数组array100保存将线性块号转换为磁道号。 2.模块接口设计（1） 各函数原型为： void main(); /主函数 int menu() ; / 菜单界面 void FCFS(); /FCFS算法 void SSTF(); /SSTF算法 void SCAN(); /SCAN算法 void CSCAN(); /CSCAN算法（2） 系统界面切换的实现 利用清屏函数system(cls)实现屏幕切换，在从本界面返回上一界面时，根据提示输入即可，例如：cout输入任意键返回主菜单c;则输入输入任意键都能返回上一界面，在main（）函数中用do-while语句实现各函数的循环调用，以使各功能能够重复实现，直至用户退出系统为止。 3.流程图(1) 主函数(2) 界面函数(3) 先来先服务算法（FCFS）(4) 最短寻道时间优先算法（SSTF）(5) 电梯调度算法（SCAN）(6) 循环扫描算法（CSCAN）四、源代码#include /导入库函数#include #include #include #define maxsize 100 /最大的磁道号#define max 3200 /最大块号int menu() / 菜单界面system(cls); /清屏函数int x;coutendl;coutsetfill(*)setw(26)1b 磁盘驱动调度算法模拟 setfill(*)setw(25)*endl;coutsetfill( )setw(37)算法选择：endl; coutsetfill( )setw(49)1.先来先服务算法(FCFS)endl; coutsetfill( )setw(55)2.最短寻道时间优先算法(SSTF)endl; coutsetfill( )setw(47)3.电梯调度算法(SCAN)endl; coutsetfill( )setw(48)4.循环扫描算法(CSCAN)endl;coutsetfill( )setw(33)5.退出endl;cout请输入您想选择的操作:(1-5)x;return x;void FCFS() /FCFS算法system(cls);char c;int sum=0,j,i,m=0;int avg;int amax=0,arraymaxsize=0;cout请输入线性块号,以-1结束:am; arraym=am/32; /将线性块号转换为磁道号if(am=-1) break;cout磁道号为:endl; /输出磁道号for(i=0;im;i+) printf(%d ,arrayi);printf(nFCFS调度结果: );for(i=0;im;i+) /输出FCFS磁盘调度结果printf(%d ,arrayi);for(i=0,j=1;jm;i+,j+)sum+=abs(arrayj-arrayi); /累计总的移动距离avg=sum/(m-1); /计算平均寻道长度printf(n移动的总道数： %d n,sum);printf(平均寻道长度： %d n,avg);cout输入任意键返回上一菜单c;void SSTF() /SSTF算法system(cls);char c;int temp;int k=1;int now,l,r;int i,j,sum=0,m=0;int avg;int amax=0,arraymaxsize=0;cout请输入线性块号,以-1结束:am; arraym=am/32; /将线性块号转换为磁道号if(am=-1) break;cout磁道号为:endl; /输出磁道号for(i=0;im;i+) printf(%d ,arrayi);for(i=0;im;i+)for(j=i+1;jarrayj) /两磁道号之间比较temp=arrayi;arrayi=arrayj;arrayj=temp;printf(n排序后的磁道号为:);for( i=0;im;i+) /输出排序后的磁道号数组printf(%d ,arrayi);printf(n请输入当前的磁道号：);scanf(%d,&now);printf(nSSTF调度结果: );if(arraym-1=0;i-) /将数组磁道号从大到小输出printf(%d ,arrayi);sum=now-array0; /计算移动距离else if(array0=now)/判断整个数组里的数是否都大于当前磁道号 for(i=0;im;i+) /将磁道号从小到大输出printf(%d ,arrayi);sum=arraym-1-now;/计算移动距离elsewhile(arrayk=0)&(rm)if(now-arrayl)=(arrayr-now)/判断最短距离 printf(%d ,arrayl);sum+=now-arrayl; /计算移动距离now=arrayl;l=l-1;else printf(%d ,arrayr);sum+=arrayr-now; /计算移动距离now=arrayr;r=r+1;if(l=-1) for(j=r;j=0;j-) printf(%d ,arrayj);sum+=arraym-1-array0;/计算移动距离avg=sum/m;printf(n移动的总道数： %d n,sum);printf(平均寻道长度： %d n,avg);cout输入任意键返回上一菜单c;void SCAN() /SCAN算法 /先要给出当前磁道号和移动臂的移动方向system(cls);char c;int temp;int k=1;int now,l,r,d;int i,j,sum=0,m=0;int avg;int amax=0,arraymaxsize=0;cout请输入线性块号,以-1结束:am; arraym=am/32; /将线性块号转换为磁道号if(am=-1) break;cout磁道号为:endl; /输出磁道号for(i=0;im;i+) printf(%d ,arrayi);for(i=0;im;i+)for(j=i+1;jarrayj) /对磁道号进行从小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;printf(n排序后的磁道号为:);for( i=0;im;i+)printf(%d ,arrayi); /输出排序后的磁道号数组printf(n请输入当前的磁道号：);scanf(%d,&now);if(arraym-1=0;i-)printf(%d ,arrayi); /将数组磁道号从大到小输出sum=now-array0; /计算移动距离else if(array0=now) /判断整个数组里的数是否都大于当前磁道号 printf(nSCAN调度结果: );for(i=0;im;i+)printf(%d ,arrayi); /将磁道号从小到大输出sum=arraym-1-now; /计算移动距离elsewhile(arrayk=0;j-)printf(%d ,arrayj);for(j=r;jm;j+)printf(%d ,arrayj);sum=now-2*array0+arraym-1;/计算移动距离 /磁道号减小方向elsefor(j=r;j=0;j-)printf(%d ,arrayj);sum=-now-array0+2*arraym-1;/计算移动距离 /磁道号增加方向avg=sum/m;printf(n移动的总道数： %d n,sum);printf(平均寻道长度： %d n,avg);cout输入任意键返回上一菜单c;void CSCAN() /CSCAN算法system(cls);char c;int temp;int k=1;int now,l,r,d;int i,j,sum=0,m=0;int avg;int arraymaxsize=0,amax=0;cout请输入线性块号,以-1结束:am; arraym=am/32; /将线性块号转换为磁道号if(am=-1) break;cout磁道号为:endl; /输出磁道号for(i=0;im;i+) printf(%d ,arrayi);for(i=0;im;i+)for(j=i+1;jarrayj) /对磁道号进行从小到大排列temp=arrayi;arrayi=arrayj;arrayj=temp;printf(n排序后的磁道号为:);for( i=0;im;i+)printf(%d ,arrayi); /输出排序后的磁道号数组printf(n请输入当前的磁道号：);scanf(%d,&now);if(arraym-1=now) /判断整个数组里的数是否都小于当前磁道号 printf(nCSCAN调度结果: );for(i=0;i=now) /判断整个数组里的数是否都大于当前磁道号 printf(nCSCAN调度结果: );for(i=0;im;i+) printf(%d ,arrayi); /将磁道号从小到大输出sum=arraym-1-now; /计算移动距离elsewhile(arrayk=0;j-)printf(%d ,arrayj);for(j=m-1;j=r;j-)printf(%d ,arrayj);sum=2*(arraym-1-array0)-arrayr+now;/计算移动距离 /磁道号减小方向elsefor(j=r;jm;j+)printf(%d ,arrayj);for(j=0;jr;j+)printf(%d ,arrayj);sum=2*(arraym-1-array0)+arrayr-1-now;/计算移动距离 /磁道号增加方向avg=sum/m;printf(n移动的总道数： %d n,sum);printf(平均寻道长度： %d n,avg);cout输入任意键返回上一菜单c;void main() /主函数 int x,i;for(i=0;i+)x=menu();switch(x)case 1:FCFS();break;case 2:SSTF();break;case 3:SCAN();break; case 4:CSCAN();break; case 5:coutsetfill(*)setw(35)1b正在退出!setfill(*)setw(35)*endl; coutsetfill( )setw(33)1b欢迎下次使用endl; exit(0); defa