基于反馈(Feed Back,FB)排队算法的CPU调度的模拟实现.doc

JLU操作系统 课程设计基于反馈（Feed Back，FB）排队算法的CPU调度的模拟实现操作系统课程设计报告姓名学号一组实验室：提交日期成绩指导教师实验题目：基于反馈（Feed Back，FB）排队算法的CPU调度的模拟实现实验要求：功能要求：（1）就绪队列设置（界面） 设置就绪队列个数（3）及每个就绪队列优先级和每个就绪队列时间片；（2）运行结果（界面） 模拟动态创建多个进程，依据反馈排队算法调度原理，动态显示就绪队列中的进程、进程的剩余时间及占有CPU的进程； 动态显示等待队列中的进程（假设当前只有一个事件的等待队列）； 具体细节实现（1）设置多个进程（进程名、运行时间）进入就绪队列；（2）依据反馈排队算法的调度原理，对就绪队列中的进程进行调度或使进程进入相应的就绪队列；（3）当就绪队列中进程被调度，要启动一个相对时钟以反映运行的时间片；（4）一个进程占有CPU运行时，要随机产生I/O请求或I/O请求完成；（5）当随机产生I/O请求时，占有CPU的进程要进入等待队列；（6）当随机产生I/O完成时，等待队列的进程要进入相应的就绪队列； 所需数据结构：typedef struct QNode typedef struct char name5; QueuePtr front;/队头指针 int time; QueuePtr rear; / 队尾指针 int timeType; LinkQueue; struct QNode *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 : Defines the entry point for the console application./#include stdafx.h#include /Definitions for memory and string functions. #include /Defines the ctype macros. #include /memory management functions and variables. #include #include #include /Definitions for low level I/O functions. #include /Symbols and structures for process management. #include /Direct MSDOS console input/output. #include #include / Struct and function declarations for dealing with time. #include /Defines structs, unions, macros, and functions for dealing /with MSDOS and the Intel iAPX86 microprocessor family. / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 / typedef int Status; /指定用Status和Boolean代表int类型typedef int Boolean; / typedef struct QNode char name5; int time; int timeType; struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front;/队头指针 QueuePtr rear; / 队尾指针 LinkQueue; int count=0; /时间计数变量 LinkQueue qRun,qWait,qReady1,qReady2,qReady3,qReady4; / void menu1(); void menu2(); void gotoxy(int x,int y); void clrscr(void); /清屏函数 void clreol(void); /在文本窗口中清除字符到行末 void clreoscr(void); /clear end of screenStatus InitQueue(LinkQueue &Q); Status creatPro(LinkQueue &quePro); void dealTime(); void runPro(void); void run(); void wait(); void wake(); void endPro(); / /DOS界面坐标定位函数/ void gotoxy(int x,int y) CONSOLE_SCREEN_BUFFER_INFO csbiInfo; /variablendklaration HANDLE hConsoleOut; hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE); GetConsoleScreenBufferInfo(hConsoleOut,&csbiInfo); csbiInfo.dwCursorPosition.X = x; /cursorposition X koordinate festlegen csbiInfo.dwCursorPosition.Y = y; /cursorposition Y koordinate festlegen SetConsoleCursorPosition(hConsoleOut,csbiInfo.dwCursorPosition); /den cursor an die festgelegte koordinate setzen Status InitQueue(LinkQueue &Q) / 构造一个空队列Q if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode) exit(OVERFLOW); Q.front-next=NULL; return OK; Status EnQueue(LinkQueue &Q,char e5,int proTime,int tType) / 插入元素e为Q的新的队尾元素 QueuePtr p; if(!(p=(QueuePtr)malloc(sizeof(QNode) / 存储分配失败 exit(OVERFLOW); strcpy(p-name,e); p-time=proTime; p-timeType=tType; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK; Status DeQueue(LinkQueue &Q,char e5) / 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR QueuePtr p; if(Q.front=Q.rear) return ERROR; p=Q.front-next; strcpy(e,p-name); Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK; Status QueueTraverse(LinkQueue &Q,int x,int y) QueuePtr p; p=Q.front-next; while(p) gotoxy(x,y); printf(%s,p-name); gotoxy(x,y+1); printf(%d,p-time); p=p-next; x+=6; printf(n); return OK; void print() if(qRun.front!=qRun.rear) QueueTraverse(qRun,17,5); if(qWait.front!=qWait.rear) QueueTraverse(qWait,17,8); if(qReady1.front!=qReady1.rear) QueueTraverse(qReady1,17,11); if(qReady2.front!=qReady2.rear) QueueTraverse(qReady2,17,14); if(qReady3.front!=qReady3.rear) QueueTraverse(qReady3,17,17); if(qReady4.front!=qReady4.rear) QueueTraverse(qReady4,17,20); Status creatPro(LinkQueue &quePro) char proName5; int proTime; QueuePtr p; b: gotoxy(22,3); printf(进程名: ); gotoxy(36,3); printf(所需时间: ); gotoxy(30,3); scanf(%s,&proName); gotoxy(46,3); scanf(%d,&proTime); if(proTimename,proName); p-time=proTime; p-timeType=10; /进入时间片为10的就绪队列,即优先级最高的就绪队列 p-next=NULL; quePro.rear-next=p; quePro.rear=p; return OK; void dealTime() char e5; int tType=qRun.front-next-timeType; +count; qRun.front-next-time-; if(qRun.front-next-time=0) DeQueue(qRun,e); runPro(); count=0; else if(qRun.front-next-timeType=count) if(qRun.front-next-timeType=10) EnQueue(qReady2,qRun.front-next-name,qRun.front-next-time,tType+10); if(qRun.front-next-timeType=20) EnQueue(qReady3,qRun.front-next-name,qRun.front-next-time,tType+20); if(qRun.front-next-timeType=40) EnQueue(qReady4,qRun.front-next-name,qRun.front-next-time,80); if(qRun.front-next-timeType=80) EnQueue(qReady4,qRun.front-next-name,qRun.front-next-time,80); DeQueue(qRun,e); runPro(); count=0; void runPro(void) char e5; int pTime,f1=0,f2=0,f3=0,f4=0; if(qReady1.front!=qReady1.rear) pTime=qReady1.front-next-time; EnQueue(qRun,qReady1.front-next-name,pTime,qReady1.front-next-timeType); DeQueue(qReady1,e); f1=1; else if(qReady2.front!=qReady2.rear) pTime=qReady2.front-next-time; EnQueue(qRun,qReady2.front-next-name,pTime,qReady2.front-next-timeType); DeQueue(qReady2,e); f2=1; else if(qReady3.front!=qReady3.rear) pTime=qReady3.front-next-time; EnQueue(qRun,qReady3.front-next-name,pTime,qReady3.front-next-timeType); DeQueue(qReady3,e); f3=1; else if(qReady4.front!=qReady4.rear) pTime=qReady4.front-next-time; EnQueue(qRun,qReady4.front-next-name,pTime,qReady4.front-next-timeType); DeQueue(qReady4,e); f4=1; gotoxy(0,4); menu2(); if(f1=0 & f2=0 & f3=0 & f4=0) gotoxy(0,0); menu1(); gotoxy(22,3); printf(信息提示:无就绪进程,请输入其他功能选项!); gotoxy(0,4); menu2(); void run() if(qRun.front=qRun.rear) runPro(); else dealTime(); void endPro() char e5; if(qRun.front=qRun.rear) gotoxy(0,0); menu1(); gotoxy(22,3); printf(信息提示:无运行进程,请按Enter键运行进程!); gotoxy(15,3); else DeQueue(qRun,e); gotoxy(0,0); menu1(); gotoxy(22,3); printf(信息提示:选择菜单功能或按Enter键执行进程!); gotoxy(0,4); menu2(); print(); void wait() char e5; if(qRun.front!=qRun.rear) EnQueue(qWait,qRun.front-next-name,qRun.front-next-time,qRun.front-next-timeType); DeQueue(qRun,e); gotoxy(0,4); menu2(); print(); gotoxy(22,3); printf(信息提示: 选择菜单功能或按Enter键执行进程!); else gotoxy(0,0); menu1(); gotoxy(22,3); printf(信息提示:无运行进程,请输入其他功能选项!); void wake() char e5; if(qWait.front!=qWait.rear) EnQueue(qReady1,qWait.front-next-name,qWait.front-next-time,qWait.front-next-timeType); DeQueue(qWait,e); gotoxy(0,4); menu2(); print(); gotoxy(22,3); printf(信息提示: 选择菜单功能或按Enter键执行进程!); else gotoxy(0,0); menu1(); gotoxy(22,3); printf(信息提示:无等待进程,请输入其他功能选项!); void menu1() printf( n); printf( 1- 创建进程 2- 撤销进程3- 阻塞进程4- 唤醒进程0-退出系统 n); printf( n); printf( 菜单选择: n); void menu2() printf( n); printf( Run: n); printf( Time n)