通常在使用多级队列调度算法时，进程进入系统时被永久地分配到某个队列。例如，如果前台和后台进程分别具有单独队列，那么进程并不从一个队列移到另一个队列，这是因为进程不会改变前台或后台的性质。这种设置的优点是调度开销低，缺点是不够灵活。
相反，多级反馈队列(multievel feedback queue)调度算法允许进程在队列之间迁移。这种想法是，根据不同CPU执行的特点来区分进程。如果进程使用过多的CPU时间，那么它会被移到更低的优先级队列。这种方案将I/O密集型和交互进程放在更高优先级队列上。 此外，在较低优先级队列中等待过长的进程会被移到更高优先级队列。这种形式的优化可阻止饥饿的发生。
多级反馈队列
例如，一个多级反馈队列的调度程序有三个队列，从0到2(如上图)。调度程序首先执行队列0内的所有进程。只有当队列0为空时，它才能执行队列1内的进程。类似地，只有队列0和1都为空时，队列2的进程才能执行。到达队列1的进程会抢占队列2的进程。同样，到达队列0的进程会抢占队列1的进程。
每个进程在进入就绪队列后，就被添加到队列 0 内。队列 0 内的每个进程都有 8ms 的时间片。如果一个进程不能在这一时间片内完成，那么它就被移到队列1的尾部。如果队列0为空，队列 1 头部的进程会得到一个16ms 的时间片。如果它不能完成，那么将被抢占，并添加到队列2。只有当队列 0 和 1 为空时，队列 2 内的进程才可根据FCFS来运行。这种调度算法将给那些 CPU 执行不超过 8ms 的进程最高优先级。这类进程可以很快得到 CPU，完成 CPU 执行，并且处理下个 I/O 执行。
所需超过 8ms 但不超过 24ms 的进程也会很快得以服务，但是它们的优先级要低一点。长进程会自动沉入队列2，队列0和1不用的CPU周期按 FCFS 顺序来服务。
算法思想: 对其他调度算法的折中权衡。
算法规则: 
a.设置多级就绪队列，各级队列优先级从高到低，时间片从小到大。
b. 新进程到达时先进入第1级队列，按FCFS原则排队等待被分配时间片，若用完时间片进程还未结束，则进程进入下一级队列队尾。如果此时已经是在最下级的队列，则重新放回该队列队尾。
c. 只有第k级队列为空时，才会为k+1级队头的进程分配时间片
用于作业/进程调度： 用于进程调度
是否可抢占？ 抢占式算法
优缺点: 对各类型进程相对公平(FCFS的优点)；每个新到达的进程都可以很快就得到响应(RR优点)；短进程只用较少的时间就可完成(SPF优点)；不必实现估计进程的运行时间；可灵活地调整对各类进程的偏好程度，比如CPU密集型进程、I/O密集型进程(拓展：可以将因I/O而阻塞的进程重新放回原队列，这样I/O型进程就可以保持较高优先)
是否会导致饥饿: 会
通常，多级反馈队列调度程序可由下列参数来定义：
队列数量。
每个队列的调度算法。
用以确定何时升级到更高优先级队列的方法。
用以确定何时降级到更低优先级队列的方法。
用以确定进程在需要服务时将会进入哪个队列的方法。
多级反馈队列调度程序的定义使其成为最通用的CPU调度算法。通过配置，它能适应所设计的特定系统。但是，由于需要一些方法来选择参数以定义最佳的调度程序，所以它也是最复杂的算法。

