操作系统课程设计,磁盘调度算法

目录1课程设计目的及要求错误!未定义书签。相关知识错误!未定义书签。题目分析.概要设计.4.1先来先服务FCF）的设计思想.24.2最短寻道时间优先调度S4.2最短寻道时间优先调度STB的设计思想，目4.3扫描算法SCAN的设计思想2……4.4循环扫描GSCAN的设计思想・2.…代码及流错35.1流程图..35.2源代码J86运行结果.367设计心得・319参考文献1课程设计目的及要求19设计目的：加深对操作系统原理的进一步认识，加强实践动手能力和程序开发能力的培养，提高分析问题解决问题的能力，培养合作精神，以巩固和加深磁盘调度的概念。操作系统是一门工程性很强的课程，它不仅要求学生掌握操作系统的工作原理和理论知识，也要求学生的实际动手能力，以加深对所学习内容的理解，使学生熟练地掌握计算机的操作方法，使用各种软件工具，加强对课程内容的理解。这次课程设计，就是通过模拟磁臂调度来加深对操作系统中磁臂调度概念的理解。使学生熟悉磁盘管理系统的设计方法；加深对所学各种磁盘调度算法的了解及其算法的特点。设计要求：编程序实现下述磁盘调度算法，并求出每种算法的平均寻道长度；要求设计主界面可以灵活选择某算法，且以下算法都要实现1、先来先服务算法(FCFS)2、最短寻道时间优先算法(SSTF)3、扫描算法(SCAN)4、循环扫描算法(CSCAN)2相关知识数据结构：数组now:当前磁道号；array：]:放置磁道号的数组；voidFCFS(intarray[],intm)先来先服务算法(FCFS)voidSSTF(intarray[],intm)最短寻道时间优先算法(SSTF)voidSCAN(intarray[],intm)扫描算法(SCAN)voidCSCAN(intarray[],intm)循环扫描算法(CSCAN)磁盘调度：当有多个进程都请求访问磁盘时，采用一种适当的驱动调度算法，使各进程对磁盘的平均访问(主要是寻道)时间最小。目前常用的磁盘调度算法有：1)闲来先服务2)最短寻道时间优先3)扫描算法4)循环扫描算法等3题目分析选择一个自己熟悉的计算机系统和程序设计语言模拟操作系统基本功能的设计方法及其实现过程完成各分项功能。在算法的实现过程中，要求可决定变量应是动态可变的；同时模块应该有一个合理的输出结果。具体可参照实验的程序模拟.各功能程序要求自行编写程序实现，不得调用现有操作系统提供的模块或功能函数。磁盘调度程序模拟。先来先服务调度算法.最短寻道时间优先调度，循环（SCAN）调度算法。程序设计语言自选，最终以软件（含源代码以及执行程序）和设计报告的形式提交课程设计结果.。磁盘调度让有限的资源发挥更大的作用。在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列。4概要设计先来先服务（FCFS）的设计思想即先来的请求先被响应。FCFS策略看起来似乎是相当"公平"的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候fcfs也被看作是最简单的磁盘调度算法。最短寻道时间优先调度（SSTF）的设计思想最短时间优先算法选择这样的进程。要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。扫描算法（SCAN）的设计思想扫描（SCAN）调度算法:该算法不仅考虑到欲访问的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现''饥饿〃现像。循环扫描（CSACN）的设计思想循环扫描（CSCAN）算法：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。但本实验已完全能演示循环扫描的全过程。5代码及流程1.先来先服务（FCFS）图1—1FCFS的流程图2.最短寻道时间优先调度（SSTF）图1—2SSTF的流程图3.扫描算法（SCAN）图1—3SCAN的流程图4.循环扫描（CSCAN）dV^uriL>iii.图1—4CSCAN的流程图priiitfif晴光世Hl时山叫i])iffitmnw*pdirtflf1^算京谨祥…bt^lk；'F航l〔l叫reluinO;图1—5主函数的流程图源代码：#include"stdio.h”#include"stdlib.h”//#include"iostream.h”#definemaxsize100//定义最大数组域//先来先服务调度算法voidFCFS(intarray[],intm){intsum=0,j,i;intavg;printf("\nFCFS调度结果：”)；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);}//最短寻道时间优先调度算法voidSSTF(intarray[],intm){inttemp;intk=1;intnow,l,r;inti,j,sum=0;intavg;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("\nSSTF调度结果：”)；if(array[m-1]<=now)//判断整个数组里的数是否都小于当前磁道号{for(i=m-1;i>=0;i--)//<数组磁道号从大到小输出printf("%d",array[i]);sum=now-array[0];//计算移动距离}elseif(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);}〃扫描算法voidSCAN(intarray[],intm)/冼要给出当前磁道号和移动臂的移动方向{inttemp;intk=1;intnow,l,r,d;inti,j,sum=0;intavg;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("\nSCAN调度结果：”)；for(i=m-1;i>=0;i--){printf("%d",array[i]);//将数组磁道号从大到小输出}sum=now-array[0];//计算移动距离}elseif(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号{printf("\nSCAN调度结果：”)；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("\nSCAN调度结果：”)；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);}//循环扫描算法voidCSCAN(intarray[],intm){inttemp;intk=1;intnow,l,r,d;inti,j,sum=0;intavg;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("\nCSCAN调度结果：”)；for(i=0;i<m;i++){printf("%d",array[i]);//将磁道号从小到大输出}sum=now-array[0]+array[m-1];//计算移动距离}elseif(array[0]>=now)//判断整个数组里的数是否都大于当前磁道号{printf("\nCSCAN调度结果：”)；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("\nCSCAN调度结果：”)；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;//i十算移动距离}}//磁道号增加方向avg=sum/m;printf("\n移动的总道数：%d\n",sum);printf("平均寻道长度：%d\n",avg);}//操作界面intmain(){intc;FILE*fp;//定义指针文件intcidao[maxsize];//定义磁道号数组inti=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("计算机科学与技术二班4”);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)//算法选择{case1:FCFS(cidao,count);//先来先服务算法printf("\n");break;case2:SSTF(cidao,count);//最短寻道时间优先算法printf("\n");break;case3:

