进程调度算法实验报告资料

1、、实验目的多道程序系统中，当就绪进程数大于处理机数时，须按照某种策略决定哪些进程优先占用处理机。本实验模拟实现进程调度，以加深对进程概念和不同进程调度算法的理解。二、实验环境PC 微机。Windows 操作系统。C/C+/VB 等开发集成环境。三、实验内容与步骤编程实现如下进程调度算法：时间片轮转调度算法：时间片长度在运行时可从键盘输入。多级反馈队列调度算法：至少要有三个队列，第i+1 队列进程运行的时间片是第队列的2 倍。高响应比优先调度算法：当调度响应比高的进程运行时，仍然是运行一个时间片，而不是完全结束，刚运行的进程，其以前的等待时间清零。实现提示：PCB 数据结构（参考）PCB 至少包

2、括：进程标识符、进程名、到达时间、服务时间、等待时间、完成时间、响应比等（可根据不同的算法增减）。假设多个PCB 利用链接方式进行组织。主要功能模块（参考）进程初始化；显示初始化后进程的基本信息；时间片轮转调度算法；多级反馈队列调度算法；高响应比优先调度算法；输入要求：可将进程初始化信息事先存入文件中，程序运行从文件中读取信息，避免从键盘输入速度慢且易出错。输出要求：每种调度算法每次调度后应直观显示，进程调度的依据、各进程的各项参数。每种调度算法运行结束后，输出各个进程对应的完成时间、周转时间和带权周转时间，以及整体的平均带权周转时间。四、实验结果与分析33、高响应比优先调度算法(1)程序的框

3、架说明I I冲H时比质*盾显产量国取周方屁I I冲H时比质*盾显产量国取周方屁3)幽质也犹无揖慢啤而(2)各调度算法的设计思想1、时间片轮转算法该算法采取了非常公平的方式，即让就绪队列上的每个进程每次仅运行一个时间 片。如果就绪队列上有N个进程，则每个进程每次大约都可获得1/N的处理机时 问。时间片的大小对于系统性能有很大的影响。 若选择很小的时间片，将有利于 短作业，但意味着会频繁地执行进程调度和进程上下文的切换，这无疑会增加系统的开销。反之，若时间片选择得太长，且为使每个进程都能在一个时间片内完 成，RRB法便退化为FCFST法，无法满足短作业和交互式用户的需求。进程的 切换时机体现出RR

4、算法的特点。若一个进程在时间片还没结束时就已完成，此 时立即激活调度程序，将它从执行队列中删除。若一个进程在时间片结束时还未 运行完毕，则调度程序将把它送往就绪队列的末尾，等待下一次执行。2、多级反馈队列调度算法1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程， 则调度次优先级队列中的进程。例如： Q1,Q2,Q3三个队列，只有在Q1中没有进 程等待时才去调度Q2,同理，只有Q1,Q2都为空时才会去调度Q33、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间 片为N,那么Q1中的作业在经历

5、了 N个时间片后若还没有完成，则进入 Q2队列 等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。 4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这 个时间片后，CPU上分配给新到达的作业(抢占式)。33、多级反馈队列调度算法一种动态优先调度算法，它以相应比作为作业或进程的动态优先权， 其目的是既 照顾短作业，又考虑到作业的等待时间，使长作业不会长期等待；但每次调度前， 都要进行响应比计算，会增加系统开销。(3)实验结果1.RR算法 EMsudl ShJdid Prdjec t w占题 II n讯15由.201 ? I ftLexe青输入时间片的大小

6、Y依行时闱片拈传面传呼法脏银P2进入就绪队列内等恃史程P进入过靖队列内等侍回前时间为泮区小 进程曲P2；到达时皿为要求来?m闻5;刷余取势时间工1 洸程.P3进人就端队列内警恃当前时间为42报疔：迸程名：PS；到时间：4-要求服务时间I 7：剿奈噩务时间：3进程P1出.X西结队列内等待，前时间为：16执行，进程作P3;到葩时回：8;要求服务时间：制和余服务时间；1 进程P4进入就绪网列内峰恃当M时间为t20执仔：道他名：P2;到班时间：2:要求服务时间：副剌*服务时间:0 心棺酎间为:M技厅：起程名1 Plr .利达时间r 10:辕求用；算时司：4: F除堰今叶I可：0 当前时间为：28执行；

