Linux 2.6任务调度器及其重要属性 （2）

除了 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 绑定型的任务对于 CPU 访问来说是无私的，因此其优先级减少（奖励）最多 5 个优先级。CPU 绑定的任务会通过将其优先级增加最多 5 个优先级进行惩罚。

任务到底是 I/O 绑定的还是 CPU 绑定的，这是根据交互性 原则确定的。任务的交互性指标是根据任务执行所花费的时间与睡眠所花费的时间的对比程度进行计算的。注意，由于 I/O 任务先对 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 缓存对于迁移过来的任务为冷的情况。