多级反馈队列

​ 多级反馈队列（Multi-level Feedback Queue， MLFQ），与上个世纪70年代提出，主要应用于时分共享系统。主要解决两方面问题：一个是优化周转时间，一个是要给用户很好的交互体验。MLFQ中有很多独立的队列，每个队列有不同的优先级，任何时刻，一个任务只能存在于一个队列中。先引出MLFQ的两个基本规则

• 规则1：如果A优先级 > B优先级，则运行 A
• 规则2：如果A优先级 = B优先级，则轮转执行A和B。

​ 还是引出一个问题，就是如果优先级都是不变的，这样不就相当于在计算机中出现了贵族阶级吗。但是如何改变优先级呢，由此引入以下几个规则来尝试调整优先级。

• 规则3：工作进入系统时，优先级最高
• 规则4a：工作用完整个时间片之后，降低优先级，到下一个队列
• 规则4b：如果工作在其时间片内主动释放CPU，优先级不变。

两个工作：A 是一个长时间运行的 CPU 密集型工作，B 是一个运行时间很短的交互型工作。A执行一段时间之后B到达，结果如左图所示。比如说系统既有CPU密集型任务，又有IO密集型任务。IO密集型会在时间片用完之后放弃CPU，维护优先级不变，如右图所示。

​ 上面看似很优秀的调度任务，其实还有问题，就是如果有太多的交互性任务，不断占用CPU，对于长工作则无法得到满足。我们可以尝试对优先级做一些改变。

如何提升优先级？

• 规则5：经过一段时间，就把系统中所有工作重新加入最高优先级队列。

​ 在最高优先级队列中，它会以轮转的方式，与其他高优先级工作分享 CPU，从而最终获得执行。如果一个 CPU 密集 型工作变成了交互型，当它优先级提升时，调度程序会正确对待它。假设这样一个场景，一个长工作与两个交互式工作竞争CPU，每50ms进行一次优先级提升。可以看到能很好的避免调度过程中的饥饿问题。

如何设置优先级提升间隔？

​ 假设这样一个问题场景，就是进程在每一个时间片结束的时候主动申请释放CPU，按照规则4，则会报纸CPU优先级，从而几乎垄断CPU时间。这个规则显然不对，因此修改为下面规则。可以发现对于两个任务来说都能比较公平的共享CPU资源。

• 规则4：一旦工作用完再某一层中的时间配额，不管是不是主动释放CPU资源，都会降低优先级。

​ 这里也有一个问题，就是如何设置队列大小呢，如何设置每一级时间片大小呢。也就是说如何更好的进行MLFQ性能调优，这里提出一个解决方案是，对于越高优先级队列，它的时间片越小，对于优先级越小的队列，它的时间片越大。如下图所示。

队列，它的时间片越小，对于优先级越小的队列，它的时间片越大。如下图所示。

多级队列调度算法

操作系统实验导航
实验一：银行家算法 https://blog.csdn.net/weixin_46291251/article/details/115384510
实验二：多级队列调度和多级反馈队列调度算法 https://blog.csdn.net/weixin_46291251/article/details/115530582
实验三：动态分区式内存管理 https://blog.csdn.net/weixin_46291251/article/details/115772341
实验四：Linux下多进程通信 https://blog.csdn.net/weixin_46291251/article/details/116274665
实验五：进程通信的三种方式 https://blog.csdn.net/weixin_46291251/article/details/116301250
实验六：Linux文件系统实验 https://blog.csdn.net/weixin_46291251/article/details/116423798
实验七：自制简单U盘引导程序 https://blog.csdn.net/weixin_46291251/article/details/116427629
实验八：磁盘调度算法 https://blog.csdn.net/weixin_46291251/article/details/116431907
实验九：请求分页系统中的置换算法 https://blog.csdn.net/weixin_46291251/article/details/116443021
学习笔记：操作系统复习笔记 https://blog.csdn.net/weixin_46291251/article/details/117086851

• 多级队列：该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
  多级队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。

题目描述：

• 设RQ分为RQ1和RQ2
• RQ1采用轮转法，时间片q=7.
• RQ1>RQ2
• RQ2采用短进程优先调度算法。
• 测试数据如下：

• 其中：RQ1: P1-P5,   RQ2: P6-P10　
  

程序功能

• 对于给定的数据使用多级队列调度算法进行分析计算周转时间。其中多级队列分为RQ1和RQ2 ，RQ1采用的是时间片长度为7的时间片轮转算法，RQ2采用的是短进程优先算法。并且RQ1的优先级高于RQ2（即只有在RQ1内所有程序运行结束，RQ2才能开始运行）

设计思路

