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

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

2、步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用 c 语言进行程序设计 的能力。 2、设计内容：、设计内容：设计并实现一个本别利用下列磁盘调度算法进行磁盘调度的模拟 程序。 1、先来先服务算法fcfs 2、最短寻道时间优先算法sstf 3、设计要求：、设计要求： 1.磁头初始磁道号，序列长度，磁道号序列等数据可从键盘输入，也可从 文件读入。 2.最好能实现磁道号序列中磁道号的动态增加。 3.磁道访问序列以链表的形式存储 4. 给出各磁盘调度算法的调度顺序和平均寻道长度 2、总体设

3、计总体设计 1 1、算法实现、算法实现 1.先来先服务算法（fcfs） 先来先服务（fcfs）调度:按先来后到次序服务，未作优化。 最简单的移臂调度算法是“先来先服务”调度算法，这个算法实际上不考虑访 问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。例如， 如果现在读写磁头正在 50 号柱面上执行输出操作，而等待访问者依次要访问的 柱面为 130、199、32、159、15、148、61、99，那么，当 50 号柱面上的操作 结束后，移动臂将按请求的先后次序先移到 130 号柱面，最后到达 99 号柱面。 采用先来先服务算法决定等待访问者执行输入输出操作的次序时，移动臂 来回地

4、移动。先来先服务算法花费的寻找时间较长，所以执行输入输出操作的 总时间也很长。 2.短寻道时间优先算法（sstf） 最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个 请求先执行的，而不管访问者到来的先后次序。现在仍利用同一个例子来讨论， 现在当 50 号柱面的操作结束后，应该先处理 61 号柱面的请求，然后到达 32 号 柱面执行操作，随后处理 15 号柱面请求，后继操作的次序应该是 99、130、148、159、199。 采用最短寻找时间优先算法决定等待访问者执行操作的次序时，读写磁头 总共移动了 200 多个柱面的距离，与先来先服务、算法比较，大幅度地减少了 寻找时间，因而

5、缩短了为各访问者请求服务的平均时间，也就提高了系统效率。 但最短查找时间优先（sstf）调度，fcfs 会引起读写头在盘面上的大范围移动， sstf 查找距离磁头最短（也就是查找时间最短）的请求作为下一次服务的对象。 sstf 查找模式有高度局部化的倾向，会推迟一些请求的服务，甚至引起无限拖 延（又称饥饿） 。 先来先服务算法（先来先服务算法（fcfsfcfs）流程图: 输入磁道号 求平均寻道长度 输出移动的平均磁道数 按输入顺序将磁道序列输出 开始 结束 最短寻道时间优先算法（最短寻道时间优先算法（sstfsstf）流程图: 求平均寻道长度 选择与当前磁道距离最 近的磁道进行扫描 移动到最小

6、（大）号， 改向外（内）移动扫描 未扫描的磁道 输出移动的平均磁道数 输出排好序的磁道序列 判断当前磁头在 序列中的位置 结束 开始 输入磁道号 使用冒泡法从小到大排序 输入当前磁道号 三、总体验证 1、数据结构及信号量定义的说明； 本系统划分为四个模块：先来先服务算法模块 void fcfs(int array, int m)、最短寻道时间优先算法模块 void sstf(int array,int m)、扫描算 法模块 void scan(int array,int m) 和循环扫描算法模块：void cscan(int array,int m) 。 2. 先来先服务算法模块：void f

7、cfs(int array,int m) 输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度， 输出移动平均磁道数。 3、 最短寻道时间优先算法模块：void sstf(int array,int m) 将磁道号用冒泡法从小到大排序，输出排好序的磁道序列，输入当前磁道 号，根据前磁道在已排的序列中的位置，选择扫描的顺序，求出平均寻道长度， 输出移动的平均磁道数。 4 4、代码分析、代码分析 1 1、先来先服务算法模块：、先来先服务算法模块：void fcfs(int array,int m) 主要代码： for(i=0,j=1;jm;i+,j+) sum+=abs(arrayj-a

8、rrayi); ave=(float)(sum)/(float)(m); 2 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-) coutarrayi=now) /*若当前磁道号小于请求序列中最小者，则直接由内向 外依次给予各请求服务*/ while(l=0) sum+=now-arrayl; now=a

9、rrayl; l=l-1; 3、实验的步骤； 1 先来先服务算法 输入磁道序列：55 58 39 18 90 160 150 38 184 当前磁道号：100 2 最短寻道时间优先算法 （1）当前磁道号大于磁道序列中的最大的磁道号时 （2）输入磁道序列：55 58 39 18 90 160 150 38 184 当前磁道号：100 四、源代码： #include #include #include using namespace std; typedef struct node int data; struct node *next; node,*linklist; void main() v

10、oid create_linklist(node *); void fcfs();/声明先来先服务函数 fcfs void sstf();/声明最短寻道时间优先函数 sstf void print(node *); int s; printf(*磁盘调度算法*n); printf(t*1,先来先服务算法 fcfsn); printf(t*2,最短寻道时间优先算法 sstfn); printf(t*0,退出n); printf(t*请选择:); scanf(%d, while(s!=0) switch(s) case 1:printf(tt*你选择了:先来先服务算法 fcfsn);fcfs();

11、 break; case 2:printf(tt*你选择了:最短寻道时间优先算法 sstfn);sstf(); break; printf(tt*退出请选 0,继续请选 1,2,n);scanf(%d, /*/ 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

12、-next=null; printf(*新建一个单链表,以 0 作为结束标志:*n); create_linklist(head); c=length_linklist(head); printf(tt*从几号磁道开始:*); scanf(%d,/f 为磁道号 print(head); printf(t*链表长度为:%dn,c); l=head-next; for(int i=0;idata-f);f=l-data;l=l-next; num=num/c; printf(tt*先来先服务的寻道顺序是:n); print(head); printf(tt*平均寻道长度:%fn,num); /*/

13、 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); create_linklist(head); c=length_linklist(head); printf(tt*从几号磁道开始:*); scanf(%

14、d, /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-data)data); r=p; s=q; num+=abs(f-r-data); f=r-data; s-next=r-next; r-next=null; m-next=r;

15、 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); printf(n); else while(p-next!=null) printf(%dt,p-data); p=p-next; printf(%dt,p-data); pr

16、intf(n); /*/ void create_linklist(node *head)/创建链表 node *p,*q; int i; scanf(%d, 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(node *head)/计算链表长 int l; node *p; p= head-next; l=1; while(p-next) p=p-next; l+; return l; 五、总结 通过此次课程设计，我对操作系统的基础知识了解得更透彻了， 同时对磁盘调度的四种算法先来先服务算法（fcfs） 、最短寻 道时间优先算法（sstf） 、有了更深刻的理解和掌握，使我能够为 磁盘调度选择适当的算法，提高 cpu 工作效率。设计过程中遇到的 困难在老师和同学的帮助下顺利解决并通过了验收