当前位置：文档之家› 多级反馈队列调度

多级反馈队列调度

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

实验目标

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

// 函数结果状态代码

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

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

}

void clrscr(void) //clearscreen: gesamten Bildschirm leeren

{

CONSOLE_SCREEN_BUFFER_INFO csbiInfo; //variablendklaration

HANDLE hConsoleOut;

COORD Home = {0,0};

DWORD dummy;

hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);

GetConsoleScreenBufferInfo(hConsoleOut,&csbiInfo);

FillConsoleOutputCharacter(hConsoleOut,' ',csbiInfo.dwSize.X * csbiInfo.dwSize.Y,Home,&dummy); //bis cursorposition leerzeichen ausgeben csbiInfo.dwCursorPosition.X = 0; //cursorposition X koordinate festlegen

csbiInfo.dwCursorPosition.Y = 0; //cursorposition Y koordinate festlegen

SetConsoleCursorPosition(hConsoleOut,csbiInfo.dwCursorPosition); //den cursor an die festgelegte koordinate setzen

}

void clreol(void) //clear end of line

{

CONSOLE_SCREEN_BUFFER_INFO csbiInfo; //variablendklaration

HANDLE hConsoleOut;

COORD Home,pos;

DWORD dummy;

hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);

GetConsoleScreenBufferInfo(hConsoleOut,&csbiInfo);

Home = csbiInfo.dwCursorPosition;

pos.X = 80 - csbiInfo.dwCursorPosition.X;

FillConsoleOutputCharacter(hConsoleOut,' ',pos.X,Home,&dummy);

}

void clreoscr(void) //clear end of screen: alles nach dem cursor

{

CONSOLE_SCREEN_BUFFER_INFO csbiInfo;

HANDLE hConsoleOut;

COORD Home;

DWORD dummy;

hConsoleOut = GetStdHandle(STD_OUTPUT_HANDLE);

GetConsoleScreenBufferInfo(hConsoleOut,&csbiInfo);

Home=csbiInfo.dwCursorPosition;

FillConsoleOutputCharacter(hConsoleOut,' ',csbiInfo.dwSize.X * csbiInfo.dwSize.Y,Home,&dummy);

}

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

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 e[5],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 e[5])

{ // 若队列不空,删除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 proName[5];

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(proTime<=0)

{

gotoxy(22,3);

printf("信息提示: 输入时间错误!请按Enter键返回!");gotoxy(15,3);

getchar();getchar();

gotoxy(0,0);

menu1();

goto b;

}

getchar();

if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败

exit(OVERFLOW);

strcpy(p->name,proName);

p->time=proTime;

p->timeType=10; //进入时间片为10的就绪队列,即优先级最高的就绪队列p->next=NULL;

quePro.rear->next=p;

quePro.rear=p;

return OK;

}

void dealTime()

{

char e[5];

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 e[5];

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 e[5];

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 e[5];

if(qRun.front!=qRun.rear)

{

EnQueue(qWait,qRun.front->next->name,qRun.front->next->time,qRun.front->next->timeTy pe);

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 e[5];

if(qWait.front!=qWait.rear)

{

EnQueue(qReady1,qWait.front->next->name,qWait.front->next->time,qWait.front->next->ti meType);

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