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

多级反馈队列调度算法一实验内容以链式结构组成空闲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）函数 init（）初始化变量、初始化调度队列和睡眠队列 printlist（struct list *List）打印调度队列中的进程和剩余运行时间 gotosleep（struct mypcb *process）根据进程的剩余运行时间p_time,使其运行一段时间，并设置睡眠状态 iv.structproc *wakeup（struct list *List）判断是否有进程苏醒，本程序设计调用5次，唤醒队列首进程 wakeup_work（struct mypcb *p，struct list *List）苏醒进程插进原先优先级队列 newp（char pri，int size，int time）根据优先数、进程大小和运行时间的参数创建一个新进程，为新进程分配内存空间,睡眠原因为空，如进入睡眠，状态为s； addlist（struct list *List，struct mypcb *process）将进程添加到队列的尾部，包括睡眠队列;四、测试与分析程序输入格式为：./sched 输入文件内容为：优先级内存大小分配时间H 1000 301H 1000 200M 1000 203M 1000 200H 1000 100M 1000 102L 1000 200五、总结和思考1、总结自己实验过程中的心得体会；2、思考以下问题：（1）如何用简单的方法模拟I/O中断或其他事件，使进程睡眠若干时间。（2）如何设计触发睡眠队列中进程的事件，使其被唤醒，转变为运行状态。3、回答以下问