1、淮北师范大学操作系统课程设计磁盘调度算法的模拟实现学 院 计算机科学与技术 专 业 计算机科学与技术（师范）学 号 学 生 姓 名 指导教师姓名 2015年7月1日目录一、引言2二、总体设计21.功能实现22.流程图33.具体内容3三、实验验证51.结果截图72.代码分析6四、源代码9五、总结13六、参考资料13一、 引言1、课程设计的目的：操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 l 进一步巩固和复习操作系统的基础知识。 l 培养学生结构化程序、模块化程序设计的方法和能力。 l 提高学生
2、调试程序的技巧和软件设计的能力。 l 提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。 2、设计内容：设计并实现一个本别利用下列磁盘调度算法进行磁盘调度的模拟程序。 1、先来先服务算法FCFS 2、最短寻道时间优先算法SSTF 3、设计要求：1. 磁头初始磁道号，序列长度，磁道号序列等数据可从键盘输入，也可从文件读入。 2. 最好能实现磁道号序列中磁道号的动态增加。3. 磁道访问序列以链表的形式存储 4. 给出各磁盘调度算法的调度顺序和平均寻道长度二、 总体设计1、算法实现 1.先来先服务算法（FCFS）先来先服务（FCFS）调度:按先来后到次序服务，未作优化。最简单的移臂
3、调度算法是“先来先服务”调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如，如果现在读写磁头正在50号柱面上执行输出操作，而等待访问者依次要访问的柱面为130、199、32、159、15、148、61、99，那么，当50号柱面上的操作结束后，移动臂将按请求的先后次序先移到130号柱面，最后到达99号柱面。采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。2.短寻道时间优先算法（SSTF）最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个
4、请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论，现在当50号柱面的操作结束后，应该先处理61号柱面的请求，然后到达32号柱面执行操作，随后处理15号柱面请求，后继操作的次序应该是99、130、148、159、199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头总共移动了200多个柱面的距离，与先来先服务、算法比较，大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（SSTF）调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。SST
5、F查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。先来先服务算法（FCFS）流程图:输入磁道号求平均寻道长度输出移动的平均磁道数按输入顺序将磁道序列输出开始结束最短寻道时间优先算法（SSTF）流程图:求平均寻道长度选择与当前磁道距离最近的磁道进行扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道输出移动的平均磁道数输出排好序的磁道序列判断当前磁头在序列中的位置结束开始输入磁道号使用冒泡法从小到大排序输入当前磁道号三、总体验证 1、数据结构及信号量定义的说明；本系统划分为四个模块：先来先服务算法模块void FCFS(int array,int m)、最短寻
6、道时间优先算法模块void SSTF(int array,int m)、扫描算法模块void SCAN(int array,int m) 和循环扫描算法模块：void CSCAN(int array,int m) 。2. 先来先服务算法模块：void FCFS(int array,int m)输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输出移动平均磁道数。3、 最短寻道时间优先算法模块：void SSTF(int array,int m)将磁道号用冒泡法从小到大排序，输出排好序的磁道序列，输入当前磁道号，根据前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度，输出
7、移动的平均磁道数。4、代码分析 1、先来先服务算法模块：void FCFS(int array,int m)主要代码：for(i=0,j=1;jm;i+,j+) sum+=abs(arrayj-arrayi); ave=(float)(sum)/(float)(m);2 最短寻道时间优先算法模块：void SSTF(int array,int m)主要代码：for(i=0;im;i+) /*使用冒泡法按从小到大顺序排列*/for(j=i+1;jarrayj) temp=arrayi; arrayi=arrayj; arrayj=temp; if(arraym-1=0;i-) coutarray
8、i=now) /*若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务*/ while(l=0)&(rm) /*当前磁道在请求序列范围内*/ if(now-arrayl)=(arrayr-now) /*选择与当前磁道最近的请求给予服务*/ coutarrayl ; sum+=now-arrayl; now=arrayl; l=l-1; 3、实验的步骤； 1先来先服务算法输入磁道序列：555839189016015038184当前磁道号：100 2最短寻道时间优先算法（1） 当前磁道号大于磁道序列中的最大的磁道号时（2） 输入磁道序列：555839189016015038184当前
9、磁道号：100四、源代码：#include#include#includeusing namespace std;typedef struct nodeint data;struct node *next;Node,*Linklist;void main()void Create_Linklist(Node *);void fcfs();/声明先来先服务函数FCFSvoid sstf();/声明最短寻道时间优先函数sstfvoid print(Node *);int s;printf(*磁盘调度算法*n);printf(t*1,先来先服务算法FCFSn);printf(t*2,最短寻道时间优先
10、算法SSTFn);printf(t*0,退出n);printf(t*请选择:);scanf(%d,&s);while(s!=0)switch(s)case 1:printf(tt*你选择了:先来先服务算法FCFSn);fcfs();break;case 2:printf(tt*你选择了:最短寻道时间优先算法SSTFn);sstf();break;printf(tt*退出请选0,继续请选1,2,n);scanf(%d,&s);/*/void fcfs()/先来先服务算法 void Create_Linklist(Node *);void print(Node*);int Length_Linkl
11、ist(Node *);Node *l,*head;/*m,*n;*/float num=0;/num为平均寻道长度 int c,f;head=(Node *)malloc(sizeof(Node);head-next=NULL;printf(*新建一个单链表,以0作为结束标志:*n);Create_Linklist(head);c=Length_Linklist(head);printf(tt*从几号磁道开始:*);scanf(%d,&f);/f为磁道号 print(head);printf(t*链表长度为:%dn,c); l=head-next; for(int i=0;idata-f);
12、f=l-data;l=l-next;num=num/c;printf(tt*先来先服务的寻道顺序是:n);print(head);printf(tt*平均寻道长度:%fn,num);/*/ void sstf()/最短寻道时间优先算法void Create_Linklist(Node *);void print(Node *);int Length_Linklist(Node *);Node *p,*q,*r,*s,*l,*m,*head;int c,f;head=(Node *)malloc(sizeof(Node);head-next=NULL;printf(*新建一个单链表,以0作为结束
13、标志:*n); Create_Linklist(head); c=Length_Linklist(head); printf(tt*从几号磁道开始:*); scanf(%d,&f); /f为磁道号print(head); printf(t*链表长度为:%dn,c); l=(Node *)malloc(sizeof(Node); l-next=NULL; m=l; q=head; p=head-next; s=head; r=head-next; float num=0; for(int i=0;idata); for(int j=0;jnext; q=q-next; if(abs(f-p-da
14、ta)data); r=p; s=q; num+=abs(f-r-data); f=r-data; s-next=r-next; r-next=NULL; m-next=r; m=r; q=head; p=head-next; s=head; r=head-next; num=num/c; printf(tt*最短寻道时间优先顺序是:n); print(l); printf(tt*平均寻道长度:%fn,num); /*/ void print(Node *head) /输出链表 Node *p;p=head-next; coutnext=NULL) printf(%dt,p-data); pr
15、intf(n); else while(p-next!=NULL) printf(%dt,p-data); p=p-next; printf(%dt,p-data); printf(n); /*/ void Create_Linklist(Node *head)/创建链表 Node *p,*q; int i; scanf(%d,&i); q=head; while(i!=0) p=(Node *)malloc(sizeof(Node); p-next=NULL; p-data=i; q-next=p; q=p; cini; /* c+;*/ /*/ int Length_Linklist(No
16、de *head)/计算链表长int l;Node *p; p= head-next; l=1; while(p-next) p=p-next; l+; return l; 五、总结 通过此次课程设计，我对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、有了更深刻的理解和掌握，使我能够为磁盘调度选择适当的算法，提高CPU工作效率。设计过程中遇到的困难在老师和同学的帮助下顺利解决并通过了验收，我深刻认识到算法的逻辑性对程序的重要影响，算法的准确度对程序运行结果的重要影响，这对我以后在操作系统的学习中有极大帮助。六、 参考资料1 黄维通等. Visual C+ 面向对象与可视化程序设计. 北京：清华大学出版社，2011.2 郑宗汉等. 算法设计与分析. 北京：清华大学出版社，2005.3 赵剑云等译, 美George Shepherd等著. 深入解析MFC. 北京：中国电力出版社，2003.4 Microsoft Platform SDK, August 2001 Edition.
免费区 
