Linux 调度器内幕

Linux®内核继续不断发展并采用新技术，在可靠性、可伸缩性和性能方面获得了长足的发展。2.6版本的内核最重要的特性之一是由IngoMolnar实现的调度器。这个调度器是动态的，可以支持负载均衡，并以恒定的速度进行操作——O(1)。本文将介绍Linux2.6调度器的这些属性以及更多内容。

本文将回顾一下Linux2.6的任务调度器及其最重要的一些属性。在深入介绍调度器的详细信息之前，让我们先来理解一下调度器的基本目标。

什么是调度器？

通常来说，操作系统是应用程序和可用资源之间的媒介。典型的资源有内存和物理设备。但是CPU也可以认为是一个资源，调度器可以临时分配一个任务在上面执行（单位是时间片）。调度器使得我们同时执行多个程序成为可能，因此可以与具有各种需求的用户共享CPU。

调度器的一个重要目标是有效地分配CPU时间片，同时提供很好的用户体验。调度器还需要面对一些互相冲突的目标，例如既要为关键实时任务最小化响应时间，又要最大限度地提高CPU的总体利用率。下面我们来看一下Linux2.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系统中，选择一个任务执行就会阻碍其他处理器操作这个运行队列。结果是空闲处理器只能等待这个处理器释放出运行队列锁，这样会造成效率的降低。

最后，在早期的内核中，抢占是不可能的；这意味着如果有一个低优先级的任务在执行，高优先级的任务只能等待它完成。

回页首

Linux2.6调度器简介

2.6版本的调度器是由IngoMolnar设计并实现的。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.Linux2.6调度器的运行队列结构

除了CPU的运行队列（称为活动运行队列（activerunqueue））之外，还有一个过期运行队列。当活动运行队列中的一个任务用光自己的时间片之后，它就被移动到过期运行队列（expiredrunqueue）中。在移动过程中，会对其时间片重新进行计算（因此会体现其优先级的作用；稍后会更详细地介绍）。如果活动运行队列中已经没有某个给定优先级的任务了，那么指向活动运行队列和过期运行队列的指针就会交换，这样就可以让过期优先级列表变成活动优先级的列表。

调度器的工作非常简单：它在优先级最高的队列中选择一个任务来执行。为了使这个过程的效率更高，内核使用了一个位图来定义给定优先级列表上何时存在任务。因此，在大部分体系架构上，会使用一条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的热缓存。

任务抢占

Linux2.6版本调度器的另外一个优点是它允许抢占。这意味着当高优先级的任务准备运行时低优先级的任务就不能执行了。调度器会抢占低优先级的进程，并将这个进程放回其优先级列表中，然后重新进行调度。

回页首

但是请等一下，还有更多功能呢！

似乎2.6版本调度器的O(1)特性和抢占特性还不够，这个调度器还提供了动态任务优先级和SMP负载均衡功能。下面就让我们来讨论一下这些功能都是什么，以及它们分别提供了哪些优点。

动态任务优先级

为了防止任务独占CPU从而会饿死其他需要访问CPU的任务，Linux2.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上。Linux2.6版本的调度器使用负载均衡（loadbalancing）提供了这种功能。每隔200ms，处理器都会检查CPU的负载是否不均衡；如果不均衡，处理器就会在CPU之间进行一次任务均衡操作。

这个过程的一点负面影响是新CPU的缓存对于迁移过来的任务来说是冷的（需要将数据读入缓存中）。

记住CPU缓存是一个本地（片上）内存，提供了比系统内存更快的访问能力。如果一个任务是在某个CPU上执行的，与这个任务有关的数据都会被放到这个CPU的本地缓存中，这就称为热的。如果对于某个任务来说，CPU的本地缓存中没有任何数据，那么这个缓存就称为冷的。

不幸的是，保持CPU繁忙会出现CPU缓存对于迁移过来的任务为冷的情况。

回页首

挖掘更多潜能

2.6版本调度器的源代码都很好地封装到了/usr/src/linux/kernel/sched.c文件中。我们在表1中对在这个文件中可以找到的一些有用的函数进行了总结。

表1.Linux2.6调度器的功能 函数名 函数说明

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都提供了很多数据，包括负载均衡和进程迁移的统计信息。

回页首

展望

Linux2.6调度器从早先的Linux调度器已经跨越了一大步。它极大地改善了最大化利用CPU的能力，同时还为用户提供了很好的响应体验。抢占和对多处理器体系架构的更好支持使整个系统更接近于多桌面和实时系统都非常有用的操作系统。Linux2.8版本的内核现在谈论还为时尚早，但是从2.6版本的变化中，我们可以期望会有更多的好东西。