磁盘调度算法的实现与分析

1、计算机操作系统课程设计设计说明书（题目）磁盘调度算法的实现与分析起止日期： 2013 年12月25日至 2013年12 月 31日学 生班学成 指导教师（签字）计算机与通信学院2013年12月31日 TOC o 1-5 h z HYPERLINK l bookmark7 o Current Document 1课程设计简介31.1课程设计的目的31.2课程设计内容3 HYPERLINK l bookmark14 o Current Document 2数据结构的设计4 HYPERLINK l bookmark17 o Current Document 2.1变量和数组的定义4 HYPERLIN

2、K l bookmark20 o Current Document 2.2函数的定义4 HYPERLINK l bookmark23 o Current Document 3功能模块（或算法）描述4 HYPERLINK l bookmark26 o Current Document 3.1模块划分43.2模块调用关系图8错误！未定义书签。124程序运行结果5心得体会. HYPERLINK l bookmark43 o Current Document 参考文献13 HYPERLINK l bookmark52 o Current Document 附源代码131课程设计简介1.1课程设计的目的

3、本课程设计的目的是通过设计一个磁盘调度模拟系统，从而使磁盘调度算法 更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对 先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调 度算法的理解。1.2课程设计内容系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、 最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。1、先来先服务算法（FCFS）这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进 行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不 会出现某一进程的请求长期得不到

4、满足的情况。此算法由于未对寻道进行优化， 在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平 均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。2、最短寻道时间优先算法（S STF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近， 以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均 寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响 应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会 无限期的被延迟，有些请求的响应时间将不可预期。3、扫描算法（SCAN）扫描算法不仅考虑到欲访问的磁道

5、与当前磁道的距离，更优先考虑的是磁头 的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个 访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向 外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时， 同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从 而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故 又称为电梯调度算法。此算法基本上克服了最短寻道时间优先算法的服务集中于 中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即 吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两

6、侧磁道被访问 的频率仍低于中间磁道。4、循环扫描算法(CSCAN)循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的， 当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是 由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待 的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自 里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道， 即将最小磁道号紧接着最大磁道号构成循环，进行扫描。2数据结构的设计2.1变量和数组的定义intTrackN;用来存放随机生成的磁道请求序列int Sum=0;用来存放移动的总磁

7、道数float AverTime=0.0;用来存放平均寻道数2.2函数的定义void Sort(int Track,int Num):冒泡法从小到大排序void Output(int Track,int Num):用于将随机生成的磁道请求序列和当 前磁道数输出void FCFS(int Track,int Num):先来先服务算法模块void SSTF(int Track,int Num):最短寻道时间优先算法模块void SCAN(int Track,int Num)扫描算法模块void C_SCAN(int Track,int Num):循环扫描算法模块3功能模块(或算法)描述3.1模块划

