多级反馈队列调度算法

2023-08-11 14:08:16

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

基本概念

多级反馈队列调度算法是一种根据先来先服务原则给就绪队列排序，为就绪队列赋予不同的优先级数，不同的时间片，按照优先级抢占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再经过一个时间片，完成了任务。于是整个调度过程结束。

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

解决步骤：

这个过程中，男人既完了了母亲的任务，也完成了妻子的任务，两件事情交叉处理，没有出现母亲一直等，或是妻子一直等的情况。这就是多任务的一种调度方式。

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