7、进程名：P6；型/时间：生要求噩弃时间：7；剁余眼符时间二0当前时间为：32执仃；出程加 M 刎达时啊】乳骁求战外时间；瓢上氽服务时间:0 当R时间为：36执厅;进程名：P3；勤电时间：的 要求里得时间：5;剩余里务时间：O乩741 44*444*4*4*+144*4*444中一*31441*啊*44祖坦名到总时间版着时间完应时间封转时间鬲杖周拈时间 TOC o 1-5 h z P22520183P5472R243P3E53C285F110424143P413232199平应忙出sm时闻46卜* *444 *1*申* 申*+4l44*中*4* * 卡2、HRN算法11入n卜”丫 11 ；髭M网

8、席泡:；： ；而叫不出防丐口出“市：*X调质鼻启尚久出就需队则内呼梏鼎码明比伏兀凋庠*沆号前时间为:？览L:进程名工期到达附画.E：鎏求黑多忖间:加热杂H尊时间13ififfPS 4时玷逆再咻科i前时司内门尚久出就需队则内呼梏鼎码明比伏兀凋庠*沆号前时间为:？览L:进程名工期到达附画.E：鎏求黑多忖间:加热杂H尊时间13ififfPS 4时玷逆再咻科i前时司内门tfi遇桂名士园F驯店忖间工备要求鹏招时向：篇亲M存时刊：叱FTP避人前击队列内等片11m时同去馈ffl.tr；题程名=P2；到店时皿2；费或总务时咏融朝能2落时期 3比胆”期人断帮认则内事梢h超时同为;】。帆行；ififiSi F2j

9、到5f同：Z;要里龈弄时呵：依泰(余K等时卧2 口地，倒人就璃丸皿内幕带行而忖列内;1、 他上：进标南：寸翻时间为:黑 枸斤；今苒时间为：24 他杷出超唐二 1ti肝时间内!29 次七二港程招工 当命时同育:热 他.打：电/名I到达时间;P1:到也时间:到工节同二Z：要求般务时间：5：抱亲能务时间：0I3i 0戏解学时间：3j嘉余孤务时悯:010.要求雅委附间翼宗腥器时间二0利上财同：4：要求m势所近1 71 M津n用时网 0kttt + f* + t + *1*t*+=* * *，I- T T r T T忸程名物达时向 鼬势酎问 之成时何 闺线时间 用打展转打回I& 酒 J1.24 2Die

10、1?2111平均带权周转时同;獴4* * * *事*1 *事事革单单 * * * * * A * * *U济输入以卜一数丁（1： 响片轮到7度津法：2： 白缴反胃队列用咬算法：3：点则它比比 3请输入第级队列的时间片的大小:2m程P2理人就盘队列内等行名或反笛认列谓变克法当前时间为：2执行：进程名：P2t到达时间：2；要求般分时间: 5；刎余版务时间：3进程Pa进入就绪队列内等待当前时间为:4执了：进程名：P5；到达时间：4：理求职务时间：7：刊登出号时间；5当前时间为：11执行；进程名；P2;到达时间：2；要求版务时间* 5:剩余康务时间；0进程3进入就绪队列内等待进程P1进入就绪队列内等待

11、当前时间为：口执行;进程名：P3；到达时间；3;要求服务时间，5；剩余期务时间；3进程F4.也入徜绳队列内等恃当前时间为：L3执行；进程名：P1；到达时间：10；要求服务时间：4;剩余服务时间：2当前时间为：15执行，进隹名：P*到达时间t 11要求服势时间：2：剩余服务时间，0当前时间为：17执仃：避程名：PS；到达时间：丸要求般苏时间：7;剌余用.务时间：1当蓟时间为:26执才门进程名: P3:到达忖间；8要求员外时间* 5:剌余昵为时间：0 当前时间为加执厅上进程名：Ph到达时间：1口：要求服务时间：4；剧余藤务时间:。当前时网为:赛执行二迸程名:P/到达时间；13;要求服务时间：2:超

12、余服务时间：。节前时间为：39执行F进程左 国器到达时间：工要求服务时间f 1则奈暇莠时间：0，*1|*1|*相仁*率*1|8*率*事*率进程到达时间服务时间定成时间冏转时网带被冏转时间P2591困739355P352&183PL)0430205P413232199怦均带气周转时间:4. 6*#，：*会后率4年+字字导丰字学辛丰奉学学学学丰字*+*零辛*4=*奈率号*+*(4)实验源程序#include #include algorithm#include vector#include #include string using namespacestd;class JCB public :i

