本文将回顾一下 Linux 2.6 的任务调度器及其最重要的一些属性。在深入介绍调度器的详细信息之前，让我们先来理解一下调度器的基本目标。
什么是调度器？
通常来说，操作系统是应用程序和可用资源之间的媒介。典型的资源有内存和物理设备。但是 CPU 也可以认为是一个资源，调度器可以临时分配一个任务在上面执行（单位是时间片）。调度器使得我们同时执行多个程序成为可能，因此可以与具有各种需求的用户共享 CPU。
调度器的一个重要目标是有效地分配 CPU 时间片，同时提供很好的用户体验。调度器还需要面对一些互相冲突的目标，例如既要为关键实时任务最小化响应时间，又要最大限度地提高 CPU 的总体利用率。下面我们来看一下 Linux 2.6 调度程序是如何实现这些目标的，并与以前的调度器进行比较。
早期 Linux 调度器的问题
O-notation 的重要性
O-notation 可以告诉我们一个算法会占用多少时间。一个 O(n) 算法所需要的时间依赖于输入的多少（与 n 是线性关系），而 O(n^2) 则是输入数量的平方。O(1) 与输入无关，可以在固定的时间内完成操作。
在 2.6 版本的内核之前，当很多任务都处于活动状态时，调度器有很明显的限制。这是由于调度器是使用一个复杂度为 O(n) 的算法实现的。在这种调度器中，调度任务所花费的时间是一个系统中任务个数的函数。换而言之，活动的任务越多，调度任务所花费的时间越长。在任务负载非常重时，处理器会因调度消耗掉大量的时间，用于任务本身的时间就非常少了。因此，这个算法缺乏可伸缩性。
在对称多处理系统（SMP）中，2.6 版本之前的调度器对所有的处理器都使用一个运行队列。这意味着一个任务可以在任何处理器上进行调度 —— 这对于负载均衡来说是好事，但是对于内存缓存来说却是个灾难。例如，假设一个任务正在 CPU-1 上执行，其数据在这个处理器的缓存中。如果这个任务被调度到 CPU-2 上执行，那么数据就需要先在 CPU-1 使其无效，并将其放到 CPU-2 的缓存中。
以前的调度器还使用了一个运行队列锁；因此在 SMP 系统中，选择一个任务执行就会阻碍其他处理器操作这个运行队列。结果是空闲处理器只能等待这个处理器释放出运行队列锁，这样会造成效率的降低。
最后，在早期的内核中，抢占是不可能的；这意味着如果有一个低优先级的任务在执行，高优先级的任务只能等待它完成。
Linux 2.6 调度器简介
2.6 版本的调度器是由 Ingo Molnar 设计并实现的。Ingo 从 1995 年开始就一直参与 Linux 内核的开发。他编写这个新调度器的动机是为唤醒、上下文切换和定时器中断开销建立一个完全 O(1) 的调度器。触发对新调度器的需求的一个问题是 Java? 虚拟机（JVM）的使用。Java 编程模型使用了很多执行线程，在 O(n) 调度器中这会产生很多调度负载。O(1) 调度器在这种高负载的情况下并不会受到太多影响，因此 JVM 可以有效地执行。
2.6 版本的调度器解决了以前调度器中发现的 3 个主要问题（O(n) 和 SMP 可伸缩性的问题），还解决了其他一些问题。现在我们将开始探索一下 2.6 版本的调度器的基本设计。
主要的调度结构
首先我们来回顾一下 2.6 版本的调度器结构。每个 CPU 都有一个运行队列，其中包含了 140 个优先级列表，它们是按照先进先出的顺序进行服务的。被调度执行的任务都会被添加到各自运行队列优先级列表的末尾。每个任务都有一个时间片，这取决于系统允许执行这个任务多长时间。运行队列的前 100 个优先级列表保留给实时任务使用，后 40 个用于用户任务（参见图 1）。我们稍后将来看一下为什么这种区别非常重要。
图 1. Linux 2.6 调度器的运行队列结构
除了 CPU 的运行队列（称为活动运行队列（active runqueue））之外，还有一个过期运行队列。当活动运行队列中的一个任务用光自己的时间片之后，它就被移动到过期运行队列（expired runqueue） 中。在移动过程中，会对其时间片重新进行计算（因此会体现其优先级的作用；稍后会更详细地介绍）。如果活动运行队列中已经没有某个给定优先级的任务了，那么指向活动运行队列和过期运行队列的指针就会交换，这样就可以让过期优先级列表变成活动优先级的列表。
调度器的工作非常简单：它在优先级最高的队列中选择一个任务来执行。为了使这个过程的效率更高，内核使用了一个位图来定义给定优先级列表上何时存在任务。因此，在大部分体系架构上，会使用一条 find-first-bit-set 指令在 5 个 32 位的字（140 个优先级）中哪一位的优先级最高。查找一个任务来执行所需要的时间并不依赖于活动任务的个数，而是依赖于优先级的数量。这使得 2.6 版本的调度器成为一个复杂度为 O(1) 的过程，因为调度时间既是固定的，而且也不会受到活动任务个数的影响。
更好地支持 SMP 系统
那么什么是 SMP 呢？SMP 是一种体系架构，其中多个 CPU 可以用来同时执行各个任务，它与传统的非对称处理系统不同，后者使用一个 CPU 来执行所有的任务。SMP 体系架构对多线程的应用程序非常有益。
尽管优先级调度在 SMP 系统上也可以工作，但是它这种大锁体系架构意味着当一个 CPU 选择一个任务进行分发调度时，运行队列会被这个 CPU 加锁，其他 CPU 只能等待。2.6 版本的调度器不是使用一个锁进行调度；相反，它对每个运行队列都有一个锁。这样允许所有的 CPU 都可以对任务进行调度，而不会与其他 CPU 产生竞争。
另外，由于每个处理器都有一个运行队列，因此任务通常都是与 CPU 密切相关的，可以更好地利用 CPU 的热缓存。
任务抢占
Linux 2.6 版本调度器的另外一个优点是它允许抢占。这意味着当高优先级的任务准备运行时低优先级的任务就不能执行了。调度器会抢占低优先级的进程，并将这个进程放回其优先级列表中，然后重新进行调度。
但是请等一下，还有更多功能呢！
似乎 2.6 版本调度器的 O(1) 特性和抢占特性还不够，这个调度器还提供了动态任务优先级和 SMP 负载均衡功能。下面就让我们来讨论一下这些功能都是什么，以及它们分别提供了哪些优点。
动态任务优先级
为了防止任务独占 CPU 从而会饿死其他需要访问 CPU 的任务，Linux 2.6 版本的调度器可以动态修改任务的优先级。这是通过惩罚 CPU 绑定的任务而奖励 I/O 绑定的任务实现的。I/O 绑定的任务通常使用 CPU 来设置 I/O，然后就睡眠等待 I/O 操作完成。这种行为为其他任务提供了 CPU 的访问能力。
用户响应能力更好
与用户进行通信的任务都是交互型的，因此其响应能力应该比非交互式任务更好。由于与用户的通信（不管是向标准输出上发送数据，还是通过标准输入等待输入数据）都是 I/O 绑定型的，因此提高这些任务的优先级可以获得更好的交互式响应能力。
由于 I/O 绑定型的任务对于 CPU 访问来说是无私的，因此其优先级减少（奖励）最多 5 个优先级。CPU 绑定的任务会通过将其优先级增加最多 5 个优先级进行惩罚。
任务到底是 I/O 绑定的还是 CPU 绑定的，这是根据交互性 原则确定的。任务的交互性指标是根据任务执行所花费的时间与睡眠所花费的时间的对比程度进行计算的。注意，由于 I/O 任务先对 I/O 进行调度，然后再进行睡眠，因此 I/O 绑定的任务会在睡眠和等待 I/O 操作完成上面花费更多的时间。这会提高其交互性指标。
有一点值得注意，优先级的调整只会对用户任务进行，对于实时任务来说并不会对其优先级进行调整。
SMP 负载均衡
在 SMP 系统中创建任务时，这些任务都被放到一个给定的 CPU 运行队列中。通常来说，我们无法知道一个任务何时是短期存在的，何时需要长期运行。因此，最初任务到 CPU 的分配可能并不理想。
为了在 CPU 之间维护任务负载的均衡，任务可以重新进行分发：将任务从负载重的 CPU 上移动到负载轻的 CPU 上。Linux 2.6 版本的调度器使用负载均衡（load balancing） 提供了这种功能。每隔 200ms，处理器都会检查 CPU 的负载是否不均衡；如果不均衡，处理器就会在 CPU 之间进行一次任务均衡操作。
这个过程的一点负面影响是新 CPU 的缓存对于迁移过来的任务来说是冷的（需要将数据读入缓存中）。
记住 CPU 缓存是一个本地（片上）内存，提供了比系统内存更快的访问能力。如果一个任务是在某个 CPU 上执行的，与这个任务有关的数据都会被放到这个 CPU 的本地缓存中，这就称为热的。如果对于某个任务来说，CPU 的本地缓存中没有任何数据，那么这个缓存就称为冷的。
不幸的是，保持 CPU 繁忙会出现 CPU 缓存对于迁移过来的任务为冷的情况。
挖掘更多潜能
2.6 版本调度器的源代码都很好地封装到了 /usr/src/linux/kernel/sched.c 文件中。我们在表 1 中对在这个文件中可以找到的一些有用的函数进行了总结。
| 函数名 | 函数说明 |
|---|---|
| schedule | 调度器主函数。调度优先级最高的任务执行。 |
| load_balance | 检查 CPU，查看是否存在不均衡的情况，如果不均衡，就试图迁移任务。 |
| effective_prio | 返回任务的有效优先级（基于静态策略，但是可以包含任何奖励和惩罚）。 |
| recalc_task_prio | 根据任务的空闲时间确定对任务的奖励或惩罚。 |
| source_load | 适当地计算源 CPU（任务从中迁移出的 CPU）的负载。 |
| target_load | 公平地计算目标 CPU（任务可能迁移到的 CPU）的负载。 |
| migration_thread | 在 CPU 之间迁移任务的高优先级的系统线程。 |
运行队列的结构也可以在 /usr/src/linux/kernel/sched.c 文件中找到。2.6 版本的调度器还可以提供一些统计信息（如果启用了CONFIG_SCHEDSTATS）。这些统计信息可以从 /proc 文件系统中的 /proc/schedstat 看到，它为系统中的每个 CPU 都提供了很多数据，包括负载均衡和进程迁移的统计信息。
展望
Linux 2.6 调度器从早先的 Linux 调度器已经跨越了一大步。它极大地改善了最大化利用 CPU 的能力，同时还为用户提供了很好的响应体验。抢占和对多处理器体系架构的更好支持使整个系统更接近于多桌面和实时系统都非常有用的操作系统。Linux 2.8 版本的内核现在谈论还为时尚早，但是从 2.6 版本的变化中，我们可以期望会有更多的好东西。