Linux进程调度：完全公平调度器CFS

对于分时操作系统来说，表面上看起来同时多个进程在运行，其实系统内部同一时间只有一个进程在运行，但进程是以比较快的速度在切换。这样就引入了进程切换和进程调度的概念了。进程调度应该是操作系统的核心功能了，它非常的复杂。

尽管刚出Linux开发为的是桌面操作系统，但现在服务器，嵌入式设备，个人pc都会使用它，不同领域对进程调度的差异非常大，所以要考虑整体的平衡性。Linux进程在调度器中被分为三种：

交互式进程：大量的人机交互，所以会有大量的睡眠状态，等待用户操作。例如：编辑器，这类进程需要比较高的响应速度。

批处理进程：这类进程需要大量的CPU资源，但是响应延迟可以忍受，比如：视频编码，算法；

实时进程：对调度延迟要求最高。比如：视频播放

在Linux中，线程和进程一视同仁，所以讲到进程调度，也包含了线程调度。

Linux调度器的简史

Linux进程调度，有一段非常有趣的历史。在2.5版本之前，Linux采用传统的UNIX调度算法。由于没有考虑到SMP，所以SMP不支持。性能表现就非常不好。

所以在后来的2.5版本中，进行了大改。采用了O（1）的算法，之所以O(1)，因为它的运行时间是常量，与系统的任务数量是无关的。该调度器增加了对SMP的支持。但是在许多的桌面交互进程的响应时间却表现不是很好。

在之后的2.6版本中，调度器再一次的大的改动。2.6.23的版本中，完全公平调度器（CFS）最终成为Linux调度算法。

Linux的进程调度基于调度类。每个调度类都有一个特定优先级。每一个不同的调度类，都有不同的调度算法，就是为了满足不同的需要。也许手机中的Linux和服务器的Linux调度器准则也是不一样。

Linux内核有两个调度类：CFS和实时调度类。

CFS

CFS 调度程序并不采用严格规则来为一个优先级分配某个长度的时间片，而是为每个任务分配一定比例的 CPU 处理时间。每个任务分配的具体比例是根据nice值来计算的。nice值的范围从 -20 到 +19，数值较低的nice值表示较高的相对优先级。具有较低nice值的任务，与具有较高nice值的任务相比，会得到更高比例的处理器处理时间。默认nice值为 0。

为什么叫nice？当一个任务增加了它的nice，说明它的优先级降低了，进而对其他任务变得nice

CFS 调度程序没有直接分配优先级。相反，它通过每个任务的变量 vruntime 以便维护虚拟运行时间，进而记录每个任务运行多久。虚拟运行时间与基于任务优先级的衰减因子有关，更低优先级的任务比更高优先级的任务具有更高衰减速率。对于正常优先级的任务（nice值为 0），虚拟运行时间与实际物理运行时间是相同的。下面分析一下 CFS 调度程序是如何工作的。

假设有两个任务，它们具有相同的nice值。一个任务是 I/O 密集型而另一个为 CPU 密集型。通常，I/O 密集型任务在运行很短时间后就会阻塞以便等待更多的 I/O；而 CPU 密集型任务只要有在处理器上运行的机会，就会用完它的时间片。

因此，I/O 密集型任务的虚拟运行时间最终将会小于 CPU 密集型任务的，从而使得 I/O 密集型任务具有更高的优先级。这时，如果 CPU 密集型任务在运行，而 I/O 密集型任务变得有资格可以运行（如该任务所等待的 I/O 已成为可用)，那么 I/O 密集型任务就会抢占 CPU 密集型任务。

实时调度

采用 SCHED_FIFO 或 SCHED_RR 实时策略来调度的任何任务，与普通（非实时的）任务相比，具有更高的优先级。

Linux 采用两个单独的优先级范围，一个用于实时任务，另一个用于正常任务。实时任务分配的静态优先级为 0〜99，而正常任务分配的优先级为 100〜139。

这两个值域合并成为一个全局的优先级方案，其中较低数值表明较高的优先级。正常任务，根据它们的nice值，分配一个优先级；这里 -20 的nice值映射到优先级 100，而 +19 的nice值映射到 139。下图显示了这个方案。

CFS 性能

Linux CFS 调度程序釆用高效算法，以便选择运行下个任务。每个可运行的任务放置在红黑树上（这是一种平衡的、二分搜索树，它的键是基于虚拟运行时间的）。这种树如下图所示：

当一个任务变成可运行时，它被添加到树上。当一个任务变成不可运行时（例如，当阻塞等待 I/O 时），它从树上被删除。一般来说，得到较少处理时间的任务（虚拟运行时间较小）会偏向树的左侧；得到较多处理时间的任务会偏向树的右侧。

根据二分搜索树的性质，最左侧的结点有最小的键值；从 CFS 调度程序角度而言，这也是具有最高优先级的任务。由于红黑树是平衡的，找到最左侧结点会需要操作（这里 N 为树内结点总数）。不过，为高效起见，Linux 调度程序将这个值缓存在变量 rb_leftmost 中，从而确定哪个任务运行只需检索缓存的值。

总结

本文没有特别复杂的一些细节，只是把原理告诉大家。没有告诉进程权重的概念，觉得大部分不是做内核开发，没有必要掌握的太细。只需要把原理弄懂即可，也足够。

觉得不错，记得转发，关注！