13、nt id; /进程标识符string name; / 进程名int arriveTime; / 到达时间int serveTime; /要求服务时间int waitTime; /等待时间，只用于最高响应比优先调度算法中int finshTime; / 完成时间int roundTime; / 周转时间double clock = 0; /记录该进程真实服务时间已经用时的时长，用于在时间轮转调度算法中比 较当前进程能否在当前时间片执行完毕double weightingRoundTime; / 带权周转时间JCB() JCB(string name, int arriveTime , int

14、serveTime , double priority ) this -name = name;this -arriveTime = arriveTime ;this -serveTime = serveTime ;this -waitTime = 0; / 初始等待时间置0void printInf() cout 进程名： name ；到达时间： arriveTime ；要求服务时间： serveTime ；剩余服务时间： (serveTime - clock) 0 ? 0 : (serveTime - clock) endl;/ 按照到达时间升序bool cmp_arrvieTime_as

15、cend( JCB j1 , JCB j2 ) return j1 .arriveTime j2 .weightingRoundTime;/ 作业调度基础类class JobScheduling public :vector process; / 存放所有进程JCBnowPro; / 当前应执行进程int k = 0; / process 中的进程遍历时的下标int nowTime = 0; / 当前时间void printProcess() double aveRoundTime = 0;cout *cout * endl;cout 进程名到达时间服务时间完成时间周转时间带权周转时间 end

16、l;for ( int i = 0; i process.size(); +i) aveRoundTime += process i .weightingRoundTime; cout process i .name process i .arriveTime process i .serveTime process i .finshTime process i .roundTimeprocess i .weightingRoundTime endl;cout 平均带权周转时间: aveRoundTime / process.size() endl;process.clear();cout ”

17、*”cout ”*” endl;/ 时间片轮转调度算法class RR: public JobScheduling public :queue RRQueue;/ 就绪队列 double sliceTime;RR(vector jcb , double sliceTime ) this -process = jcb ; this -sliceTime = sliceTime ; / 初始对所有进程按到达时间进行排序 sort(process.begin(), process.end(), cmp_arrvieTime_ascend); void run() cout 执行时间片轮转调度算法 e

