操作系统磁盘调度算法课程设计报告.doc

成绩 课程设计报告 题 目 磁盘调度算法 课 程 名 称 操作系统课程设计 院 部 名 称 信息技术学院 专 业 计算机科学与技术 班 级 09计算机科学与技术(1) 学 生 姓 名 周浩 学 号 0905101005 课程设计地点 A105 课程设计学时 20 指 导 教 师 何健 【注：根据课程设计大纲第四项具体要求撰写课程设计报告】一、 程序设计的目的和要求磁盘是经常使用的一个外设，对磁盘数据的寻道时间的长短直接影响机器的整体运行速度，本设计要求用C语言(或高级语言)编写程序模拟实现磁盘调度的常用算法。以加深对磁盘调度常用算法的理解和实现技巧。二、 课程设计环境要求 1、硬件环境Intel Croe 2 Duo CPU2、软件环境Windows7 Turbo C 2.0三、 设计任务介绍及系统需求分析1、系统分析设备的动态分配算法与进程调度相似，也是基于一定的分配策略的。常用的分配策略有先请求先分配、优先级高者先分配等策略。在多道程序系统中，低效率通常是由于磁盘类旋转设备使用不当造成的。操作系统中，对磁盘的访问要求来自多方面，常常需要排队。这时，对众多的访问要求按一定的次序响应，会直接影响磁盘的工作效率，进而影响系统的性能。访问磁盘的时间因子由3部分构成，它们是查找（查找磁道）时间、等待（旋转等待扇区）时间和数据传输时间，其中查找时间是决定因素。因此，磁盘调度算法先考虑优化查找策略，需要时再优化旋转等待策略。2、系统设计：(1) 先来先服务(First-Come，First-Served，FCFS):这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。(2) 最短寻道时间优先(ShortestSeekTimeFirst，SSTF): 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。(3) 扫描(SCAN)算法:SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。四、概要设计本系统划分为三个模块：先来先服务算法模块void FCFS(int array,int m)、最短寻道时间优先算法模块void SSTF(int array,int m)、扫描算法模块void SCAN(int array,int m)。系统模块图磁盘调度模拟系统 先来先服务算法最短寻道时间优先扫描算法五、详细设计1、先来先服务(FCFS)这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。先来先服务算法（FCFS）流程图：2、最短寻道时间优先(SSTF)该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。最短寻道时间优先流程图：3、扫描算法(SCAN) SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。六、测试数据和结果1、先来先服务调度(FCFS)输入起始磁道（你可以输入50），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入100），然后点确定。选择磁盘调度算法1 2 3 中的任意一个，若选择1后确认，则随机输出10个小于100的磁道数(41 67 34 0 69 24 78 58 62 64)，则先来先服务调度(FCFS)输出：(41 67 34 0 69 24 78 58 62 64)，在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度运行结果图：2、最短寻道时间优先调度(SSTF) 输入起始磁道（你可以输入50），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入100），然后点确定。选择磁盘调度算法1 2 3 中的任意一个，若选择2后确认，则随机输出10个小于100的磁道数(41 67 34 0 69 24 78 58 62 64) ,则最短寻道时间优先调度(SSTF)：(58 62 64 67 69 78 41 34 24 0) 。在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度运行结果图：3、扫描调度算法(SCAN) 输入起始磁道（你可以输入50），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入100），然后点确定。选择磁盘调度算法1 2 3 中的任意一个，若选择3后确认，则随机输出10个小于100的磁道数：(41 67 34 0 69 24 78 58 62 64)，则扫描调度算法(SCAN)：(58 62 64 67 69 78 41 34 24 0) 。七、结论与体会至此，计算机操作系统课程设计算法已经完成。此次设计基本完成了所规定的功能，但由于这次设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。由于平时上课不是很认真许多概念没有理解清楚，导致在做设计时有点无从下手的感觉，只好边实验边看书直到弄懂概念后才开始做，最终在同学和老师的指导下我完成了设计。此设计基本能够实现规定的要求但是还是不够完善，很多东西做的不够好，程序不够完善和严谨。此次课程设计中我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。八、参考文献（1） 胡志刚，谭长庚等. 计算机操作系统.中南大学出版社. 2005（2） 汤子瀛、哲凤屏、汤小丹. 计算机操作系统.西安电子科技大学出版社, 2001,8.（3） 陈向群 杨芙清.操作系统教程. 北京大学出版社,2004,7.（4） 张尧学 史美林.计算机操作系统教程. 清华大学出版社, 2000.（5） 庞丽萍.操作系统原理(第三版). 华中理工大学出版社,2000.（6） 罗宇，邹鹏等.操作系统(第2版). 电子工业出版社. 2007.4附件：源程序清单#include stdio.h#include stdlib.hvoid CopyL(int Sour,int Dist ,int x); /数组Sour复制到数组Dist，复制到x个数void SetDI(int DiscL); /随机生成磁道数 void Print(int Pri,int x); /打印输出数组Privoid DelInq(int Sour,int x,int y); /数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即会出现2个y) void FCFS(int Han,int DiscL); /先来先服务算法(FCFS)void SSTF(int Han,int DiscL); /最短寻道时间优先算法(SSTF)int SCAN(int Han,int DiscL,int x,int y); /扫描算法(SCAN)void CSCAN(int Han,int DiscL); /循环扫描算法(CSCAN)void PaiXu(); /寻道长度由低到高排序void Pri();int NAll=0;int Best52; /用作寻道长度由低到高排序时存放的数组 int Limit=0; /输入寻找的范围磁道数iint Jage;float Aver=0;int main() int i; int DiscLine10; /声明准备要生成的随机磁道号的数组 int Hand; /磁道数 int Con=1; int n; while(Con=1) Jage=0; printf(n 请输入初始的磁道数:); scanf(%d,&Hand); printf(n+ 输入寻找的范围:); scanf(%d,&Limit); if(Limit65536) printf(超出磁道范围!); else printf(1.先来先服务算法(FCFS )n); printf(2.最短寻道时间优先算法(SSTF)n); printf(3.扫描算法(SCAN) n); scanf(%d,&n); if(n=0) exit(0); printf(n); switch(n) case 1: SetDI(DiscLine); /随机生成磁道数 FCFS(Hand,DiscLine); /先来先服务算法(FCFS) break; case 2: SetDI(DiscLine); /随机生成磁道数 SSTF(Hand,DiscLine); /最短寻道时间优先算法(SSTF) break; case 3: SetDI(DiscLine); /随机生成磁道数 SCAN(Hand,DiscLine,0,9); /扫描算法(SCAN) break; SetDI(DiscLine); /随机生成磁道数 FCFS(Hand,DiscLine); /先来先服务算法(FCFS) SSTF(Hand,DiscLine); /最短寻道时间优先算法(SSTF) SCAN(Hand,DiscLine,0,9); /扫描算法(SCAN) printf(nn+ 是否继续(按0结束,按1继续)?); scanf(%5d,&Con); /数组Sour复制到数组Dist，复制到x个数void CopyL(int Sour,int Dist ,int x) int i; for(i=0;i=x;i+) Disti=Souri; /打印输出数组Privoid Print(int Pri,int x) int i; for(i=0;i=x;i+) printf(%5d,Prii); /随机生成磁道数void SetDI(int DiscL) int i; for(i=0;i=9;i+) DiscLi=rand()%Limit;/随机生成10个磁道号 printf(+ 需要寻找的磁道号:); Print(DiscL,9); /输出随机生成的磁道号 printf(n);/数组Sour把x位置的数删除，并把y前面的数向前移动，y后的数保持不变(即会出现2个y) void DelInq(int Sour,int x,int y) int i; for(i=x;iy;i+) Souri=Souri+1; x+; /先来先服务算法(FCFS)void FCFS(int Han,int DiscL) int RLine10; /将随机生成的磁道数数组Discl复制给数组RLine int i,k,All,Temp; /Temp是计算移动的磁道距离的临时变量 All=0; /统计全部的磁道数变量 k=9; /限定10个的磁道数 CopyL(DiscL,RLine,9); /复制磁道号到临时数组RLine printf(n+ FCFS访问顺序为:); All=Han-RLine0; for(i=0;i=9;i+) Temp=RLine0-RLine1;/求出移动磁道数,前一个磁道数减去后一个磁道数得出临时的移动距离 if(Temp0) Temp=(-Temp);/移动磁道数为负数时,算出相反数作为移动磁道数 printf(%5d,RLine0); All=Temp+All;/求全部磁道数的总和 DelInq(RLine,0,k);/每个磁道数向前移动一位 k-; BestJage1=All;/Best1存放移动磁道数 BestJage0=1; /Best0存放算法的序号为:1 Jage+;/排序的序号加1 Aver=(float) All)/10;/求平均寻道次数 printf(n+ 移动磁道数: ,All); printf(n+ 平均寻道长度:*%0.2f* ,Aver);/最短寻道时间优先算法(SSTF)void SSTF(int Han,int DiscL) int i,j,k,h,All; int Temp; /Temp是计算移动的磁道距离的临时变量 int RLine10; /将随机生成的磁道数数组Discl复制给数组RLine int Min; All=0; /统计全部的磁道数变量 k=9; /限定10个的磁道数 CopyL(DiscL,RLine,9); /复制磁道号到临时数组RLine printf(n+ SSTF访问顺序为:); for(i=0;i=9;i+) Min=64000; for(j=0;jHan) /如果第一个随机生成的磁道号大于当前的磁道号，执行下一句 Temp=RLinej-Han; /求出临时的移动距离 else Temp=Han-RLinej; /求出临时的移动距离 if(TempMin) /如果每求出一次的移动距离小于Min，执行下一句 Min=Temp; /Temp临时值赋予Min h=j; /把最近当前磁道号的数组下标赋予h All=All+Min; /统计一共移动的距离 printf(%5d,RLineh); Han=RLineh; DelInq(RLine,h,k); /每个磁道数向前移动一位 k-; BestJage1=All;/Best1存放移动磁道数 BestJage0=2;/Best0存放算法的序号为:2 Jage+;/排序序号加1 Aver=(float)All)/10;/求平均寻道次数 printf(n+ 移动磁道数: ,All); printf(n+ 平均寻道长度:*%0.2f* ,Aver);/扫描算法(SCAN)int SCAN(int Han,int DiscL,int x,int y) int j,n,k,h,m,All; int t=0; int Temp; int Min; int RLine10; /将随机生成的磁道数数组Discl复制给数组RLine int Order; Order=1; k=y; m=2; /控制while语句的执行，即是一定要使当前磁道向内向外都要扫描到 All=0; /统计全部的磁道数变量 CopyL(DiscL,RLine,9); /复制磁道号到临时数组RLine printf(n+ SCAN访问顺序为:); Min=64000; for(j=x;jHan) /如果第一个随机生成的磁道号大于当前的磁道号，执行下一句 Temp=RLinej-Han; /求出临时的移动距离 else Temp=Han-RLinej; /求出临时的移动距离 if(Temp=Han) /判动方向，即是由里向外还是由外向里断磁道的移 Order=0; t=1; Han=RLineh; DelInq(RLine,h,k); /每个磁