如果有很多任务排队等着被处理，哪个任务先被处理，哪个任务后处理，这个需要由操作系统决定，这就是调度。多级反馈队列调度算法是目前操作系统调度算法中被公认的一种较好的调度算法。它可以满足各种类型进程的需要，既能使高优先级的作业得到响应又能使短作业(进程)迅速完成。
基本概念
多级反馈队列调度算法是一种根据先来先服务原则给就绪队列排序，为就绪队列赋予不同的优先级数，不同的时间片，按照优先级抢占CPU的调度算法。算法的实施过程如下：
按照先来先服务原则排序，设置N个就绪队列为Q1，Q2...QN，每个队列中都可以放很多作业；
为这N个就绪队列赋予不同的优先级，第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低；
设置每个就绪队列的时间片，优先权越高，算法赋予队列的时间片越小。时间片大小的设定按照实际作业(进程)的需要调整；
进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了时间片为N的时间后，若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业即抢占式调度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再经过一个时间片，完成了任务。于是整个调度过程结束。
应用案例
应用1-男主人处理妻子和母亲的要求
案例：中国男人在婆媳关系的融洽中起着非常重要的作用。现有一例子，母亲有一件事情A要男人帮忙，1小时后妻子也有一件事情B要男人帮忙，两件事情各自需要的时间为2小时和1小时。假设事情在家里就可以完成，男人在家，母亲叫儿子帮忙后，男人开始做的时间为下午3:00。 男人该怎么样分配做事情的顺序？
解决步骤：
根据题目，设定男人连续做事时长分别为半小时和1小时
下午3:00，按照先来先服务原则，母亲先叫儿子办事情，所以男人先帮母亲做事情A，此时事情A等级为1；
下午4:00，妻子叫男人帮忙，于是男人暂停事情A(事情A还剩下1个小时的执行过程)，开始做事情B，事情B等级为1，此时事情A等级降为2，
下午4:30，男人暂停事情B，此时事情B等级降为2(事情B还剩下半个小时的执行过程)，帮母亲干事情A
下午5:30，男人完成事情A，帮妻子干事情B
下午6:00，男人完成事情B
这个过程中，男人既完了了母亲的任务，也完成了妻子的任务，两件事情交叉处理，没有出现母亲一直等，或是妻子一直等的情况。这就是多任务的一种调度方式。
可以体现的计算思维
多级反馈队列调度算法体现了计算思维的调度特点，应用了先来先服务原则、应用时间片等做法使得每个申请者都能及时使用资源，是一种很好的协调整体的解决方案。

