多级队列：该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
 多级队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。
 
多级反馈队列：1）设置多个就绪队列。在系统中设置多个就绪队列，并未每个队列赋予不同的优先级。第一个队列的优先级最高，第二个次之，其余的优先级逐个降低。该算法为不同的队列中的进程所赋予的执行时间片的大小也各不相同，在优先级愈高的队列中，其时间片就愈小。
 2）每个队列都采用FCFS算法。3）按队列优先级调度。

多级队列调度算法
 
多级队列：该算法将系统中的进程就绪队列从一个拆分为若干个，将不同类型或性质的进程固定分配在不同的就绪队列，不同的就绪队列采用不同的调度算法，一个就绪队列中的进程可以设置不同的优先级，不同的就绪队列本身也可以设置不同的优先级。
 多级队列调度算法由于设置多个就绪队列，因此对每个就绪队列就可以实施不同的调度算法，因此，系统针对不同用户进程的需求，很容易提供多种调度策略。
 
题目描述：
 
设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, 
 
上述两种代码分别实现了上述两种功能，执行时只需选一种在相应位置即可。
 
多级反馈队列调度测试结果：
 
由分析上述数据容易发现：在该测试数据的情况下多级反馈队列调度算法是要优于多级队列调度的

多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。
 
多级(假设为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得到处理器开始运行。 J1再经过一个时间片，完成了任务。于是整个调度过程结束。
 
从上面的例子看，在多级反馈队列中，后进的作业不一定慢完成。

 
目录
 
1.题目
2.程序设计
3.测试结果
4.源码

 
1.题目
 
多级队列调度算法
 设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
 实现描述：
 
 typedef  struct  tag_pcb
    {
char name[8];
          int need;//须运行的时间
          int turn;//周转时间(周转时间=完成时间-到达时间)
          struct  tag_pcb  *next;
     }PCB(进程控制块);
PCB  * RQ1,*RQ2，*Finish;
int clock=0;  //时钟
main()
{
输入RQ1；
          输入RQ2；（最好从文件读入）
          while（ＲＱ１！＝ＮＵＬＬ）
       ｛
从RQ1中选取一进程Pi准备运行；
               计算其运行的时间t;
               clock+=t;  //表示Pi运行t;
               if (Pi完成）  计算其turn;
               否则   Pi加入到队尾；
          }
          while（ＲＱ2!＝ＮＵＬＬ）
          {
从RQ2中选取一进程Pi准备运行；
               clock+=Pi.need;
               计算Pi的turn;
          }
          输出进程的周转时间；
}
 
2.程序设计
 
首先在头文件里面包含list.h，使得程序可以使用链表的各个操作函数。然后就是设立一个进程信息结构体，其中包括进程名字、须运行时间、开始运行时间等进程信息，接着就是利用list RQ1和list RQ2声明两个就绪队列RQ1和RQ2，并设置系统时间和轮转法的时间片。接着就是RQ1和RQ2的初始化，由于两者基本一样，所以只介绍RQ1的：首先初始化已知的进程信息，然后利用for循环以及RQ1.push_back(project1)依次将所有属于该队列的进程信息输入至链表，并cout部分进程信息。
然后就是轮转法的定义：首先调用函数CreateRQ1()创建队列，初始化时钟之后当RQ1不空时，PCB* p=&RQ1.front();//指向第一个元素，先输出进程部分信息，当进程执行时间大于时间片时，调整系统时间、程序还需时间、程序已执行时间以及执行次数，而执行次数主要目的是用来设立进程最初开始执行时间(p->count)++;if (p->count == 1){p->first_starttime = p->starttime;}，然后再输出执行次数以及已执行时间，由于该进程还未执行完成，所以利用RQ1.push_back(RQ1.front());RQ1.pop_front()首先将其插入至队列尾部，然后再删除头结点；若进程所需时间小与等于时间片，则进行各个进程信息的更新之后直接利用RQ1.pop_front();//删除头结点，至此，轮转法算法结束。
接下来就是短进程优先算法：同样的先创建队列，当！RQ2.empty()时，std::
 list::iterator q=RQ2.begin();//迭代器iterator提供一种访问对象容器中的元素，返回第一个元素的迭代器，然后利用循环for (std::list::iterator p = RQ2.begin();p != RQ2.end();++p) 找到最短预计执行时间的进程，找到之后再对进程的部分信息更新，然后由于该进程已执行完，所以直接利用RQ2.erase(q)从队列删除结点q，短进程优先算法结束。
程序最后在main函数里面直接依次调用RR();//轮转法、SPPSM();//短进程优先调度法即可，整个程序结束。
 
3.测试结果
 
 
4.源码
 
/*操作系统实验一  多级队列调度算法　 
设RQ(就绪队列)分为Q1 > RQ2，RQ2采用短进程优先调度算法。
测试数据如下：RQRQ1和RQ2，RQ1采用轮转法，时间q = 7.
R1: 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 */

#include<iostream>
#include<list>//包含双向链表的各个操作函数
using namespace std;

struct PCB//进程信息
{
	int name;           //进程名字
	int needtime;       //须运行时间
	int starttime;      //开始运行时间
	int endtime;        //结束时间
	int first_starttime;//第一次开始运行时间(用来计算周转时间)
	int runtime;        //已经运行时间
	int waittime;       //已等待时间
	int count;          //运行次数
};

list<PCB> RQ1;
list<PCB> RQ2;
int clock;       //系统时间
int capacity = 7;//时间片

void CreateRQ1()//创建队列RQ1(以队列为结构创建)
{
	int name1[5] = { 1,2,3,4,5 };
	int needtime1[5] = { 16,11,14,13,15 };
	int waittime1[5] = { 6,5,4,3,2 };

	for (int i = 0;i < 5;i++)
	{
		PCB project1;
		project1.name = name1[i];
		project1.waittime = waittime1[i];
		project1.needtime = needtime1[i];
		project1.runtime = 0;
		project1.count = 0;
		project1.endtime = 0;
		project1.first_starttime = 0;
		project1.starttime = 0;
		RQ1.push_back(project1);//放进链表
		cout << "创建进程 : p"<<project1.name<<"\t"<<"执行所需时间 : "<<project1.needtime<<endl;
	}
}

void CreateRQ2()//创建队列RQ2(以链表为结构创建)
{
	int name2[5] = { 6,7,8,9,10 };
	int needtime2[5] = { 21,18,10,7,14 };
	int waittime2[5] = { 1,2,3,4,5 };

	for (int i = 0;i < 5;i++)
	{
		PCB project2;
		project2.name = name2[i];
		project2.waittime = waittime2[i];
		project2.needtime = needtime2[i];
		project2.runtime = 0;
		project2.count = 0;
		project2.endtime = 0;
		project2.first_starttime = 0;
		project2.starttime = 0;
		RQ2.push_back(project2);
		cout << "创建进程 : p" << project2.name << "\t" << "执行所需时间 : " << project2.needtime << endl;
	}
}

void RR()//轮转法(round-robin)
{
	cout << "***********轮转法***********"<<endl;
	CreateRQ1();
	clock = 0;
	while (!RQ1.empty())
	{
		PCB* p = &RQ1.front();//指向第一个元素
		p->starttime = clock;
		cout << "进程 : p" << p->name << "\t" << "执行还需时间 : "
			<< p->needtime << "\t" << "开始执行时间 : " << p->starttime <<"\t";
		if (p->needtime > capacity)
		{
			clock += capacity;
			p->needtime -= capacity;
			p->runtime += capacity;
			(p->count)++;
			if (p->count == 1)
			{
				p->first_starttime = p->starttime;
			}
			cout << "执行次数 ：" << p->count << "\t" << "已执行时间 : " << p->runtime << endl;
			RQ1.push_back(RQ1.front());//首先插入头结点到尾部
			RQ1.pop_front();           //然后把头结点删除
		}
		else
		{
			p->runtime += p->needtime;
			clock += p->needtime;
			p->endtime = clock;
			(p->count)++;
			cout << "执行次数 : " << p->count << "\t" << "已执行时间 : " << p->runtime
				<< "\t" << "结束时间 : " << p->endtime <<"\t"<< "周转时间 : " 
				<< p->endtime - p->first_starttime <<"\t"<< "执行完毕" <<endl;
			p->needtime = 0;
			RQ1.pop_front();//删除头结点
		}
	}
	cout << endl;
}

void SPPSM()//短进程优先调度法(short process priority scheduling method)
{
	cout << "*******短进程优先调度法*******"<<endl;
	CreateRQ2();
	clock = 0;
	while (!RQ2.empty())
	{
		std::list<PCB>::iterator q = RQ2.begin();
		//迭代器iterator提供一种访问对象容器中的元素，返回第一个元素的迭代器
		for (std::list<PCB>::iterator p = RQ2.begin();p != RQ2.end();++p)
		{    //找到最短预计执行时间的进程
			if (p->needtime < q->needtime)
			{
				q = p;
			}
		}
		q->starttime = clock;
		q->endtime = clock + q->needtime;
		clock = q->endtime;
		cout<< "进程 : p" << q->name << "\t" << "执行所需时间 : " << q->needtime << "\t"
			<< "开始执行时间 : " << q->starttime << "\t" << "结束时间 : " 
			<< q->endtime <<"\t"<<"周转时间 : "<< q->endtime - q->starttime<<endl;
		RQ2.erase(q);//删除节点q
	}
}

int main(void)
{
	RR();//轮转法
	SPPSM();//短进程优先调度法
	return 0;
}