18、ndl;Enqueue(); while (!RRQueue.empty() | k process.size() Dequeue(); / 出队， 因为如果时间片结束当前进程未执行完又到达了新的进程，需要让刚到达的进程先进队列，再让当前进程进队列，所以进队操作写在这个函数里了 / 输出进程运行信息 printProcess(); void Enqueue() / 进程进入就绪队列while (k process.size() / 当遍历完jcb 中的所有进程时结束if (process k .arriveTime = nowTime) / 已经到达的进程按到达时间先后进入队process k

19、 .id = k;cout 进程 process k .name 进入就绪队列内等待 endl;RRQueue.push(process k );k+;else break; / 如果该进程还未到达，结束遍历。void Dequeue() nowTime += sliceTime; / 更新当前时间/ 如果就绪队列不为空if (!RRQueue.empty() nowPro = RRQueue.front(); / 获取队首元素RRQueue.pop(); / 移除队列的队首元素nowPro.clock += sliceTime; / 更新当前进程的实际服务时间cout 当前时间为: nowT

20、ime endl;cout = 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.

21、push(nowPro);/ 上一轮出的再紧接着进入队尾 else / 如果就绪队列为空，则执行入队Enqueue();class HRN: public JobScheduling public :vector HRNQueue;/ 就绪队列HRN(vector jcb ) process = jcb ;/ 初始化带权轮转时间为1for ( int i = 0; i process.size(); i+) process i .weightingRoundTime = 1;/ 按到达时间升序排序sort(process.begin(), process.end(), cmp_arrvieTi

22、me_ascend);void run() / 最高响应比优先调度算法nowTime = process 0 .arriveTime;Enqueue();cout 最高响应比优先调度算法 endl;while (!HRNQueue.empty()|kprocess.size() / 如果将要执行的进程执行完毕之前，下一个进程都不会到来if (k = process.size() | nowTime + (HRNQueue 0 .serveTime -HRNQueue0 .clock) process k .arriveTime) Dequeue(); / 出队/ 下一个进程执行到一半，会出现被

23、新到来的进程抢占的可能else int time = process k .arriveTime - nowTime;Dequeue(time);Enqueue(); / 已到达的进程入队sort(HRNQueue.begin(),HRNQueue.end(),cmp_weightingRoundTime_descend); / 队列中的进程按响应比进行排序printProcess();void Enqueue() / 进程入队，可一次进多个while (k process.size() / 当遍历完jcb 中的所有进程时结束if (process k .arriveTime = nowTim

24、e) / 已经到达的进程按到达时间先后进入队列process k .id = k;cout 进程 process k .name 进入就绪队列内等待 endl;HRNQueue.push_back(process k );k+;else break;/如果该进程还未入队，即先结束遍历，保留当前下标k值，注意：此处不要k- ；void Dequeue() if (!HRNQueue.empty() nowPro = HRNQueue0 ;/ 移除队列的队首元素并且返回该对象元素HRNQueue.erase(HRNQueue.begin();/nowProess.beginTime = nowTi

25、me;/ 计算开始时间，即为上一个进程的结束时间nowPro.finshTime = nowTime + nowPro.serveTime; / 计算结束时间，该进程开始时 间 +服务时间nowPro.roundTime = nowPro.finshTime - nowPro.arriveTime; / 计算周转时间 nowPro.weightingRoundTime = nowPro.roundTime / nowPro.serveTime; / 计算带权 周转时间nowTime = nowPro.finshTime; / 获得结束时间，即当前时间，方便判断剩下的进程是否已到达nowPro.

26、clock = nowPro.serveTime;cout 当前时间为: nowTime endl;cout 执行： ;nowPro.printInf();process nowPro.id = nowPro;for ( int i = 0; i HRNQueue.size(); +i) HRNQueuei .waitTime += nowPro.serveTime; / 所有进入等待队列的进程等待时间 +1HRNQueuei .weightingRoundTime = (HRNQueue i .waitTime + HRNQueuei .serveTime) / ( double )HRNQ

27、ueuei .serveTime;void Dequeue( int time ) if (!HRNQueue.empty() nowPro = HRNQueue0 ;/ 该进程不会执行完毕，无需移除nowPro.clock += time ;cout 当前时间为: nowTime endl;cout 执行： ;nowPro.printInf();nowTime += time ;process nowPro.id = nowPro;for ( int i = 0; i HRNQueue.size(); +i) HRNQueuei .waitTime += time ; / 所有进入等待队列的

28、进程等待时间+1HRNQueuei .weightingRoundTime = (HRNQueue i .waitTime + HRNQueuei .serveTime) / ( double )HRNQueuei .serveTime;class MFQ: public JobScheduling public :queue queue3;double sliceTime3;int sign;MFQ(vector jcb , double sliceTime ) this -sliceTime0 = sliceTime ;this -sliceTime1 =this -sliceTime0

29、* 2;this -sliceTime2 =this -sliceTime1 * 2;process = jcb ;sort(process.begin(), process.end(), cmp_arrvieTime_ascend); void run() nowTime = process 0 .arriveTime;Enqueue(0);cout 多级反馈队列调度算法 endl;while (k = sliceTime0) /cout 0 endl;Dequeue(sliceTime0);else /cout 1 endl;Dequeue();Enqueue(0);while (!que

30、ue1.empty() /cout 1 = sliceTime1) Dequeue(sliceTime1);else Dequeue();Enqueue(0);if (queue0.size() 0) break; / 如果第一级队列中新到来了进程/ 到最后一个队列，直接实行FCFSwhile (!queue2.empty() /cout 2 0) break; / 如果第一级队列中新到来了进程printProcess();void Enqueue( int sign ) / 进程入队，可一次进多个while (k process.size() / 当遍历完jcb 中的所有进程时结束if (p

31、rocess k .arriveTime = nowTime) / 已经到达的进程按到达时间先后进入队列process k .id = k;cout 进程 process k .name 进入就绪队列内等待 endl;queue sign .push(process k );k+;else break;/如果该进程还未入队，即先结束遍历，保留当前下标k值，注意：此处不要 k- ；void Dequeue() if (!queuesign.empty() nowPro = queuesign.front(); / 移除队列的队首元素并且返回该对象元素queuesign.pop();/nowProess.beginTime = nowTime;/ 计算开始时间，即为上一个进程的结束时间nowPro.finshTime = nowTime + nowPro.serveTime; / 计算结束时间，该进程开始时 间 +服务时间nowPro.roundTime = nowPro.finshTime - nowPro.arriveTime; / 计算周转时间nowPro.weightingRoundTime = nowPro.roundTime / nowPro.serveTime; / 计算带权周转时间nowTime = nowPro.fins