多级反馈队列调度算法
参考一
多级反馈队列调度算法
- 背景/需求分析
在科学技术迅速发展的当代以及经济发展的需求,服务器和任务的数量都在高速增长,同时资源调度的方式以及数量也在成倍增长，目前存在的多种调度算法中，有的调度算法有利于长作业，有的有利于短作业，都有其优点和缺点。然而，有一种调度算法既适用于长作业调度，又能适用于短作业调度，还能很好的处理长作业和短作业的先后调度关系，比如多级反馈队列调度算法。多级反馈队列调度算法是目前公认的较好的一种进程调度算法，它能较好的满足各类进程的需要。
多级反馈队列调度算法是一种CPU处理机调度算法,UNIX操作系统采取的便是这种调度算法。 多级反馈队列调度算法即能使高优先级的作业得到响应又能使短作业(进程)迅速完成。 多级反馈队列调度算法是一种性能较好的作业低级调度策略,能够满足各类用户的需要。对于分时交互型短作业,系统通常可在第一队列(高优先级队列)规定的时间片内让其完成工作,使终端型用户都感到满意;对短的批处理作业,通常,只需在第一或第一、第二队列(中优先级队列)中各执行一个时间片就能完成工作,周转时间仍然很短;对长的批处理作业,它将依次在第一、第二、......,各个队列中获得时间片并运行,决不会出现得不到处理的情况。此系统模拟了多级反馈队列调度算法及其实现。
- 系统设计
程序采用键盘输入或随机生成的方式来模拟网络信号、文件操作等各类等待事件。程序的主体部分为三个函数体，init，MFQ，print。使用结构体来存储进程的信息。
主函数main中给用户提供随机测试样例和键盘输入测试样例两种选择，并打印菜单。在init函数中完成变量输入与初始化，包括就绪队列总数、第一队列时间片大小（该程序中设定后一队列时间片大小为前一队列时间片大小两倍）、进程总数、各个进程的到达时间和运行时间。在MFQ函数中主要模拟多级反馈队列调度算法。设置多级就绪队列，优先级最低的采用RR算法，其他采用FCFS算法。在这里先把所有的队列都用FCFS排列，先调度高优先度的进程，若在时间片内不能运行完就放入下一队列，这样能够保证优先级最低的队列是RR。如果有高优先级的进程到达，则放弃正在调度的进程，转向调度最高优先级的进程。在print函数中，将算法计算出的进程完成时间、周转时间、带权周转时间、平均周转时间、平均带权周转时间输出，作为测试结果。
- 详细设计
设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片。若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经在最下级的队列，则重新放回最下级队列队尾。只有第k级队列为空时，才会为k+1级队头的进程分配时间片被抢占处理机的进程重新放回原队列队尾。
对于优先级最低的队列来说，里面是遵循时间片轮转法（RR）。也就是说，位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法（FCFS），每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。
图3-1算法示意图
图3-2算法流程图
- 系统编码
main.cpp
#include<bits/stdc++.h>
using namespace std;
const int MAXSIZE=100;
int qsize=7; //就绪队列总数默认为7
struct node
{
int id; //进程编号
int num; //进程个数
int arrive; //到达时间
int finish; //完成时间
int run; //运行时间
int turn; //周转时间
double wturn; //带权周转时间
};
vector<node> v;
//进程按照到达时间先后排序
bool cmp(node x,node y)
{
return x.arrive<y.arrive;
}
//变量输入与初始化
void init(int test,int &tslice)
{
srand(time(0));
int number; //第一队列时间片大小，进程个数
node temp;
if(test==1)
{
tslice=rand()%5+1;
number=rand()%30+2;
for(int i=1;i<=number;i++)
{
temp.id=i;
temp.arrive=rand()%30;
temp.run=rand()%50+1;
temp.finish=0;
v.push_back(temp);
}
}
else
{
cout<<"请输入就绪队列总数：";cin>>qsize;
cout<<"请输入第一队列时间片大小（默认后一队列时间片大小为前一队列时间片大小两倍）：";
cin>>tslice;
cout<<"请输入进程个数：";cin>>number;
cout<<"请输入进程的到达时间和运行时间：";
for(int i=1;i<=number;i++)
{
temp.id=i;
cin>>temp.arrive>>temp.run;
temp.finish=0;
v.push_back(temp);
}
}
}
//多级反馈队列调度算法(抢占式)
void MFQ(int tslice)
{
queue<node> ready[MAXSIZE]; //定义就绪队列
vector<node> ans; //答案
sort(v.begin(),v.end(),cmp); //按照FCFS原则排序
int time=(*v.begin()).arrive; //第一个进程到达时间
ready[0].push(*v.begin());v.erase(v.begin());
cout<<endl<<"--测试进程运行过程--"<<endl;
while(!v.empty())
{
for(int i=0;i<qsize;i++)
{
int nowslice=tslice*pow(2,i);
if(i!=qsize-1)//当前不是最后一个
{
while(!ready[i].empty())
{
if(!v.empty()&&time>=(*v.begin()).arrive)//有新进程到达，加入就绪队列，转到第一队列
{
ready[0].push(*v.begin());
v.erase(v.begin());
i=0;nowslice=tslice*pow(2,i);
continue;
}
if(!v.empty()&&((time+nowslice>(*v.begin()).arrive&&ready[i].front().finish+nowslice<ready[i].front().run)
||(time+ready[i].front().run-ready[i].front().finish>(*v.begin()).arrive&&ready[i].front().finish+nowslice>=ready[i].front().run)))//时间片未用完，就有新进程到达
{
//cout<<"****time:"<<time<<" (*v.begin()).arrive:"<<(*v.begin()).arrive<<" nowslice:"<<nowslice<<" "<<ready[i].front().run-ready[i].front().finish<<endl;
ready[i].front().finish+=(*v.begin()).arrive-time;
ready[i].push(ready[i].front());
ready[i].pop();
//cout<<"ready[i].front().finish:"<<ready[i].front().finish<<" time:"<<time<<" i:"<<i<<endl;
cout<<"->p"<<ready[i].front().id<<"("<<(*v.begin()).arrive-time<<")"<<endl;
time=(*v.begin()).arrive;
ready[0].push(*v.begin());
v.erase(v.begin());
i=0;nowslice=tslice*pow(2,i);
continue;
}
else //整个时间片都没有新进程
{
if(ready[i].front().finish+nowslice<ready[i].front().run)//时间片用完没运行完,加入下一队列队尾
{
ready[i].front().finish+=nowslice;
ready[i+1].push(ready[i].front());
cout<<"->p"<<ready[i].front().id<<"("<<nowslice<<")"<<endl;
ready[i].pop();
time+=nowslice;
}
else//该进程结束
{
time+=ready[i].front().run-ready[i].front().finish;
cout<<"->p"<<ready[i].front().id<<"("<<ready[i].front().run-ready[i].front().finish<<")"<<endl;
ready[i].front().finish=time-1;
ready[i].front().turn=ready[i].front().finish-ready[i].front().arrive+1;
ready[i].front().wturn=(double)ready[i].front().turn/ready[i].front().run;
//从就绪队列中移除
ans.push_back(ready[i].front());
ready[i].pop();
}
}
}
}
else //按照RR算法调度
{
while(!ready[i].empty())
{
if(!v.empty()&&time>=(*v.begin()).arrive)//有新进程到达，加入就绪队列，转到第一队列
{
ready[0].push(*v.begin());
v.erase(v.begin());
i=-1;
break;
}
if(!v.empty()&&((time+nowslice>(*v.begin()).arrive&&ready[i].front().finish+nowslice<ready[i].front().run)
||(time+ready[i].front().run-ready[i].front().finish>(*v.begin()).arrive&&ready[i].front().finish+nowslice>=ready[i].front().run)))//时间片未用完，就有新进程到达
{
//cout<<"****time:"<<time<<" (*v.begin()).arrive:"<<(*v.begin()).arrive<<" nowslice:"<<nowslice<<" "<<ready[i].front().run-ready[i].front().finish<<endl;
ready[i].front().finish+=(*v.begin()).arrive-time;
ready[i].push(ready[i].front());
ready[i].pop();
//cout<<"ready[i].front().finish:"<<ready[i].front().finish<<" time:"<<time<<" i:"<<i<<endl;
cout<<"->p"<<ready[i].front().id<<"("<<(*v.begin()).arrive-time<<")"<<endl;
time=(*v.begin()).arrive;
ready[0].push(*v.begin());
v.erase(v.begin());
i=-1;
break;
}
else //整个时间片都没有新进程
{
if(ready[i].front().finish+nowslice<ready[i].front().run)//时间片用完没运行完,加入下一队列队尾
{
ready[i].front().finish+=nowslice;
ready[i].push(ready[i].front());
cout<<"->p"<<ready[i].front().id<<"("<<nowslice<<")"<<endl;
ready[i].pop();
time+=nowslice;
}
else//该进程结束
{
time+=ready[i].front().run-ready[i].front().finish;
cout<<"->p"<<ready[i].front().id<<"("<<ready[i].front().run-ready[i].front().finish<<")"<<endl;
ready[i].front().finish=time-1;
ready[i].front().turn=ready[i].front().finish-ready[i].front().arrive+1;
ready[i].front().wturn=(double)ready[i].front().turn/ready[i].front().run;
//从就绪队列中移除
ans.push_back(ready[i].front());
ready[i].pop();
}
}
}
}
}
}
v=ans;
sort(v.begin(),v.end(),cmp);
}
//输出
void print()
{
int sumturn=0;
double sumwturn=0;
cout<<endl<<"--测试结果--"<<endl;
cout<<" 进程编号 到达时间 运行时间 完成时间 周转时间 带权周转时间"<<endl;
for(auto i=v.begin();i!=v.end();i++)
{
sumturn+=(*i).turn;
sumwturn+=(*i).wturn;
printf("%6d%10d%10d%10d%10d%13.2lf\n",(*i).id,(*i).arrive,(*i).run,(*i).finish,(*i).turn,(*i).wturn);
}
printf("平均周转时间:%.2lf\n",(double)sumturn/v.size());
printf("平均带权周转时间:%.2lf\n",sumwturn/v.size());
}
signed main()
{
while(1)
{
cout<<endl<<"******菜单******"<<endl;
cout<<"1.随机样例测试"<<endl;
cout<<"2.输入样例测试"<<endl;
cout<<"0.结束测试"<<endl;
cout<<"请输入编号:";
int test;cin>>test;
if(!test)break;
else if(test!=1&&test!=2){cout<<"输入错误"<<endl;continue;}
int tslice=1;
init(test,tslice);
MFQ(tslice);
print();
v.clear();
}
}
- 系统测试
| 序号 | 条件 | 预期结果 | 测试结果 | 测试过程 |
| ① | qsize=7;num=20 | finish=469 | OK | 图5-1 |
| ② | qsize=10;num=6 | finish=24 | OK | 图5-2 |
| ③ | qsize=7;num=30 | finish=770 | OK | 图5-3 |
| ④ | qsize=10;num=13 | finish=270 | OK | 图5-4 |
| ⑤ | qsize=7;num=29 | finish=719 | OK | 图5-5 |
| ⑥ | qsize=7;num=14 | finish=157 | OK | 图5-6 |
| ⑦ | qsize=7;num=3 | finish=111 | OK | 图5-7 |
图5-1
图5-2
图5-3
图5-4
图5-5
图5-6
图5-7
总结
在本次的课题实践中，多级反馈队列调度算法是一种综合性特别强的算法，它不必事先知道各进程所需的执行时间，而且还可以满足各种类型进程的需要。它是目前被公认的种较好的进程调度算法。
在编写程序之前我先模拟了一下多级反馈队列调度算法的运行过程，并选择使用结构体来存储进程信息，使用STL保存进程串和各级就绪队列。由于此算法还运用到了先来先服务算法和时间片轮转算法，我一时间无法把握程序的切入口，我参考了网络上的流程，绘制了自己的流程图。但是我发现网上的图和内容都有些错误或者缺漏或是和我最初的想法不是很吻合，特别是在有新进程到来发生抢占的时候。为了不让网络上的内容影响我最初的想法，我将程序段中的框架编辑好后，主要操作的部分按照自己绘制的图进行模拟。好在大学前两年学习算法过程中提高的代码能力，让我在实现起这个算法时并没有很困难。虽然中间运行过程中发生了运行无法结束的情况，后来在我一步步调试后发现是因为没有对queue判空就对其的front进行取值操作，if的分类讨论不够仔细。在测试过程中我还发现计算出的进程结束时间竟是负数，后来发现是因为我设置的保存进程信息的vector是全局变量，每次计算完我忘记clear了。最开始我的输出只设置了测试结果输出进程信息，后来觉得有必要把进程调度过程的运行过程也一起输出，每次进程几运行了几个时间单位，这样有利于用户测试和理解。
。。。。。。
参考二
背景分析
多级反馈队列调度算法既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。（对比一下FCFS与高响应比优先调度算法的缺陷）。该算法为操作系统的核心功能，通过模拟该功能的实现，了解操作系统特性。
系统设计
- 实验目的：分析操作系统的核心功能模块，理解相关功能模块实现的数据结构和算法，并加以实现， 加深对操作系统原理和实现过程的理解。
- 实验环境：
操作系统：windows 10 家庭版
Cpu: i5-8300H
Gpu: gtx 1060 6g
内存:8g
Java jdk:
编译器: Intellij IDEA 2022.2.2
详细设计
- 实验内容：
多级反馈队列调度的模拟：
本算法设置了三个优先级从高到低的队列，时间片长度分别为：
队列一：2
队列二：4
队列三：8
- 实现思路：
3.1 采用自定义类Progress实例化进程对象，组成进程数组；
3.2 初始化三个优先级从高到低（时间片长：2、4、8）的队列；
3.3 按照：
3.3.1 首次加入的进程入最高优先级队列尾等待；
3.3.2 某队列内时间片完而进程还没结束就立即调入次级优先级队列尾等待继续运行；
3.3.3 只要有进程进入高优先级队列内，便对低优先级队列中的进程进行抢占式运行；
的思想每一秒对每个队列内的进程具有的进程标识符、到达时间、运行时间、仍需运行时间（方便显示）等属性进行更新和输出，以此模拟实际操作系统的调度状态。
- 主要的数据结构
/*三个队列*/
private static Queue<Progress> firstQueue = new LinkedList<>();
private static Queue<Progress> secondQueue = new LinkedList<>();
private static Queue<Progress> thirdQueue = new LinkedList<>();
/**
* 内部进程类：模拟进程
*/
private static class Progress implements Comparable<Progress> {
String id; //进程标识符
int reachTime; //到达时间
int cpuTime; //运行时间
int needTime; //仍需时间
char state; //进程状态
/*重写比较器*/
@Override
public int compareTo( Progress b ) {
//按reachTime从小到大排序
return Float.compare(reachTime, b.reachTime);
}
}
/*进程数组*/
Progress[] pro = new Progress[proNum];
- 流程图
编码
package com.algorithm.multiStageFeedback;
import java.util.*;
/**
* @Class MSFQS
* @Description 多级反馈队列调度算法
* @Author Naren
* @Date 2020/5/30 10:46
* @Version 1.0
*/
public class MSFQS {
/*三个队列*/
private static Queue<Progress> firstQueue = new LinkedList<>();
private static Queue<Progress> secondQueue = new LinkedList<>();
private static Queue<Progress> thirdQueue = new LinkedList<>();
private static int firstTime; //第一队列cpu时间片
private static int secondTime; //第二队列cpu时间片
private static int thirdTime; //第三队列cpu时间片
private static int proNum; //进程数量
private static Scanner sc = new Scanner(System.in);
/**
* 内部进程类：模拟进程
*/
private static class Progress implements Comparable<Progress> {
String id; //进程标识符
int reachTime; //到达时间
int cpuTime; //运行时间
int needTime; //仍需时间
char state; //进程状态
/*重排输出格式*/
@Override
public String toString() {
System.out.println();
return String.format("进程%s: %10d %7d %8d %7c\n", id, reachTime, cpuTime, needTime, state);
}
/*重写比较器*/
@Override
public int compareTo( Progress b ) {
//按reachTime从小到大排序
return Float.compare(reachTime, b.reachTime);
}
}
/**
* 进程调度算法：Multi-stage feedback queue scheduling algorithm
*/
private static void progressScheduling(Progress[] pro){
int firstCpu = firstTime;
int secondCpu = secondTime;
int thirdCpu = thirdTime;
int currentTime = 0;
int num = 0;
//System.out.println(Arrays.toString(pro));
/*当有进程未运行时或进程队列不为空时，以每1时间片为单位*/
while(num < proNum || !firstQueue.isEmpty() || !secondQueue.isEmpty() || !thirdQueue.isEmpty()){
/*当前时刻有进程到达，则添加入第一队列*/
while(num < proNum && pro[num].reachTime == currentTime)
firstQueue.offer(pro[num++]);
//打印上一秒各队列进程状态
viewMenu(currentTime);
/*当前为队列1在运行进程*/
if(!firstQueue.isEmpty()){
if (secondQueue.peek() != null) secondQueue.peek().state = 'R';
if (thirdQueue.peek() != null) thirdQueue.peek().state = 'R';
//仍需时间：-1
firstQueue.peek().needTime -= 1;
//CPU剩余时间片：-1
firstTime -= 1;
//更新当前时间：+1
currentTime++;
//进程正在运行，状态：E.
if(firstQueue.peek().needTime > 0){
firstQueue.peek().state = 'E';
//当前队列CPU时间片用完而进程仍未运行完时，进程出队，入次优先级队尾
if(firstTime == 0) {
firstQueue.peek().state = 'R';
secondQueue.offer(firstQueue.poll());
firstTime = firstCpu;
}
}
//进程运行完毕，状态：F，记录完成时刻并出队
else if(firstQueue.peek().needTime == 0){
firstQueue.peek().state = 'F';
System.out.printf("\n当前时刻：%d,此进程运行结束：\n",currentTime);
System.out.println(firstQueue.peek());
Objects.requireNonNull(firstQueue.poll());
firstTime = firstCpu;
}
}
/*当前为队列2在运行进程*/
else if(!secondQueue.isEmpty()){
if (thirdQueue.peek() != null) thirdQueue.peek().state = 'R';
//仍需时间：-1
secondQueue.peek().needTime -= 1;
//CPU剩余时间片：-1
secondTime -= 1;
//更新当前时间：+1
currentTime++;
//进程运行完毕，状态：F，记录完成时刻并出队
if(secondQueue.peek().needTime == 0){
secondTime = secondCpu;
secondQueue.peek().state = 'F';
System.out.printf("\n当前时刻：%d,此进程运行结束：\n",currentTime);
System.out.println(secondQueue.peek());
Objects.requireNonNull(secondQueue.poll());
}
//进程正在运行，状态：E.
else if(secondQueue.peek().needTime > 0){
secondQueue.peek().state = 'E';
//当前队列CPU时间片用完而进程仍未运行完时，进程出队，入次优先级队尾
if(secondTime == 0) {
secondQueue.peek().state = 'R';
thirdQueue.offer(secondQueue.poll());
secondTime = secondCpu;
}
}
}
/*当前为队列3在运行进程*/
else if(!thirdQueue.isEmpty()){
//仍需时间：-1
thirdQueue.peek().needTime -= 1;
//CPU剩余时间片：-1
thirdTime -= 1;
//更新当前时间：+1
currentTime++;
//进程正在运行，状态：R.
if(thirdQueue.peek().needTime > 0){
thirdQueue.peek().state = 'E';
//当前队列CPU时间片用完而进程仍未运行完时，进程出队，入次优先级队尾
if(thirdTime == 0) {
thirdQueue.peek().state = 'R';
thirdQueue.offer(thirdQueue.poll());
thirdTime = thirdCpu;
}
}
//进程运行完毕，状态：F，记录完成时刻并出队
else{
firstTime = firstCpu;
thirdQueue.peek().state = 'F';
System.out.printf("\n当前时刻：%d,此进程运行结束：\n",currentTime);
System.out.println(thirdQueue.peek());
Objects.requireNonNull(thirdQueue.poll());
}
}
}
}
/**
* 输入面板：获取到进程数组
*/
private static Progress[] operator(){
System.out.println("-----------------朱哲琛+张星宇+段雨辰-----------------\n");
System.out.println("欢迎进入多级队列反馈调度模拟系统，队列个数：3。\n\n");
System.out.println("请按队列优先级从高到低的顺序输入各个队列的时间片长度：");
firstTime = sc.nextInt();
secondTime = sc.nextInt();
thirdTime = sc.nextInt();
System.out.print( "请输入进程数:" );
proNum = sc.nextInt();
/*获取到进程数组*/
Progress[] pro = new Progress[proNum];
System.out.println( "请依次输入进程标识符,进程到达时间,进程运行时间:" );
for( int i = 0; i < proNum; i++ ) {
pro[i] = new Progress();
pro[i].id = sc.next();
pro[i].reachTime = sc.nextInt();
pro[i].cpuTime = sc.nextInt();
pro[i].needTime = pro[i].cpuTime;
pro[i].state = 'R';
}
//对进程按照compareTo()的要求按照到达时间排序
Arrays.sort(pro);
return pro;
}
/**
* 输出面板：实时输出运行结果
*/
private static void viewMenu(int currentTime){
System.out.printf("\n当前时刻：%d\n",currentTime);
System.out.println("---------------------------------------------");
System.out.println(" 到达时间 运行时间 剩余时间 状态");
if(firstQueue.isEmpty()) System.out.println("队列一：空");
else System.out.println("队列一：\n"+ firstQueue.toString()
.replace("[", "").replace("]", "")
.replace(", ", ""));
if(secondQueue.isEmpty()) System.out.println("队列二：空");
else System.out.println("队列二：\n"+ secondQueue.toString()
.replace("[", "").replace("]", "")
.replace(", ", ""));
if(thirdQueue.isEmpty()) System.out.println("队列三：空");
else System.out.println("队列三：\n"+ thirdQueue.toString()
.replace("[", "").replace("]", "")
.replace(", ", ""));
System.out.println("=============================================");
}
/**
* main()
*/
public static void main(String[] args) {
progressScheduling(operator());
}
}
}
测试
总结
多级反馈调度算法非常神奇，关键在于这三点：
- 首次加入的进程入最高优先级队列尾等待；
- 某队列内时间片完而进程还没结束就立即调入次级优先级队列尾等待继续运行；
- 只要有进程进入高优先级队列内，便对低优先级队列中的进程进行抢占式 运行；
3.1 多级反馈队列调度算法的特点是适合大中小进程同时到达时的情况，对于大进程多的情况，其性能与资源的使用远优于短作业优先、先来先服务等算法。并且对于时间片完而未结束的进程、会在次优先级队列中为其提供倍增的时间等待继续运行。
3.2运行的结果中会使得到达时间晚的进程可能也会先运行结束。它对于各个进程的统筹调度安排非常合理，使得每个进程都有机会执行。我模拟的是三级反馈调度，在此过程中其实可以将其拓展为更多级，只需要新建一个自定义队列类，最后按照用户意愿的个数初始化队列数组即可。