• 时间片轮转：首先对RQ1按照等待时间长短排序，然后从头设置循环，只要队列不空就一直进行下去，每次取队头RQ1的下一个元素（RQ1仅用作标志，不存储数据）判断need是否小于等于时间片大小，小于等于则置为0后踢出队列进入finish队列，大于则将need减去时间片大小，然后将其移动至队尾。
• 短进程优先：开始前需要对RQ2按照剩余执行时间大小进行排序，与时间片轮转法类似，不同的是这里一旦开始执行就直接执行完毕，然后下一个进程上处理机运行。

数据结构

• 本程序每个进程用一个PCB表示，每个PCB内含有name（标识符）、need（当前仍然需要多长时间才能运行结束）、turn（周转时间（等于等待时间+运行时间））、next指针（指向等待队列的下一个进程）。两个队列的头节点分别为RQ1、RQ2还有一个结束队列Finish（运行结束后进程从原队列进入这里）

typedef struct tag_pcb {
    char name[8];
    int need = 0;//需要运行的时间
    int turn = 0;//周转时间=等待时间+运行时间
    struct tag_pcb* next = NULL;
}PCB;
PCB* RQ1=new PCB, * RQ2 = new PCB, * Finish = new PCB;

代码实现：

#include<iostream>
#include <fstream>
using namespace std;


typedef struct tag_pcb {
    char name[8];
    int need = 0;//需要运行的时间
    int turn = 0;//周转时间=等待时间+运行时间
    struct tag_pcb* next = NULL;
}PCB;
PCB* RQ1=new PCB, * RQ2 = new PCB, * Finish = new PCB;
const int TimePiece = 7;//时间片长度

void ReadFile(){

    ifstream In("RQ1.txt");
    PCB* Current = RQ1;

    while (!In.eof()) {
        PCB* Cur = new PCB;

        In >> Cur->name >> Cur->need>> Cur->turn;

        Current->next = Cur;
        Current = Current->next;
    }
    In.close();

    ifstream In1("RQ2.txt");
    PCB* Current1 = RQ2;

    while (!In1.eof()) {
        PCB* Cur1 = new PCB;

        In1 >> Cur1->name >> Cur1->need >> Cur1->turn;
        Current1->next = Cur1;
        Current1 = Current1->next;
    }
    In1.close();
}

void Q1_Insert(PCB a) { //时间片轮转算法队列的插入(插入尾部)

    PCB* Current = RQ1;
    while (Current->next != NULL)
        Current = Current->next;
    Current->next = new PCB;

    *Current->next = a;
    //Current->next = &a;

    Current->next->next = NULL;

}
void Q2_Insert(PCB b) { //短进程优先调度算法队列的插入

    
    PCB* Current = RQ2;
    while (Current->next != NULL)
        Current = Current->next;
    Current->next = new PCB;

    *Current->next = b;
    Current->next->next = NULL;
    
}
void Fin_Insert(PCB c) { //短进程优先调度算法队列的插入
    
    PCB* cc = new PCB;
    *cc = c;

    cc->next = Finish->next;
    Finish->next = cc;   
}
void Q2_sort(PCB *T) {

    PCB* X = new PCB;//用来保存排序后的链表
    PCB* p = new PCB;//用来保存当此最小值的前一位
    PCB* Current = T->next;
    PCB * PreCurrent = T;
    PCB* TailX = X;
    
    while (T->next != NULL) {
        int tem = 999999;

        Current = T->next;
        PreCurrent = T;
        while (Current != NULL) {
            if (Current->need < tem) {
                tem = Current->need;
                
                p = PreCurrent;
                //cout << "处理" << p->name << p->need << "\n";
            }
            Current = Current->next;
            PreCurrent = PreCurrent->next;
        }
     

        TailX->next = p->next;
        TailX = TailX->next;

        if (p->next->next != NULL)
            p->next = p->next->next;
        else
            p->next = NULL;      
    }
    *T = *X;
}