实验课程：操作系统
实验名称：进程调度的设计与实现     (综合实验)
第一部分 实验内容
1．实验目标
1、 综合应用下列知识点设计并实现操作系统的进程调度：邻接表，布尔数组，非阻塞输入，图形用户界面GUI，进程控制块，进程状态转换，多级反馈队列进程调度
2、 加深理解操作系统进程调度的过程。
3、 加深理解多级反馈队列进程调度算法。
2. 实验任务
1、 用一种熟悉的语言，如C、PASCAL或C++等，编制程序。
2、 采用多级反馈队列调度算法进行进程调度。
3. 实验设备及环境
PC；C/C++
4. 实验主要步骤
(1) 根据实验目标，明确实验的具体任务；
(2) 编写程序实现进程调度算法；
(3) 设计实验数据并运行程序、记录运行的结果；
(4) 分析实验结果；
(5) 实验后的心得体会。
第二部分 问题及算法
1. 问题描述
(1) 采用一种熟悉的语言，如C、PASCAL或C++等，编制程序。
(2) 采用多级反馈队列调度算法进行进程调度。
(3) 每个进程对应一个PCB。在PCB中包括进程标识符pid、进程的状态标识status、进程优先级priority、进程的队列指针next和表示进程生命周期的数据项life(在实际系统中不包括该项)。
(4) 创建进程时即创建一个PCB，各个进程的pid都是唯一的，pid是在1到100范围内的一个整数。可以创建一个下标为1到100的布尔数组，“真”表示下标对应的进程标识号是空闲的，“假”表示下标对应的进程标识号已分配给某个进程。
(5) 进程状态status的取值为“就绪ready”或“运行run”，刚创建时，状态为“ready”。被进程调度程序选中后变为“run”。
(6) 进程优先级priority是0到49范围内的一个随机整数。
(7) 进程生命周期life是1到5范围内的一个随机整数。
(8) 初始化时，创建一个邻接表，包含50个就绪队列，各就绪队列的进程优先级priority分别是0到49。
(9) 为了模拟用户动态提交任务的过程，要求动态创建进程。进入进程调度循环后，每次按ctrl+f即动态创建一个进程，然后将该PCB插入就绪队列中。按ctrl+q退出进程调度循环。
(10) 在进程调度循环中，每次选择优先级最大的就绪进程来执行。将其状态从就绪变为运行，通过延时一段时间来模拟该进程执行一个时间片的过程，然后优先级减半，生命周期减一。设计图形用户界面GUI，在窗口中显示该进程和其他所有进程的PCB内容。如果将该运行进程的生命周期不为0，则重新把它变为就绪状态，插入就绪队列中；否则该进程执行完成，撤消其PCB。以上为一次进程调度循环。
(11) 在上机实现该程序之后，要求写出实验报告，其中包括实验名称、实验目的、实验内容、程序的主要流程图、实验心得和主要源程序清单等。
2. 多级反馈队列进程调度算法的一般思路
(1)进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
(2)首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
(3)对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
(4)在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业(抢占式)。
3. 算法实现的关键点
队列的切换和优先级的变化。
第三部分 实验结果与分析
1. 实验数据及结果
实验数据为随机数据，所以结果也为随机值，故见下文
2. 实验分析及结论
由于不会关于GUI的相关程序，所以做不了GUI界面，故而比较难看。
第四部分 心得与展望
1. 自我评价及心得体会
看起来很简单，但是做起来很复杂，需要很长一段时间。
2.  展望
以后有时间要学GUI编程。
第五部分 附录
1. 主要界面
2. 源程序
/**
made by FrankieCCT
time:2013.5.19 7:13
main.cpp
**/
#include "myQueue.h"
int main()
{
char chioce;
PCB *tmp_pcb;
int i;
int flag = 0;
fill(&pid_queue[0],&pid_queue[100],true);
while (1)
{
menu();
cin >> chioce;
switch (chioce)
{
case 'y':
case 'Y':
tmp_pcb = get_a_random_ready_PCB();
insert_pcb(tmp_pcb, tmp_pcb->priority);
break;
case 'n':
case 'N':
break;
default:
puts("illegal!");
system("pause");
system("cls");
continue;
break;
}
for (i = 49; i > -1; i--)
{
if (p_queue[i].first_task != NULL)
{
puts("上一时间片运行情况：");
tmp_pcb = p_queue[i].first_task;
tmp_pcb->status = RUN_PCB;
cout <pid
<
<life--;
cout <life <
p_queue[i].first_task->status = READY_PCB;
if (p_queue[i].first_task->life > 0)
{
cout <
<priority;
cout <priority/2
<
tmp_pcb->priority /= 2;
insert_pcb(tmp_pcb, tmp_pcb->priority);
}
else if (p_queue[i].first_task->life == 0)
{
cout <
pid_queue[p_queue[i].first_task->pid] = true;
}
p_queue[i].first_task = p_queue[i].first_task->next;
break;
}
}
if (i == -1)
{
puts("all complete!");
}
puts("现在线程情况：");
for (i = 49; i > -1; i--)
{
if (p_queue[i].first_task != NULL)
{
cout <
cout <pid
<life <
tmp_pcb = p_queue[i].first_task->next;
while (tmp_pcb != NULL)
{
cout <pid
<life <
tmp_pcb = tmp_pcb->next;
}
}
}
}
return 0;
}
/**
made by FrankieCCT
time:2013.5.19 7:13
myQueue.h
**/
#ifndef MYQUEUE_H_INCLUDED
#define MYQUEUE_H_INCLUDED
#include 
using namespace std;
#include 
#include 
#include 
#include 
#define MAX_PID_NUM 101
#define MAX_PCB_NUM 50
#define READY_PCB 1
#define RUN_PCB 2
struct PCB;
int get_available_pid();
void menu();
PCB *get_a_random_ready_PCB();
bool pid_queue[MAX_PID_NUM];
struct PCB
{
int pid;
int status;
int priority;
PCB *next;
int life;
PCB()
{
srand(time(0));
status = READY_PCB;
pid = get_available_pid();
if (pid == -1)
{
puts("full pid queue!");
system("pause");
abort();
}
else
{
pid_queue[pid] = false;
}
next = NULL;
priority = rand() % 49 + 1;
life = rand() % 5 + 1;
}
PCB(const PCB&pcb)
{
status = pcb.status;
pid = pcb.pid;
next = pcb.next;
priority = pcb.priority;
life = pcb.life;
}
};
struct PCB_queue
{
PCB *first_task;
PCB_queue()
{
first_task = NULL;
}
};
int get_available_pid()
{
for (int i = 0; i 
if (pid_queue[i])
return i;
return -1;
}
void menu()
{
puts("是否新建进程？(Y/N)");
}
PCB *get_a_random_ready_PCB()
{
PCB *a_pcb = new PCB();
cout <pid
<life
<priority
<
return a_pcb;
}
PCB_queue p_queue[MAX_PCB_NUM];
void insert_pcb(PCB *tmp_pcb, int i)
{
PCB *tmp_pcb_other;
if (p_queue[i].first_task == NULL)
{
p_queue[i].first_task = tmp_pcb;
p_queue[i].first_task->next = NULL;
}
else
{
tmp_pcb_other = p_queue[i].first_task;
while (tmp_pcb_other->next != NULL)
{
tmp_pcb_other = tmp_pcb_other->next;
}
tmp_pcb_other->next = tmp_pcb;
tmp_pcb_other->next->next = NULL;
}
}
#endif // MYQUEUE_H_INCLUDED
参考文献
l 《操作系统教程》谢旭东，朱明华，张练兴，李宏伟等，机械工业出版社，2013年

该楼层疑似违规已被系统折叠 隐藏此楼查看此楼
【问题描述】
多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程(任务)得到响应又能使短进程(任务)迅速完成。UNIX操作系统便采取这种算法。试用C语言模拟某多级反馈队列调度算法。
【具体要求】
多级反馈队列调度算法描述：
1、该调度算法设置四级就绪队列：前三级就绪队列采用时间片轮转法，时间片大小分别为2、4和8；最后一级就绪队列采用FIFO调度。
2、任务在进入待调度的队列等待时，首先进入优先级最高的队列等待。
3、首先调度优先级高的队列中的任务。若高优先级中队列中已没有调度的任务，则调度次优先级队列中的任务，依次类推。
4、对于同一个队列中的各个任务，按照队列指定调度方法调度。每次任务调度执行后，若没有完成任务，就被降到下一个低优先级队列中。
5、低优先级队列中的任务在运行时，若有高优先级任务新到达，那么低优先级任务在运行完一个时间片后中止运行，CPU马上分配给新到达的任务，即算法支持抢占式。(这部分可作为选做，最低要求可以是非抢占式的，即低优先级队列中的某任务完成规定的时间片后再去检查高优先级队列是否有新任务到达。)
6、为方便实现，时间以1为单位，用整数数据表示；且每个时间点，最多只有一个任务请求服务(即输入)。
【实现提示】
实现一个队列数组(queue array)，该数组的每个元素都代表一个长度可变的队列，队列中的每个元素则代表一个任务job，任务结构定义如下：
typedef  struct  Job {
int  JobNum;                          //任务号
int  ArriveTime；          //到达时刻
int  ResponTime                      //响应时间
int  RunTime;                          //运行时间
struct  Job  *next;
}
【测试数据】
输入：任务号 到达时刻 运行时间
输出：任务号 响应时间 离开时刻 周转时间
样例：
输入数据：
任务号 到达时刻    运行时间
1           0            3
2           1            2
3           4           15
4           5            2
5           6            6
6          12            2
输出数据(非抢占式)：
任务号  响应时间  离开时刻  周转时间
2            1           4            3
4            1           8            3
1            0          11         11
6            3          17            5
5            2          21         15
3            0          30         26
输出数据(抢占式)：
任务号  响应时间  离开时刻  周转时间
2            1           4            3
4            1           8            3
1            0          11         11
6            0          14            2
5            2          21         15
3            0          30         26
自己设计多批数据测试，报告上要求写出多批数据测试结果。

多级反馈队列调度算法

 



如果有很多任务排队等着被处理，哪个任务先被处理，哪个任务后处理，这个需要由操作系统决定，这就是调度。多级反馈队列调度算法是目前操作系统调度算法中被公认的一种较好的调度算法。它可以满足各种类型进程的需要，既能使高优先级的作业得到响应又能使短作业（进程）迅速完成。

基本概念

多级反馈队列调度算法是一种根据先来先服务原则给就绪队列排序，为就绪队列赋予不同的优先级数，不同的时间片，按照优先级抢占CPU的调度算法。算法的实施过程如下：

按照先来先服务原则排序，设置N个就绪队列为Q1，Q2...QN，每个队列中都可以放很多作业；
	
为这N个就绪队列赋予不同的优先级，第一个队列的优先级最高，第二个队列次之，其余各队列的优先权逐个降低；
	
设置每个就绪队列的时间片，优先权越高，算法赋予队列的时间片越小。时间片大小的设定按照实际作业（进程）的需要调整；
	
进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。
	
首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。
	
对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1队列的时间片为N，那么Q1中的作业在经历了时间片为N的时间后，若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。
	
在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业即抢占式调度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再经过一个时间片，完成了任务。于是整个调度过程结束。

应用案例

应用1-男主人处理妻子和母亲的要求

案例：中国男人在婆媳关系的融洽中起着非常重要的作用。现有一例子，母亲有一件事情A要男人帮忙，1小时后妻子也有一件事情B要男人帮忙，两件事情各自需要的时间为2小时和1小时。假设事情在家里就可以完成，男人在家，母亲叫儿子帮忙后，男人开始做的时间为下午3:00。 男人该怎么样分配做事情的顺序？

解决步骤：

根据题目，设定男人连续做事时长分别为半小时和1小时
	
下午3:00，按照先来先服务原则，母亲先叫儿子办事情，所以男人先帮母亲做事情A，此时事情A等级为1；
	
下午4:00，妻子叫男人帮忙，于是男人暂停事情A（事情A还剩下1个小时的执行过程），开始做事情B，事情B等级为1，此时事情A等级降为2，
	
下午4:30，男人暂停事情B，此时事情B等级降为2（事情B还剩下半个小时的执行过程），帮母亲干事情A
	
下午5:30，男人完成事情A，帮妻子干事情B
	
下午6:00，男人完成事情B
这个过程中，男人既完了了母亲的任务，也完成了妻子的任务，两件事情交叉处理，没有出现母亲一直等，或是妻子一直等的情况。这就是多任务的一种调度方式。

可以体现的计算思维

多级反馈队列调度算法体现了计算思维的调度特点，应用了先来先服务原则、应用时间片等做法使得每个申请者都能及时使用资源，是一种很好的协调整体的解决方案。

——摘自计算思维百科

 

转载自：https://www.cnblogs.com/Roni-i/p/10291822.html