多级反馈队列调度

[操作系统] 多级反馈队列的调度

实验目标

1.理解有关进程控制块，进程队列的概念。

2.掌握进程多级反馈队列的调度的处理逻辑。

3.设计进程控制块PCB的结构，分别适用于多级反馈队列的调度。

4.建立进程就绪队列。

5.编制多级反馈队列的调度算法。

实验要求

用高级语言编写和调试一个进程调度程序，以加深对进程的概念及进程调度算法的理解。设计思路

多级反馈队列

多级反馈队列原理

多级反馈队列调度算法又称反馈循环队列或多队列策略，主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在选不到时，才从较低级的就绪进程队列中选取。

具体描叙如下：

①OS设置有多个就绪队列（用qReadyi, i=1,2, ... ,n表示），用于存放等待处理的进程，每个队列的优先权（priority）各不相同，从第一个到最后一个依次降低；

②各个队列中进程执行的时间片大小各不相同，优先级越高的队列时间片越小，各个队列的时间片可按下面的规定：每一个队列时间片都比前一个队列时间片长1倍；

③当一个进程进入内存后，先放入第一队列qReady1末尾，按先来先响应的原则排队等待处理。该进程执行时若在规定的时间片内完成，则处理完毕，可撤离系统，若第一个时间片结束时尚未完成，则该进程转入第二队列qReady2的末尾排队等待处理，依次下去，直至转到最后一个队列中。

④仅当第i个队列qReadyi为空，才能调度第i+1队列qReady (i+1)中的进程运行。如果第qReadyi队列中某进程正在执行，又有新进程进入第qReady1至qReady(i-1)中任何队列，则此时正在运行的进程放回第i队列末尾，运行新进程。

●每个进程在输入时，需描述下面的特征：

进程名（可用字符串或用整数简单表示）

到达时间（可用整数表示，以时间片为单位）

所需执行时间（整数，以时间片为单位）

多级反馈队列调度算法

需求分析

多级反馈队列调度算法是一种性能较好的作业低级调度策略，能够满足各类用户的需要。对于分时交互型短作业，系统通常可在第一队列（高优先级队列）规定的时间片内让其完成工作，使终端型用户都感到满意；对短的批处理作业，通常，只需在第一或第一、第二队列（中优先级队列）中各执行一个时间片就能完成工作，周转时间仍然很短；对长的批处理作业，它将依次在第一、第二、……，各个队列中获得时间片并运行，决不会出现得不到处理的情况。此系统模拟了多级反馈队列调度算法及其实现，包含了一下几个功能模块：（注：此系统中无法实现线程的功能，只能用人为的方式实现对多级反馈队列调度算法的模拟！）

①创建进程

该模块实现对进程任务的创建，要求用户在创建进程时输入进程名，所需运行时间，任务的到达时间（时间片）则由系统自动赋值，即任务一被创建后立刻进入qReady1中，则该

任务的到达时间（时间片）为qReady1就绪队列的时间片。

该模块由涉及的算法有：

Status creatPro(LinkQueue &quePro)；

②运行进程

该模块首先判断运行队列中是否有任务在执行，如果处理器处于空闲状态，则按照多级反馈队列调度算法的原理依次从第一、第二……第i个就绪队列中选中一个进程任务进入运行队列。当处理器执行任务时间片到或者在规定的时间片内任务已完成，则把任务从处理器撤消或者让任务进入低优先级就绪队列中去，从新调度高优先级就绪队列中的任务进入运行队列，直到所有的就绪队列空了为止，或者处理器响应其他请求。

该模块由涉及的算法有：

void run();

void dealTime();

void runPro(void);

③阻塞进程

处理器在执行任务的过程中，出现等待使用资源或某事件的发生，如等待外设传输、等待人工干预等，则系统把运行队列中正在执行的任务撤消，让任务进入等待队列。

该模块由涉及的算法有：

void wait();

void wake();

④唤醒进程

任务进入等待队列后，当资源得到满足或某事件已经发生，如外设传输结束、人工干预完成时，处理器将等待队列中对应的任务重新调度到就绪队列中，等待处理器执行该任务。

该模块由涉及的算法有：

void wake();

⑤撤消进程

处理器在执行运行队列中的任务时，该模块模拟人工干预或其他中断导致任务提前退出系统的功能。

多级反馈队列调度算法主要数据结构

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

#include

// 函数结果状态代码

#define TRUE 1

#define FALSE 0

#define OK 1

#define ERROR 0

#define INFEASIBLE -1

#define OVERFLOW -2

///////////////////////

typedef int Status;

typedef int Boolean;

//////////////////////////////////////////

typedef struct QNode

{

char name[5];

int time;

int timeType;

QNode *next;

}*QueuePtr;

struct LinkQueue

{

QueuePtr front,rear; // 队头、队尾指针

};

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);

Status InitQueue(LinkQueue &Q);

Status creatPro(LinkQueue &quePro);

void dealTime();

void runPro(void);

void run();