磁盘调度算法的模拟实现课程设计报告

1、淮北师范大学操作系统课程设计磁盘调度算法的模拟实现学院计算机科学与技术专业 计算机科学与技术（师范）学号学生姓名指导教师姓名2015年 7月 1日目录一、引言2二、总体设计错误！未定义书签。1. 功能实现错误！未定义书签。2. 流程图错误！未定义书签。3. 具体内容3三、实验验证51. 结果截图72. 代码分析6四、源代码9五、总结31六、参考资料131一、引言1、课程设计的目的：操作系统课程设计是计算机专业重要的教学环节， 它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来， 独立分析和解决实际问题的机会。进一步巩固和复习操作系统的基础知识。培养学生结构化程序、模块化程序

2、设计的方法和能力。提高学生调试程序的技巧和软件设计的能力。提高学生分析问题、 解决问题以及综合利用 C 语言进行程序设计的能力。2、设计内容： 设计并实现一个本别利用下列磁盘调度算法进行磁盘调度的模拟程序。1FCFS2、SSTF3、设计要求：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 号2柱面执行操作， 随后处理 15 号柱面请求， 后继操作的次序应该是 99、130、148、159、 199。采用最短寻找时间优先算法决定等待访问者执行操作的次序时， 读写磁头总共移动了 200 多个柱面的距离， 与先来先服务、 算法比较， 大幅度地减少了寻找时间，因而缩短了为各访问者请求服务的平均时间，也就提高了系统效率。但最短查找时间优先（ SSTF）调度， FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最

5、短（也就是查找时间最短）的请求作为下一次服务的对象。 SSTF 查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖延（又称饥饿）。 先来先服务算法（ FCFS）流程图 :开始输入磁道号按输入顺序将磁道序列输出求平均寻道长度输出移动的平均磁道数结束3 最短寻道时间优先算法（SSTF）流程图 :开始输入磁道号使用冒泡法从小到大排序输出排好序的磁道序列输入当前磁道号判断当前磁头在序列中的位置选择与当前磁道距离最近的磁道进行扫描移动到最小（大）号，改向外（内）移动扫描未扫描的磁道求平均寻道长度输出移动的平均磁道数结束4三、总体验证1 、数据结构及信号量定义的说明；本系统划分为四个模块：先

6、来先服务算法模块void FCFS(int array,intm)、最短寻道时间优先算法模块void SSTF(int array,int m)、扫描算法模块 void SCAN(int array,int m)和循环扫描算法模块：void CSCAN(intarray,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;j<m;i+,j+)sum+=abs(arrayj-arrayi);ave=(float)(sum)/(float)(m);2 最短寻道时间优先算法模块：void SSTF(int array,int m)主要代码：for(i=0;i<m;i+)/* 使用冒泡法按从小到大顺序排列*/for(j=i+1;j<m;j+)if(arrayi>arrayj)t

8、emp=arrayi;5arrayi=arrayj;arrayj=temp;if(arraym-1<=now)/* 若当前磁道号大于请求序列中最大者，则直接由外向内依次给予各请求服务 */for(i=m-1;i>=0;i-)cout<<arrayi<<" "sum=now-array0;else if(array0>=now)/* 若当前磁道号小于请求序列中最小者，则直接由内向外依次给予各请求服务 */while(l>=0)&&(r<m)/* 当前磁道在请求序列范围内*/if(now-arrayl)<

9、;=(arrayr-now)/* 选择与当前磁道最近的请求给予服务 */cout<<arrayl<<" "sum+=now-arrayl;now=arrayl;l=l-1;3、实验的步骤；1 先来先服务算法输入磁道序列： 55 58 39 18 90 160 150 38 184当前磁道号： 1002 最短寻道时间优先算法6（ 1）当前磁道号大于磁道序列中的最大的磁道号时（ 2）输入磁道序列： 55 58 39 18 90 160 150 38 184当前磁道号： 1007四、源代码 ：#include<iostream>#include

10、<cmath>#include<stdio.h>using namespace std;typedef struct nodeint data;struct node *next;Node,*Linklist;void main()void Create_Linklist(Node *);void fcfs();/ 声明先来先服务函数FCFSvoid sstf();/ 声明最短寻道时间优先函数sstfvoid print(Node *);8int s;printf("*磁盘调度算法 *n");printf("t*1, 先来先服务算法FCFS

11、n");printf("t*2, 最短寻道时间优先算法SSTFn");printf("t*0, 退出 n");printf("t* 请选择 :");scanf("%d",&s);while(s!=0)switch(s)case1:printf("tt*你选择了: 先来先服务算法FCFSn");fcfs();break;case 2:printf("tt* 你 选 择 了 : 最 短 寻 道 时 间 优 先 算 法 SSTFn");sstf();break;p

12、rintf("tt*退出请选 0,继续请选 1,2,n");scanf("%d",&s);/*/ void fcfs()/ 先来先服务算法void Create_Linklist(Node *);void print(Node*);int Length_Linklist(Node *);Node *l,*head;/*m,*n;*/float num=0;/num 为平均寻道长度int c,f;head=(Node *)malloc(sizeof(Node);head->next=NULL;printf("*新建一个单链表 ,以

13、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;i<c;i+)num+=abs(l->data-f);f=l->data;l=l->next;num=num/c;printf("tt*先来先

14、服务的寻道顺序是:n");9print(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 作为结束标志 :*n&

15、quot;); 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;i<c;

16、i+)int min=abs(f-r->data);for(int j=0;j<c-i-1;j+)p=p->next;q=q->next;if(abs(f-p->data)<min)min=abs(f-p->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;10p=head->next;s=head;r=head->next;num=num/c;printf("

17、;tt*最短寻道时间优先顺序是:n");print(l);printf("tt*平均寻道长度 :%fn",num);/*/void print(Node *head)/ 输出链表Node *p;p=head->next;cout<<"单链表显示 :"if(p=NULL)printf(" 单链表为空 :n");else if(p->next=NULL)printf("%dt",p->data);printf("n");elsewhile(p->next

18、!=NULL)printf("%dt",p->data);p=p->next;printf("%dt",p->data);printf("n");/*/voidCreate_Linklist(Node *head)/创建链表Node *p,*q;int i;scanf("%d",&i);q=head;while(i!=0)11p=(Node *)malloc(sizeof(Node);p->next=NULL;p->data=i;q->next=p;q=p;cin>>i; /* c+;*/*/int Length_Linklist(Node *head)/ 计算链表长int l;Node *p;p= head->next;l=1;while(p->next)p=p->next;l+;return l;五、总结通过此次课程设计，我对操作系统的基础知识了解得更透彻了，同时对磁盘调度的四种算法先来先服务算法（FCFS）、最短寻道时间优先算法（ SSTF）、有了更深刻的理解和掌握，使我能够为磁盘调度选择适当的算法，提高CPU 工