多优先级队列调度算法

一、多优先级队列调度算法的描述 

该算法有多个队列，同一个队列中的进程优先级相同，不同队列中进程优先级不同；最高优先级上的进程运行1个时间片，次高优先级上的进程运行2个时间片，再下一级运行4个时间片，依此类推；每次从队列头开始运行进程，每当一个进程在一个优先级队列中用完它的时间片后，就移到队列的尾部；只有当高优先级队列为空时才会从不为空的低优先级队列中选择进程运行；在低优先级队列中等待时间过长的进程，将移入高优先级队列。 

二、多优先级队列数据结构的定义 

多优先级队列数据结构的定义 
进程数据结构的定义 

class MultiPriorityQueueSchedule{ 

private: 

MYPROCESS MultiPriorityQueue[QUEUESIZE]; 

private: 

void MPQSFreeProcess(MYPROCESS); 

MYPROCESS MPQSSelectProcess(); 

void MPQSRunProcess(MYPROCESS); 

void MPQSGoAfter(MYPROCESS);//到队列尾 

void MPQSPriorityScheduling();//优先级调度 

public: 

MultiPriorityQueueSchedule(); 

bool MPQSAppendProcess(MYPROCESS); 

void MPQSExecute(); 

void MPQSDisplayQueue(ofstream&); 

}; 
typedef struct MyProcess 

{ 

char* MyProcessname; 

int CreateTime; 

int LastExecTime; 

int JobWeight; 

int EstimateUsedTime; 

int Priority; 

MyProcess *next; 

}* MYPROCESS; 

其他函数： 

MYPROCESS CreateMyProcess(char* name, int JW, int Prio); //创建进程 

int EstimateRunTime(int JW); //估计进程运行时间 

void BurstTime(int st); //SYSTIME增加 

void PriorityScheduling(MYPROCESS); //调整进程优先级 


三、Select方法 

1） 从高优先级队列到低优先级队列，当高优先级队列为空时才进入低优先级队列，否则跳到2）。当所有队列为空时，跳到4）。 

2） 选择此优先级队列的头一个进程运行，进程运行完它的时间片后，把此进程放到此优先级队列的尾部，跳到3）。 

3） 调整所有进程的优先级，跳到1）。 

4） 

四、编程测试 

根据上述内容进行编程，运行程序截图如下： 




图1：动态多优先级调度的过程图 




图2：静态多优先级队列和动态多优先级队列的比较 

附录中展示了程序中的类、函数和一些变量的定义。 



附录 
/*MultiPriorityQueue.h*/ 
/*Power by Keamou@CS@CITS@NKU*/ 

#include <string.h> 
#include <math.h> 
#define QUEUESIZE 32 //队列大小 
#define SLICETIME 5 //时间片 
static int SYSTIME = 0; //假设系统时间 

int EstimateRunTime(int JobWeight) 
{ 
return JobWeight; 
} /*估计进程运行时间*/ 

typedef struct MyProcess 
{ 
char* MyProcessname; 
int CreateTime; 
int LastExecTime; 
int JobWeight; 
int EstimateUsedTime; 
int Priority; 
MyProcess *next; 
}* MYPROCESS; /*进程定义*/ 

MYPROCESS CreateMyProcess(char* name, int JW, int Prio) 
{ 
MYPROCESS myproc; 
myproc = new MyProcess; 
myproc->MyProcessname = new char [10]; 
strcpy(myproc->MyProcessname,name); 
myproc->CreateTime = SYSTIME ; 
myproc->LastExecTime = SYSTIME; 
myproc->JobWeight = JW ; 
myproc->EstimateUsedTime = EstimateRunTime(JW) ; 
myproc->Priority = Prio; 
myproc->next=NULL; 
return myproc; 
} /*创建进程*/ 

void BurstTime(int st) 
{ 
SYSTIME += st ; 
} /*改变系统时间*/ 

void PriorityScheduling(MYPROCESS myproc) 
{ 
if ((SYSTIME-myproc->LastExecTime) > myproc->EstimateUsedTime) 
{ 
myproc->Priority--; 
if (myproc->Priority<0) 
{ 
myproc->Priority=0; 
} 
} 
} /*优先级调度*/ 

class MultiPriorityQueueSchedule 
{ 
private: 
MYPROCESS MultiPriorityQueue[QUEUESIZE]; 
private: 
void MPQSFreeProcess(MYPROCESS); 
MYPROCESS MPQSSelectProcess(); 
void MPQSRunProcess(MYPROCESS); 
void MPQSGoAfter(MYPROCESS); 
void MPQSPriorityScheduling(); 
public: 
MultiPriorityQueueSchedule(); 
bool MPQSAppendProcess(MYPROCESS); 
void MPQSExecute(); 
void MPQSDisplayQueue(ofstream&); 
}; /*多优先级调度队列的定义*/ 

