Linux任务调度(4)

演进过程 ##

首先，再次回顾下下Linux进程调度器的一个发展历史：

• v0.01~v2.4.x: the very first scheduler，复杂度O(n)
• v2.6.0~v2.6.22: O(1) scheduler，复杂度O(1)
• v2.6.23~: Completely Fair Scheduler (CFS)，复杂度O(log(n))

前一篇文章中我们介绍了v0.01版本中的调度器实现，复杂度为O(n)，在v0.01内核实现中写死了最多可调度的任务数量，只能算作是一个toy！随着从v0.01~v2.4.x版本中的优化，能调度的任务数量也上来了，但是复杂度还是O(n)。O(1)调度器对其进行了优化，但是其启发式算法来识别、奖惩交互性的逻辑难以建模、理解、维护、优化。

O(1)调度器的问题 ##

随着 2.6.0 版本的临近，一些开发人员担心 CPU 调度程序的问题会让这个稳定版本系列垮台。交互性能差、NUMA 系统支持不佳等等的抱怨很常见。随着时间的推移，大部分问题都已得到解决，大量的交互工作和域调度程序已经解决了大部分问题。近年来，有关调度程序的投诉相对较少。

然而，2.6 调度程序的复杂性仍然困扰着一些人。尤其是交互性工作，添加了大量非常晦涩的代码。调度程序竭尽全力尝试识别交互式任务并相应地提高其优先级。这个过程涉及到许多奇怪的计算，很难理解，更不用说改进了。

比CFS更早的探索 ##

楼梯调度器 ##

内核开发人员 Con Kolivas 于2004年提出了 “楼梯调度算法(Starecase Deadline Scheduler)”，简称。Con Kolivas 参与了大部分交互工作，他发布了“楼梯调度程序”补丁的新版本，该补丁旨在大大简化调度程序，同时提高交互响应；它删除了 498 行代码，同时添加了不到 200 行代码。删除的大部分内容是“黑魔法”交互计算；它全部被一个相对简单的、基于等级的方案所取代。

楼梯调度程序为每个 CPU 设置一个多优先级运行队列。最初，每个进程按照其基本优先级确定的等级进入运行队列；然后调度程序可以以常见的方式找到并运行最高优先级的进程。到目前为止，与O(1)相比没有太大变化。

在当前的O(1)调度程序中，用完其时间片的进程将被移至单独的“过期”运行队列（expire runqueue）；它们在那里一直等待，直到活跃运行队列（active runqueue）中的其余进程也用完它们的时间片（或被阻塞），此时二者交换后才能被调度。

而楼梯调度程序中删除了expired runqueue这个设计，时间片用光的进程，其优先级将被调低，并据此重新计算一个时间片，然后将其放回到新优先级对应的队列中。因此，它可以继续运行，但优先级较低。当它耗尽这个时间片时，它再次向下移动，一直这样重复。

当其从最低优先级队列掉出来时，它的优先级、时间片可以被重置并重新放入runqueue，但是其优先级比原来初始优先级低一级、时间片+1。

ps：当时内核社区还不愿意在稳定系列中进行另一次重大调度程序更改，很多人希望看到 2.6 真正稳定下来。然而，这个补丁似乎值得考虑，因为它简化了内核的复杂部分。

旋转楼梯调度器 ##

2007年，Con Kolivas继续提出了 “旋转楼梯截止时间调度器(Rotating Staircase Deadline Scheduler, RSDL)”，旋转楼梯调度器，是对楼梯调度器的增强，为什么呢？我个人认为，旋转楼梯调度器更好的建模了优先级、公平性、响应性、解决饿死等的问题，它更好理解和维护。

简而言之，CPU调度似乎是一项无法完美解决的工作。尽管开发者不断优化调度算法，但总会有某些类型的工作负载得不到很好的调度服务，特别是对交互型任务要求响应迅速的用户。现在的调度器为了提高交互式进程的响应,已经发展出了非常复杂的优化手段。但复杂的代码也带来维护困难，而用户对响应时间的抱怨仍未止息。CPU调度需要持续改进，才能更好平衡不同类型任务的需要。

Con Kolivas长期致力于改进交互性的工作，RSDL调度器试图通过相对简单的设计来提供良好的交互响应、完全的公平性和有界的延迟。这项工作吸收了Con早期楼梯调度器(2004年6月报道过)的思想,但实现方法上有明显不同。

与许多调度器一样，RSDL维护一个优先级数组，如上图所示。