多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。
多级反馈队列调度算法即能使高优先级的作业得到响应又能使短作业(进程)迅速完成。(对比一下FCFS与高优先响应比调度算法的缺陷)。
多级(假设为N级)反馈队列调度算法可以如下原理：
1、设有N个队列(Q1,Q2….QN)，其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，优先级Priority(Q1) > Priority(Q2) > … > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高(也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度)，依次类推其它的队列。
2、对于某个特定的队列来说，里面是遵循时间片轮转法。也就是说，位于队列Q2中有N个作业，它们的运行时间是通过Q2这个队列所设定的时间片来确定的(为了便于理解，我们也可以认为特定队列中的作业的优先级是按照FCFS来调度的)。
3、各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个问题)。
多级反馈队列调度算法描述：
1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业(抢占式)。
我们来看一下该算法是如何运作的：
假设系统中有3个反馈队列Q1,Q2,Q3，时间片分别为2，4，8。
现在有3个作业J1,J2,J3分别在时间 0 ，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。
1、时刻0 J1到达。于是进入到队列1 ， 运行1个时间片 ， 时间片还未到，此时J2到达。
2、时刻1 J2到达。 由于时间片仍然由J1掌控，于是等待。 J1在运行了1个时间片后，已经完成了在Q1中的2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给J2。
3、时刻2 J1进入Q2等待调度，J2获得CPU开始运行。
4、时刻3 J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。
5、时刻4 J2处理完成，由于J3，J1都在等待调度，但是J3所在的队列比J1所在的队列的优先级要高，于是J3被调度，J1继续在Q2等待。
6、时刻5 J3经过1个时间片，完成。
7、时刻6 由于Q1已经空闲，于是开始调度Q2中的作业，则J1得到处理器开始运行。
8、时刻7 J1再经过一个时间片，完成了任务。于是整个调度过程结束。
从上面的例子看，在多级反馈队列中，后进的作业不一定慢完成。

