操作系统课程设计进程调度模拟设计.doc

课程设计任务书 题 目: 进程调度模拟设计先来先服务、非强占式短进程优先算法 初始条件：1预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2设计报告内容应说明： 课程设计目的与功能； 需求分析，数据结构或模块说明(功能与框图)； 源程序的主要部分； 测试用例，运行结果与运行情况分析； 自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名： 年 月 日系主任（或责任教师）签名： 年 月 日目录课程设计目的与功能3实验目的3开发平台3需求分析，数据结构或模块说明3 问题描述.3 实验要求.3 功能描述.4程序框图.5源程序的主要部分6 结构体的创建.6 主函数.6 SJF调度算法的函数7 FCFS调度算法的函数.9测试用例，运行结果与运行情况分析10自我评价与总结11实验优点11实验不足11收货与体会12实验改进方面12参考文献12进程调度模拟设计先来先服务、非强占式短进程优先算法一、课程设计目的与功能1实验目的模拟进程调度，能够处理以下的情形： 能够选择不同的调度算法（要求中给出的调度算法）； 能够输入进程的基本信息，如进程名、到达时间和运行时间等； 根据选择的调度算法显示进程调度队列； 根据选择的调度算法计算平均周转时间和平均带权周转时间。2开发平台Visual C+ 6.0、Windows XP二、需求分析，数据结构或模块说明1.问题描述：设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个进程分别在T1, ,Tn时刻到达系统，它们需要的服务时间分别为S1, ,Sn。分别采用先来先服务FCFS和短作业优先SJF进程调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。2.实验要求：1）进程个数n；每个进程的到达时间T1, ,Tn和服务时间S1, ,Sn；选择算法1-FCFS，2-SJF。2）要求采用先来先服务FCFS和短作业优先SJF分别调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间；3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等；4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间，所有进程的平均周转时间，带权平均周转时间。3.功能描述1）先来先服务(FCFS)调度算法 将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。在没有特殊理由要优先调度某类作业或进程时，从处理的角度来看，FCFS方式是一种最合适的方法，因为无论是追加还是取出一个队列元素在操作上都是最简单的。先来先服务(FCFS)调度算法直观看，该算法在一般意义下是公平的。即每个作业或进程都按照它们在队列中等待时间长短来决定它们是否有限享受服务。先来先服务(FCFS)调度算法不过对于那些执行时间较短的作业或进程来说，如果它们在某些执行时间很长的作业或进程之后到达，则它们将等待很长时间。 在实际操作系统中，尽管很少单独使用FCFS算法，但和其他一些算法配合起来，FCFS算法还是使用的相当多的。例如基于优先级的调度算法就是对具有同样优先级的作业或进程采用的FCFS方式。2）最短作业优先法（SJF） 在批处理为主的系统中，如果采用FCFS的方式进程作业调度，虽然系统开销小，算法简单，但是，如果估计执行时间很多的作业实在那些长作业的后面到达系统的话，则必须等待长作业执行完成之后才有机会获得执行。这就造成不必要的等待和某种不公平。最短作业优先发（SJF）就是选择那些估计需要执行时间最短的作业投入执行，为他们创建进程和分配资源。最短作业优先法优势：直观上说，采用最短作业有限的调度方法，可使得系统在同一时间内处理的作业个数最多，从而吞吐量也就大于其他的调度方式。但是，对于一个不断有作业进入的批处理系统来说。最短作业优先法缺点：最短作业优先法有可能使得那些长作业永远得不到调度执行的机会。4.程序框图预定义FCFS调度方法SJF调度方法主函数输出注释：预定义：包括程序结构体等，程序结构体设计到后面函数所用的作业号、提交时间、运行时间、开始时间、结束时间、周转时间、带权周转时间、执行顺序等内容FCFS调度方法：程序重要的组成函数，将输入的N个程序结构体用链表的方式重新排序，按照函数给定的计算方法，列出作业从新计算过的作业号、提交时间、运行时间、开始时间、结束时间、周转时间、带权周转时间、执行顺序等内容SJF调度方法：采用最短优先法，将输入的N个程序结构体用链表的方式重新排序，列出作业从新计算过的作业号、提交时间、运行时间、开始时间、结束时间、周转时间、带权周转时间、执行顺序等内容主函数：先进行输入操作，将输入的pro结构体存储起来，再调用两个算法函数，将FCFS调度方法所列出的作业结构体和SJF调度方法所列出的结构体整合表示出来，最后方便输出。三、源程序的主要部分1、结构体的创建struct prodouble handtime;double asktime;double starttime;double endtime;double usetime;double right;int runorder;int num;pro *next;2、主函数 int main()pro p20;cout<<"请输入进程的个数:"cin>>pronum;cout<<"按时间先后顺序输入进程的提交时间和运行时间"<<endl;for(int i=0;i<pronum;i+)pi.num=i+1; cout<<"第"<<i+1<<"个进程:" cin>>pi.handtime>>pi.asktime;while(pi.handtime<pi-1.handtime)cout<<"请从新输入第"<<i+1<<"个进程:" cin>>pi.handtime>>pi.asktime; FCFS(p,pronum); SJF(p,pronum); return 0; /cout<<p1->handtime <<p1->asktime<<endl;3、SJF调度算法的函数void SJF(pro p,int n)int i,order=1;pro *now=&p0;pro *temp,*nextrun;p0.starttime=p0.handtime;p0.endtime=p0.handtime+p0.asktime;p0.usetime=p0.asktime;p0.right=1.0;p0.runorder=order;+order;for(i=0;i<n-1;i+)pi.next=&pi+1;/cout<<now->next->num<<endl;pn-1.next=NULL;/*while(now!=NULL)cout<<now->num<<"t"<<now->handtime<<endl;now=now->next;*/while(now->next!=NULL)nextrun=now->next;/cout<<nextrun->handtime<<"t"<<nextrun->asktime<<"asdfafdsa"<<endl;/while(nextrun!=NULL) /确定nextrun /if(nextrun->handtime>=now->endtime)nextrun->starttime=nextrun->handtime; elseif(nextrun->next!=NULL)temp=nextrun->next; while(temp->handtime<=now->endtime) /用来确定nextrun是否改变 if(temp->asktime<nextrun->asktime)nextrun=temp; if(temp->next!=NULL)temp=temp->next;else break; nextrun->starttime=now->endtime; /确定nextrun完毕 if(nextrun!=now->next)temp=now; /修改链表while(temp->next!=nextrun)temp=temp->next;temp->next=nextrun->next;temp=now->next; now->next=nextrun;nextrun->next=temp; /链表修改完毕 nextrun->endtime=nextrun->starttime+nextrun->asktime;nextrun->usetime=nextrun->endtime-nextrun->handtime;nextrun->right=nextrun->usetime/nextrun->asktime;nextrun->runorder=order;+order; /进程信息修改完毕 now=nextrun;double sumtime=0,sumright=0;cout<<"SJF"<<endl;cout<<"作业号t提交t运行t开始t结束t周转t带权t执行"<<endl;for(i=0;i<n;i+)sumtime+=pi.usetime;sumright+=pi.right;cout<<pi.num<<"t"<<pi.handtime<<"t"<<pi.asktime<<"t"<<pi.starttime<<"t"<<pi.endtime<<"t"<<pi.usetime<<"t"<<pi.right<<"t"<<pi.runorder<<endl;cout<<"平均ttttt"<<sumtime/n<<"t"<<sumright/n<<endl;4、FCFS调度算法的函数void FCFS(pro p,int n)int i;p0.starttime=p0.handtime;p0.endtime=p0.handtime+p0.asktime;p0.usetime=p0.asktime;p0.right=1.0;p0.runorder=1;for(i=1;i<n;i+)if(pi.handtime<pi-1.endtime) pi.starttime=pi-1.endtime;elsepi.starttime=pi.handtime;pi.endtime=pi.starttime+pi.asktime;pi.usetime=pi.endtime-pi.handtime;pi.right=pi.usetime/pi.asktime;pi.runorder=i+1;double sumtime=0,sumright=0;cout<<"FCFS"<<endl;cout<<"作业号t提交t运行t开始t结束t周转t带权t执行"<<endl;for(i=0;i<n;i+)sumtime+=pi.usetime;sumright+=pi.right;cout<<pi.num<<"t"<<pi.handtime<<"t"<<pi.asktime<<"t"<<pi.starttime<<"t"<<p i.endtime<<"t"<<pi.usetime<<"t"<<pi.right<<"t"<<pi.runorder<<endl;cout<<"平均ttttt"<<sumtime/n<<"t"<<sumright/n<<endl<<endl;四、测试用例，运行结果与运行情况分析（图1：运行3个进程数的情况下程序结果）（图2：运行5个进程数的情况下程序结果）（图3：提交时间错误的情况下，程序自动纠正的运行结果）五、自我评价与总结1. 实验优点我认为我的实验重在进程调度的算法，使用到最常用的FCFS调度算法和SJF最短作业优先法，在程序编辑上，程序比较简明，使观看者能一眼分析出整个程序的脉络和构架，方便阅读。在程序结果显示上，也非常简明扼要，通过输入作业的提交时间和运行时间，可以用FCFS调度算法和SJF最短作业优先法分辨显示出，开始时间，结束时间，周转时间和带权周转时间，和执行次序。平均周转时间和平均带权周转时间，整体看上去符合课程设计题目要求，又非常详细。2. 实验不足我认为还有不足，在于如果第一个作业和第二个作业同时提交，无论二者所用的时间如何，都是先完成第一个作业，默认第一个作业先运行，对于后面的作业才会比较运行时间和提交时间，这在程序设计上出现了逻辑问题，虽然不影响使用，但是这还是算是美中不足，是在SJF函数的时间运算比较中出现问题，在链表的表头以后应该要改正。3. 收货与体会本次课程设计可以说是对操作系统课程本学期所学内容的一次综合应用，虽然称不上一个完整的操作系统进程调度程序，但已经展现了一个完整作业调度的雏形。通过本次课程设计，不仅进一步熟悉了操作系统所涉及的各方面知识，更掌握了一个进程调度的整体架构方式以及作业调度构造的整体流程。并且，从中认识到，进程调度模块化(先来先服务、轮转法、优先级法、最短作业优先法、最高响应比优先法)的重要，更是程序设计模块化的重要。但，在其过程中也暴漏了自身知识的匮乏，包括，C+知识学习不扎实，不能很好的运用链表；关于函数运用不熟练，导致在做两个函数的算法，用if else语句进行链表的重新排列（有点像冒泡排序）耗费大量时间等等。但总的来说，本次编程还是收获不少，不仅仅是实现了课程设计所要求的内容，更为以后深入的学习（包括课程相关与不相关）打下了坚实的基础。4. 实验改进方面可以在以后的课程实验中，结合实际，将先来先服务与最短作业优先法结合起来，完整的绘制一个应用程序，模拟进程调度，不仅更加真实，也更能锻炼我们的动手能力。六、参考文献（1） 计算机操作系统教程（第3版） 张尧学 史美林 张高编著（2） 计算机操作系统教程（第2版） 张尧学 史美林编著（3） 计算机操作系统（第3版） 汤小丹 梁红兵 哲凤屏编著（4） C+程序设计教程 闵联营 何克右编著（5） 百度文库本科生课程设计成绩评定表班级：计科0904班姓名：刘宇学号：0120910340403序号评分项目满分实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规范性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优（90-100分）、良（80-89分）、中（70-79分）、及格（60-69分）、60分以下为不及格指导教师签名：201 年月日