linux 操作系统的进程调度（上） -- 进程调度算法的演进

1. 引言

上一篇文章中，我们介绍了内核调度的基本概念，知道了调度器设计中最核心的两个指标 -- 周转时间与响应时间：

linux 操作系统的进程调度（上） -- 进程调度的基本概念

本文，我们就继续顺着上文的思路，来看看在操作系统的进程调度设计中，都有哪些调度算法，他们的思路和优劣又分别体现在哪些方面。

2. 先来先服务算法 FCFS

“先来先服务”翻译自“First Come First Service”，所以缩写为 FCFS，顾名思义，就是让操作系统按照任务到来的顺序顺次执行，很显然，这是各种调度算法设计中最为简单的一个。

这个算法的缺点是显而易见的，一旦此时有一个需要长时间执行的任务被操作系统执行，那么，后续所有的任务都必须等待这个长时间运行的任务执行完毕，假设在操作系统的任务队列中，存在着一个需要执行 30s 的任务，而它后面排队着两个只需执行 10s 的任务，那么这些小任务都需要等待这个长任务运行完成才可以开始执行，极大地拉长了系统的平均响应时间，周转时间当然也随之变长。

3. 最短任务优先算法 SJF

SJF 是 Shortest Job First 的缩写，还拿上面的例子来说，只要把长任务放在所有短任务之后执行，整个系统的平均响应时间就会变成最优。

具体来看，如果长任务在前，则整体的响应时间为 0s + 30s + 40s = 70s，周转时间为 30s + 40s + 50s = 120s，而如果长任务在最后执行，则整体响应时间为 0s + 10s + 20s = 30s，而整体周转时间为 10s + 20s + 50s = 80s，显然，越是短任务越应该优先执行，这样才能让整个系统的响应时间和周转时间降到最低。

SJF 算法的理想虽然很美好，但在实际系统执行过程中，却往往存在着两个致命的问题：

1. 在进程执行过程中，新的任务随时都有可能到来，如果任务不是同时到来的，那么 SJF 算法事实上就退化成了 FCFS 算法，无法实现动态调度。
2. 一个进程究竟会运行多久，往往在运行前我们是无法预测的。

4. 抢占式最短任务优先 PSJF

最短任务优先算法看起来很不错，但实际场景中却总是显得过于理想化。要想解决这个问题会稍显复杂。

既然我们无法预知一个进程究竟会执行多久，我们就按顺序先执行第一个进程，当新的任务到来时，操作系统通过预测任务可能的运行时间，来判断新的进程的运行时间是否短于当前正在运行的任务的运行时间，从而决定是否切换到新的进程。这便解决了 SFJ 算法退化的问题。这就是抢占式最短任务优先算法 --Preemptive Shortest Job First。

显然，PSJF 算法的重点在于如何预测新来的任务的运行时长。然而，即便是这个预测是准确的，仍然存在一个很大的问题，假设系统起先执行了一个长任务一段时间后，持续不断地有新的短任务到来，那么，这个长任务将一直被这些短任务抢占，产生饥饿效应，结果这个长任务永远都无法得到执行。

5. 时间片轮转算法 RR

Round-Robin 算法是现代操作系统调度器诞生的基石。它按照 CPU 时钟芯片产生的若干个时钟脉冲为单位，将 CPU 时间进行切分，每个分片就是 CPU 调度的时间片。

每个进程都以 CPU 时间片为单位进行调度，当时间片的时间到期，如果任务队列中存在其他任务，那么就保存当前进程的上下文并切换到另一个进程再执行一个时间片，如此往复，就可以让每个进程“雨露均沾”地使用到 CPU，实现了调度算法的公平性。

但上下文的保存和切换并不是无损的，每次上下文切换都需要耗费一定的时间，时间片越短，这浪费掉的额外时间占比也就越大，从而会使整个系统的响应时间和周转时间都被大幅拉升。但如果时间片过大，那么就仍然会出现上述算法所具有的问题，即排在后面的短进程被迫等待排在前面的长进程完成较长的时间片，从而让整个系统的响应时间被随之拉升。

6. 多级反馈队列 MLFQ

针对 RR 算法存在的问题，结合我们上一篇文章中介绍的 IO 密集型与 CPU 密集型进程的区别：

• IO 密集型：频繁 IO，但占用 CPU 的时间不多；
• CPU 密集型：进程执行过程中很少执行 IO 操作，大部分时间都在占用 CPU 资源执行计算任务。

我们能够得出结论，如果要想降低整体响应时间，那么就需要满足这几个原则：

1. 单个时间片尽量缩短。
2. 如果进程是 IO 密集型，那么就频繁调度，但每次调度给与少量时间片。
3. 如果进程是 CPU 密集型，那么就降低调度频率，但每次调度过于多个时间片。

从这三条原则，我们看出，操作系统必须在运行过程中区分一个进程究竟是 IO 密集型还是 CPU 密集型，并且在正确区分它们的基础上，需要增加优先级概念，从而让 IO 密集型进程更为优先和频繁地被分配到 CPU 时间片，这就需要引入多级的任务队列。

但即使有了多级的任务队列，仍然存在着以下几个问题：

1. 怎么保证低优先级的任务不会因为高优先级任务的持续抢占而一直得不到调度。
2. 在进程的持续执行中，原本低优先级的 CPU 密集型任务可能在某一时刻变成了 IO 密集型任务，从而需要进入高优先级队列。
3. 由于 IO 密集型任务具有更高的优先级，那么进程编写者可能会通过故意进行 IO 操作来骗取操作系统的误判，从而将本是 CPU 密集型的任务被故意包装成 IO 密集型任务，进而被错误地优先调度。

所以，光是有多级队列是远远不够的，还需要反馈机制，周期性地对进程类型进行重新评估，避免上述问题。综上，这就是多级反馈队列 Multi-Level Feedback Queue 算法。

7. 结语

正是有了多级反馈队列算法，现代生产级操作系统中的进程调度器才得以真正建立起来。

下一篇文章，我们就来深入 linux，来了解具体的 linux 进程调度器的发展历史和实现机制，敬请期待。