int main()
{
    ReadFile();

    int clock = 0; //时钟
    while (RQ1->next != NULL) {//表示RQ1还有元素
        int t = TimePiece;
        PCB* Current = RQ1->next;
        int fin = 0;

        if (Current->need <= t)
            t = Current->need, fin = 1;
           
        clock += t;//表示pi运行t

        //输出计算过程
        //cout << "\n" << Current->name << "_____" << Current->turn << "__+ ___" << clock << "__= ___" << Current->turn +clock << "\n";
       
        Current->need -= t;
  
        if (fin)
            Current->turn += clock, Fin_Insert(*Current);//运行结束    
        else
            Q1_Insert(*Current);//进入队尾等待运行

        if (Current->next == NULL)
            break;
        RQ1->next = Current->next;
    }


    clock = 0;//时钟要清空一次
    Q2_sort(RQ2);//先排序

    cout << "RQ2:__"; 
    for (PCB* Current2 = RQ2->next; Current2 != NULL; Current2 = Current2->next)
        cout << Current2->name << "--";

    while (RQ2->next != NULL) {//表示RQ2还有元素(到这一步默认RQ1已经为空)
        PCB* Current3 = RQ2->next;
        int t = Current3->need;

        clock += t;//表示pi运行t
        Current3->need -= t;//实质为清空
        Current3->turn += clock;

        Fin_Insert(*Current3);

        if (Current3->next == NULL)
            break;
        RQ2->next = Current3->next;
    }

    int SUM = 0;
    for (PCB* Current2 = Finish->next; Current2 != NULL; Current2 = Current2->next) {
        cout << "\n" << Current2->name <<"\t"<< Current2->turn ;
        SUM += Current2->turn;
    }

    cout << "\n总周转时间为：" << SUM << "\n";
}

• 多级队列调度测试结果：
  

附：

多级反馈队列调度算法如下原理：

• 1、设有N个队列（Q1,Q2…QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1) > Priority(Q2) > … > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。
• 2、对于优先级最低的队列来说，里面是遵循时间片轮转法。也就是说，位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾。
• 3、各个队列的时间片是一样的吗？
  不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个问题)。

上述程序在某一进程在一级队列运行一轮后没有运行完毕，若加入二级队列而不是加入原队列的尾部，则可以实现简单的多级反馈队列调度算法
两种算法的不同之处就在于：当一个RQ1中的进程在时间片结束之后是回到当前的队尾还是到RQ2队列之中。
在上述程序中也很容易实现：

		if (fin)
            Current->turn += clock, Fin_Insert(*Current);//运行结束    
        else
            Q1_Insert(*Current);//进入队尾等待运行

修改为：

		if (fin)
            Fin_Insert(*Current);//运行结束    
        else
            Q2_Insert(*Current);//进入二级队列等待运行
        Current->turn += clock, 

上述两种代码分别实现了上述两种功能，执行时只需选一种在相应位置即可。

• 多级反馈队列调度测试结果：

由分析上述数据容易发现：在该测试数据的情况下多级反馈队列调度算法是要优于多级队列调度的

实验一 多级反馈队列调度算法

一. 主要实现方法和代码介绍

​ 1.编写进程类,其只包含所需的运行时间和进程编号两个属性,还有一个运行方法,此方法就是将所需的运行时间属性减去.传入的运行时间.

​ 2.创建进程函数:创建maxp个进程,(应该不超过10,在此创建九个,即暂时不进行进程队列越界处理),其运行时间符合均值为0,方差为20的高斯分布,并取整取绝对之后所得到的值, (此处是为了全自动创建进程),进程号自己自增. 在创建进程时,使用mutex库将每一个queue 加锁和解锁,以实现互斥访问.

​ 3.运行函数. 主要的算法函数. 首先判断队列非空,即进入运行,一级队列非空时,优先运行第一级队列,一级队列空后,才检差后几级队列. 但是后几级队列每一次执行后,都重新检查一级队列是否非空.具体实现是:if(一级队列非空) { while(一级队列非空){ 运行}} ;而高级别不执行while. 其次,当一次执行没有执行完,则立即放入下一级队列,每次写入都加锁.

二. 程序流程图

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-B8AyJRjO-1647856457764)(C:\Users\51330\AppData\Roaming\Typora\typora-user-images\image-20211009101816266.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S14kJ5Lg-1647856457765)(C:\Users\51330\AppData\Roaming\Typora\typora-user-images\image-20211009101923526.png)]

三. 程序代码

#include <iostream>
#include <queue>
//随机数
#include <random>
#include <chrono>
#include <cmath>
#include <thread>
#include <mutex>