SCAN(cidao,count);//扫描算法printf("\n");break;case4:CSCAN(cidao,count);//彳循环扫描算法printf("\n");break;case5:exit(0);}}return0;}6运彳丁结果'K:\Deb。新果程谀计■吨盘调度算拄系统1牯学与亟术西册5脚以军■盼日3既驯342011^12^29日磁道读取结果'1112453244222517劳时<算劳时<算肝逗注指洼羞扫.来短描环出□rlntuSC^^AHI算间sc法请咂择=图2—1运行界面

请选择，1FCF&调度结果：1112453244222517移动曲直措既92平均寻道长蔑：13(SSTFJFS(SSTFJFS法N)

FC算CA

—先}c£

茬AN1法务时—算服道青J:先寻骨梅来短描环出混先最iQW!"W'12345田■3图2—2运行FCFS的界面请选择3>112172225324445请输入当前的磁道号，30i3225221?121144割，5757服道靠GSCftN)〔FCFS服道靠GSCftN)〔FCFS平均寻道长窿12345FS法N)FC算S—先JCS亲AN1MI^SC法务时—算馨富.先1WG平均寻道长窿12345FS法N)FC算S—先JCS亲AN1MI^SC法务时—算馨富.先1WG.来短描环出.先最iGW(SSTF；请输入当前的磁道号；睥请输入当前移动臀的移动的方向d磁道号增加方向，©磁道号减小方向):0:171211222532444545图2—4运行SCAN的界面SCAN调度结果移动菌懿数平均寻道长〔商明法务时—算H.先om一来短描环出(FCFS)先算法SCAN调度结果移动菌懿数平均寻道长〔商明法务时—算H.先om一来短描环出(FCFS)先算法)CSCAN)(SSTF)请输入当前的磁道号：22请输入当前移动曾的移动的方向＜1磁道号增加方向，。磁道号减小方向〉:12225324445171211577图2—5运行SCAN的界面请选择：41112172225324445请输入当前的磁道号：22请输入当前移动臂的移动的方向＜1磁道号增加方向，瞰道号减小方向》:0CSCAN调度结具：1712114544322522移动的鑫寒68平均寻道长篱8算123算12345FS法N)FC算3—先>cs希AN1"商盹法务时{算H.先寻兽_来短描环出（SSTF）图2—6运行CSCAN的界面请选择：41112172225324445请输入当前的破道号：2