• 在每个级别上都有一个要求以该优先级运行的进程列表，每个进程在该优先级上都拥有一个执行时间配额。最高优先级的进程优先被调度，调度器使用典型的轮转算法在它们之间进行切换。
• 当一个进程在给定优先级上的配额用完时，它会被降至下一优先级，并获得一个新的配额。因此该进程可以继续运行，但只能在高优先级进程都运行过后。随着进程在这楼梯结构中下降，它们必须越来越多地与低优先级进程竞争，这些低优先级进程一直在低级别队列上耐心等待。最终结果是，即使是最低优先级的进程，最终也能获得至少一点CPU时间，实现公平性。
• 这个调度器的一个有趣特性是,每个优先级都有自己的配额。一旦最高优先级用完了配额，无论这些进程是否用完了自己的CPU时间配额，所有在这一级运行的进程都会被推到下一更低的级别。通过这种“次要旋转”机制，等待在较低优先级的进程只需要在有界时间内等待，之后所有其他进程就会运行在它们这一级。因此任何等待运行的进程的最大延迟是有界的，并且可以通过计算确定，这个调度器不会出现饥饿。
• 当进程用完它们的时间后，它们会被移动到另一个数组，称为“过期”数组。在那里，它们的优先级被重置。过期数组中的进程不运行，直到在当前活动数组中不再有进程会被调度。此时，会发生“主要旋转”，活动数组和过期数组交换，整个进程调度序列从头开始重新启动。

与O(1)调度器对比的话，O(1)调度器通过跟踪每个进程睡眠事件来确定是否是交互任务然后再决定是否奖励它们。RSDL放弃了所有这些。相反，进入睡眠的进程在较高优先级运行时应该不会使用完它们的时间配额。这样和那些CPU密集型容易耗光时间片的比，它们自然处于有利地位。如果一个进程在主要旋转期间睡眠，它的优先级、时间片配额会被加回到当前运行队列的对应等级的队列中。因此，即使其他高优先级进程在此期间一直在运行并通过次要旋转被降到更低优先级，该进程也仍能以高优先级运行。

所有这些合起来就进一步改善了程序的交互性。

ps：RSDL调度器确实建模上更容易理解了，而且据不少内核开发人员反馈这个实现方案效果确实不错，之前O(1)调度器存在的问题，打上这个RSDL调度器的补丁后就消失了，大家呼声很高。但是由于Torvalds、Ingo等人坚持没有证明其有效性Con Kolivas对此也表达了质疑，最终吧RSDL调度器没有进入内核主线。

CFS调度器诞生 ##

调度器主要维护人人员Ingo，借鉴了RSDL算法对于公平性的建模，提出了 Complete Fair Scheduler （CFS，完全公平调度器），通过虚拟运行时间vruntime来建模调度的公平性，同样也可以解决公平性、饿死、交互性问题。并且Ingo还实现了一个支持可插拔自定义调度器实现的方案，而这些都是之前Con Kolivas极力主张并遭到Torvalds和Ingo反对并拒绝掉的。Con Kolivas对此感觉到很愤怒，于是他最终下决定离开了内核开发社区。

ps：可以了解下对ck的访谈，了解下他为什么离开内核开发社区：https://geek.digit.in/community/threads/why-i-quit-kernel-developer-con-kolivas.81361/。

我们这里不搞那些阴谋论哈，说实话，个人感觉CFS中通过vruntime量化统计并表征公平性的建模更容易理解并被接受。我们将在下面的小节中重点介绍CFS相关的知识。

CK，BFS又来了 ##

Con Kolivas消失了一段时间，直到后面2009年他又回到了Linux社区提出了 Brain Fucker Scheduler（BFS），业内很多开发人员反映将CFS切换到BFS之后，其在桌面上的交互响应、用户体验有不错的改善、提升，但是时至今日因为这样那样的原因BFS仍然是没有进入Linux内核主线的，它的宿命可能像RSDL一样，但是它的思路可能是对的，Linux没法提供一个通用的调度器来同时最佳适应服务器、桌面、移动设备、嵌入式设备，即使是CFS也无法胜任，内核应该允许在不同场景下采用适应性更好的调度器实现。但是Torvalds、Ingo更倾向于提供一个通用的解决方案。

本文小结 ##

本文介绍了O(1)调度器存在的问题，以及为调度器设计实现所努力钻研的Con Kolivas提出的几个经典调度算法“楼梯截止时间调度器”、“旋转楼梯截止时间调度器”的设计及实现，从中我们也了解了其中的一些对公平性、饿死问题、交互性问题的处理方法，也对方案建模、论证方案有效性了解了点相关知识。

篇幅原因，将另外开一篇文章重点介绍CFS的设计实现以及实际用法，怎么调度器还有什么花活吗？如果你感兴趣，不妨一起来学习下。

参考文献 ##

1. The staircase Scheduler,https://lwn.net/Articles/87729/