下面我们首先介绍，多级反馈队列调度算法 然后对前面介绍的各种调度算法进行比较  之后呢，我们简单讨论一下 在设计多处理器调度算法时所要考虑的几个问题  多级反馈队列调度算法 是  UNIX 的一个分支，BSD 5.3  版所采用的调度算法 它是在前面各种调度算法的基础之上  提出的一个综合的调度算法，是在考虑了各种  因素之后进行折中权衡的一个结果 下面我们介绍  一下多级反馈队列调度算法的基本思想 就绪队列设置成多个  其中第一级队列的优先级最高 依次从高到低，系统  给不同的就绪队列分配了长度不同的时间片  第一级队列优先级最高 但分配给它的时间片最小  随着队列优先级的不断降低 分配给队列的时间片就越大  比如说第一级队列分配给它一个单位的话 第二级队列就可以分配成两倍的时间片  那么第三级可以分配四倍的时间片，这就是 级别越低，时间片越大  在进行调度的时候 首先从优先级高的队列进行调度  如果第一级队列没有进程了  那么系统会从第二级队列进行调度，以此类推  每一个队列都是按照时间片轮转的方式进行调度  新创建的进程  就绪的时候呢都进入第一级队列 如果一个被调度上  CPU 的进程用完了时间片 而放弃了  CPU，那么它就进入下一集就绪队列 也就是说，它被降级了  那么如果一个被调度上 CPU 的进程  由于等待 I/O 而被阻塞，进入了等待队列  当等待的事件发生后，这个进程从等待队列  回到原来一级就绪队列。  那么这里头 我们可以根据不同的情况来设计不同的方案  以体现系统对这一类进程的 偏好程度，比如说  这个进程是回到原来一级就绪队列的队首呢  还是队尾？如果回到队首，说明系统对这类进程更加友好  另外，当这个进程再度被调度上 CPU 之后  是让它运行完剩余的时间片呢 还是重新给它分配一个完整的时间片让它去运行？  也体现了系统对这类进程的偏好程度 那么我们现在所看到的  多级反馈队列调度算法呢是一个非抢占式的 如果允许抢占呢  也就是说当有一个更高优先级的进程就绪的时候 可以抢占正在运行进程的  CPU 那么被抢占的进程呢  会回到原来一级就绪队列的末尾 当然也可以有不同的设计方案  比如说回到原来一级就绪队列的队首 当这个进程再度被调度上  CPU 时呢 可以运行完它刚才剩余的时间片  也可以重新给它一个完整的新的时间片让它运行  因此呢又派生出不同的设计方案 下面我们来看一下这张图  它反映了一个进程在 队列里头的一些迁移活动  当创建一个新的进程时 所有的进程都进入第一级队列  如果是 I/O 型的进程，那么它可能  被调度上 CPU 之后很短时间就去等待  I/O 当它从等待队列又回到就绪队列的时候  由于我们让它回到原来一级就绪队列，所以它呢优先级没有降低 被调度上 CPU 的机会很多。  但是对于 CPU 型的进程 它被调度上  CPU，用完了一个时间片之后 它就会回到下一级队列  那么如果每次都用完了它的时间片，它就会降级 可能一个  CPU 型的进程就慢慢降到了 优先级最低的这个队列里头，因此我们可以看到  通过这样一个调度算法 就可以慢慢地区分出来哪些进程是  CPU 型进程 哪些进程是 I/O 型进程，很显然  多级反馈队列调度算法对 I/O 型进程更偏好一点  对 CPU 型进程呢不太有利  但是呢它也做了一些弥补，比如说 优先级高的队列时间片短  而优先级低的队列时间片会很大 所以当低优先级的  CPU 型进程被调度上 CPU 之后，它可以运行更长的时间  那这里呢也是一种平衡的结果。  下面 我们对前面介绍的各种调度算法 做一下小结。  在占用 CPU 的方式上 先来先服务，短作业优先  最高响应比优先调度算法是非抢占式的调度策略 最短剩余时间优先  则是一个抢占式的调度策略，而时间片轮转 多级反馈队列调度算法  则是允许在时间片到的时候可以进行抢占 在追求调度算法指标上  我们来看一下短作业优先 最短剩余时间优先和最高响应比优先  这三个调度算法都可以带来比较高的吞吐量 而  时间片轮转调度算法 如果时间片很小，那么它的吞吐量就很低  先来先服务调度算法 还有多级反馈队列调度算法对吞吐量这个指标  并不强调，在响应时间方面 时间片轮转，短作业优先两个调度算法  对短的作业可以提供很快的响应时间 最短剩余时间优先  和最高响应比优先调度算法呢，也可以提供很好的响应时间 而对于先来先服务调度算法  当不同的进程 它们的时间有很大差别的时候，对于某些进程  它的响应时间会很慢，下面我们来看一下 调度算法本身所带来的开销  先来先服务和时间片轮转调度算法 因为实现比较简单，所以开销比较小  而其它四种调度算法它们的开销可能很大 比如说最高响应比优先调度算法  它要计算每一个进程的响应比 才能选择响应比最高的那个进程。  所以计算响应比需要花时间 多级反馈队列调度算法需要维护多个就绪队列，这也需要花时间  接着我们来看一下不同的调度算法 对进程的影响。  时间片轮转调度算法 公平地对待每一个进程。  最高响应比优先调度算法 则是在先就绪的进程和短进程之间做了一个很好的平衡  而来先来先服务调度算法 对长进程之后的短进程，或者是  I/O 型进程 是不利的。  那么最短作业优先 和最短剩余时间优先的调度算法对长进程不利  会导致长进程产生饥饿现象 多级反馈队列调度算法  对于 I/O 型进程是偏好的，也就是说对 I/O  型进程有利 而对 CPU 型进程不利 会导致 CPU  型进程产生饥饿 所以没有一种调度策略是完美的  也不可能有一种调度策略对各种类型的进程都能够照顾到  因此在设计调度策略的时候，我们应该  考虑综合性的因素，下面  我们简要介绍一下在设计多处理器调度算法时 需要考虑的几个问题  在设计多处理器调度算法时 我们不仅要决定选择哪一个进程执行  而且还要确定这个被选中的进程在哪一个 CPU  上执行 另外我们必须要考虑  进程在多个 CPU 之间迁移时所带来的高速缓存  TLB 失效的开销 如果一个进程  之前在 CPU1 上执行，后来又被调度到了 CPU2  上执行 那么高速缓存 TLB 失效就会增加  而如果这个进程每次都被指定到 同一个 CPU  上执行，那么就会减少各种 失效。  因此 应该尽可能地使进程总在同一个 CPU  上执行 另外  呢，我们还应该考虑到一个负载均衡的问题 因为有多个  CPU，那么不可能让某些 CPU  非常地忙碌 而其它 CPU 很空闲，所以  我们要通过调度使得 所有的 CPU  都保持忙碌，那么这就 是一个负载均衡的问题

多级队列调度算法

多级队列：该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。

多级队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。

题目描述：

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

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







进程
P1
P2
P3
P4
P5
P6
P7
P8
P9
P10




运行时间
16
11
14
13
15
21
18
10
7
14


已等待时间
6
5
4
3
2
1
2
3
4
5


程序功能

对于给定的数据使用多级队列调度算法进行分析计算周转时间。其中多级队列分为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, 

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

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

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