课程设计：磁盘调度算法的实现与分析.doc

湖南工业大学课 程 设 计资 料 袋 计算机与通信学院 学院（系、部）20 08 20 09 学年第 一 学期 课程名称 操作系统 指导教师 职称 讲师 学生姓名 专业班级 学号 06408100139 题 目 磁盘调度算法的实现与分析 成 绩 起止日期 2008 年 12 月 24 日 2009 年 01 月 06日目 录 清 单序号材 料 名 称资料数量备 注1课程设计任务书12课程设计说明书13课程设计图纸19张456 湖南工业大学课程设计任务书2008 2009 学年第 1 学期 计算机与通信学院 学院（系、部） 专业 班级课程名称： 操作系统 设计题目： 磁盘调度算法的实现与分析 完成期限：自 2008 年 12 月 24 日至 2009 年 01 月 06 日共 2 周内容及任务一、设计的主要技术参数二、设计任务1.先来先服务算法(FCFS)2.最短寻道时间优先算法(SSTF)3.扫描算法(SCAN) 4.循环扫描算法(CSCAN)三、设计工作量通过两周的时间进行设计、编码、测试、运行、书写实验报告。进度安排起止日期工作内容2008-12-24至2008-12-27数据结构设计2008-12-28至2008-12-30编写代码2008-12-31至2009-01-01调试运行、修改2009-01-02至2009-01-06得出最终程序、撰写实验报告主要参考资料1 袁庆龙，候文义Ni-P合金镀层组织形貌及显微硬度研究太原理工大学学报，2001，32(1)：51-53.2刘国钧，王连成图书馆史研究北京：高等教育出版社，1979：15-18，313 孙品一高校学报编辑工作现代化特征中国高等学校自然科学学报研究会科技编辑学论文集(2)北京：北京师范大学出版社，1998：10-22指导教师（签字）： 年 月 日系（教研室）主任（签字）： 年 月 日 （操作系统）设计说明书（题目） 磁盘调度算法的实现与分析起止日期： 2008 年 12 月 24 日 至 2009 年 01 月 06 日学生姓名班级 学号成绩指导教师(签字)计算机与通信学院 2009年 01 月 06 日 目 录1. 程设计简介52. 课程设计目的53. 数据结构的设计53.1 数组54.课程设计内容54.1系统分析54.2.1先来先服务（FCFS ）的策略64.2.2最短时间优先算法选择这样的进程。64.2.3扫描（SCAN）调度算法64.2.4循环扫描（CSCAN）算法65.程序设计流程图或N-S图65.1系统流程图：65.2先来先服务(FCFS)75.3最短寻道时间优先(SSTF):85.4扫描算法(SCAN)95.5循环扫描(CSCAN)算法106.功能模块（或算法）描述116.1先来先服务调度(FCFS) 126.2最短寻道时间优先调度(SSTF) 126.3扫描调度算法(SCAN) 136.4循环扫描算法(CSCAN)147.心得体会及结束语 15参考文献815附源代码9161. 程设计简介 磁盘调度程序模拟加深对操作系统原理的进一步认识，加强实践动手能力和程序开发能力的培养，提高分析问题解决问题的能力，培养合作精神，以巩固和加深磁盘调度的概念。操作系统是一门工程性很强的课程，它不仅要求学生掌握操作系统的工作原理和理论知识，也要求学生的实际动手能力，以加深对所学习内容的理解，使学生熟练地掌握计算机的操作方法，使用各种软件工具，加强对课程内容的理解。这次课程设计，就是通过模拟磁臂调度来加深对操作系统中磁臂调度概念的理解2.课程设计目的使学生熟悉磁盘管理系统的设计方法；加深对所学各种磁盘调度算法的了解及其算法的特点。3. 数据结构的设计3.1 数组Hand:当前磁道号;DiscLine10:随机生成的磁道号; void SetDI(int DiscL)生成随机磁道号算法; void CopyL(int Sour,int Dist ,int x) 数组Sour复制到数组Dist，复制到x个数（四）详细设计; void DelInq(int Sour,int x,int y) 数组Sour把x位置的数删除,x后的数组元素向前挪一位.void PaiXu()寻道长度由低到高排序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)4.课程设计内容4.1系统分析选择一个自己熟悉的计算机系统和程序设计语言模拟操作系统基本功能的设计方法及其实现过程 完成各分项功能。在算法的实现过程中，要求可决定变量应是动态可变的；同时模块应该有一个合理的输出结果。具体可参照实验的程序模拟 .各功能程序要求自行编写程序实现，不得调用现有操作系统提供的模块或功能函数。磁盘调度程序模拟。先来先服务调度算法. 最短寻道时间优先调度，循环（SCAN）调度算法。程序设计语言自选，最终以软件（含源代码以及执行程序）和设计报告的形式提交课程设计结果.。磁盘调度让有限的资源发挥更大的作用4.2磁盘调度 在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列。4.2.1先来先服务（FCFS ：afirst-come-first-served）的策略，即先来的请求先被响应。FCFS策略看起来似乎是相当公平的，但是当请求的频率过高的时候FCFS策略的响应时间就会大大延长。FCFS策略为我们建立起一个随机访问机制的模型，但是假如用这个策略反复响应从里到外的请求，那么将会消耗大量的时间。为了尽量降低寻道时间，看来我们需要对等待着的请求进行适当的排序，而不是简单的使用FCFS策略。这个过程就叫做磁盘调度管理。有时候fcfs也被看作是最简单的磁盘调度算法。 4.2.2最短时间优先算法选择这样的进程。要求访问的磁道，与当前磁头所在的磁道距离最近，以使每次的寻道时间最短。 4.2.3扫描（SCAN）调度算法:该算法不仅考虑到欲访问 的磁道与当前磁道间的距离，更优先考虑的是磁头当前的移动方向。例如，当磁头正在自里向外移动时，SCAN算法所考虑的下一个访问对象，应是其欲访问的磁道，既在当前磁道之外，又是距离最近的。这样自里向外的访问，直至再无更外的磁道需要访问时，才将磁道换向自外向里移动。这时，同样也是每次选择这样的进程来调度，也就是要访问的当前位置内距离最近者，这样，磁头又逐步地从外向里移动，直至再无更里面的磁道要访问，从而避免了出现“饥饿”现像。4.2.4循环扫描（CSCAN）算法：当磁头刚从里向外移动而越过了某一磁道时，恰好又有一进程请求访问此磁道，这时，该里程就必须等待，为了减少这种延迟，CSCAN算法规定磁头单向移动，而本实验过程中我们所设计的是磁头从里向外移动，而从外向里移动时只须改方向而已，本实验未实现。但本实验已完全能演示循环扫描的全过程。5.程序设计流程图或N-S图5.1系统流程图： 5.2先来先服务(FCFS):这是一种简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。但此算法由于未对寻道进行优化，致使平均寻道时间可能较长。先来先服务算法（FCFS）流程图：5.3最短寻道时间优先(SSTF):该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，但这种调度算法却不能保证平均寻道时间最短。最短寻道时间优先流程图：5.4扫描算法(SCAN):SCAN算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，SCAN算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。扫描算法（scan）流程图5.5循环扫描(CSCAN)算法:处理该进程的请求，致使该进程的请求被严重地推迟。为了减少这种延迟，CSCAN算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。循环扫描算法（cscan）流程图：6.功能模块（或算法）描述6.1先来先服务调度(FCFS)输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择1后确认，则随机输出10个小于50的磁道数(41 17 34 0 19 24 28 8 12 14)，则先来先服务调度(FCFS)输出：(41 17 34 0 19 24 28 8 12 14)，在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度运行结果图：6.2最短寻道时间优先调度(SSTF) 输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择2后确认，则随机输出10个小于50的磁道数(5 45 31 27 11 41 45 42 27 36) ,则最短寻道时间优先调度(SSTF)：(45 45 42 41 36 31 27 27 11) 。在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度运行结果图：6.3扫描调度算法(SCAN) 输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择3后确认，则随机输出10个小于50的磁道数：(41 4 2 3 42 32 21 16 18 45)，则扫描调度算法(SCAN)：(45 42 41 32 21 18 16 4 3 2) 。在选择1或者0，选着1则继续其它算法的磁盘调度，选着0则结束磁盘调度。运行结果图：6.4循环扫描算法(CSCAN)输入起始磁道（你可以输入100），点确定，进入第二个界面，再输入你要输入的最大磁道（你可以输入50），然后点确定。选择磁盘调度算法1 2 3 4中的任意一个，若选择4后确认，则随机输出10个小于50的磁道数：（47 26 21 38 19 12 17 49 35 44），则循环扫描算法(CSCAN)：（12 17 19 21 26 35 38 44 47 49）。运行结果图：7.心得体会及结束语 至此，计算机操作系统课程设计算法已经完成。此次设计基本完成了所规定的功能，但由于这次设计的时间比较仓促，其中不免会有些纰漏，比如在程序的实现上还不够严谨，出错处理不够完善等多方面问题，这些都有进一步改善。由于平时上课不是很认真许多概念没有理解清楚，导致在做设计时有点无从下手的感觉，只好边实验边看书直到弄懂概念后才开始做设计导致时间有点紧张，最终在同学和老师的指导下我完成了设计，此设计基本能够实现规定的要求但是还是不够完善，很多东西做的不够好，程序不够完善和严谨。此次课程设计中我学到了很多东西，无论在理论上还是实践中，都得到不少的提高，这对于我以后的工作和学习都有一种巨大的帮助。参考文献8（1） 胡志刚，谭长庚等. 计算机操作系统.中南大学出版社. 2005（2） 罗宇，邹鹏等.操作系统(第2版). 电子工业出版社. 2007.4（3） 汤子瀛、哲凤屏、汤小丹. 计算机操作系统.西安电子科技大学出版社, 2001,8.（4） 陈向群 杨芙清.操作系统教程. 北京大学出版社,2004,7.（5） 张尧学 史美林.计算机操作系统教程. 清华大学出版社, 2000.（6） 庞丽萍.操作系统原理(第三版). 华中理工大学出版社,2000.（7） Tanenbaum译著. 现代操作系统（第2版）. 机械工业出版社2005,6.（8） 徐虹.操作系统实验指导_基于LINUX内核, 清华大学出版社, 2004.（9） 马季兰等.Linux操作系统, 电子工业出版社, 2002.（10） 任爱华,李鹏,刘方毅.操作系统实验指导, 清华大学出版社,2004.附源代码9#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 N_Step_SCAN(int Han1,int DiscL); /N步扫描算法(NStepScan)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 请输入初始的磁道数(0n65536) printf(超出范围!); elseprintf( *n);printf( * 磁盘调度算法 *n); printf( *n); printf(* 1.先来先服务算法(FCFS) *n); printf( * 2.最短寻道时间优先算法(SSTF) *n); printf( * 3.扫描算法(SCAN) *n); printf( * 4.循环扫描算法(CSCAN) *n); printf( *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; case 4: SetDI(DiscLine); /随机生成磁道数 CSCAN(Hand,DiscLine); /循环扫描算法(CSCAN) break; case 5: SetDI(DiscLine); /随机生成磁道数 SetDI(DiscLine); /随机生成磁道数 FCFS(Hand,DiscLine); /先来先服务算法(FCFS) SSTF(Hand,DiscLine); /最短寻道时间优先算法(SSTF) SCAN(Hand,DiscLine,0,9); /扫描算法(SCAN) CSCAN(Hand,DiscLine); /循环扫描算法(CSCAN) PaiXu(); /寻道长度由低到高排序 printf(nn+ 寻道长度由低到高排序:); for(i=0;i5;i+) printf(%4d ,Besti0); break; 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); /每个磁道数向前移动一位 k-; while(m0) if(Order=1) /order是判断磁盘扫描的方向标签，order是1的话，磁道向内移动 for(j=x;j=y;j+) h=-1; Min=64000; for(n=x;n=k;n+) /判断离当前磁道最近的磁道号 if(RLinen=Han) Temp=Han-RLinen; if(TempMin) Min=Temp; /Temp临时值赋予Min h=n; /把最近当前磁道号的数组下标赋予h if(h!=-1) All=All+Min; /叠加移动距离 printf(%5d,RLineh); Han=RLineh; /最近的磁道号作为当前磁道 DelInq(RLine,h,k); k-; Order=0; /当完成向内的移动，order赋予0，执行else语句，使磁道向外移动 m-; /向内完成一次，m减一次，保证while循环执行两次 else /order是0的话，磁道向外移动 for(j=x;j=y;j+) h=-1; Min=64000; for(n=x;n=Han) Temp=RLinen-Han; if(Temp5) BestJage1=