8、分本系统划分为四个模块：先来先服务算法模块void FCFS(int Track口，int Num)、最短寻道时间优先算法模块void SSTF(int Track,int Num)、扫描算 法模块 void SCAN(int Track,int Num)和循环扫描算法模块：void C_SCAN (int Track,int Num)1先来先服务算法模块：void FCFS(int array,int m)输入磁道号，按先来先服务的策略输出磁盘请求序列，求平均寻道长度，输 出移动平均磁道数。主要代码：for(i=0;iN;i+)(if(NumTracki)temp二Tracki-Num;el

9、se temp二Num-Tracki;Num二Tracki;Sum+=temp;AverTime=(float)Sum/N;2最短寻道时间优先算法模块：void SSTF(int Track,int Num)首先将随机生成的磁盘请求序列与当前所在的磁道号进行比较，将所得之差 用数组Ttrack保存起来。然后在求出Ttrack数组中最小的数即为第一个访问的 磁道。再将访问过的磁道置-1。再次循环，求出平均寻道长度，输出移动的平均 磁道数。主要代码：for(j=0;jN;j+)for(i=0;iN;i+)(if(Ttracki=-1)continue;else(if(NumTracki)Ttrac

10、ki=Tracki-Num;else Ttracki=Num-Tracki;min=200;minj=0;for(i=0;iN;i+)(if(Ttracki=-1) continue;else(if(Ttrackimin)(min二Ttracki;minj=i;Num二Trackminj;DiskDcount+=Num;Sum=Sum+Ttrackminj;Ttrackminj=-1;AverTime=(float)Sum/N;3 扫描算法模块：void SCAN(int Track,int Num)将磁道号用冒泡法将随机生成的磁道请求序列从小到大排序，随机生成的当 前磁道号，选择移动臂的移动

11、方向，根据当前磁道在已排的序列中的位置，选择 扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。主要代码：Output(Track,Num);for(i=0;iN;i+)tempi=Tracki;Sort(temp,N);/将访问序列从小到大排序while(tempk=0;j-)(printf( %d ，tempj);for(j=r;jN;j+)(printf( %d ，tempj);Sum二Num-2*temp0+tempN-1;else(printf(磁道访问的序列为：)；for(j=r;j=0;j-)(printf( %d ，tempj);Sum二Num-temp0+2*tempN-1

12、;AverTime=(float)Sum/N;4 循环扫描算法模块：void C_SCAN(int Track口，int Num)将磁道号用冒泡法从小到大排序，输出排好序的序列，随机生成的当前磁道 号，规定移动臂单向反复的从内向外移动，根据当前磁道在已排的序列中的位置， 选择扫描的顺序，求出平均寻道长度，输出移动的平均磁道数。主要代码：Output(Track,Num);for(i=0;iN;i+)tempi=Tracki;Sort(temp,N);printf(磁道访问的序列为：)；while(tempkNum)k+;l=k-1;r=k;for(j=r;jN;j+)(printf( %d ，

13、tempj);for(j=0;jr;j+)printf( %d ，tempj);Sum=2*tempN-1+templ-Num-2*temp0;AverTime=(float)(Sum)/(float)(N);3.2模块调用关系图4程序运行结果磁盘调度模拟系统主界面: I：膜作紊统新建文件表Dehug 5.exeX XX XXJJOXJOXXS 京i周，度 畀 j|tJOXJOXXJXXXXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXXJOXJOXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXX请选择要使用的算法HJC JC HJC JCX JC XXxxxxxXXJ

14、CXXHJC JC HJC JCX JC XX来短描环用出碧麟蔑蓦沥 鼻法“SN 调匿算法 算法,进行比较XXJXXJJJXJJXXKJXJJXXJXXXXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXXJOXJOXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXXR青选择算法:选择第一种算法：先来先服务调度算法 I：涯作系统新建文件夹Deb ugA5.exe请选择算法：1XKJXJJXXJXXX XXX KN XXX服-务-调音畀；：J XKJXXJXXXJJXJJXXJXXJXJXJJX6 和符： 列号列为 序道道备长 争 求前道均平46 回NX XXKJXJJ X

15、XXX2 jj j 周，营畀女XXJXXJXJXJJXXXXXJCXXJCXXJCXj 青 j.近 1 莘要,使用的 丢XXX XXX XX XXXJXXXJOXJO虫 CF算 Is 法调N 算先CA法进 调间法匿法 务时算调算 H 先寻殍五 来：； 先最蓿爨右借可用出-种Afe C匕 s t C-T- 交XXJXJXJOXXX JOCHJC XX JCXXX JOXXJXJXJOXXJXXJXJXJJJXXXJOXJOXJCXXXKJXJJXXJX请选择算法:选择第二种算法：最短寻道时间优先调度算法请选择算法：2XX XX XXX XXX XXX XX XXX XXX钮寻道时间优调庶算建 X

16、XX)CX)CXX)CXX)CXX)CX)CXX)C24 5328 639 8826 90 0 2 2 1 182 3 06 0 105 -1 6 2 织务： 列号列为 房道 道留长争 求前道均平XXXXXJCXJCXXJCXXfl曲调恒7具_；去XXXXJCXXJCXXXHJCJCHJCJCXJCJCXJCJCJCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCJCJCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJC X XX XXJJJXJJXXj青 j 先才羊要使 用的 畀KJXJJXXJXXXKXXKXNNXX

17、NHJC JC HJCHJC JC HJCXXJXXJJOXJ*n来短描环用出先寻客五B& 调虞算法 算法,进行比较XXJXXJJOXJOXXJXXJXJXJOXJOXXJXXXJOXJOXXJXXJJOXJOXXJXXJXJXJOXJOXXJXXX请选择算法:选择第三种算法：扫描调度算法 I：慢作紊统新建文件夹Deb ug45.exe请选择算法：3JXJXJOXJOXXJXXXJOXJOXXJXXJJO X 才m 寸苗 i 周.庶畀汁 JXJOXXJXXXJOXJOXXJXXJXJXJOXXJXX.:!方,47 和盖为. 列身列为 房道臂-05 道胃的长 磁*回道访寻 求鼎道均 也普恩平6

18、0.1 2. 口78120 46 893834 178表示比当前磁道号大的方向138 120 92 89 62 525292 138,。表示比当前磁道小的方向46 38 34NtOCXtOCXNNXNNK2甜i周，帝女XNNXXNtOCXtOCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCJCJCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCMJCJCXJCJCJCJCHJCJCHJC NX XXX XXKJXJJ X青 j 先 j羊要,使用的 女XKJXXJXXJXJJXXJXXXJOXJC HJC JC H J

19、XXJXXXJO成 CF算AN较 c行 算先CA法进 ts算， 调间法r法 务时算调算 服道蓦种 先寻客五 来短描环用出 r 、 f f f 、 1 2 3 4 5 6XXJXXJXJKX xtocHJC JC HJCXXJXXJXJJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCJCJCJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCXJCJCXJCHJCJCHJCJCMJCJCXJCJCJCJCHJCJCHJC请选择算法:XXNNXNNXXNXXXNNXNNXXNXXNXNXNX者一为： 列口葛列为 序道臂道雷的长 磁*回道访寻 求辱道均 喜寰平:6

20、2 ：150方向虫CF算AN较 Is海比 法调Nc行 算先CA法进XJXXJXJXJOXXJXXJWJXXXJXJXJOXJXXJXJXJOXJOXX请选择算法:选择第四种算法：循环扫描调度算法 I：倨作奈统新建文件夹LDeBug45. exe1请选择算法：4JXJXJOXJOXXJXXXJOXJOXXJ法CF算F度法调算先CA法进算， 调间法M-法 务时算调算 服道蓦种 先寻殍五 来短描环用出 nAN较CLs LuDC亍N m麟 X JC H X JC H JCHJC JC HJCKX xtocXXXXXJCXJCXJJXXJXXJXJJXXJXXXJOXJOXJXXJXXXJOXJOXXJ

21、XXJJOXJOXXJXXJXJXJOXJOXXJXXXJOXJOXXJXXJWJXJOXXJXXJXJ请选择算法:四种算法比较: I：慢作奈统新建文件表DebugVl5.exe 回XXXXXXX XXX服-务-j周唐7 畀注 JCKXJJJXJJXXJXXJXJXJJXXJXXJ2 2 0 6 0 6 45 - 1 7 - _b 的藤 列号列为 序道 道蓄长 求前道均 也一平JXXJXXXJJX KJXXJXXJXJX X主 R 寻_ j 首 日寸间忧 7 i 周 遗身_ 女 KJXXJXXJXJXJJXXJXXJX9 8826 940 0 2 2 1 182 3 0 6 0 105 - 1

22、 6 的先 列号列为 序道 道蓄长 求前道均 也一平8 64124 53263JCXXJCXXXJOCXJOCXXJCXXJCXJCXJOCXXJCXX X 才m 寸苗 i周.度算 甘生 XJJOXJOXXJXXJXJXJOXXJXXJXXXJOXJEI利蓊为. 列口扈列为 房道臂道胃的长 磁*回道访寻 求景道均 也胃是平:62 ：150 方向1 :178 47.20120 46 89 38 34 178表示比当前磁道号大的方向138 120 92 89 62 5252 92 138，。表示比当前磁道小的方向46 38 34JXXJXXXJOXJOXXJXXJXJXJO X1盾壬不 Im 才苗

23、调.育畀；女箸 XJJOXJO 箸 XX 箸 XJXJXJO 箸 XX XXXXXXK0 42 3182 7 06 0 165 -1 7 列号列为 序道道蓄长 求前道均 也一平46382 09 2125 25心得体会本系统软件中的重用代码，设计成一个函数，实现了代码重用。本系统是在 dos状态下进行编译执行的，没有图形化界面。通过此次课程设计，我对操作系统的基础知识了解得更透彻了，同时对磁盘 调度的四种算法一一先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、 扫描算法（SCAN）、循环扫描算法（CSCAN）有了更深刻的理解和掌握，使我能够 为磁盘调度选择适当的算法，提高CPU工作

24、效率。设计过程中遇到的困难在老师 和同学的帮助下顺利解决并通过了验收，我深刻认识到算法的逻辑性对程序的重 要影响，算法的准确度对程序运行结果的重要影响，这对我以后在操作系统的学 习中有极大帮助。参考文献严蔚敏，吴伟民，数据结构(C语言版)，北京，清华大学出版社杨树林，胡洁萍，C#程序设计与案例教程，北京，清华大学出版社谭浩强，C+程序设计，清华大学出版社，2004谢青松.操作系统原理.人民邮电出版社.2004袁宝华.操作系统实验教程.北京交通大学出版社罗宇，邹鹏，邓胜兰.操作系统】M.北京：电子工业高等教育出版社，2012附源代码#include stdio.h#include time.h#

25、include stdlib.h#define N 10void Sort(int Array,int n)冒泡排序算法,从小到大排序int i,j,temp;for(i=1;in;i+)for(j=0;jArrayj+1)temp=Arrayj;Arrayj=Arrayj+1;Arrayj+1=temp;void Output(int Track,int Num)int i;printf(请求的磁道序列为：);for(i=0;iN;i+)printf( %d ”,Tracki); printf(n);printf（当前所在磁道号是:dn”,Num）;/* 先来先服务调度算法 */ void

26、FCFS(int Track,int Num) int i,temp;int Sum=0;来先服务调度算法float AverTime=0.0;printf(* 先“ 3 tl*nn);Output(Track,Num);for(i=0;iN;i+)if(NumTracki)temp=Tracki-Num;else temp=Num-Tracki;Num=Tracki;Sum+=temp;AverTime=(float)Sum/N;printf(-磁道访问的序列为：)；for(i=0;iN;i+)printf( %d ”,Tracki);printf(n 平均寻道长度为：%.2fnn,Aver

27、Time);/* 最短寻道时间优先调度算法 */ void SSTF(int Track,int Num) int i,j,TtrackN,DiskN;int min,minj,Dcount=0;int Sum=0;float AverTime=0.0;printf(*最短寻道时间优先调度算法“ 3 tl*nn);Output(Track,Num);for(i=0;iN;i+)Ttracki=0;for(j=0;jN;j+)for(i=0;iN;i+)if(Ttracki=-1)continue;elseif(NumTracki)Ttracki=Tracki-Num;else Ttracki=

28、Num-Tracki;min=200;minj=0;for(i=0;iN;i+)if(Ttracki=-1) continue;elseif(Ttrackimin) min=Ttracki; minj=i;Num=Trackminj;DiskDcount+=Num;Sum=Sum+Ttrackminj;Ttrackminj=-1;AverTime=(float)Sum/N;printf(-磁道访问的序列为：)；for(i=0;iN;i+)printf( %d ,Diski);printf(n 平均寻道长度为：%.2fnn,AverTime); /* 扫描调度算法 */ void SCAN(in

29、t Track,int Num) int i,j,k=0,r=0,l=0,choose;int tempN;int Sum=0;度算法float AverTime=0.0;printf(* 扫 描“ 3 tl*nn);Output(Track,Num);for(i=0;iN;i+)tempi=Tracki;Sort(temp,N); /将访问序列从小到大排序 while(tempk=0;j-)printf( %d ,tempj);for(j=r;jN;j+)printf( %d ,tempj);Sum=Num-2*temp0+tempN-1;elseprintf(-磁道访问的序列为：);for

30、(j=r;j=0;j-)printf( %d ,tempj);Sum=Num-temp0+2*tempN-1;AverTime=(float)Sum/N;printf(n 平均寻道长度为：%.2fnn,AverTime);/* 循环扫描调度算法 */ void C_SCAN(int Track,int Num) int i,j,k=0,r=0,l=0;int tempN;int Sum=0;扫描调度算法float AverTime=0.0;printf(* 循 环“ 3 tl*nn);Output(Track,Num);for(i=0;iN;i+)tempi=Tracki;Sort(temp,N);printf(-磁道访问的序列为：);while(tempkNum)(k+;l=k-1;r=k;for(j=r;jN;j+)printf( %d ,tem