Linux性能优化10：理解Linux调度模型

[介绍]

这一篇介绍一下Linux的调度模型，作为调优考虑问题的参考。

这不是说要介绍Linux现在具体调度算法，Linux代码大的特点就是“不断变化”，所以，介绍一个两个的调度算法不能解决调优的问题，我们要理解的是这些算法背后不变的东西，然后根据情况看代码才有意义。

[单核调度]

Linux的调度算法换过很多次了，新的调度算法称为CFS（完全公平调度器），在我们介绍这个算法的特点前，我们先理解一下调度器到底解决什么问题。

从一个线程切换到一个线程是平台相关代码，原理也比较死板简单，就是把上一个线程的CPU环境全部保存在TCB上，然后把下一个线程的TCB恢复到CPU寄存器中。这个不是调度器的重点。调度器的重点是选哪个线程投入运行。所以，严格来说，调度器是个数学问题：我给你一组参数（比如线程的优先级，使用了的时间等），你告诉我下一个要运行的线程是谁。

首先，休眠或者挂起的任务是不需要调度的，所以，理论上，我们可以认为，调度器只需要考虑需要运行的线程，这种线程的数量，就称为CPU当前的load。正如我们在这个系列的个文档中说的，这是调度队列的“长度”。

CPU把什么线程投入运行呢？这个问题在RTOS中是很好解决的，就是按优先级呗，谁的优先级高就谁运行，一直运行到这个线程不需要CPU为止。我们以前招过一位来自老牌服务器OS的专家来带领我们的OS开发团队，这个专家和我们讨论调度算法的时候就说：RTOS的调度器有什么好做的？玩来玩去不就那么点东西？这种说法显得有点骄傲了，但至少说明，在这些老牌服务器OS的人眼中，是不把实时调度算法看作是调度器要解决的主要问题的。

我们真正要解决的是SCHED_NORMAL的线程如何调度。自然的想法是按时间片，每人50ms，一路执行过去即可。 这就是CFS的所谓“公平”的含义：大家都用那么多时间，谁也不要亏欠谁。但这样带来一个基本的问题：比如你有200个线程，每人执行50ms，其中你有一个编辑器，那么你在这个编辑器上敲一个a，这个a得10秒以后回显给你——这个系统怎么用？

一个简单的补救是，把这个线程定义为实时线程，这样，这个线程会优先得到调度。但服务器不是嵌入式系统，服务器是不能这么干的。因为服务器是通用系统，如果随便一个编辑器就是实时线程，那很轻松就可以用一个编辑把这个CPU完全占用了，别的程序就不用跑了。所以每一代Linux调度器都要解决这个基本的问题：找出谁是“编辑器”。这种线程，调度器称为“交互线程”，如果你看的是Linux传统的O(1)调度器，或者更早的调度器实现，调度器是有明确的交互线程的概念在算法中的。其基本原理是挑出每次都用不完自己时间片的线程。提升这种线程的优先级，这种就是交互线程。

CFS没有这个问题，CFS的算法是这样的：给每个在调度队列中的线程一个vruntime的变量，记录这个线程运行了多久，每次调度，都调度vruntime小的线程，这样，自动优先执行的就是交互线程了。

这是理解Linux调度器的基础，无论哪个算法，Linux必须保证交互线程优先得到调度。然后才考虑其他问题。这是我们调优调度问题的基础。

有了这个基础，线程的nice值就仅仅是个如何加权的问题了。比如在CFS算法中，nice值作为vruntime流逝的加权， 这个nice大的进程时间流逝就快，它占据的时间片就少了。

[多核调度]

多核调度其实是单核调度算法的复制。多核的CPU其实互相是看不到对方的，CPU不过就是一条指令一条指令向下执行。所谓多核调度，就是每个CPU有一个run queue（下面简称rq），创建线程（下面简称task）的时候把线程扔到一个rq中，那个CPU就对这个rq执行单核的调度算法而已。

当然，那个仅仅是基础。多核调度还有一个任务是平衡调度。就是一个核特别忙，另一个核特别闲，就需要把task从一个核迁移到另一个核的runqueue中。

迁移要考虑的问题比前面说的这个模型复杂，因为有很多额外的要素要考虑：比如，一个核的两个超线程，它们共享相同的执行部件，很多时候平衡它们是没有意义的。又比如说，两个CPU，有不同的L2 Cache，你轻易切换它们，就有可能发生大量的Cache失效。还有，如果你把线程从NUMA系统的一个Node迁移到另一个，就把它的内存和它运行CPU拉远了，这会直接降低这个线程的执行性能。

所以Linux把线程组织在多个不同的sched_domain中，每个domain包含一组线程，每个domain有自己独立的算法，这些算法自行决定是否进行调度平衡。我们可以通过lscpu看CPU的组成结构，但真正有哪些domain，以及domain的参数，则需要看/proc/sys/kernel/sched_domain（或者简单一点可以看/proc/schedstat）。

不过要我说，如果你不能看懂调度算法，其实只要记住两个技巧就好了：

1. 通过ftrace跟踪sched:sched_migrate_task跟踪任务转移的频度

2. 把老切换的任务绑定在特定的核上

其他问题还是留给调度器专家吧。

[功耗问题]

在服务器上，我们一般只关注通量和时延，但现在的调度器开始要关心功耗问题了。这个真的让这个问题变成一个数学问题了。功耗要考虑的要素包括几个：

1. 休眠：CPU休眠就可以降功耗，那么你是把两个任务放两个CPU上以便提高速度呢？还是把它们合并到一个CPU上让其中一个CPU休眠呢？

2. DVFS：CPU可以调频来降功耗，还是那句话，你是把两个任务合并到一个CPU上，让另一个休眠呢，还是分在两个CPU上，让两个一起降频呢？

3. CPU热插拔：休眠可以降功耗，但比不上把这个CPU直接下电，但下了电，要恢复就很不容易了，那你要更快恢复还是要降功耗呢？

ARM现在尝试通过AWS项目（Energy-Aware Scheduling (EAS) Project）把这三个要素整合在一起。但终内核会修改成什么样子，还有待观察。在EAS可以商用前，每个手机还要考虑自己用那种策略去聚合前面的要素。

谢天谢地，我现在不用搞手机了：）