操作系统课程设计磁盘调度算法 目 录 1 课程设计目的及要求……………………………………………………1 2 相关知识…………………………………………………………………1 3 题目分析…………………………………………………………………2 4 概要设计…………………………………………………………………2 4.1 先来先服务（FCFS）的设计思想……………………………….2 4.2 最短寻道时间优先调度（SSTF）的设计思想…………………..2 4.3 扫描算法（SCAN）的设计思想…………………………………2 4.4 循环扫描（CSCAN）的设计思想………………………………..2 5 代码及流程………………………………………………………………3 5.1 流程图……………………………………………………………...3 5.2 源代码……………………………………………………………...8 6 运行结果…………………………………………………………………16 7 设计心得…………………………………………………………………19 参考文献…………………………………………………………………………19 1 课程设计目的及要求 设计目的：加深对操作系统原理的进一步认识，加强实践动手能力和程序开发能力的培养，提高分析问题解决问题的能力，培养合作精神，以巩固和加深磁盘调度的概念。操作系统是一门工程性很强的课程，它不仅要求学生掌握操作系统的工作原理和理论知识，也要求学生的实际动手能力，以加深对所学习内容的理解，使学生熟练地掌握计算机的操作方法，使用各种软件工具，加强对课程内容的理解。这次课程设计，就是通过模拟磁臂调度来加深对操作系统中磁臂调度概念的理解。使学生熟悉磁盘管理系统的设计方法；
加深对所学各种磁盘调度算法的了解及其算法的特点。
设计要求：编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长度；
要求设计主界面可以灵活选择某算法，且以下算法都要实现 1、先来先服务算法（FCFS）
2、最短寻道时间优先算法（SSTF）
3、扫描算法（SCAN）
4、循环扫描算法（CSCAN）
2 相关知识 数据结构：数组 now:当前磁道号; array[]:放置磁道号的数组; void FCFS(int array[],int m )先来先服务算法(FCFS) void SSTF(int array[],int m)最短寻道时间优先算法(SSTF) void SCAN(int array[],int m) 扫描算法(SCAN) void CSCAN(int array[],int m)循环扫描算法(CSCAN) 磁盘调度：当有多个进程都请求访问磁盘时，采用一种适当的驱动调度算法，使各进程对磁盘的平均访问（主要是寻道）时间最小。目前常用的磁盘调度算法有：1）闲来先服务2）最短寻道时间优先3）扫描算法4）循环扫描算法等 3 题目分析 选择一个自己熟悉的计算机系统和程序设计语言模拟操作系统基本功能的设计方法及其实现过程 完成各分项功能。在算法的实现过程中，要求可决定变量应是动态可变的；
同时模块应该有一个合理的输出结果。具体可参照实验的程序模拟 .各功能程序要求自行编写程序实现，不得调用现有操作系统提供的模块或功能函数。磁盘调度程序模拟。先来先服务调度算法. 最短寻道时间优先调度，循环（SCAN）调度算法。程序设计语言自选，最终以软件（含源代码以及执行程序）和设计报告的形式提交课程设计结果.。磁盘调度让有限的资源发挥更大的作用。在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列。
4 概要设计 1.先来先服务（FCFS）的设计思想 即先来的请求先被响应。FCFS策略看起来似乎是相当“公平“的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候fcfs也被看作是最简单的磁盘调度算法。
2.最短寻道时间优先调度（SSTF）的设计思想 最短时间优先算法选择这样的进程。要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。
3.扫描算法（SCAN）的设计思想 扫描（SCAN）调度算法:该算法不仅考虑到欲访问 的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像。
4.循环扫描（CSACN）的设计思想 循环扫描（CSCAN）算法：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。但本实验已完全能演示循环扫描的全过程。
5 代码及流程 1.先来先服务（FCFS）
图 1—1 FCFS的流程图 2.最短寻道时间优先调度（SSTF）
图1—2 SSTF的流程图 3.扫描算法（SCAN）
图1—3 SCAN的流程图 4.循环扫描（CSCAN）
图1—4 CSCAN的流程图 图1—5 主函数的流程图 源代码：
#include“stdio.h“ #include“stdlib.h“ //#include“iostream.h“ #define maxsize 100 //定义最大数组域 //先来先服务调度算法 void FCFS(int array[],int m) { int sum=0,j,i; int avg; printf(“＼n FCFS调度结果: “); for(i=0;i<m;i++)//输出FCFS磁盘调度结果 { printf(“%d “,array[i]); } for(i=0,j=1;j<m;i++,j++) { sum+=abs(array[j]-array[i]);//累计总的移动距离 } avg=sum/(m-1);//计算平均寻道长度 printf(“＼n 移动的总道数：
%d ＼n“,sum); printf(“ 平均寻道长度：
%d ＼n“,avg); } //最短寻道时间优先调度算法 void SSTF(int array[],int m) { int temp; int k=1; int now,l,r; int i,j,sum=0; int avg; for(i=0;i<m;i++) { for(j=i+1;j<m;j++)//对磁道号进行从小到大排列 { if(array[i]>array[j])//两磁道号之间比较 { temp=array[i]; array[i]=array[j]; array[j]=temp; } } } for( i=0;i<m;i++)//输出排序后的磁道号数组 { printf(“%d “,array[i]); } printf(“＼n 请输入当前的磁道号：“); scanf(“%d“,&now); printf(“＼n SSTF调度结果: “); if(array[m-1]<=now)//判断整个数组里的数是否都小于当前磁道号 { for(i=m-1;i>=0;i--)//将数组磁道号从大到小输出 printf(“%d “,array[i]); sum=now-array[0];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { for(i=0;i<m;i++)//将磁道号从小到大输出 printf(“%d “,array[i]); sum=array[m-1]-now;//计算移动距离 } else { while(array[k]<now)//逐一比较以确定K值 { k++; } l=k-1; r=k; //确定当前磁道在已排的序列中的位置 while((l>=0)&&(r<m)) { if((now-array[l])<=(array[r]-now))//判断最短距离 { printf(“%d “,array[l]); sum+=now-array[l];//计算移动距离 now=array[l]; l=l-1; } else { printf(“%d “,array[r]); sum+=array[r]-now;//计算移动距离 now=array[r]; r=r+1; } } if(l=-1) { for(j=r;j<m;j++) { printf(“%d “,array[j]); } sum+=array[m-1]-array[0];//计算移动距离 } else { for(j=l;j>=0;j--) { printf(“%d “,array[j]); } sum+=array[m-1]-array[0];//计算移动距离 } } avg=sum/m; printf(“＼n 移动的总道数：
%d ＼n“,sum); printf(“ 平均寻道长度：
%d ＼n“,avg); } //扫描算法 void SCAN(int array[],int m)//先要给出当前磁道号和移动臂的移动方向 { int temp; int k=1; int now,l,r,d; int i,j,sum=0; int avg; for(i=0;i<m;i++) { for(j=i+1;j<m;j++) { if(array[i]>array[j])//对磁道号进行从小到大排列 { temp=array[i]; array[i]=array[j]; array[j]=temp; } } } for( i=0;i<m;i++) { printf(“%d “,array[i]);//输出排序后的磁道号数组 } printf(“＼n 请输入当前的磁道号：“); scanf(“%d“,&now); if(array[m-1]<=now)//判断整个数组里的数是否都小于当前磁道号 { printf(“＼n SCAN调度结果: “); for(i=m-1;i>=0;i--) { printf(“%d “,array[i]);//将数组磁道号从大到小输出 } sum=now-array[0];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { printf(“＼n SCAN调度结果: “); for(i=0;i<m;i++) { printf(“%d “,array[i]);//将磁道号从小到大输出 } sum=array[m-1]-now;//计算移动距离 } else { while(array[k]<now)//逐一比较以确定K值 { k++; } l=k-1; r=k; printf(“＼n 请输入当前移动臂的移动的方向 (1 磁道号增加方向，0磁道号减小方向) : “); scanf(“%d“,&d); printf(“＼n SCAN调度结果: “); if(d==0) { for(j=l;j>=0;j--) { printf(“%d “,array[j]); } for(j=r;j<m;j++) { printf(“%d “,array[j]); } sum=now-2*array[0]+array[m-1];//计算移动距离 }//磁道号减小方向 else { for(j=r;j<m;j++) { printf(“%d “,array[j]); } for(j=l;j>=0;j--) { printf(“%d “,array[j]); } sum=-now-array[0]+2*array[m-1];//计算移动距离 }//磁道号增加方向 } avg=sum/m; printf(“＼n 移动的总道数：
%d ＼n“,sum); printf(“ 平均寻道长度：
%d ＼n“,avg); } //循环扫描算法 void CSCAN(int array[],int m) { int temp; int k=1; int now,l,r,d; int i,j,sum=0; int avg; for(i=0;i<m;i++) { for(j=i+1;j<m;j++) { if(array[i]>array[j])//对磁道号进行从小到大排列 { temp=array[i]; array[i]=array[j]; array[j]=temp; } } } for( i=0;i<m;i++) { printf(“%d “,array[i]);//输出排序后的磁道号数组 } printf(“＼n 请输入当前的磁道号：“); scanf(“%d“,&now); if(array[m-1]<=now)//判断整个数组里的数是否都小于当前磁道号 { printf(“＼n CSCAN调度结果: “); for(i=0;i<m;i++) { printf(“%d “,array[i]);//将磁道号从小到大输出 } sum=now-array[0]+array[m-1];//计算移动距离 } else if(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号 { printf(“＼n CSCAN调度结果: “); for(i=0;i<m;i++) { printf(“%d “,array[i]);//将磁道号从小到大输出 } sum=array[m-1]-now;//计算移动距离 } else { while(array[k]<now)//逐一比较以确定K值 { k++; } l=k-1; r=k; printf(“＼n 请输入当前移动臂的移动的方向 (1 磁道号增加方向，0磁道号减小方向) : “); scanf(“%d“,&d); printf(“＼n CSCAN调度结果: “); if(d==0) { for(j=l;j>=0;j--) { printf(“%d “,array[j]); } for(j=m-1;j>=r;j--) { printf(“%d “,array[j]); } sum=2*(array[m-1]-array[0])-array[r]+now;//计算移动距离 }//磁道号减小方向 else { for(j=r;j<m;j++) { printf(“%d “,array[j]); } for(j=0;j<r;j++) { printf(“%d “,array[j]); } sum=2*(array[m-1]-array[0])+array[r-1]-now;//计算移动距离 } }//磁道号增加方向 avg=sum/m; printf(“＼n 移动的总道数：
%d ＼n“,sum); printf(“ 平均寻道长度：
%d ＼n“,avg); } // 操作界面 int main() { int c; FILE *fp;//定义指针文件 int cidao[maxsize];//定义磁道号数组 int i=0,count; fp=fopen(“cidao.txt“,“r+“);//读取cidao.txt文件 if(fp==NULL)//判断文件是否存在 { printf(“＼n 请 先 设 置 磁 道! ＼n“); exit(0); } while(!feof(fp))//如果磁道文件存在 { fscanf(fp,“%d“,&cidao[i]);//调入磁道号 i++; } count=i-1; printf(“＼n --------------------------------------------------＼n“); printf(“ 10-11年度OS课程设计--磁盘调度算法系统＼n“); printf(“ 计算机科学与技术二班＼n“); printf(“ 姓名：宋思扬＼n“); printf(“ 学号：0803050203＼n“); printf(“ 电话：************＼n“); printf(“ 2010年12月29日＼n“); printf(“＼n --------------------------------------------------＼n“); printf(“＼n 磁道读取结果：＼n“); for(i=0;i<count;i++) { printf(“%5d“,cidao[i]);//输出读取的磁道的磁道号 } printf(“＼n “); while(1) { printf(“＼n 算法选择：＼n“); printf(“ 1、先来先服务算法（FCFS）＼n“); printf(“ 2、最短寻道时间优先算法（SSTF）＼n“); printf(“ 3、扫描算法（SCAN）＼n“); printf(“ 4、循环扫描算法（CSCAN）＼n“); printf(“ 5. 退出＼n“); printf(“＼n“); printf(“请选择：“); scanf(“%d“,&c); if(c>5) break; switch(c)//算法选择 { case 1: FCFS(cidao,count);//先来先服务算法 printf(“＼n“); break; case 2: SSTF(cidao,count);//最短寻道时间优先算法 printf(“＼n“); break; case 3: SCAN(cidao,count);//扫描算法 printf(“＼n“); break; case 4: CSCAN(cidao,count);//循环扫描算法 printf(“＼n“); break; case 5: exit(0); } } return 0; } 6 运行结果 图2—1 运行界面 图2—2 运行FCFS的界面 图2—3 运行SSTF的界面 图2—4 运行SCAN的界面 图2—5 运行SCAN的界面 图2—6 运行CSCAN的界面 图2—7 运行CSCAN的界面 运行结果：
四种磁盘调度运行结果正确，与预期的相符。
7 设计心得 此次操作系统的课程设计，从理论到实践，在两个星期的日子里，可以说是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。
本次实验首先要了解磁盘调度的工作原理及四种调度方法的工作原理。在课程设计前的准备工作时，先把这部分工作做完了。在设计总的程序框架的时候，要注意各功能模块的位置，尽量做到简洁、有序；
各功能模块与主程序要正确衔接。
在设计的过程中遇到许多问题，我设计的是四种调度算法中的后两种。例如：在最初程序设计时主要有两种构思：1）选用数据结构是链表的。2）选用数组。我最初尝试了用链表，觉得方便易懂，但是在循环扫描处出现了些问题，后来又转变了设计思路，选用了数组，直接进行排序，然后再联系到各功能模块。
同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，自身知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能力还急需提高。比如说编语言掌握得不好，应用程序编写不太会……通过这次课程设计之后，一定把以前所学过的知识重新温故。在此，也感谢在课程设计过程中帮我解惑的老师和同学。
8 参考文献 [1] 《操作系统》
人民邮电出版社 宗大华 宗涛 陈吉人 编著 [2] 《C语言程序设计》
清华大学出版社 马秀丽 刘志妩 李筠 编著 [3] 《操作系统实验指导书》
沈阳理工大学 唐巍 菀勋 编著
推荐访问: