进程调度算法实验报告

一、实验目的多道程序系统中，当就绪进程数大于处理机数时，须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现进程调度，以加深对进程概念和不同进程调度算法的理解。二、实验环境1．PC微机。2．Windows操作系统。3．C/C++/VB等开发集成环境。三、实验内容与步骤编程实现如下进程调度算法：1)时间片轮转调度算法：时间片长度在运行时可从键盘输入。2)多级反馈队列调度算法：至少要有三个队列，第i+1队列进程运行的时间片是第i队列的2倍。3)高响应比优先调度算法：当调度响应比高的进程运行时，仍然是运行一个时间片，而不是完全结束，刚运行的进程，其以前的等待时间清零。实现提示：（1）PCB数据结构（参考）PCB至少包括：进程标识符、进程名、到达时间、服务时间、等待时间、完成时间、响应比等（可根据不同的算法增减）。假设多个PCB利用链接方式进行组织。（2）主要功能模块（参考）进程初始化；显示初始化后进程的基本信息；时间片轮转调度算法；多级反馈队列调度算法；高响应比优先调度算法；输入要求：可将进程初始化信息事先存入文件中，程序运行从文件中读取信息，避免从键盘输入速度慢且易出错。输出要求：每种调度算法每次调度后应直观显示，进程调度的依据、各进程的各项参数。每种调度算法运行结束后，输出各个进程对应的完成时间、周转时间和带权周转时间，以及整体的平均带权周转时间。四、实验结果与分析（1）程序的框架说明（2）各调度算法的设计思想1、时间片轮转算法该算法采取了非常公平的方式，即让就绪队列上的每个进程每次仅运行一个时间片。如果就绪队列上有N个进程，则每个进程每次大约都可获得1/N的处理机时间。时间片的大小对于系统性能有很大的影响。若选择很小的时间片，将有利于短作业，但意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完成，RR算法便退化为FCFS算法，无法满足短作业和交互式用户的需求。进程的切换时机体现出RR算法的特点。若一个进程在时间片还没结束时就已完成，此时立即激活调度程序，将它从执行队列中删除。若一个进程在时间片结束时还未运行完毕，则调度程序将把它送往就绪队列的末尾，等待下一次执行。2、多级反馈队列调度算法1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。3、高响应比优先调度算法一种动态优先调度算法，它以相应比作为作业或进程的动态优先权，其目的是既照顾短作业，又考虑到作业的等待时间，使长作业不会长期等待；但每次调度前，都要进行响应比计算，会增加系统开销。（3）实验结果1.RR算法2、HRN算法3、多级反馈队列调度算法（4）实验源程序#includeiostream#includealgorithm#includevector#includequeue#includestringusingnamespacestd;classJCB{public:intid;//进程标识符stringname;//进程名intarriveTime;//到达时间intserveTime;//要求服务时间intwaitTime;//等待时间，只用于最高响应比优先调度算法中intfinshTime;//完成时间introundTime;//周转时间doubleclock=0;//记录该进程真实服务时间已经用时的时长，用于在时间轮转调度算法中比较当前进程能否在当前时间片执行完毕doubleweightingRoundTime;//带权周转时间JCB(){}JCB(stringname,intarriveTime,intserveTime,doublepriority){this-name=name;this-arriveTime=arriveTime;this-serveTime=serveTime;this-waitTime=0;//初始等待时间置0}voidprintInf(){cout进程名：name；到达时间：arriveTime；要求服务时间：serveTime；剩余服务时间：((serveTime-clock)0?0:(serveTime-clock))endl;}};//按照到达时间升序boolcmp_arrvieTime_ascend(JCBj1,JCBj2){returnj1.arriveTimej2.arriveTime;}//用于高响应比优先调度算法boolcmp_weightingRoundTime_descend(JCBj1,JCBj2){returnj1.weightingRoundTimej2.weightingRoundTime;}//作业调度基础类classJobScheduling{public:vectorJCBprocess;//存放所有进程JCBnowPro;//当前应执行进程intk=0;//process中的进程遍历时的下标intnowTime=0;//当前时间voidprintProcess(){doubleaveRoundTime=0;cout*****************************************************endl;cout进程名到达时间服务时间完成时间周转时间带权周转时间endl;for(inti=0;iprocess.size();++i){aveRoundTime+=process[i].weightingRoundTime;coutprocess[i].nameprocess[i].arriveTimeprocess[i].serveTimeprocess[i].finshTimeprocess[i].roundTimeprocess[i].weightingRoundTimeendl;}cout平均带权周转时间:aveRoundTime/process.size()endl;process.clear();cout*****************************************************endl;}};//时间片轮转调度算法classRR:publicJobScheduling{public:queueJCBRRQueue;//就绪队列doublesliceTime;RR(vectorJCBjcb,doublesliceTime){this-process=jcb;this-sliceTime=sliceTime;//初始对所有进程按到达时间进行排序sort(process.begin(),process.end(),cmp_arrvieTime_ascend);}voidrun(){cout执行时间片轮转调度算法endl;Enqueue();while(!RRQueue.empty()||kprocess.size()){Dequeue();//出队，因为如果时间片结束当前进程未执行完又到达了新的进程，需要让刚到达的进程先进队列，再让当前进程进队列，所以进队操作写在这个函数里了}//输出进程运行信息printProcess();}voidEnqueue(){//进程进入就绪队列while(kprocess.size()){//当遍历完jcb中的所有进程时结束if(process[k].arriveTime=nowTime){//已经到达的进程按到达时间先后进入队列process[k].id=k;cout进程process[k].name进入就绪队列内等待endl;RRQueue.push(process[k]);k++;}else{break;//如果该进程还未到达，结束遍历。}}}voidDequeue(){nowTime+=sliceTime;//更新当前时间//如果就绪队列不为空if(!RRQueue.empty()){nowPro=RRQueue.front();//获取队首元素RRQueue.pop();//移除队列的队首元素nowPro.clock+=sliceTime;//更新当前进程的实际服务时间cout当前时间为:nowTimeendl;cout执行：;nowPro.printInf();//如果这个时间片时间片尚未用完，当前进程执行完毕。if(nowPro.clock=nowPro.serveTime){nowPro.finshTime=nowTime;//计算该进程完成时间nowPro.roundTime=nowPro.finshTime-nowPro.arriveTime;//计算周转时间nowPro.weightingRoundTime=nowPro.roundTime/nowPro.serveTime;//计算带权周转process[nowPro.id]=nowPro;//更新jcb中的进程信息}else{//当前进程未运行完Enqueue();//已到达的进程先入队RRQueue.push(nowPro);//上一轮出的再紧接着进入队尾}}else{//如果就绪队列为空，则执行入队Enqueue();}}};classHRN:publicJobScheduling{public:vectorJCBHRNQueue;//就绪队列HRN(vectorJCBjcb){process=jcb;//初始化带权轮转时间为1for(inti=0;iprocess.size();i++){process[i].weightingRoundTime=1;}//按到达时间升序排序sort(process.begin(),process.end(),cmp_arrvieTime_ascend);}voidrun(){//最高响应比优先调度算法nowTime=process[0].arriveTime;Enqueue();cout最高响应比优先调度算法endl;while(!HRNQueue.empty()||kprocess.size()){//如果将要执行的进程执行完毕之前，下一个进程都不会到来if(k==process.size()||nowTime+(HRNQueue[0].serveTime-HRNQueue[0].clock)process[k].arriveTime){Dequeue();//出队}//下一个进程执行到一半，会出现被新到来的进程抢占的可能else{inttime=process[k].arriveTime-nowTime;Dequeue(time);Enqueue();//已到达的进程入队}sort(HRNQueue.begin(),HRNQueue.end(),cmp_weightingRoundTime_descend);//队列中的进程按响应比进行排序}printProcess();}voidEnqueue(){//进程入队，可一次进多个while(kprocess.size()){//当遍历完jcb中的所有进程时结束if(process[k].arriveTime=nowTime){//已