多级反馈队列调度算法
在Linux下编程实现多级反馈队列调度算法，采用三级调度策略，所有进程先按到达顺序进入一级队列，按照时间片为2轮转一次，一个时间片内未完成的进程被依次移入二队列尾部。当一级队列中没有进程时，开始调度二级队列，按照时间片4轮转一次，一个时间片内未完成的进程被依次移入三队列尾部。当一级队列和二级队列中都没有进程时，开始调度三级队列，三级队列按照FCFS调度。队列之间按抢占式优先级调度，即只有高级队列中
实验目的：
在Linux下编程实现多级反馈队列调度算法，采用三级调度策略，所有进程先按到达顺序进入一级队列，按照时间片为2轮转一次，一个时间片内未完成的进程被依次移入二队列尾部。当一级队列中没有进程时，开始调度二级队列，按照时间片4轮转一次，一个时间片内未完成的进程被依次移入三队列尾部。当一级队列和二级队列中都没有进程时，开始调度三级队列，三级队列按照FCFS调度。队列之间按抢占式优先级调度，即只有高级队列中无进程时才能执行低级队列中的进程，且一级队列中的新来进程可抢占二级队列或者三级队列中的进程。
本实验设置了三级就绪队列ready1、ready2、ready3，前两级采用时间片轮转法，时间片大小分别为2和4，最后一级就绪队列采用FCFS调度（当时间片大于最大运行时间时RR就会变成FCFS）。
实验环境描述：
虚拟机：Ubuntu 5.4.0-6ubuntu1~16.04.12
操作系统版本：Linux version 4.15.0-142-generic (buildd@lgw01-amd64-039)
编译器版本：gcc version 5.4.0 2016060
实验测试数据（调试用）：
特定实验测试数据（调试用）
进程号 优先级 到达时刻 区间时间 剩余时间 进程状态
P1 2 6 8 8 N
P2 2 3 6 6 N
P3 2 2 10 10 N
P4 2 2 8 8 N
P5 3 9 4 4 N
随机测试数据（测试用)
由程序自动随机生成，因每次生成的数据不同故这里不举例了。
程序预期运行效果：
1）实验结果必须能够验证队列1中正确按照轮转（时间片2）调度
2）实验结果必须能够验证队列2中正确按照轮转（时间片4）调度
3）实验结果必须能够验证队列3中正确按照FCFS调度
4）实验结果必须能够观察到高级队列新来进程抢占低级队列中正在运行的进程的情况
5）实验结果中应输出每个时间点三个就绪队列的进程信息，以及被调度的进程。
6）可能需要多次运行才能观察到上述实验结果，需仔细分析实验结果。
7）进程的到达时间和运行时间随机生成，进程的数量不少于5个。
8）预计甘特数组应该为：空闲，空闲，P3,P3,P4,P4,P2,P2,P1,P1,P5,P5,P3,P3,
P3,P3,P4,P4,P4,P4,P2,P2,P2,P2,P1,P1,P1,P1,P5,P5,P3,P3,P3,P3,P4,P4,P1,P1。
9）程序应能够输出调度过程，所有进程结束后输出甘特图、响应时间、周转时间、
等待时间等信息。
调试过程问题：
在编写好代码调试时，我发现当切换不同级别的就绪队列时，甘特数组会在切换的那一时刻被吃掉一位，即少一位，继而会影响到进程的周转时间、等待时间等，造成数据错误。如下图，运行第二级别前应该是P3,P3,P4,P4,P2,P2,P1,P1,P5,P5，结果这里却少了一个P5。
分析出现上述错误的原因，发现是在切换不同级别队列的那一时刻，进行了两个进程的运行，本来S1最后一个进程运行完就该结束到下一时刻的，但这里却直接开始进行第二队列进程的运行了，所以我针对S2、S3设置了flag来判断是否是第一次切换就绪队列，从而解决了这个问题，如下图。
但是解决的并不彻底，如果设置随机生成的进程到达时间跨度比较大时，仍会出现换队列时吞进程的情况，目前还没想到怎么解决。
完整代码：
根据原来RR算法改编的，有一些冗余部分。
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<unistd.h>
#include<time.h>
#include<string.h>
#include <sys/types.h>
#include<sys/syscall.h>
/*本次实验模拟实现操作系统中进程调度算法,模拟进程在不同时刻到达的情况*/
#define PNUM 5 //进程的数量
#define TIMER 10 //定时器,最长CPU区间时间
//#define SLICE 2//轮转算法的时间片1
int timenow=0; //当前时刻
typedef struct node{
int pid; //进程号
int priority;//进程优先级,1~3,数字越小优先级越高
int arrival; //到达时间
int burst; //CPU区间时间
int rest; //剩余时间
char state;//进程状态,'N'新建,'R'运行,'W'等待CPU(就绪),'T'终止
struct node *next;
}PCB;
//int gantt[TIMER*PNUM]={0}; //用一个gantt数组记录调度过程,每个时刻调度的进程号
int gantt[1000]={0}; //用一个gantt数组记录调度过程,每个时刻调度的进程号
PCB *job;//所有作业的序列,带头节点(为简化编程)
PCB *ready1=NULL; //进程就绪队列,不带头节点
PCB *ready2=NULL; //进程就绪队列,不带头节点
PCB *ready3=NULL; //进程就绪队列,不带头节点
PCB *tail1=NULL; //记录就绪队列的尾节点
PCB *tail2=NULL; //记录就绪队列的尾节点
PCB *tail3=NULL; //记录就绪队列的尾节点
PCB *run1=NULL;//正在运行中的进程,不带头结点
PCB *run2=NULL;//正在运行中的进程,不带头结点
PCB *run3=NULL;//正在运行中的进程,不带头结点
PCB *finish=NULL;//已经结束的程序,不带头结点
void InitialJob()
{
int i=0;
PCB *p,*tail;
job=(PCB *)malloc(sizeof(PCB));//生成头节点,其它域无意义
job->next=NULL;
tail=job;
for(i=0;i<PNUM;i++)
{ p=(PCB *)malloc(sizeof(PCB));//生成新节点(新进程)
p->pid=i+1;
p->priority=rand()%3+1;//随机生成优先级:1~3
p->arrival=rand()%TIMER;//随机生成到达时刻0-10,(预计到达就绪队列的时间)
//p->arrival=rand()%20;//随机生成到达时刻0-50,(预计到达就绪队列的时间) expand
p->burst=rand()%TIMER+1;//随机生成CPU区间时间:1~10;(估计运行时间)
p->rest=p->burst;
p->state='N';//初始化进程的状态为'新建'
p->next=NULL;
tail->next=p;
tail=p; //带头结点
}
}
void DisplayPCB(PCB *pcb) //显示队列
{
struct node *p=pcb;
if(pcb==NULL) {printf("XXXXXX\n");return;}
printf("进程号 优先级 到达时刻 区间时间 剩余时间 进程状态\n");
do{
printf("P%-3d\t",p->pid);
printf("%3d\t",p->priority);
printf("%3d\t",p->arrival);
printf("%3d\t",p->burst);
printf("%3d\t",p->rest);
printf("%3c\t",p->state);
printf("\n");
p=p->next;
}while(p!=NULL);
}
void DisplayGantt() //显示甘特数组
{
int i=0;
for(i=0;i<timenow;i++)
{
if(gantt[i]==0) printf("空闲,");
else
printf("P%d,",gantt[i]);
}
printf("\n");
}
/*注:关于周转时间,等待时间与响应时间的概念释疑:
在课程教材<操作系统概念第7版>中(P141),上述三个时间是从进程到达的时间开始的.
在辅助教材<现代操作系统第4版>中(P89),上述三个时间时从进程提交的时刻(0时刻)开始的.
国内普遍接受前一种理解,本程序以课程教材中的解释为准来计算时间.
*/
void DisplayTime() //显示周转时间t,等待时间w和响应时间r
{
int t=0,w=0,r=0;
float t_avg=0,w_avg=0,r_avg=0;
int i,j;
PCB *p; //用p遍历finish队列,查找进程Pi的到达时间,调用该函数时所有进程都已放入finish队列
if(finish==NULL) {return;}
printf("进程号 周转时间 等待时间 响应时间\n");
for(i=1;i<=PNUM;i++)
{ p=finish;
while(p->pid!=i) p=p->next;
j=0;
while(gantt[j]!=i) j++; //遍历甘特数组,求进程Pi的响应时间
r=j; //响应时刻
t=j+1;
for(j=r+1;j<timenow;j++) //继续遍历,求周转时间
{ if(i==gantt[j]) t=j+1;}//结束时刻
r=r-p->arrival; //响应时间=响应时刻-到达时刻
t=t-p->arrival; //周转时间=结束时刻-到达时刻
w=t-p->burst; //等待时间=周转时间-运行时间
r_avg+=(float)r/PNUM; //平均响应时间
w_avg+=(float)w/PNUM; //平均等待时间
t_avg+=(float)t/PNUM; //平均周转时间
printf("P%d %4d %4d %4d\n",i,t,w,r);
}
printf("平均周转时间:%.2f,平均等待时间%.2f,平均响应时间%.2f\n",t_avg,w_avg,r_avg);
}
void ReadyQueue(char * algo,int t) //根据作业队列构造就绪队列,algo:算法,t:当前时刻
{
struct node *jpre,*jcur,*rpre,* rcur;
int j,r,a=0;
if(strcmp(algo,"FCFS")==0||strcmp(algo,"RR")==0)//FCFS和RR的就绪队列的构造方式相同
a=0;
else {printf("ReadyQueue()函数调用参数错误!\n");exit(0);}
if(job->next==NULL) {printf("作业队列为空!\n");return;}
jpre=job;
jcur=job->next;
while(jcur!=NULL) //遍历作业序列中选择已到达进程,将其从作业队列移入就绪队列,直到作业队列为空
{
if(jcur->arrival<=t) //如果当前时刻进程已经到达,则将其插入到就绪队列的合适位置
{
printf("P%d到达.\n",jcur->pid);
jpre->next=jcur->next; //将jcur从作业队列移除
jcur->state='W';//将进程状态设置为就绪
if(ready1==NULL) //就绪队列为空
{jcur->next=NULL;ready1=jcur;tail1=ready1;}
else //就绪队列不为空,遍历就绪队列,将jcur插入到合适位置
{ rpre=ready1;
rcur=ready1;
switch (a){ //遍历就绪队列查找插入点
case 0: //FCFS,RR.根据到达时间arrival查找合适插入点
while((rcur!=NULL)&&(jcur->arrival>=rcur->arrival))
{rpre=rcur;rcur=rcur->next;}
break;
case 1: //SJF,根据区间时间burst查找合适插入点
while((rcur!=NULL)&&(jcur->burst>=rcur->burst))
{rpre=rcur;rcur=rcur->next;}
break;
default: break;
}
if(rcur==NULL)// 插入点在就绪队列尾部
{
jcur->next=NULL;
rpre->next=jcur;
tail1=jcur;
}
else if(rcur==ready1) //插入点在头部
{
jcur->next=rcur;
ready1=jcur;
}
else //插入到rpre和rcur之间
{
jcur->next=rcur;
rpre->next=jcur;
}
}
jcur=jpre->next; //下一个作业
}else //当前作业未达到
{jpre=jcur;jcur=jcur->next;} //下一个作业
}
printf("\n作业队列:\n");
DisplayPCB(job->next);
}
void MFQ()
{
int timeslice[3];//时间片设置
timeslice[0]=2;
timeslice[1]=4;
timeslice[2]=11;//>10 -> FCFS()
timenow=0;
int flag1=0,flag2=0;
int count=0; //时间片计数,count==slice表示进程已经运行一个时间片
while(true)
{
printf("\n当前时刻:%d\n",timenow);
ReadyQueue("RR",timenow);//刷新就绪队列
printf("就绪队列1:\n");
DisplayPCB(ready1);
printf("就绪队列2:\n");
DisplayPCB(ready2);
printf("就绪队列3:\n");
DisplayPCB(ready3);
if(job->next==NULL&&ready1==NULL&&ready2==NULL&&run1==NULL&&run2==NULL&&ready3==NULL&&run3==NULL) {break;} //没有进程,结束循环
if(ready1==NULL) {tail1=NULL;}
if(tail1!=NULL) printf("就绪队列1尾节点:P%d\n",tail1->pid);
if(ready1!=NULL||run1!=NULL) //有进程处于就绪或者运行状态
{
if(run1==NULL)//若CPU空闲
{
count=0;
run1=ready1; //将CPU分配给ready队列1的第一个进程
ready1=ready1->next;
run1->next=NULL;
printf("\nP%d被调度程序分派CPU!\n",run1->pid);
}
count++;
run1->rest--; //修改进程PCB
run1->state='R';
printf("\nP%d正在运行.......\n",run1->pid);
printf("运行进程:\n");
DisplayPCB(run1);
gantt[timenow]=run1->pid; //记录当前时刻调度进程的ID号
printf("\ncount=%d\n",count);
if(run1->rest==0) //进程结束,将进程设置为终止状态,移入结束进程队列
{ printf("P%d结束!\n",run1->pid);
// count=0;
run1->state='T';
run1->next=finish; //新完成的节点插入到finish的头结点,简单一点
finish=run1;
run1=NULL;
printf("结束进程队列:\n");
DisplayPCB(finish);
}
else if(count==timeslice[0]) //时间片2结束,进程未结束,将run插入就绪队列2尾部
{
printf("P%d时间片结束!\n",run1->pid);
// count=0;
run1->state='W';
if(ready2!=NULL)
{tail2->next=run1;
tail2=run1;
}
else //时间片结束时就绪队列为空,将run直接放入就绪队列
{ ready2=tail2=run1;
}
run1=NULL;
}
}
//the second 二级队列
if(ready2==NULL) {tail2=NULL;}
if(tail2!=NULL) printf("就绪队列2尾节点:P%d\n",tail2->pid);
if(ready1==NULL&&run1==NULL&& (ready2!=NULL||run2!=NULL))flag1=flag1+1;
if(ready1==NULL&&run1==NULL&&flag1>=2&& (ready2!=NULL||run2!=NULL)) //有进程处于就绪或者运行状态
//if(ready1==NULL&&run1==NULL&& (ready2!=NULL||run2!=NULL)) //有进程处于就绪或者运行状态
{
if(run2==NULL)//若CPU空闲
{
count=0;
run2=ready2; //将CPU分配给ready队列1的第一个进程
ready2=ready2->next;
run2->next=NULL;
printf("\nP%d被调度程序分派CPU!\n",run2->pid);
}
count++;
run2->rest--; //修改进程PCB
run2->state='R';
printf("\nP%d正在运行.......\n",run2->pid);
printf("运行进程:\n");
DisplayPCB(run2);
gantt[timenow]=run2->pid; //记录当前时刻调度进程的ID号
printf("\ncount=%d\n",count);
if(run2->rest==0) //进程结束,将进程设置为终止状态,移入结束进程队列
{ printf("P%d结束!\n",run2->pid);
// count=0;
run2->state='T';
run2->next=finish; //新完成的节点插入到finish的头结点,简单一点
finish=run2;
run2=NULL;
printf("结束进程队列:\n");
DisplayPCB(finish);
}
else if(count==timeslice[1]) //时间片4结束,进程未结束,将run插入就绪队列尾部
{
printf("P%d时间片结束!\n",run2->pid);
// count=0;
run2->state='W';
if(ready3!=NULL)
{tail3->next=run2;
tail3=run2;
}
else //时间片结束时就绪队列为空,将run直接放入就绪队列
{ ready3=tail3=run2;
}
run2=NULL;
}
}
//third 三级队列
if(ready3==NULL) {tail3=NULL;}
if(tail3!=NULL) printf("就绪队列3尾节点:P%d\n",tail3->pid);
if(ready1==NULL && run1==NULL && ready2==NULL && run2==NULL && (ready3!=NULL||run3!=NULL))flag2=flag2+1;
//fang zhi qie huan ji bie shi tun P5
if(ready1==NULL&&run1==NULL&&ready2==NULL&&run2==NULL && flag2>=2 &&(ready3!=NULL||run3!=NULL)) //有进程处于就绪或者运行状态
// if(ready1==NULL&&run1==NULL&&ready2==NULL&&run2==NULL &&(ready3!=NULL||run3!=NULL))
{
if(run3==NULL)//若CPU空闲
{
count=0;
run3=ready3; //将CPU分配给ready队列1的第一个进程
ready3=ready3->next;
run3->next=NULL;
printf("\nP%d被调度程序分派CPU!\n",run3->pid);
}
count++;
run3->rest--; //修改进程PCB
run3->state='R';
printf("\nP%d正在运行.......\n",run3->pid);
printf("运行进程:\n");
DisplayPCB(run3);
gantt[timenow]=run3->pid; //记录当前时刻调度进程的ID号
printf("\ncount=%d\n",count);
if(run3->rest==0) //进程结束,将进程设置为终止状态,移入结束进程队列
{ printf("P%d结束!\n",run3->pid);
// count=0;
run3->state='T';
run3->next=finish; //新完成的节点插入到finish的头结点,简单一点
finish=run3;
run3=NULL;
printf("结束进程队列:\n");
DisplayPCB(finish);
}
else if(count==timeslice[2]) //时间片15结束(FCFS()),进程未结束,将run插入就绪队列尾部
{
printf("P%d时间片结束!\n",run3->pid);
// count=0;
run3->state='W';
if(ready3!=NULL)
{tail3->next=run3;
tail3=run3;
}
else //时间片结束时就绪队列为空,将run直接放入就绪队列
{ ready3=tail3=run3;
}
run3=NULL;
}
}
timenow++; //下一时刻继续扫描作业队列
DisplayGantt();
}
}
int main()
{ //srand((int)time(NULL)); //随机数种子
srand(0); //固定测试数据
InitialJob();
DisplayPCB(job->next);
MFQ();
DisplayGantt();
DisplayTime();
return EXIT_SUCCESS;;
}程序运行结果：
... ...
... ...
结果分析：
甘特图如下：
| 空 | 空 | P3 | P3 | P4 | P4 | P2 | P2 | P1 | P1 | P5 | P5 | P3 | P3 | P3 | P3 | P4 | P4 | P4 | P4 | P2 | P2 | P2 | P2 | P1 | P1 | P1 | P1 | P5 | P5 | P3 | P3 | P3 | P3 | P4 | P4 | P1 | P1 |
| S1队列 | S2队列 | S3队列 | |||||||||||||||||||||||||||||||||||
在进程到达前，甘特数组为空，当t=2时，P3、P4到达，因为在第一级S1队列，时间片为2，所以依次执行P3、P4各两次，t=6，因时间片结束但进程没结束，所以将进程放入第二级队列S2，进程状态为等待；t=3时P2到达，t=6时P1到达，t=9时P5到达S1就绪队列，在P2、P1、P5依次到达S1后，由于他们位于最高级别的队列，所以先执行P2、P1、P5各两个时间片，此时t=12，当S1就绪队列没有进程时才能执行S2就绪队列，时间片为4，同理，如果S2中进程时间片结束但进程没结束，就将进程放入第三级队列S3。如甘特数组所示，P3、P4、P2、P1各执行了4次，因为P5只剩2了所以再执行两次进程就结束了，而P3、P4、P1在S2中仍未结束，所以被放入第三级队列，当第一、二队列为空时，将第三队列进程按照FCFS算法（当RR轮转调度时间片大于执行时间时就是FCFS调度）依次执行完，最终结束。由甘特图可知，最终结果和与预期一致。
实验总结：
通过本次实验，我学习了新的调度方法——多级反馈队列调度算法，该算法是操作系统中CPU处理机调度算法之一，它既可以使高优先级的任务得到优先的响应，又能够使短作业任务迅速完成，此算法应用于同一个资源的多个使用者可分优先级使用资源的情况，也是目前操作系统调度算法中被公认的一种较好的调度算法。
对我而言，本次实验并不简单，实验过程中遇到了不少困难，但也收获了很多，比如在算法编程的过程中我对数据结构的运用也有了进一步的认识。虽然一开始有点无从下手，但是通过广泛的查阅资料，我逐渐理清了多级反馈队列调度算法的实现机理，可是仍写不出正确的代码，程序运行时总会出现意料之外的各种小Bug，不能实现预期的结果，后来听从老师的建议，先固定实验测试数据，然后单步调试，逐一排查问题，最终完成了多级反馈队列调度算法，这个算法程序还有一些不足之处，比如不够简洁等，在今后的学习时间里我会继续完善。
为开发者提供学习成长、分享交流、生态实践、资源工具等服务，帮助开发者快速成长。
更多推荐
11
0- 0
已为社区贡献2条内容
所有评论(0)