在之前的文章中我介绍了OS任务调度算法相关的内容，里面有一个核心概念就是任务队列，Queue对应一个任务调度系统来说至关重要，那该怎么设计一个合理的任务队列呢？如何合理的调度任务队列中的任务前面的文章介绍几种基础的常见的调度算法FCFS、SJF这类的算法，这篇文章将介绍基于这些调度算法之上的多级队列调度算法。
多级任务队列
在之前的文章中我们提到任务队列概念，大部分都是单任务队列也就是批任务处理系统，把大量的任务加载到一个任务队列中然后等待调度器进行调度工作，大部分都是单任务队列，如下图这样的：
但是在虚拟线程那篇文章中我介绍了Go的GMP调度模型，最新的Go的GMP调度模型中有多级的任务队列，一个全局加多个本地队列的概念，本节我要介绍的也是一种多级任务队列概念，但是比GMP中的多级队列要相对复杂。
前面的文章介绍几个单一的任务队列调度算法，他们的差异我整理成一个表格如下：
| 策略 | 优先级调度方式 |
|---|---|
| FCFS | 任务到达时间早的优先级高 |
| SJF | 任务运行时间短的优先级高 |
| STCF | 任务剩余完成时间短的优先级高 |
| RR | 所有任务调度时间平等 |
通过上面这些任务调度策略的例子可以看出来但是针对特定场景的调度，而没有一个完全针对于队列任务调度的类型还有优先级做调度设计的策略和队列模型，包括Go的GMP模型在优先级调度上也只是做一个runnext指针的字段，在这个指针指向的任务会被立即调度执行，也就仅此而已。
关于的Go的GMP调度器可以查看我之前写的这篇文章：Go内置调度器模型。
多级任务调度： 相对于上面讨论的这些策略，是可以任务按照不同的优先级进行了分类分队处理，例如在飞机出行的时候，机长和乘务人员先登机，然后是商务舱VIP乘客，然后再是普通乘客，这就是生活中按照多个优先级来排队的例子。
如果任务可以被分类，那么可以将其置于不同的队列之中，每个队列都可以有自己的调度算法，如果多个队列的任务都处于ready状态那么调度器会按照队列的优先级来决定调度具体哪个队列的里面的任务，如下图：
多优先级队列需要注意的是如果有大量的高优先级的任务被加入到队列中，那么调度器可能一直在处理高优先级无法调度到低优先级的队列中的任务，导致会出现类似于STCF饿死任务的情况，低优先级的任务存在饿死情况，低优先级任务不能被调度。
优先级继承问题
高优先级优先调度，根据进程紧急程度、重要性赋予不同优先级可以静态，也可以动态调整，进程调度时，从就绪队列中选取优先级最高的进程运行。看似很简单，然而，当多个进程访问同一个临界资源时，可能会出现优先级反转问题。
问题出现的场景，假设现在有一个调度顺序是：A>B>C，但是任务A和C需要去访问一个共同的加锁资源，因为C任务先拿到锁🔐，然后A也想去拿锁，但是发现锁已经被C占有了，此时A就要去阻塞等待锁释放才能正常执行，那么此时的调度顺序就是B然后C再是A，这样导致外界观察到效果是A的优先级要小于B；其实这个就是因为锁带来的优先级反转问题，为了方便理解我画了一副图如下：
怎么解决这个呢？解决办法很简单，就看哪个任务先拿到锁，拿到锁的哪个任务先执行，执行完成释放锁然后，按照之前调度顺序继续执行，最后通过优先继承之后的执行顺序就为下图：
上面的任务C拿到锁就临时提高此任务的调度权限，当任务C锁释放，A任务就会直接抢占执行，然后再去执行B任务，为了方便看图，我在每个执行流后面都加了一个CPU标识。
多级反馈队列
多级反馈队列 MLFQ 调度策略每个队列都可以有自己对应任务调度策略，一般短任务拥有较高的调度优先权，例如上图中的IO事件的任务可以被优先调度，因为IO任务一般只会占用短暂的CPU事件，大部分在等待IO返回，先调度IO有助于IO资源的利用率，还有一种短任务是交互任务，优先调度也可以降低任务响应时间，其次就是CPU密集型任务调度，为了方便理解我画一幅图：
MLFQ设计原则： 设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的任务调度的优先级也是不一样的。所有任务队列对应自己的调度器策略实现，但是任务执行优先级则是从上往下执行的；有了这样的设计我们就可以把任务按照是计算密集型任务还是IO密集型任务来存放到不同队列中，并且也可以按照是否为及时交互类型的任务，如果是则将其放入高优先级队列中，并且还能动态调整每个队列的调度器逻辑代码的实现。
MLFQ设计的好处： 对于优先级最低的队列来说，里面是遵循时间片轮转，也就是说，位于队列QN中有M个作业，它们的运行时间是通过QN这个队列所设定的时间片来确定的；对于其他队列，遵循的是先来先服务算法，每一进程分配一定的时间片，若时间片运行完时进程未结束，则进入下一优先级队列的末尾；各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大。
其实这样看的话和多级队列没有什么区别，唯一的区别就是每个队列有对应调度器策略算法的具体实现，那么这里的多级反馈队列，反馈这个设计体现在哪里呢?
在之前的OS调度中介绍过SJF和RR为了解决一部分OS
调度器在运行任务的无法预知每个任务的完成时间的问题，把CPU分成了时间片来执行，如上图中任务时间片用完了循环放回队列中。而多级反馈队列设计是每个任务进入调度系统时都会默认认为优先级在最高层，那怎么调节任务调度优先级呢？
多级反馈队列为了能动态调节任务所在的层，会为层的任务队列设置一个最大允许运行时间，如果一个任务在高层的队列中频繁被执行并且任务每次运行时间的总和超过阀值就会触发降级操作；为了方便理解我画了一张图，如下图中的Task5在每次执行的都会被计时器记录。
这些共同缺点就是低层次的任务可能长期无法得到调度，一个长任务被从高层降级到低层次之后就很难被频繁调度，解决这个问题的常用的方式就是另外加入一个定时器，定时器会自动升级这些任务到高层，当然也可以有其他办法，这里只是一个思路开导而已，具体要去做什么样的实现看谁脑洞大了。
事件循环
上面讨论一堆关于调度队列和调度器的实现，这里我讲介绍一个多级队列的应用案例，在Node.Js这款JavaScript执行引擎有一个叫Event Loop组件吧。
中文都叫事件循环，事件循环是干什么的？写过Js的应该知道JavaScript是单线程的，如果想做多线程并发（异步操作）怎么办？在之前的文章我讲过现在OS都是支持多线程的内核，可以把任务丢给内核的多线程去做，当这些操作之一完成时，内核会告诉Node.js，以便将适当的回调添加到轮询队列中以最终执行，Event Loop大致的架构设计如下动图：
有时候在写web页面的时候我可能会做一个定时器事件，或者在后端起一个Ajax做异步页面数据刷新，例如一段代码如下:
// A 任务
setTimeout(() => {
console.log(1)
}, 20)
// B 任务
setTimeout(() => {
console.log(2)
}, 0)
// C 任务
setTimeout(() => {
console.log(3)
}, 10)
// D
setTimeout(() => {
console.log(5)
}, 10)
console.log(4)
/* 输出
* 4 -> 2-> 3 -> 5 -> 1
*/这是什么？不都是有时间顺序的吗？为什么执行结果是这样的呢？这就要回到上面那副图了，其中的Call Stack就是一个Js函数执行栈，其实还有一个内存分配区堆的没有画出来；这里主要看的是轮询队列，轮询队列中的任务都是按照FCFS调度策略来排队的，如果后台有内核把任务完成了就会把回调扔到这个队列中，等待到Call Stack中执行，所以这里队列取决于调度方式和队列组织方式，这里就没有优先级概念。
这方面的应用据我所知Java的最新框架ActiveJ中也使用的了，官方地址为：https://activej.io，使用之后跑起来事件循环很简单，代码如下：
class Main {
public static void main(String[] args) {
Eventloop eventloop = Eventloop.create();
eventloop.post(() -> System.out.println("Hello world"));
eventloop.run();
}
}小结
上面讨论的多级队列理论相关的问题中队列可以是固定长度的数组实现，例如Go里面的队列就是一个255数组，也可以是一对大顶堆来实现，自适应调整；多级反馈队列相比普通队列调度算法增加了容易的公平性，根据任务类型来调度而不是单一的调度策略，都有各执其职的调度器，还有一个共同的全局优先级策略，也是一种典型的计算机分而治之的应用设计。Event Loop调度设计模式和Reactor多路复用模式很类似，这个后面我讲会继续写相关的IO文章介绍此类的应用设计与实现。
