进程调度模拟设计――先来先服务、最高响应比优先调度算法

武汉理工大学《计算机操作系统》课程设计学号：012091034001课程设计题目进程调度模拟设计——先来先服务、最高响应比优先调度算法学院计算机科学与技术专业计算机科学与技术班级计算机009班姓名旭指导教师汪祥莉2012年1月9日武汉理工大学《计算机操作系统》课程设计课程设计任务书学生姓名：旭专业班级：计算机009指导教师：汪祥莉工作单位：计算机科学与技术学院题目:进程调度模拟设计——先来先服务、最高响应比优先调度算法初始条件：1．预备内容：阅读操作系统的处理机管理章节内容，对进程调度的功能以及进程调度算法有深入的理解。2．实践准备：掌握一种计算机高级语言的使用。要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）1．模拟进程调度，能够处理以下的情形：⑴能够选择不同的调度算法（要求中给出的调度算法）；⑵能够输入进程的基本信息，如进程名、到达时间和运行时间等；⑶根据选择的调度算法显示进程调度队列；⑷根据选择的调度算法计算平均周转时间和平均带权周转时间。2．设计报告内容应说明：⑴课程设计目的与功能；⑵需求分析，数据结构或模块说明(功能与框图)；⑶源程序的主要部分；⑷测试用例，运行结果与运行情况分析；⑸自我评价与总结：i）你认为你完成的设计哪些地方做得比较好或比较出色；ii）什么地方做得不太好，以后如何改正；iii）从本设计得到的收获（在编写，调试，执行过程中的经验和教训）；iv）完成本题是否有其他方法（如果有，简要说明该方法）；v）对实验题的评价和改进意见，请你推荐设计题目。时间安排：设计安排一周：周1、周2：完成程序分析及设计。周2、周3：完成程序调试及测试。周4、周5：验收、撰写课程设计报告。（注意事项：严禁抄袭，一旦发现，抄与被抄的一律按0分记）指导教师签名：年月日系主任（或责任教师）签名：年月日武汉理工大学《计算机操作系统》课程设计目录1设计题目................................12需求分析................................12.1功能需求....................................12.1.1进程调度模拟设计先来先服务法..................12.1.2进程调度模拟设计最高响应比优先调度算法.........22.2环境需求....................................32.3用户界面需求................................33功能设计................................33.1数据结构.....................................33.2模块说明.....................................44开发平台及源程序的主要部分...............54.1开发平台.....................................54.2源程序主要部分................................55测试用例，运行结果与运行情况分析.........65.1测试用例....................................65.2运行结果.....................................66自我评价与总结..........................77附加代码.................................8武汉理工大学《计算机操作系统》课程设计-1-1.设计题目1.先来先服务、最高响应比优先调度算法需求分析模拟进程调度，能够处理以下的情形：⑴能够选择不同的调度算法（要求中给出的调度算法）；⑵能够输入进程的基本信息，如进程名、到达时间和运行时间等；⑶根据选择的调度算法显示进程调度队列；⑷根据选择的调度算法计算平均周转时间和平均带权周转时间。2.1功能需求2.1.1实现先来先服务法：先来先服务算法基本思想：按照作业提交或进程变为就绪状态的先后次序，调入系统或分派CPU，换句话说，调度程序每次选择的作业/进程是等待时间最久的，而不管其运行时间的长短。这种调度算法突出的优点是实现简单，效率较低，在一些实际的系统和一般应用程序中采用这种算法的较多。因此，在设计中，首先对输入的各进程的提交时间进行比较，对武汉理工大学《计算机操作系统》课程设计-2-先进入等待队列的进程提供服务。2.1.2实现最高响应比优先调度算法：最高响应比优先法（HRN）是对FCFS方式和SJF方式的一种综合平衡。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。响应比R定义如下：R=(W+T)/T=1+W/T其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W/T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF法时的吞吐量。另外，武汉理工大学《计算机操作系统》课程设计-3-由于每次调度前要计算响应比，系统开销也要相应增加。2.2环境需求开发环境、运行环境及开发语言：开发环境：Windows平台＋VisualC++6.0运行环境：Windows全系列平台开发语言：C++2.3用户界面需求输入输出均采用命令行界面。格式如下：首先输入进程数。其次输入进程编号，姓名，到达时间，执行时间等相关信息。然后选择算法，优先法或者是最高响应比算法。最后，输出程序运行所得结果。3功能设计：3.1数据结构：创建一个进程信息结构：structPCB{stringname;//进程名floatta;//进程到达时间floatts;//进程估计运行的时间floattb;//进程开始运行时间floattm;//进程仍需运行的时间floatto;//进程完成的时间floatrn;//进程运行的次数武汉理工大学《计算机操作系统》课程设计-4-floattotalTime;//周转时间doubleweightTotalTime;//带权周转时间(周转时间/估计运行时间）PCB*next;//定义指向下一个进程的指针};此外，对输入信息进行创建链表队列：PCB*create(PCB*head){PCB*p1,*p2;p1=p2=newPCB;head=p1;cout请输入进程数：;cinpronum;for(inti=0;ipronum;i++){p2=p1;p1=newPCB;p1-next=NULL;cout请依次输入第i+1个进程的信息(进程名、到达时间、估计运行时间)：;cinp1-namep1-tap1-ts;p1-tm=p1-ts;p1-rn=1;p2-next=p1;}returnhead;}3.2模块说明首先选择调度算法，若选1先来先服务然则调用create（）武汉理工大学《计算机操作系统》课程设计-5-创建进程队列，然后调用fcfsrun()进行先来先服务算法，后Goto到起始点。若选择2最高响应比算法则调用create（）创建进程队列，然后调用Hrn（）进行最高响应比算法，后Goto到起始点。若选择3则退出，选择其他则报错。4开发平台及源程序的主要部分：4.1开发平台：开发环境、运行环境及开发语言：开发环境：Windows平台＋VisualC++6.04.2源程序主要部分：structPCB｛｝；//进程结构#defineMAX_NUM15intpronum;//定义进程数为pronumfloattotal;//记录所有进程的总时间doubleweight;//记录所有进程的带权周转时间PCB*create(PCB*head);//创建进程队列voiddeal(PCB*head);//FCFS记录处理voidsort(PCB*head);//将进程按到达的先后顺序排列voidfcfsrun(PCB*head);//先来先服务算法voidHrn(PCB*head,intn);//最高响应比算法voidmain(){}//主函数武汉理工大学《计算机操作系统》课程设计-6-流程图如下：5测试用例，运行结果与运行情况分析：5.1测试用例：正确的测试用例：先来先服务算法结果：开始1：先来先服务2：最高响应比3：退出程序输入进程数进程1信息进程2信息进程n信息武汉理工大学《计算机操作系统》课程设计-7-最高响应比结果：其他：六自我评价与总结：这次课程设计是让我们用已经学过的操作系统知识对先来先服务算法和最高响应比算法进行设计，使我在对进程调度的先来先服务和最高响应比优先算法充分理解的同时，也使我的实践编程能力和运用理论知识的能力得到进一步提高。在此次实验中，我认为我比较出色的是自己一开始就有了一个整体的思路，不像以前的课程设计一样，对全局的规划不是很清楚，以至于在后来模块的衔接做得不到位，但是此次的设计由于初始就对各个功能块的相互调用也比较了解，所以对该课设的设计整体上比较轻松，也使程序的编写比较清晰。武汉理工大学《计算机操作系统》课程设计-8-不过，在此次课设中我也出现了不少问题，尤其是在对先来先服务和最高响应比优先功能块的设计时，对其中每个进程之间的时间比较和响应比比较的具体代码还比较模糊，因此使得设计一度陷入了修改和编写中；此外，刚开始对程序的容错能力并未加入考虑的范围，所以使得程序的完整性和健壮性比较欠缺。所以，从中看出自己在具体细致的地方还约显不足，还有待提高。通过此次课程设计，也使我见到对同一实验目的可以使用多种方法，C++的编程比较符合我们现在的编程设计能力，但是使用JAVA也可以完成相同功能，而且会使得某些步骤还比较简易。此外，使程序具有较强的容错能力也对程序设计的优劣性起到较为重要的因素。相信通过这次的设计，对我以后的学习和编程能力有一定的帮助。七、附加代码#includeiostream#includestring#includeiomanipusingnamespacestd;structPCB{stringname;//进程名floatta;//进程到达时间floatts;//进程估计运行的时间floattb;//进程开始运行时间floattm;//进程仍需运行的时间floatto;//进程完成的时间floatrn;//进程运行的次数floattotalTime;//周转时间武汉理工大学《计算机操作系统》课程设计-9-doubleweightTotalTime;//带权周转时间(周转时间/估计运行时间）PCB*next;//定义指向下一个进程的指针};#defineMAX_NUM15intpronum;//定义进程数为pronumfloattotal;//记录所有进程的总时间doubleweight;//记录所有进程的带权周转时间PCB*create(PCB*head);//创建进程队列voiddeal(PCB*head);//FCFS记录处理voidsort(PCB*head);//将进程按到达的先后顺序排列voidfcfsrun(PCB*head);//先来先服务算法voidHrn(PCB*head,intn);voidmain(){intchoice;cout*进程调度模拟设计——先来先服务、最高响应比优先算法*endl;cout***********1.先来先服务算法***************************endl;cout***********2.最高响应比优先算法*********************endl;cout**********