进程调度

原文连接:https://mp.weixin.qq.com/s/eOkQu8YDszhMvyjQsesdLg

简介

对于操作系统来讲，它面对的 CPU 数量是有限的，往往需要执行的进程数目远超 CPU 数目，因而就需要合理的把 CPU 执行时间分配给进程。既要保证进程快速响应，又要保证进程相对公平的获得执行时间，这是一个十分复杂的事情。今天我们就好好讲讲 Linux 是如何进行进程调度的。如果严谨一些的话， Linux 操作系统中应该叫任务调度，不过本文就按照大家的习惯叫进程调度了。

之前讲过，可以把进程细分为五种状态，或者粗分为三种状态。五种状态已经在之前讲过了，今天在讲进程调度前咱们简单看下三种基本状态：

• 就绪（Ready）: 进程已经获得了 CPU 以外的所有必要资源，如进程空间、网络连接等。就绪状态下的进程等到CPU，便可立即执行。
• 执行（Running）：进程获得 CPU，执行程序。
• 阻塞（Blocked）：当进程由于等待某个事件而无法执行时，便放弃 CPU，处于阻塞状态。

调度器主要就是负责进程在就绪态和执行态之间转换。Linux调度器主要负责做以下两件事：（1）选择出最合适的处于就绪态的进程来执行；（2）打断某些执行中的进程，让他们变为就绪态。

Linux 操作系统把需要调度的进程分为两类：

普通进程（Normal Process）：优先级低的进程。

实时进程（Real-Time Process）：优先级高、需要尽快被执行的进程。

对于普通进程和实时进程，会分配不同的优先级。进程的优先级是 0 到 139 的整数，0-99 留给实时进程，100-139 留给普通进程。另外在调度过程中内核根据进程的情况，会对进程的优先级进行一定的调整。

普通进程和实时进程对于调度器的需求也不一样。对于实时进程，最重要的是快速的对进程进行调度。对于普通进程，要兼顾调度的公平性、系统的吞吐量，以及进程调度的响应时间。

进程调度器的发展

最原始的Linux调度策略就是按照优先级排好进程，一个进程运行完后再运行剩下进程中优先级最高的那一个。但这种方式无法满足多任务系统的需求。接下来我们按照出现顺序介绍 3 种调度器进化过程中经典的调度器。在下面的介绍中，主要介绍调度器的一个演化思路，不会特别注重细节，我们都从调度器的设计理念、进程执行时间设计、组织进程的数据结构以及相应具有的问题来介绍。

O（n）调度器

设计理念

O(n) 调度器把时间分成大量的微小时间片（Epoch）。在每个时间片开始的时候，调度器会检查所有处在就绪状态的进程。调度器计算每个进程的优先级，然后选择优先级最高的进程来执行。一旦被调度器切换到执行，进程可以用尽这个时间片。如果进程没有用尽时间片，那么该时间片的剩余时间会增加到下一个时间片中。

进程执行时间的设计

O（n）在设计默认时间片时根据进程的静态优先级固定分配一个默认的时间片，优先级越高，所得到的时间片就越大。分配的具体算法叫 NICE_TO_TICKS。大家感兴趣的可以自行学习。说到优先级，O（n）调度器把优先级分为静态优先级和动态优先级，刚提到的静态优先级就是进程创建时初始的优先级，不会改变，进程默认的时间片就是根据静态优先级进行计算分配。而每次进程调度的过程中，都会基于进程的静态优先级和该进程所剩的时间片，计算一个动态优先级，动态优先级最高的就是下一次要调度的。该进程静态优先级越高，所剩的时间片越多，那么这个进程的动态优先级也就越高。

数据结构

O（n）调度器采用一个全局队列将进程组织起来。只要进程变为就绪态，进程就会被挂到这个队列中，每一次进程调度，都需要把队列中所有进程的动态优先级计算一遍，选出动态优先级最高的进程。

问题

看上面的架构图。O（n）最大的问题就在于以一个队列就把所有的进程组织起来，每次要选择出下一个要执行的进程时， 都需要把队列全部遍历一遍。且要把队列中所有进程的动态优先级都计算一遍。这对于队列中进程较多时是难以接受的。

O(1）调度器

设计理念

由于O（n）调度器的性能受进程数量的影响很大，后续调度器一直想解决这个问题，于是O（1）调度器被设计了出来。O（1）调度器的目得是，不管进程队列中有几个进程，都要直接能把下一个要执行得进程挑出来。然后接下来就和O（n）调度器基本一致，让得到执行的进程不受打扰的执行完自己分到的时间片，除非自己因为某些原因放弃执行。

进程执行时间的设计

和O（n）调度器类似，O（1）也是基于进程的优先级计算分给该进程的时间片。计算公式如下：

优先级120以下进程时间片 =  （140 - 优先级） x 20 毫秒                                  //进程优先级数字越小优先级越高
优先级120及以上进程时间片 = （140 - 优先级）x 5 毫秒

O（1）调度器还会根据平均休眠时间来调整进程优先级。其实也就是进程和用户交互越多，进程优先级就越高。

数据结构

看该调度器的架构图，O（n）调度器其实也很暴力，之前说进程得优先级是0-139 的整数。那就直接生成了 139 个队列，进程的优先级是多少就放在哪个队列中。相同优先级的进程放在同一个队列中。这样，按照优先级依次执行，遇到一个队列中有多个进程的情况，就从队列中随机选择一个。

问题

可以看出，进程的运行顺序和所得时间片太依赖优先级了。另外O（1）调度器根据平均休眠时间来调整进程优先级是基于频繁和用户交互得信息是需要更高优先级的假设，如果这个假设不成立，那么调度器对CPU的调配就有问题了。

完全公平调度器（CFS）

完全公平调度器（CFS）的出现在调度器的发展史上具有划时代的意义。CFS 在进程执行时间片和进程排列的数据结构上都有一个很大的创新。

设计理念

CFS 调度器是这样一个逻辑，每一个进程都有一个虚拟运行时间，每次执行进程时，都挑出虚拟执行时间最短的进程分给时间片让他执行。但是呢，优先级高的进程需要更多的执行时间，所以，就要照顾优先级高的进程能更多的时间片。这样，就需要在虚拟运行时间上做一些措施，对于高优先级的进程，就让他的虚拟运行时间增的慢一点，而优先级低的进程，就让它的虚拟运行时间增的快一点。

另外，该进程调度器还是需要能直接的找到运行虚拟时间最少的进程，进而分给它时间片让它执行。

进程执行时间设计

CFS 调度器增加了一个虚拟运行时间的概念。每次一个进程在 CPU 中执行一段时间，就会增加它的虚拟运行时间，但是这个虚拟运行时间增加的幅度会受进程优先级的影响。比如同样实际运行了 300ms，高优先级的进程虚拟时间只增加了100ms，而低优先级的进程虚拟运行时间却增加了300ms，因为每次选择要执行的进程时，选取虚拟运行时间最少的进程去执行，所以下次执行时高优先级的进程优先执行的可能性更大。

虚拟运行时间的计算是基于这样一个公式 vruntime += 实际运行时间 / 权重。大家也应该能猜出，高优先级的权重会高，低优先级的权重就低一些，这样就能达到我们的目的了。

数据结构

为了方便找到虚拟运行时间最少的进程，CFS 将进程采用了红黑树的方式组织了起来。就像上面的架构图，每次通过遍历，可以很方便快捷的找到虚拟运行时间最短的进程。

参考资料：

1.https://www.cnblogs.com/vamei/p/9364382.html

2.http://www.wowotech.net/process_management/scheduler-history.html

3.极客时间《趣谈 Linux 操作系统》