多级反馈队列调度算法_多级反馈队列调度

2020-02-27 其他范文下载本文

多级反馈队列调度算法由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“多级反馈队列调度”。

多级反馈队列调度算法

一实验内容

以链式结构组成空闲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.ii.iii.int init（）初始化变量、初始化调度队列和睡眠队列

int printlist（struct list *List）打印调度队列中的进程和剩余运行时间

int gotosleep（struct mypcb *proce）根据进程的剩余运行时间p_time,struct proc *wakeup（struct list *List）判断是否有进程苏醒，本程序设int wakeup_work（struct mypcb *p，struct list *List）苏醒进程插进原使其运行一段时间，并设置睡眠状态

iv.计调用5次，唤醒队列首进程

v.先优先级队列

vi.int newp（char pri，int size，int time）根据优先数、进程大小和运行时间的参数创建一个新进程，为新进程分配内存空间,睡眠原因为空，如进入睡眠，状态为‘s’；

vii.int addlist（struct list *List，struct mypcb *proce）将进程添加到队列的尾部，包括睡眠队列;

四、测试与分析

程序输入格式为：./sched

输入文件内容为：

优先级内存大小分配时间 H 1000 301 H 1000 200 M 1000 203 M 1000 200 H 1000 100 M 1000 102 L 1000 200

五、总结和思考

1、总结自己实验过程中的心得体会；

2、思考以下问题：

（1）如何用简单的方法模拟I/O中断或其他事件，使进程睡眠若干时间。（2）如何设计触发睡眠队列中进程的事件，使其被唤醒，转变为运行状态。