Linux® 内核继续不断发展并采用新技术，在可靠性、可伸缩性和性能方面获得了长足的发展。2.6 版本的内核最重要的特性之一是由 Ingo Molnar 实现的调度器。这个调度器是动态的，能够支持负载均衡，并以恒定的速度进行操作 —— O(1)。本文将介绍 Linux 2.6 调度器的这些属性连同更多内容。
本文将回顾一下 Linux 2.6 的任务调度器及其最重要的一些属性。在深入介绍调度器的周详信息之前，让我们先来理解一下调度器的基本目标。
什么是调度器？
通常来说，操作系统是应用程式和可用资源之间的媒介。典型的资源有内存和物理设备。但是 CPU 也能够认为是个资源，调度器能够临时分配一个任务在上面执行（单位是时间片）。调度器使得我们同时执行多个程式成为可能，因此能够和具备各种需求的用户共享 CPU。
调度器的一个重要目标是有效地分配 CPU 时间片，同时提供很好的用户体验。调度器还需要面对一些互相冲突的目标，例如既要为关键实时任务最小化响应时间，又要最大限度地提高 CPU 的总体利用率。下面我们来看一下 Linux 2.6 调度程式是如何实现这些目标的，并和以前的调度器进行比较。
早期 Linux 调度器的问题
 |
|
在 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) 的过程，因为调度时间既是固定的，而且也不会受到活动任务个数的影响。
文章整理：西部数码--专业提供域名注册、虚拟主机服务
http://www.west263.com
以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!
