搜索
JLU《操作系统》课程设计[基于反馈（FeedBack，FB）排队算法的CPU调度的模拟实现]《操作系统》课程设计报告姓名学号一组实验室：提交日期成绩指导教师实验题目：基于反馈（FeedBack，FB）排队算法的CPU调度的模拟实现实验要求：功能要求：（1）就绪队列设置（界面）•设置就绪队列个数（≥3）及每个就绪队列优先级和每个就绪队列时间片；（2）运行结果（界面）•模拟动态创建多个进程，依据反馈排队算法调度原理，动态显示就绪队列中的进程、进程的剩余时间及占有CPU的进程；•动态显示等待队列中的进程（假设当前只有一个事件的等待队列）；•具体细节实现（1）设置多个进程（进程名、运行时间）进入就绪队列；（2）依据反馈排队算法的调度原理，对就绪队列中的进程进行调度或使进程进入相应的就绪队列；（3）当就绪队列中进程被调度，要启动一个相对时钟以反映运行的时间片；（4）一个进程占有CPU运行时，要随机产生I/O请求或I/O请求完成；（5）当随机产生I/O请求时，占有CPU的进程要进入等待队列；（6）当随机产生I/O完成时，等待队列的进程要进入相应的就绪队列；所需数据结构：typedefstructQNodetypedefstruct{{charname[5];QueuePtrfront;//队头指针inttime;QueuePtrrear;//队尾指针inttimeType;}LinkQueue;structQNode*next;}QNode,*QueuePtr;算法设计：多级反馈队列调度算法，不必事先知道各进程所需的进程时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下：1．设置多个就绪队列，并为各个队列赋予不同的优先级。第一个队列的优先权最高，第二个的次之，其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同，在优先权愈高的队列中，为每个进程所规定的执行时间片就愈小。例如，第二个队列的时间片要比第一个队列的时间片长一倍，……，第I+1个队列的时间片要比第I个队列的时间片长一倍。2．一个新进程进入内存后，首先将它放在第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统，如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列，……，如此下去，当一个长作业（进程）从第一队列依次降到第n队列后，在第n队列中便采取按时间片轮转的方式进行。3．仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；仅当第1~（I-1）队列均空时，才会调度第I队列中为某进程服务时，又有新进程进入优先权较高的队列（第1~（I-1）中的任何一个队列），则此时新进程将抢占正在运行进程的处理机，即由调度程序把正在运行的进程放回到第I队列的末尾，把处理机分配给新到的高优先权进程。流程图：否是是否否否是否是否否是否是图一输入若干进程信息取对头进程执行一次操作任务是否完成撤离系统入下个队列队尾是否有新进程到达按FCFS执行本队列中的进程执行中是否有新进程来该进程插入本队列队尾进程是否完成下队列是否为最后队列入该队列且进程按时间片轮转法执行时间片内是否完成完成创建四级就绪队列及等待队列新进程入第一对列当前队列是否为第一对队列新进程入就绪第一队列运行原进程开始是图二图三多级反馈队列算法实现流程图图解：图一：展示了程序的具体流程。首先输入进程首先将它放在第一队列的末尾，按FCFS原则排队等待调度。当轮到该进程执行时，如它能在该时间片内完成，便可准备撤离系统，如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行，以此类推得出结果；图二：展示了进程阻塞唤醒的过程图三：展示了进程撤销的过程。执行中选择阻塞进程进程进入阻塞队列选择唤醒进程进程进入第一级等待队列末尾队列完成执行中选择撤销进程进程被撤销队列删除当前运行进程完成任务分工及各分工实现方法：组长学号及姓名：分工：一直以来担任组长，要做的事很多，既要给组员分排任务，安排每个人的在课程设计要完成的任务，又要协调各个之间的分歧与合作，尽量融合大家的各种想法，汇总好的建议，好的做法，达到我们组的团体合作精神，这样才能把课程设计做的更好。负责算法的总体设计程序的全局变量和编写多级调度函数，整理每个人的工作，组合成整个算法。听取大家提出的问题和建议，完善算法。组员1学号及姓名：分工：设计程序中主要的进程控制块信息及其需要的变量，交由组讨论决定。编写系统中模块的程序进程插入进程到队尾、取对头进程函数。参与程序的调试。组员2学号及姓名：分工：设计程序多级反馈队列的具体实现方式，由组共同讨论决定。编写就绪队列创建函数，以及将就绪队列链栈起来。参与测试程序。测试结果：总结（对所作程序进行分析、评价运行效果，总结遇到的问题和解决办法）本程序基本上实现了多级反馈队列调度算法，能够创建新进程进入系统，系统按照设定的调度策略选择进程执行。新进程全部入第一级就绪队列，按FCFS取对头进程执行，在时间片没有完成插入下一个队列队尾，在执行的过程中可以插入新进程。新进程可以抢的当前进程的执行；如果所有进程都进入了第四级队列，便按时间片轮转法执行。经过了一周的设计时间，我们全体组员共同的努力下，终于完成了多级反馈队列调度算法的从设计到编程测试再到提交设计报告，完成了我们小组的课程设计任务。通过对多级反馈队列调度算法的模拟，大家一起讨论。一起设计。编写程序，在一起合作中，编程的能力得到增强，培养了自己的团队合作精神。最难的还是多级调度，刚开始不知道具体该怎样做的，各个模块在一个大的模块中实现多级调度，把一些其他的功能分别按照不同的作用，设置成一个个模块，进程的创建，取对头进程，进程插入队尾等等。把整个程序的主要部分集中在一个模块中，其中使用其他部分的模块组合成功能齐全的多级调度实施算法。主程序中调用这样的模块，便可实现了基本的调度模拟。在实际编写程序，有时想的和做的是不很一样的，在设计时函数功能是这样实现，但实际时，又往往不是这样，还有多方面考虑。有些功能需要反复多次使用，如果把它单独编写成一个功能模块完，这样便可实现全局的应用，减少代码的长度。不足与改进：设计的模拟算法还不是很好的，有需要完善的地方，程序中创建新进程是，感觉只输入进程的名字也不太好，还有创建的新进程名重复没把它考虑进去，导致输入已有的进程名，程序不能识别，仍然可以执行插入。随机有新进程的到来，没能完全做到，我们只是没间隔固定的时间，就可以输入新进程，模拟新进程的随机到来。可以把界面做的更美观一些，演示出每次执行的动态变化的结果，能够使程序的运行更加清晰明了。程序代码：//223.cpp:Definestheentrypointfortheconsoleapplication.//#includestdafx.h#includeSTRING.H//Definitionsformemoryandstringfunctions.#includeCTYPE.H//Definesthectypemacros.#includeMALLOC.H//memorymanagementfunctionsandvariables.#includeSTDIO.H#includeSTDLIB.H#includeIO.H//DefinitionsforlowlevelI/Ofunctions.#includePROCESS.H//Symbolsandstructuresforprocessmanagement.#includeCONIO.H//DirectMSDOSconsoleinput/output.#includeWINDOWS.H#includeTIME.H//Structandfunctiondeclarationsfordealingwithtime.#includeDOS.H//Definesstructs,unions,macros,andfunctionsfordealing//withMSDOSandtheInteliAPX86microprocessorfamily.//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2//////////////////////////////////////////typedefintStatus;//指定用Status和Boolean代表int类型typedefintBoolean;//////////////////////////////////////////typedefstructQNode{charname[5];inttime;inttimeType;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;//队头指针QueuePtrrear;//队尾指针}LinkQueue;intcount=0;//时间计数变量LinkQueueqRun,qWait,qReady1,qReady2,qReady3,qReady4;//////////////////////////////////////////////////////////////////////////voidmenu1();voidmenu2();voidgotoxy(intx,inty);voidclrscr(void);//清屏函数voidclreol(void);//在文本窗口中清除字符到行末voidclreoscr(void);//clearendofscreenStatusInitQueue(LinkQueue&Q);StatuscreatPro(LinkQueue&quePro);voiddealTime();voidrunPro(void);voidrun();voidwait();voidwake();voidendPro();////////////////////////////////////////////////////////////////////////////DOS界面坐标定位函数/////////////////////////////////////////////////////voidgotoxy(intx,inty){CONSOLE_SCREEN_BUFFER_INFOcsbiInfo;//variablendklarationHANDLEhConsoleOut;hConsoleOut=GetStdHandle(STD_OUTPUT_HANDLE);GetConsoleScreenBufferInfo(hConsoleOut,&csbiInfo);csbiInfo.dwCursorPosition.X=x;//cursorpositionXkoordinatefestlegencsbiInfo.dwCursorPosition.Y=y;//cursorpositionYkoordinatefestlegenSetConsoleCursorPosition(hConsoleOut,csbiInfo.dwCursorPosition);//dencursorandiefestgelegtekoordinatesetzen}StatusInitQueue(LinkQueue&Q){//构造一个空队列Qif(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))exit(OVERFLOW);Q.front-next=N