优先级法、非强占式短进程优先算法

学号：课程设计题目进程调度模拟设计——优先级法、非强占式短进程优先算法学院计算机专业班级姓名指导教师吴利军2013年1月16日课程设计任务书学生姓名：指导教师：吴利军工作单位：计算机科学与技术学院题目:进程调度模拟设计——优先级法、非强占式短进程优先算法初始条件：1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2．实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．模拟进程调度，能够处理以下的情形：⑴能够选择不同的调度算法（要求中给出的调度算法）；⑵能够输入进程的基本信息，如进程名、优先级、到达时间和运行时间等；⑶根据选择的调度算法显示进程调度队列；⑷根据选择的调度算法计算平均周转时间和平均带权周转时间。2．设计报告内容应说明：⑴需求分析；⑵功能设计（数据结构及模块说明）；⑶开发平台及源程序的主要部分；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，一律按0分记）指导教师签名：年月日系主任（或责任教师）签名：年月日进程调度模拟设计--优先级法、非强占式短进程优先算法一．问题描述设计一程序模拟进程调度，能够选择优先级和非抢占短作业两种算法对进程调度。可以输入相关进程信息（进程名，达到时间，执行时间，优先级），最终能显示进程调度的序列。并能显示这些进程的平均周转时间和带权平均周转时间。二．需求分析通过设计一个模拟进程调度的系统，来实现进程调度，对进程调度的功能以及进程调度算法有一个更加深入的理解。进程PCB（包含进程名、到达时间、预计运行时间）调度算法（优先级、非强占式短进程优先）模拟进程调度，能够处理以下的情形：⑴能够选择不同的调度算法（要求中给出的调度算法）；⑵能够输入进程的基本信息，如进程名、到达时间和运行时间等；⑶根据选择的调度算法显示进程调度队列；⑷根据选择的调度算法计算平均周转时间和平均带权周转时间。此次做的进程调度模拟系统，用户可以输入各进程信息（包含进程名、到达时间、运行时间）。输入进程数，然后输入进程的提交时间和运行时间，显示优先级和非强占式短进程优先调度算法的进程名、提交时间、运行时间、开始时间、结束时间、周转时间、带权周转时间、执行时间、平均周转时间和平均带权周转时间。优先级法：优先级法可被用做作业或进程的调度策略。首先，系统或用户按某种原则为作业或进程指定一个优先级来表示该进程或作业所享有的优先权。改算法的核心是确定进程或作业的优先级。确定优先级的方法可分为两类。即静态法和动态法。静态法根据作业的或进程的静态特性，在作业或进程开始执行前就确定它们的优先级，一旦开始执行之后就不能改变。动态法则不然，它把作业或进程的静态特性结合起来确定作业或进程的优先级，随着作业或进程的执行过程，其优先级不断变化。非抢占短作业优先法：不可抢占式Non-preemptive（非剥夺式）：某一进程被调度运行后，除非由于它自身的原因不能运行，否则一直运行下去。短作业优先调度算法(SJF,ShortestJobFirst)，又称为“短进程优先”SPN(ShortestProcessNext)；这是对FCFS算法的改进，其目标是减少平均周转时间。基本思想：对预计执行时间短的作业（进程）优先处理。通常后来的短作业不抢先正在执行的作业。在一般情况下这种调度算法比先来先服务调度算法的效率要高一些。实现相对先来先服务调度算法要困难些，如果作业的到来顺序及运行时间不合适，会出现饿死现象，例如，系统中有一个运行时间很长的作业J，和几个运行时间小的作业，然后，不断地有运行时间小于J的作业的到来，这样，作业J就得不可调度而饿死。另外，作业运行的估计时间也有问题。三．功能设计1.数据结构在此次课程设计中主要采用了结构体数组的存储方式，将一个进程信息存储在一个结构体中，包括进程名称、进程优先级、进程提交时间、进程运行时间、进程周转时间。具体实现如下：structPRO{charname[10];//进程名floatarrivetime;进程时间floatservicetime;//进程执行时间floatstarttime;//开始时间floatfinishtime;//完成时间intxy;//优先级floatzztime;//周转时间floatdqzztime;//带权周转时间};2.程序流程框图优先级非抢占式短作业优先综合流程图3.模块说明本次课程设计中一共涉及五个模块（结构体定义，要处理进程信息的输入，两种算法的实现，处理完毕后进程信息的输出，主函数）（1）结构体定义如上所示（2）进程信息的输入voidinput(PRO*p,intn)P为结构体数组名，n为进程个数。（3）两种算法的实现优先级算法的具体实现voidYX(PRO*p,intN){floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0;floatdqzztime;intxy=0;sortxy(p,N);//基于时间的排序同时处理多个进程同时到达情况。for(intm=0;mN-1;m++){if(m==0)p[m].finishtime=p[m].arrivetime+p[m].servicetime;elsep[m].finishtime=p[m-1].finishtime+p[m].servicetime;inti=0;for(intn=m+1;n=N-1;n++){if(p[n].arrivetime=p[m].finishtime)i++;}floatmin=p[m+1].xy;intnext=m+1;//m+1=nfor(intk=m+1;km+i;k++){if(p[k+1].xymin){min=p[k+1].xy;next=k+1;}}PROtemp;temp=p[m+1];p[m+1]=p[next];p[next]=temp;}//令优先级高的执行deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy);//将排好序的进程处理计算出其周转时间和带权周转时间print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy);//输出处理完毕后进程信息}非抢占式短作业优先voidSJF(PRO*p,intN){floatarrivetime=0,servicetime=0,starttime=0,finishtime=0,zztime=0;floatdqzztime=0;intxy=0;sortt(p,N);//按到达时间进行排序printf(p[0].name);for(intm=0;mN-1;m++){if(m==0)p[m].finishtime=p[m].arrivetime+p[m].servicetime;elsep[m].finishtime=p[m-1].finishtime+p[m].servicetime;inti=0;for(intn=m+1;n=N-1;n++){if(p[n].arrivetime=p[m].finishtime)i++;}//得出在第m+1个进程执行完之前有多少个进程需要进行比较floatmin=p[m+1].servicetime;intnext=m+1;//m+1=nfor(intk=m+1;km+i;k++){if(p[k+1].servicetimemin){min=p[k+1].servicetime;next=k+1;}}//PROtemp;temp=p[m+1];p[m+1]=p[next];p[next]=temp;}//将执行时间最短的进程放在数组最前面deal(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy);//将排好序的进程处理计算出其周转时间和带权周转时间print(p,arrivetime,servicetime,starttime,finishtime,zztime,dqzztime,N,xy);//输出处理完毕后进程信息}（4）处理完进程信息的输出voidprint(PRO*p,floatarrivetime,floatservicetime,floatstarttime,floatfinishtime,floatzztime,floatdqzztime,intN,intxy)（5）主函数主要设计一个菜单功能。四．开发平台及源代码主要部分1.开发平台VisualStdio20102.源代码主要部分五．测试用例，运行结果与运行情况分析1.测试优先级进程在同一时刻到达进程名进程到达时间进程执行时间进程优先级a023b042c071可以得出当进程同时到达时，按优先级顺序执行。当进程不是同时到达，且优先级高的到的比较晚。进程名进程到达时间进程执行时间优先级a033b142c651从这个实例可以得出尽管c的优先级最高，但它最后到达，所以在c之前会执行已到达的进程。当进程不是全部同时到达，但有部分同时到达。进程名进程到达时间进程执行时间优先级a122b063c171尽管b的优先级最低，但其最先到达，所以最先执行，由于a，c进程，c进程的优先级高，所以c先执行。2.测试非抢占短作业优先当进程同时到达进程名进程到达时间进程处理时间优先级a051b012c023由于同时到达，那个进程执行时间短就先执行。当进程全部不是同时到达进程名进程到达时间进程执行时间优先级a321b462c913尽管c的执行时间最短，但因为其最后到达，之前cpu空闲，所以就先执行完前面到达的进程。当进程不是全部同时到达，但存在部分同时到达。进程名进程到达时间进程执行时间优先级a131b122c463当有同时到达的进程时，按照其执行时间排序，让执行时间短的进程先执行。六．自我评价与总结1.本系统的特点本系统是在数据结构上采用了结构体数组，这样使得进程的信息显得简单，明了，从而也为系统的设计降低了难度。再者本系统在设计的过程中，各个模块结构清晰，功能明确。在很多地方实现了代码重用，从而减少了代码的长度。并且本系统考虑到了诸多情况，相对比较完善。2.本系统的缺点由于本系统采用的是结构体数组，进程的信息全部存与p这个数组中，导致输入的信息最大不能超过p这个数组的初始长度。由于进程的时间一般涉及的都是毫秒级或者更小的单位，所以本系统中时间采用的是逻辑上的时间。当没有进程执行时，CPU怎么利用没有考虑。3.经验与小结通过本次课程设计使我对进程调度的算法在实践中有重新学习了一遍，从而理解的也就更深刻。从而也就对各个算法的优缺点有了更直观的认识。在测试用例中可以看到短进程优先法在处理时间问题上有很大的意义，可以有效地缩短平均周转时间以及平均带权周转时间，而优先级法却可以让某些重要的进程优先执行，两种方法各有所长。在本次设计中，发现小错误不断，耽误了不少时间。比如比较运算符和算术运算符弄混，中英文输入格式不对等等；这写错误的改正需要我们养成良好的编程习惯。通过本次课程设计也使我体会到了我们应该怎样解决问题。首先应该分析问题，应从哪里着手去解决问题，而不是一拿到问题就去写代码。只要分析正确，就可以使我们在后面的实现过程中事半功倍。总而言之，我们对操作系统的理解和认识还很肤浅，还需要进一步加大努力。