#define T 10
#define Qsize 10
using namespace std;
mutex mym1;
mutex mym2;
mutex mym3;
mutex mym4;
int ALLP = 0;
int CPUTIME = 0;
int information = 0;
class Process
{
public:
    int RUNTIME;
    int PNUM;
    void run(int runt);
};
void Process::run(int rt)
{
    cout << CPUTIME << ":" << ends;
    if (rt >= RUNTIME)
    {
        RUNTIME = 0;
        cout << "进程" << PNUM << "已运行完." << endl;
        CPUTIME += rt;
    }
    else
    {
        RUNTIME -= rt;
        cout << "进程" << PNUM << "已运行" << rt << "时,还需" << RUNTIME << "时即可运行完." << endl;
        CPUTIME += rt;
    }
}
queue<Process> q1, q2, q3, q4;
void createProcess(int maxp)
{
    // 从epoch（1970年1月1日00:00:00 UTC）开始经过的纳秒数，unsigned类型会截断这个值
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine generator(seed);
    // 第一个参数为高斯分布的平均值，第二个参数为标准差
    std::normal_distribution<double> distribution(0.0, 20.0);
    //   for (int i = 0; i < 10; ++i)
    //     std::cout << distribution(generator) << std::endl;
    for (int i = 1; i <= maxp; i++)
    {
        Process c1;
        c1.RUNTIME = std::abs((int)distribution(generator));
        c1.PNUM = ALLP++;
        mym1.lock();
        q1.push(c1);
        mym1.unlock();
        cout << "已创建" << ALLP - 1 << "号进程,需要" << c1.RUNTIME << "时来完成." << endl;
    }
    information++;
}
void running()
{
    int performed = 0;
    while (true)
    {
        // if (!q1.empty() || !q2.empty() || !q3.empty() || !q4.empty())
        {
            if (!q1.empty())
            {
                while (!q1.empty())
                {
                    Process c1 = q1.front();
                    mym1.lock(); // lock
                    q1.pop();
                    mym1.unlock();
                    c1.run(T);
                    if (c1.RUNTIME != 0)
                    {
                        if (q2.size() < Qsize)
                        {
                            mym2.lock(); //加锁
                            q2.push(c1);
                            mym2.unlock();
                        }
                        else
                        {
                            暂时没管队列已满时的卡死状态
                        }
                    }
                }
            }
            else if (!q2.empty())
            {
                Process c2 = q2.front();
                mym2.lock();
                q2.pop();
                mym2.unlock();
                c2.run(2 * T);
                if (c2.RUNTIME != 0)
                {
                    if (q3.size() < Qsize)
                    {
                        mym3.lock();
                        q3.push(c2);
                        mym3.unlock();
                    }
                    else
                    {
                        暂时没管队列已满时的卡死状态
                    }
                }
                if (!performed)
                {
                    createProcess(9);
                    performed = 1;
                }
            }
            else if (!q3.empty())
            {
                Process c3 = q3.front();
                mym3.lock();
                q3.pop();
                mym3.unlock();
                c3.run(4 * T);
                if (c3.RUNTIME != 0)
                {
                    if (q4.size() < Qsize)
                    {
                        mym4.lock();
                        q4.push(c3);
                        mym4.unlock();
                    }
                    else
                    {
                        暂时没管队列已满时的卡死状态
                    }
                }
            }
            else if (!q4.empty())
            {
                Process c4 = q4.front();
                mym4.lock();
                q4.pop();
                mym4.unlock();
                c4.run(8 * T);
                if (c4.RUNTIME != 0)
                {
                    if (q4.size() < Qsize)
                    {
                        mym4.lock();
                        q4.push(c4);
                        mym4.unlock();
                    }
                    else
                    {
                        暂时没管队列已满时的卡死状态
                    }
                }
            }
            else
            {
                cout << CPUTIME << ":当前时刻所有进程已运行完." << endl;
                while (!q1.empty() || !q2.empty() || !q3.empty() || !q4.empty())
                {
                    break;
                }
                if (information == 2)
                    break;
            }           // }
        }
    }
}
int main()
{
    // thread t1(createProcess, 9);
    createProcess(9);
    thread t2(running);
    // t1.join();
    t2.join();
    return 0;
}

四. 运行结果

五.结果分析

​ 观察上方运行结果即可得到:

1. 先进行创建进程,创建了九个进程. 而后当一级队列运行完成后,再次创建了九个进程,后面重新从一级队列开始运行. 运行完后,才运行下级队列的1~7号进程.

   故可以看出,一级队列最高优先级实现成功.

2. 代码缺陷分析:

   • 创建进程和运行不能同步进行. 虽然尝试实现创建两个线程,让运行函数和创建进程的函数分开运行,通过对共享变量(共享内存通信)的修改通知不同的进程运行,但总是进入死循环,尝试失败
   • 没有按照老师上课讲得PCB的大部分信息来创建进程, 而是偷懒只考虑自己的模拟需求,只有运行时间和进程号两个属性.

. 运行完后,才运行下级队列的1~7号进程.

故可以看出,一级队列最高优先级实现成功.

2. 代码缺陷分析:

   • 创建进程和运行不能同步进行. 虽然尝试实现创建两个线程,让运行函数和创建进程的函数分开运行,通过对共享变量(共享内存通信)的修改通知不同的进程运行,但总是进入死循环,尝试失败
   • 没有按照老师上课讲得PCB的大部分信息来创建进程, 而是偷懒只考虑自己的模拟需求,只有运行时间和进程号两个属性.