MultiPriorityQueueSchedule::MultiPriorityQueueSchedule(){ 
for(int i=0;i<QUEUESIZE;i++) 
{ 
MultiPriorityQueue[i] = NULL; 
} 
} /*构造函数*/ 

bool MultiPriorityQueueSchedule::MPQSAppendProcess(MYPROCESS myproc) 
{ 
if (myproc->Priority >= QUEUESIZE) 
{ 
return false; 
} 
myproc->next = MultiPriorityQueue[myproc->Priority]; 
MultiPriorityQueue[myproc->Priority] = myproc; 
return true; 
} /*在多优先级队列中加入进程*/ 

void MultiPriorityQueueSchedule::MPQSFreeProcess(MYPROCESS myproc) 
{ 
MultiPriorityQueue[myproc->Priority] = myproc->next ; 
delete myproc; 
} /*释放进程*/ 

MYPROCESS MultiPriorityQueueSchedule::MPQSSelectProcess() 
{ 
int SearchNum ; 
for(SearchNum = 0; SearchNum < QUEUESIZE; SearchNum++ ) 
{ 
if (MultiPriorityQueue[SearchNum] != NULL) 
{ 
return MultiPriorityQueue[SearchNum]; 
} 
} 
return NULL; 
} /*选择运行进程*/ 

void MultiPriorityQueueSchedule::MPQSGoAfter(MYPROCESS myproc) 
{ 
int QueueNum; 
QueueNum = myproc->Priority ; 
MultiPriorityQueue[QueueNum] = myproc->next; 
MYPROCESS proctemp; 
proctemp= MultiPriorityQueue[QueueNum]; 
if (proctemp == NULL) 
{ 
MultiPriorityQueue[QueueNum] = myproc; 
return; 
} 
while (proctemp->next != NULL) 
{ 
proctemp = proctemp->next ; 
} 
proctemp->next = myproc ; 
myproc->next=NULL; 
} /*将运行后的进程放到队列尾部*/ 

void MultiPriorityQueueSchedule::MPQSPriorityScheduling() 
{ 
int PriorityNum ; 
MYPROCESS myproc; 
MYPROCESS proctemp; 
for(PriorityNum = 0; PriorityNum < QUEUESIZE; PriorityNum++ ) 
{ 
myproc = MultiPriorityQueue[PriorityNum]; 
while (myproc!=NULL) 
{ 
PriorityScheduling(myproc); 
if (myproc->Priority != PriorityNum) 
{ 
MultiPriorityQueue[PriorityNum]=myproc->next; 
MPQSAppendProcess(myproc); 
myproc=MultiPriorityQueue[PriorityNum]; 
} 
else 
break; 
} 
while (myproc!=NULL&&myproc->next!=NULL) 
{ 
PriorityScheduling(myproc->next); 
if (myproc->next->Priority!=PriorityNum) 
{ 
proctemp=myproc->next; 
myproc->next=myproc->next->next; 
MPQSAppendProcess(proctemp); 
} 
else 
myproc=myproc->next; 
} 
} 
} 

void MultiPriorityQueueSchedule::MPQSRunProcess(MYPROCESS myproc) 
{ 
if(myproc == NULL) 
return; 
int Runtime; 
Runtime = (pow(2,myproc->Priority))*SLICETIME ; 
myproc->EstimateUsedTime -= Runtime; 
if (myproc->EstimateUsedTime <= 0) 
{ 
BurstTime(Runtime+myproc->EstimateUsedTime); 
cout<<SYSTIME<<" \t"<<myproc->MyProcessname<<" \t"<<myproc->Priority<<" \tFree"<<endl; 
MPQSFreeProcess(myproc); 
} 
else 
{ 
BurstTime(Runtime); 
cout<<SYSTIME<<" \t"<<myproc->MyProcessname<<" \t"<<myproc->Priority<<" \tSwitch"<<endl; 
MPQSGoAfter(myproc); 
} 
} /*多优先级队列中的优先级调整调度*/ 

void MultiPriorityQueueSchedule::MPQSExecute() 
{ 
MYPROCESS myproc; 
do { 
myproc=MPQSSelectProcess(); 
MPQSRunProcess(myproc); 
MPQSPriorityScheduling(); 
} while(myproc!=NULL); 
} /*运行进程*/ 

void MultiPriorityQueueSchedule::MPQSDisplayQueue(ofstream& fout) 
{ 
int SearchNum ; 
MYPROCESS myproc; 
for(SearchNum = 0; SearchNum < QUEUESIZE; SearchNum++ ) 
{ 
myproc = MultiPriorityQueue[SearchNum]; 
while (myproc != NULL) 
{ 
fout<<myproc->MyProcessname<<" \t"<<myproc->Priority<<" \t"<<myproc->EstimateUsedTime<<endl; 
myproc = myproc->next ; 
} 
} 
} /*显示多优先级队列的状态*/