多级反馈队列调度算法的研究与实现
题 目：
姓 名： 邹善席
年 月 日
目 录
摘 要 .................................................. 1
1.课题背景 ............................................... 2
2．调度算法分析 .......................................... 2
3．算法设计思想 4．详细设计与实现 4.1算法设计流程图 3
4.2主要的数据结构 4
4.3算法实现 5
5. 调试过程与测试结果分析 .5.1 ............................... 8
5.2调试结果与分析 8
6．应用前景 .参考文献致 谢
多级反馈队列调度算法的研究与实现
姓名：邹善席 学号：[1**********]1
学院：计算机科学与技术学院 专业：计算机科学与技术
指导教师：王迤冉 职称：副教授
摘 要：多级反馈队列调度算法是一种综合性能较好的算法，能很好地实现作
业的公平性与系统资源利用率之间的平衡，兼顾多方面的系统目标。本论文以时间
关键词：调度算法；进程；队列；时间片
Research and Implementation of Multi-level Feedback Queue
Scheduling Algorithm
Abstract: Multi-level Feedback Queue Scheduling Algorithm can achieve a good balance
between fairness jobs and system resource utilization, taking a wide range of system goals
into account, is a batter comprehensive performance of the algorithm. This thesis is based
on Round-robin Scheduling Algorithm and High Priority Scheduling Algorithm, by
researching the relationship between queues, the process of the different and the same
queues with processes, design and implementation of the scheduling algorithm. Currently,
application prospects of the algorithm is very broad, commonly being used in processor
scheduling of multi-channel and single-channel system programming, severing as a role to
rational allocation costly and scarce resources in each system. Therefore, the researching
of Multi-level Feedback Queue Scheduling Algorithm has great significance about
developing various systems and development of the scheduling algorithm.
Key words: Scheduling Algorithm；Process；Queue；Round
1.课题背景
自上世纪计算机诞生以来，计算机技术突飞猛进，日新月异，而作为计算机技
术的一个重要组成——调度算法，也有了很大的发展， 目前存在的多种调度算法中，有的调度算法有利于长作业，有的有利于短作业，都有其优点和缺点。然而，有一
种调度算法既适用于长作业调度，又能适用于短作业调度，还能很好的处理长作业
和短作业的先后调度关系，比如多级反馈队列调度算法。
多级反馈队列调度算法以及独立分析问题，解决问题的能力。相对于其它
业的调度具有重要意义
2．调度算法分析
和发展,多级反馈队列调度算法可以兼顾
多方面的系统目标。
较短、长作业不会长时间得不到处理等优点，下面将对该算法的设计思想进行详细
的描述。
3．算法设计思想
通过研究就绪队列和进程的关系，比如就绪队列中各个进程的调度次序和进程
在不同队列之间如何移动等，得出了该算法的基本设计思想和调度示意图，具体内
容如下所述：
(1).设置多个就绪队列，并给队列赋予不同的优先数（规定优先数越小，优先
权越高），第一个队列优先级最高，依次递减，队列之间采用优先级调度算法。
(2).各级队列中的进程具有不同的时间片，优先级越高的队列中的进程的时间
片越小。
(3).只有高优先级队列为空时才调度下一级就绪队列中的进程。
(4).允许进程在队列之间移动个就绪队列末尾；如果完成，插入完成队列末尾。
(5).
(6).除最低优先权队列外的所有其他用相同的进程调度算
法，即按时间片轮转的FCFS算法，最后一中的进程按按时间片轮转
4．详细设计与实现
4.1算法设计流程图
在设计多级反馈队列调度算法流程图的过程中，因为篇幅原因，对该算法的设
计思想中的重要部分进行了详细的描绘，比如一个就绪队列中的多个进程应如何调
度以及进程如何在不同就绪队列之间移动，至于其他部分如创建队列﹑创建进程﹑
新进程到达等，一笔带过，但在算法实现中将会实现所有的设计思想，该算法详细
图2多级反馈队列调度算法流程图 4.2主要的数据结构
在进程的整个生命周期中，系统是通过PCB感知到该进程的存在的。PCB是进程存在的唯一标志。系统为每个进程定义了一个数据结构，即进程控制块。它通常具有
进程标识符、处理机状态、进程调度信息、进程控制信息等内容。
4.2.1 PCB的数据结构
本课题所设计的PCB如下所示：
typedef struct pcb /*定义进程*/
{
char name[20]; /*进程的名字*/
int round; /*分配给进程的时间片 int worked_time; /*进程已经执行时间 int need_time; /**/
char state; /*Rea—就绪状态，RunFin—完成状态*/ int count; /*计数器*/ struct pcb *next; /**/
} PCB;
4.2.2 队列的数据结构
定义队列*/
{
本队列所分配的时间片*/
本队列的优先级*/
指向队列中的进程*/
指向下一个队列*/
多级反馈队列调度算法中的逻辑十分严谨，要求对可能出现的所有状况都进行
处理，对逻辑能力和编程能力的要求较高。在实现算法过程中,队列和进程之间的关
系复杂，各个函数相互调度，而且不同函数的执行结果相互影响，这给我带来了很
大的困扰，因此，编程过程中，我先实现设计思想的一部分，然后再将没有实现的
部分设计加入进去，比如我在编程过程中先将关于“新到进程的处理”部分“摘除”，使得设计难度相对降低，编程实现也就相对容易，这样，我将设计思想分成几个模
块，对应模块编程，最后实现整个算法。该算法的主要函数如下所示：
void Creat_Que(void); /*1创建就绪队列函数*/ void Give_Prior(Queue *que); /*2队列排序函数 */
void Creat_Proc(void); /*3创建进程函数*/
void Insert_Rea(PCB *pc,Queue *que); /*4将进程插入到就绪队列尾部*/
void Get_Fir(Queue *que); /*5取得就绪队列中的队头进程*/
void Insert_Fin(PCB *pc); /*6*/
void Round_robin(Queue *que); /*7void Multi_Disp(void); /*8*/
void Output(void); /*9*/
在以上函数中，其中对逻辑能力和编程能力为严格的函数是
Round_robin(Queue *que)和Multi_Disp(void)因为Round_robin(Queue *que)函数与Multi_Disp(void)其源代码相同，又因篇
Multi_Disp(void)函数中的源
, 其经删减后的部分源代码如下所示：
进程每次循环执行完一个时间片，跳出*/
{
进程已执行时间加1 */
进程需求时间减1 */
run->count+=1; /*进程的计数器加1 */
if(run->need_time == 0) /*进程执行完毕*/
{
Insert_Fin(run); /*插入到完成队列 */
run=NULL; /*初始化执行队列 */
k=0; /*跳出循环的标记 */
}
else
{ if(run->count == run->round) /*时间片用完*/ {
run->count = 0; /*计数器清零，为下次做准备*/
if(p ->next!=NULL) /*指向的后继队列不为空*/
{ Insert_Rea(run,p->next); /**/ k=0;
}
else /**/
{ 插入到就绪队列尾部 */ 执行队列初始化 */ }
}
}
}
初始化，为下次循环做准备*/
队列中的进程为空,指向队列的指针后移*/ }
if(p->next==NULL) /*后继队列为空，执行时间片轮转*/
{
printf("执行到最后一个队列，时间片轮转!\n"); Round_robin(p); /*调度时间片轮转函数 */ break;
}
5. 调试过程与测试结果分析
5.1调试过程中对遇到的问题的处理措施
在调试程序过程中，最重要的就是找到源程序出错的位置，不断纠正源程序，在此我总结了调试过程中如何找到错误以及如何处理错误的方法，具体有以下四点：
(1).种结果进行处理。
(2).
(3).具体语句。
(4).
5.2
（1）设初始队列个数为5，其时间片分别为2、4、6、8、10,初始进程个数为4个，进程名为1、2、3、4，所需时间分别为6、10、17、25，后到达的两个进程5和6所需时间分别是32和40，具体内容详见图3和图4。
图
3
图4
（2了2个为2和4，此时，进程1完成。在第三级队列中进程2开始执行一个为65到达，5连续执行两个为2和4的时间括新进程）6。
图5
图6
（3）所有第三级队列中的进程执行一个为6四级队列中的进程3执行一个为8进程执行一个为8调度，在第五级队列中的进程4执行一个为10到达，,第一、二、三、四级队列中的进程62、4、6、8等7和图8。
图7
图8
（4）此后，没有新进程到达，在第五级进行时间片轮转调度，执行完所有进程。具体内容详见图9。
图9
6．应用前景
多级反馈队列调度算法都处于重要的地位，UNIX操作系统中。在其他软硬件系统中，级反馈队列
参考文献
[1]Rakesh Kumar Yadav,Anurag Upadhyay.A fresh loom for Multilevel feedback Queue scheduling Algorithm [J].International Journal on Computer Science and Engineering，2012.
[2]Ajit Singh,Priyanka Goyal,Sahil Batra et al.An Optimized Round Robin Scheduling Algorithm for CPU Scheduling[J].International Journal on Computer Science and Engineering，2010.
[3]Mostafa R Mohamed,Medhat H A Awadalla.Hybrid Algorithm for Multiprocessor Task Scheduling.
International Journal on Computer Science and Engineering，2011.
[4]Rakesh Kumar yadav,Abhishek K Mishra,Navin Prakash et al.An Improved Round Robin Scheduling Algorithm for CPU scheduling.International Journal on Computer Science and Engineering，2010.
[5]谢廷婷.一种基于分布式系统的队列多级调度算法[J].贵阳学院学报,2012,03:38-41. [6]宋连鹏.算法优化是实现程序优化的关键[J].信息与电脑,2013,08:89-90.
[7]马骏,杨功流.基于服务时间的加权公平队列调度算法[J].计算机工程,. [8]胡玲芳.新时期计算机软件开发技术的应用研究.信息与电脑,[9]金宏,王宏安,王强等.一种任务优先级的综合设计方法[J]. [10]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,[11]汤小丹,梁红兵,哲凤屏等.计算机操作系统[M].:,2010. [12]谭浩强.C程序设计[M].3版..
致 谢
本课题在选题及研究过程中得到王迤冉老师的悉心指导。王迤冉老师多次询问我的研究进程，并为我指点迷津，帮助我开拓研究思路，精心点拨、热忱鼓励。王迤冉老师一丝不苟的作风，严谨求实的态度，踏踏实实的精神，不仅授我以文，而且教我做人，虽历时半载，却终生受益。同时，在答辩过程中，三位答辩老师，尤其是孙挺老师，指出了此论文的多处不足，并给予了认真的指导，针对性的提出了相应的改进方法。也要感谢我身边的同学和任课老师，的宝贵意见和帮助，本论文的设计将会走不少弯路！
附录：(源程序)
/*多级反馈队列调度算法的基本思想如下：
1，第一个队列优
2 3
4 5
6．均采用相同的进程调度算法，即按时间片轮转的FCFS */
/*待优化1：再创建一个进程插入函数， 使进程在第一个队列按高优先级优先算法排序，进程数据结构中加如优先权属性，考虑作业紧迫性。
待优化2：在时间片轮转函数和多级反馈函数中关于新进程到达部分提出来，做成两个函数，提高代码可重用性，重要函数简洁明了。
待优化3：纵观整个程序，改进后一些代码功能重复，应尽可能的合并，使整个程序简洁，重要
函数中的变量初始化可整合到其他函数中*/
#include #include #include #include #include
typedef struct pcb /*定义进程*/ {
char name[20]; /*进程的名字*/ int round; /**/ int worked_time; /**/ int need_time; /**/
char state; /*进程的状态，R——执行状态，F——完成状态，B——阻塞状态（此处略过）*/
int count; /*计数器:一个时间片内进程运行时间*/ struct pcb *next; /*指向下一个进程的指针*/ }PCB;
/*定义队列*/ {
/*本队列所分配的时间片*/
/*本队列的优先级*/
PCB *LinkPCB; /*指向队列中的进程的指针*/
struct queue *next; /*指向下一个队列*/ }Queue;
int N,M,j=1,r=1; /*N进程个数,M就绪队列个数,j和r全局整变量*/
PCB *run=NULL,*finish=NULL; /*定义执行队列和完成队列的头指针*/ Queue *Head = NULL; /*定义多级就绪队列的头指针*/
void Creat_Que(void); /*1创建就绪队列函数*/ void Give_Prior(Queue *que); /*2将队列排序，规定就绪队列的优先数越小，优先级越高*/
void Creat_Proc(void); /*3创建进程函数*/
void Insert_Rea(PCB *pc,Queue *que); /*4将进程插入到就绪队列尾部void Get_Fir(Queue *que); /*5*/ void Insert_Fin(PCB *pc); /*6*/ void Round_robin(Queue *que); /*7*/
void Multi_Disp(void); /*8*/ void Output(void); /*9*/
int main(void) {
Creat_Que(); /*创建多级就绪队列*/ /*创建队列中的进程*/ /*多级反馈队列调度算法*/ }
void Creat_Que(void) /*1创建就绪队列函数*/ {
Queue *q;
int i;
printf("请输入就绪队列的个数 M：\n");
scanf("%d",&M); if(M
{
printf("请重新输入绪队列的个数：\n"); scanf("%d",&M);
}
for(i = 0;i
if((q = (Queue *)malloc(sizeof(Queue)))==NULL)
{
printf("内存空间不足!"); exit(1); }
printf("请输入第%d\n",i+1);
/*输入此就绪队列的时间片*/
if(q->round
{
%d个队列中的时间片\n",i+1); q ->prio = q->round; /*设置其队列优先级，优先数越小，队列优先级越高，时间片越小，队列优先级越高*/
q ->LinkPCB = NULL; /*初始化队列中的进程为空*/ q->next = NULL;
Give_Prior(q); /*按照优先级从高到低，建立多级就绪队列*/
printf("当前第%d个就绪绪队列的信息\n",i+1);
printf(" round prio\n"); }
void Give_Prior(Queue *que) /*2将队列排序，创建多级就绪队列,规定就绪队列的优先数越小，优先级越高*/ {
Queue *m,*n; m = n = Head;
if(Head == NULL) /**/ { }
printf("%6d\t%6d\t\n",q->round,q ->prio);
que->next = NULL; Head = que;
}
else /*查到合适的位置将队列插入*/
{
/*不小于第一个队列的优先级，则插入到队头*/
{
else
{
while(m->next!=NULL) /*移动指针查找第一个优先级比它小,优先数比它
大的队列的位置进行前插*/
{
n = m;
m = m->next;
}
if(m ->next == NULL) /*已经搜索到队尾，则其优先级最小，将其插入到队
尾*/
{
que ->next = m ->next; m ->next = que; }
else /*插入到队列中*/ {
n->next = que; que ->next = m; } }
void Creat_Proc(void) /*3创建进程函数,并把进程插入就绪队列尾部*/ { int i; N：\n"); if(N
printf("请重新输入进程的个数\n"); scanf("%d",&N); }
}
}
for(i = 0;i
{
if((p = (PCB *)malloc(sizeof(PCB)))==NULL)
{
printf("内存空间不足!");
exit(1);
} printf("请输入第%d个进程名字和所需时间,以空格隔开：\n",i+1);
scanf("%s",p -> name);
getchar();
scanf("%d",&(p -> need_time));
if(p -> need_timeneed_time)); }
当前第%d个进程的信息\n",j++);
printf("name round worked_time need_time state count\n");
printf("%2s\t%d\t%d\t%4d\t%6c\t%6d\n",p->name,p->round,p->worked_time,p->need_time,p->state,p->count);
Insert_Rea(p,Head); /*按照先来先服务算法，插入到就绪队列*/ }
}
void Insert_Rea(PCB *pc,Queue *que) /*4将进程插入到就绪队列尾部*/
{
PCB *p; pc->state='W'; /*改变进程的状态和时间片*/ pc->round=que->round;
p = que->LinkPCB;
if(que->LinkPCB == NULL) /*队列中的进程为空,*/ {
pc->next =que->LinkPCB;
que->LinkPCB =pc;
}
else
{
while(p->next != NULL) ,将其插入到尾部*/ {
p= p->next; }
}
void Get_Fir(Queue *que) /*5取得某一个就绪队列中的队头进程*/
{
if(que ->LinkPCB != NULL) /*队列中进程不为空*/
{
run = que ->LinkPCB;
run ->state = 'R';
que ->LinkPCB = que ->LinkPCB ->next; /*队列指向进程的的指针后移*/
run ->next = NULL;
}
else
{
run=NULL;
}
}
void Insert_Fin(PCB *pc) /*6*/
{
PCB *q; pc->state='F'; */
q = finish;
if(finish == NULL) /*完成队列为空，直接插入*/
{
}
while(q->next != NULL) /*搜索到完成队列中的进程的尾部,将其插入到尾部*/ {
q = q->next;
}
pc ->next = q ->next;
q ->next = pc;
}
}
void Round_robin(Queue *que) /*7时间片轮转调度函数*/
{
Get_Fir(que);
while(run != NULL) /*循环执行(执行队列)中的进程*/
{
int k=1,n; printf("/***★★★***第%d次执行!!!***★★★while(k!=0) /**/ { run->worked_time+=1; /**/
run->need_time-=1;
run->count+=1;
进程需求时间为0，进程执行完毕*/
{
k=0; else
{ if(run->count == que ->round)/*进程计数器值等于队列的时间片的值，表明进程时间片用完*/
{ run->count = 0; /*计数器清零，下次仍记录本进程*/
Insert_Rea(run,que); /*插入到就绪队列尾部*/
run=NULL; k=0; } } } k=1;
printf("2是否有新进程到达,请选择! 1.有 2.没有\n");
scanf("%d",&n);
if(n==1) /*队列调度函数*/
{ Creat_Proc(); Multi_Disp(); }
else
{
printf("2.\n");
/*就绪队列中的进程不为空*/ { Get_Fir(que); Output(); } else { printf("检测验证„„E\n"); Output(); printf("多级反馈队列调度算法模拟结束，所有进程执行完毕!\n");
}
} } } break;
void Multi_Disp(void) /*8*/ {
int m;
Queue *p;
p = Head;
printf("/********进程开始执行, Get_Fir(p);
Output();
while(run != NULL) 循环执行(执行队列)中的进程*/
{
int k=1; printf("/****☆☆%d次执行!!!***☆☆*****/\n",r++); /*每次循环执行完一个时间片*/ {
run->need_time-=1;
run->count+=1;
if(run->need_time == 0) /*进程执行完毕*/
{
Insert_Fin(run);
run=NULL; k=0;
}
else
{ if(run->count == run->round) /*时间片用完*/ {
run->count = 0;
if(p ->next!=NULL)
{ Insert_Rea(run,p->next);/**/ k=0;
}
else
} 是否有新进程到达,请选择! 1.有 2.没有\n"); } { } } scanf("%d",&m);
if(m==1)
{
Creat_Proc();
p=Head;
Get_Fir(p);
}
} else { printf("1.没有新进程到达，多级反馈队列调度算法模拟继续中„„\n"); if(p->LinkPCB==NULL) /*队列中的进程为空,指向队列的指针后移*/ { p=p->next; } } if(p->next==NULL) /*后继队列为空*/ { printf("1.1Round_robin(p); break; } Output(); } Get_Fir(p);
/*9进程信息输出函数*/
{
PCB *p;
printf("name round worked_time need_time state count\n");
while(q) /*循环输出就绪队列*/
{
if(q ->LinkPCB != NULL)
{
p=q ->LinkPCB;
while(p)
{
->count);
p = p->next;
}
}
q = q->next;
}
p = run;
while(p!=NULL) /* {
->count);
}
/*循环输出完成队列*/
{
printf("%2s\t%d\t%d\t%4d\t%6c\t%6d\n",p->name,p->round,p->worked_time,p->need_time,p->state,p->count);
p = p->next;
} }