多级反馈队列调度算法.docxVIP

多级反馈队列调度算法 一实验内容 ????以链式结构组成空闲PCB栈，以双向链式结构组成进程的就绪队列和睡眠队列，模拟UNIX的进程管理程序，实现以下操作（可用键盘命令、命令文件或由产生的随机数决定操作和参数）。 （1）??????????创建一个新进程：如pid=newp（pri，size，time），申请空闲PCB和所需内存，填写PCB的各项初始数据，将该PCB送入就绪队列。 （2）??????????调度和执行：自己设计多级反馈队列调度算法，在就绪队列中选择一个优先级最高的进程，使其运行若干单位时间。要求在运行期间进程的p_cpu、p_pri和p_time要变化，并在适当的时机重新调度。 （3）??????????进程睡眠：进程运行时可调用自编的睡眠函数，主动进入睡眠状态，并转调度程序。也可由操作使进程强迫挂起，睡眠适当时间。进程睡眠时要在PCB中记录睡眠原因和优先数。 （4）??????????进程的唤??：根据睡眠原因，将相应的进程从睡眠队列中调出，转入就绪队列。如果该进程优先级比现在运行的优先级高，则转调度程序。 （5）??????????进程的终止：如果一个进程运行完作业所需的时间，该进程就终止，释放所占用的内存和PCB资源，转调度程序。 ? 二、设计思想 ???实现多级犯规队列调度算法，多级调度队列分别高优先级（H或h）队列、中优先级（M或m）队列和低优先级的（L或l）队列。 （1）????当一个进程在一次运行中用完了时间片（100单位时间）还未完成任务或没有进入阻塞状态，降低其优先级，进入低一级的调度队列。 （2）????进程没用完的时间片，就因为I/O等原因转变为阻塞状态。等到阻塞原因解除，转变为就绪状态后，仍回到原先队列。 （3）????当一个进程正在运行时，在更高的优先级的队列中到来了一个进程，那么高优先级的进程可以抢占当前进程的处理机。被抢占的进程已运行了一定的时间（但没到达100单位时间），仍留在原先的队列中。 （4）????进程在时间片内完成了任务，被撤离系统。 三、函数和算法 （1）????建议使用的PCB数据结构 struct mypcb { ?????? char p_pid;???? //进程标志数 ?????? char p_pstat;?? //进程状态 ?????? void *p_addr;?? //进程映像在内存中的首址 ?????? int p_size;???? //进程映像的长度 ?????? char p_pri;???? //进程优先数 ?????? int p_cpu;????? //进程当前运行的时间 ?????? int p_time;???? //作业运行的（剩余）总时间 ?????? char p_wchan;?? //进程睡眠原因 ?????? struct mypcb *p_next,*p_prior;??? //进程mypcb的双向链指针 }; （2）????主程序： 初始化变量和队列 从输入文件中读入进程信息，创建进程 打印初始的3个调度队列进程 调度主循环 ????首先调度高优先级队列进程 ??? IF?有进行苏醒 ????????设定当前进程运行一段时间，进程剩余时间减去该时间 ????????打印当前进程的信息和将要唤醒的进程 ?? ??在睡眠队列唤醒进程，回到调度主循环 IF当前进程满足睡眠条件 ???打印当前进程的信息 ???进程移出调度队列 ???加入睡眠队列，回到调度主循环 IF?当前进程不满足睡眠条件 ??? IF?进程总剩余时间100 ???????运行并用掉时间片中的剩余时间 ???????从高优先级队列中移出，加入中优先级队列 ??? ELSE ???????用掉全部剩余时间，从队列中删去 ???????其次调度次高优先级队列进程（略） ???????最后调度低优先级队列进程（略） ???????如果3个调度队列和睡眠队列皆空，调度循环终止 （3）????函数 ??????????????????????? i.??????????????int init（）初始化变量、初始化调度队列和睡眠队列 ????????????????????? ii.??????????????int printlist（struct list *List）打印调度队列中的进程和剩余运行时间 ??????????????????? iii.??????????????int gotosleep（struct mypcb *process）根据进程的剩余运行时间p_time,使其运行一段时间，并设置睡眠状态 ???????????????????? iv.??????????????struct?proc *wakeup（struct list *Li