发布时间：2023-01-23 08:00
1. 简介 3
1.1 文件综述 3
1.2 Linux内核著作 3
1.3 排版约定 4
1.4 关于该文档 4
1.5 随书CD 4
2. Linux内核源码 5
2.1 获取源码 5
2.2 内核版本管理 5
2.3 代码组织 5
3. 进程与线程综述 6
3.1 程序和进程 6
3.2 线程 6
3.3 调度 6
3.4 CPU与IO受限的线程 7
3.5 上下文切换 7
3.6 Linux进程与线程 8
4. Linux调度目标 9
4.1 Linux的目标市场及他们在调度器上所作出的努力 9
4.2 效率 9
4.3 交互性 9
4.4 公平性与饥饿预防 10
4.5 SMP调度 10
4.6 SMT调度 10
4.7 NUMA调度 11
4.8 软实时调度 11
4.9 调度性能透视 11
5. Linux 2.6.8.1调度器 13
5.1 起源及O(1)算法的重要性 13
5.2 运行队列 13
5.3 优先级数组 15
5.4 运算优先级及时间片 17
5.5 休眠眠与唤醒任务 19
5.6 主调度函数 21
5.7 负载均衡 22
5.8 软实时调度 23
5.9 NUMA调度 24
5.10 调度器调整 25
6. Linux 2.4.x调度器 27
6.1 算法 27
6.2 优势 28
6.3 劣势 28
7. Linux调度器的未来 30
7.1 调整实现 vs. 算法变换 30
8. 附录 31
8.1 致谢 31
8.2 关于作者 31
8.3 遵循法规（GNU FDL） 31
引用 32
大量与复杂的代码源使得近年来linux的发展相对迅速。这是由于他被大量的业余爱好者，家庭用户，商业用户及教育协会所接受。Linux 内核邮件列表（内核开发者的邮件列表）在2004年的夏天观察到，几乎平均每天都有50到100个开发者发出300份消息。这个数字不包括那些专注于体系结构的论坛，那些论坛的消息是另外统计的。在2003年八月到2004年八月的一年中，超过16000份不同大小的更新被提交给了官方linux内核进行审批。高速的发展导致非常少的内核重要部件在应用时能够被文档化。
文档的匮乏导致内核开发者，学生，研究者，甚至是内核老手都难以及时理解内核实现的变化。对所有这些人来说，实现级别的文档给他们带来许多好处。很显然的，那些希望能够对内核开发做出贡献的人来说，他们必须对现有的内核实现有个比较全面的了解。但是，为什么学生和研究者也应该了解现有内核实现呢？难道是了解内核理论与内核大致工作机理还不够吗？这是由于，Linux的内核的开发重点是其实用性，而不是其理论的合理性，所以，许多关于linux内核改变的决断都是基于其使用的真实效果。这意味着，大多情况下，linux的实现会从理论基础中分离出来。通常这种情况发生时，都是出于一些很重要的原因。在实践的过程中，理解被应用的算法，以及理论与实际产生分歧的推理过程，理解理论的缺陷，这是未来算法发展的几大要素。
由于上述的种种原因，linux需要针对其内核实现的专门性文档，而不仅仅是开发者在一时间设计决断的基础理论。这篇描述linux 2.6.8.1调度器的文章是受到了 Mel Gorman 所提出的关于linux虚拟内存系统的论文的启发，该论文是其领域内被最多linux虚拟内存系统的开发者所引用，受到最高评价的文章。
这篇文章的目的是提供一份深入的关于linux 2.6.8.1调度器的文档。希望这篇文章能对众多希望了解调度器的实现的内核开发者和学生及研究员提供些许帮助。同时也希望这篇文章能够减少读者深入了解调度器所需要花的时间。同样 Mr.Gorman 关于linux 2.4.20虚拟内存系统的文章对理解2.6.x系列内核的虚拟内存系统仍很有帮助，希望这篇文章也能对2.6.8.1之前版本的linux内核起到重要作用。
虽然linux内核缺乏及时更新的代码级的文档，但是仍有许多有用的高质量引导性文档。如果你希望能够深入理解linux内核的构建，所有下述的这些文章都值得一看。
《linux kernel development》 Robert Love
这本书涵盖了整个linux 2.6.x系列内核,直到2004年的秋天，恐怕这是唯一一本做到涵盖整个2.6.x系列内核的书籍。本书给出了关于每个linux组件的概述，同时描述了他们如何组织在一起。其中，包括写的非常好的linux2.6.x调度器部分。
上述这本书可能是唯一一本涵盖整个linux2.6.x内核的书籍，但是仍然有许多其他关于linux2.4.x内核的书籍，同样对理解linux2.6.x内核组件有很大的帮助。这些书籍包括：
《understand the linux kernel》 Daniel Bovet and Macro Cesati
《linux device driver》 Alessando Rubini and Jonathan
《IA-64 linux kernel》 David and Stephane
《understanding the linux virtual memory manager》 Mel Gorman
Linux文档工程是另外一个非常好的文档源。他提供的许多文档涵盖了linux各派别的许多方面内容以及linux内核的相关内容。
过去在官方LKML的讨论成果在许多网站上都可以找到。简单的在搜索引擎（例如google）上输入LKML就可以找到你想要的内容。
同时，随内核源码发布的文档或多或少的也会给我们提供些许帮助。他可以在Documentation/directory下被找到。
不幸的是Linux2.6.x内核附带的文档对本文所要描述的调度器的描述提供不了多大的帮助，因为调度器在2.4.x系列内核与2.6.x系列内核之间被修改的太多了。
新概念与URL被排版为斜体。二进制码，命令与包名被排版为粗体。代码，宏与文件路径是等宽字体。包含文件的路径两端会加上尖括号，这些文件能够在linux源码的include目录下找到。所有文件的默认根路径为linux内核源码的根目录。结构体中的字段在被使用时，会从结构体引出一个箭头指向该字段。
下载地址：http://josh.trancesoftware.com/linux
这份文档的附带CD包含linux2.6.8.1内核源码，一个给调度器代码打注释的升级程序，以及一份该文档电子版文档。该CD是ISO-9660格式的CD，可以用于所有现用的操作系统。为了使用注释补丁，需要将补丁包移动到linux源码的kernel目录下，运行如下命令：
Patch -p0 < sched_comments.patch
Linux的内核源码永远是学习linux内核最好的资源。在尝试完全了解linux内核的旅途中，没有什么文档是可以完全代替内核源码本身的。这份文档会在很大程度上引用内核源码。你可以在Linux Kernel Achives上找到内核源码。(http://www.kernel.org)主页上列出了各个版本内核的最新发布版，其中包括内核源码，升级补丁以及修改日志。所有linux内核的发布版可以在他的FTP站点上找到。(ftp://ftp.kernel.org/)
Linux内核版本号的格式为：W.X.Y.Z。W位置上的数字很少会发生更改，当且仅当内核发生了非常重大改变，以至于使用在第一个版本的linux上的大多数软件都无法运行的情况下，他才会发生变化。这种情况在linux的历史上只发生过一次。（这就是本文档所关注的版本号以2开头的原因）
X位置的数字表示linux内核系列。该位置上的数字若是偶数则代表该系列是一个稳定的发布系列，若是奇数则代表该系列是个发展中的系列。根据历史，系列号每两年改变一次。旧版本的系列仍然在开发，只要仍有对他感兴趣的人存在。
Y位置的数字代表版本号。版本号在每个发布版发布时都会加1。通常情况下，他是内核版本的最后一个位置，但偶尔也会遇到一个发布版本由于一些重大错误而需要改正的情况。在上述这种情况下，Z位置就出现了。Z位置的数字第一次出现是在2.6.8.1版本发布的时候。2.6.8内核在NFS的实现上存在一个非常严重的错误。这个错误在2.6.8版本发布后被迅速发现，这样在修复了该错误后，2.6.8.1版本就被发布了，该版本除修复了上述错误外，与2.6.8版本基本无区别。
在每个linux源码包下都包含有许多子目录。阅读本文档时，了解下面这些子目录会给你带来很大的帮助：
Documentation：包含许多很好的内核相关文档及开发过程文档；
Arch：包含与计算机体系结构相关的代码，每个体系结构都有其所对应的子目录；
Include：包含头文件；
Kernel：包含主要的内核代码；
Mm：包含内核的内存管理代码。
在学习调度器之前，对进程与线程两大概念有个比较好的认识是非常重要的。详细描述进程与线程并不是本文档的主要目的，所有这里只提供一些我们必须知道的相关知识。我们强烈建议本文的读者能够从其他相关的材料中深入学习进程与线程的相关知识，以加深对本文的体会。在参考书目中我们提供了一些非常好的书目[2，3，4，5]。
程序的执行，就是一系列指令与数据交织在一起完成一项工作。一个进程就是一个程序的实例。以此类推，程序就像是C++或JAVA中的类，而进程就像是对象。进程就是一个被创建用以具体表现程序运行过程中所经历状态的抽象概念。这意味着进程需要记录与线程或线程执行相关的数据。这些数据包括，变量，硬件状态以及一段地址空间的内容。
一个进程可以拥有许多执行的线程一起工作来完成其目的。这些线程被适宜的命名为线程。内核必须记录每一个线程的堆栈以及硬件状态，同时无论是否需要，内核仍必须记录进程内部的执行溢出。通常情况下，线程共享进程的地址空间，但这并不是必须的。我们必须了解的是，在每一个CPU时间片内，只有一个线程能够得到执行，这就是内核需要CPU调度器的原因。我们可以在大多数浏览器内找到一个进程拥有多线程这种情况。通常会有一个线程来处理用户接口事件，一个线程来处理网络事务，一个线程来生成网页。
多任务内核宏观上允许在同一时间有多个进程存在，并且每个进程能够运行地就像系统中只有其一个进程在运行一般。进程运行时是没有必要了解其他进程的运行情况的，除非他们从一开始就被设计为需要相互了解。这使得进程更容易开发，运行及维护。尽管从微观的角度，CPU在一个时间片内只能执行一个进程的一个线程，但在宏观上，许多进程的线程是同时在被运行的。这是因为每个线程执行完一个非常短的时间片后，另外的线程会得到运行下一个时间片的机会。内核的调度器就是用以执行线程调度策略的，该策略内容包括在何时，在何地，线程会被运行多久等。正常情况下，调度器工作在其独自的由时钟中断唤醒的线程内。另外，他是通过系统调用或另一个希望放弃CPU的内核线程被调用的。每个线程都会被允许运行一个固定长的时间，然后CPU会通过上下文切换，切换至调度器线程，紧接着CPU再次通过上下文切换，切换至调度器选中的线程，如此往复。这样，一个关于CPU用法的策略就被提出了。
被执行的线程通常不是CPU受限就是IO受限。一些进程在使用CPU进行计算上消耗了大量的时间，而另外一些进程则在等待相对较慢的IO操作上消耗了大量的时间。例如，一个进行DNA排序的线程就是CPU受限的；一个由字处理程序获得输入的线程就是IO受限的，因为他在等待用户输入上消耗了大量的时间。一个线程是CPU受限还是IO受限，这通常并不是很明确的。调度器能做的就只是猜测。许多调度器的确对一个线程是否是CPU受限或是IO受限相当在意，对这些调度器而言，线程分类技术是其重要的组成部分。
调度器趋向于给与那些IO受限的进程更高的优先级去使用CPU。接受用户输入的程序通常都是IO受限的。即使是最快的打字员在每次敲击键盘之间都需要有一段思考的时间，在这段时间之内，程序只能等待。给予那些与人进行交互的程序以更高的优先级是非常重要的，因为当一个人希望获得计算机立即的响应时比一个人在等待大量的工作被完成时更容易察觉到计算机在速度与响应上的缺陷。
给予IO受限的程序更高的优先级对整个系统来说都是有益的，这并不单纯因为用户输入。因为IO操作通常都需要花上相当长的时间，让他们尽早开始是很有益处的。例如，一个需要从硬盘获取一小段数据的程序在获得其所需要的数据前要等上相当长一段时间。尽快地开始数据请求能够解放CPU，使其能在数据请求的这段时间内做一些另外的工作，同时能够使得提交数据请求的程序尽早的继续执行下去。本质上讲，这样更有效地平行了系统资源。硬盘驱动器在搜索数据的同时，CPU可以工作于其他的事，所以使两个资源尽可能尽早执行是大有益处的。CPU在硬盘驱动器获取数据的这段时间内可以做许多操作。
上下文切换就是从一个运行中的线程切换到另外一个线程的过程。这个过程包括，保存CPU寄存器的状态，加载新的状态，刷新高速缓冲存储器，以及改变当前的虚拟内存映射。在大多数体系结构中，上下文切换是一个代价高昂的操作，所以在这些体系结构中，他们的执行需要被尽可能的避免。在执行上下文切换所需要的这段时间中，计算机可以完成许多实际的工作。如何控制上下文切换的执行要根据体系结构而定，同时这并非内核调度器的一个部分，尽管如此，他的实现在很大程度上影响了调度器的设计工作。在linux的源码中，上下文切换的代码在以下两文件中被定义：
Include/asm-[arch]/mmu_context.h
Include/asm-[arch]/system.h
Linux使用了唯一的一种方法来实现进程与线程的抽象。在linux中，所有的线程可以被简单的看作是进程，只不过他们可以共享一些特定的资源。在linux中，任一进程可以被简单的看做是一组线程，但又不仅仅只是一组线程，因为这些线程共享着线程组ID以及其所必须的资源。为了表示进程与线程的区别，以免混淆，从此处开始，我们使用“任务”这个词来表示线程，值得一提的是，其在POSIX中并不代表线程这个意思。在下文中，进程与线程只有在真正需要区别他们两的情况下才会被使用到。在linux任务结构体task_struct中，TGID被存在tgid字段中。Linux会给每个线程分配一个PID([task_struct]->pid)，但是人们通常说的PID是指任务的TGID。值得一提的是，这个模型与牛分叉算法的结合使得linux中进程与线程的生成更加迅速且有效，然而在许多其他的操作系统中，产生进程的代价要比产生线程的代价要高昂的多。
可惜的是，关于linux进程与线程的更多实现细节已经超出本文所要讲述的内容范围。我们现在只需要知道的是，在linux中，进程仅仅是被当做一组线程的集合来看待。进程与线程之间并没有什么非常严格的界限。正因如此，linux只针对线程进行调度，本质上忽略了各线程所归属的进程的差别。
一个操作系统的调度算法在很大程度是是由该操作系统的目标市场所决定的，反之亦然。了解一个操作系统的目标市场对理解其调度器的调度目的和调度算法有很大的帮助。
Linux一开始的时候是由Linus Torvalds开发，用于其个人PC机上的。然而，无论linux的缘由如何，由于他在服务器上的优秀表现，现在已经被作为服务器操作系统被广泛接受。造成这种情况的原因各种各样，但绝不仅仅是因为以下这个事实：在linux内核之上运行的程序大部分都是为那些具有相对专业技巧的人士准备的。这个事实导致了linux声名狼藉的复杂性，以及未经提炼的图形用户接口选项，还有其后他服务器领域的归属。Linux在服务器市场的出现促进了他自身的发展，及其在服务器行业各方面的进步。Linux作为服务器操作系统的超凡本领在当今只有为数不多的几个操作系统能够比及，其中包括SUN公司的Sloaris和IBM的AIX。但是，linux在费用与法律上的便利使得许多公司也开始弃用Sloaris与AIX，转而使用linux。
尽管linux的名号在服务器操作系统领域已经相当出名，但是许多使用者和开发者认为，linux同样能在普通桌面PC机上去的成功。在过去的几年中，有股巨大的推动力在促使linux优化其内核，从而能够更快的进军桌面PC机市场。在这个过程中，可能最重要的一步要属Ingo Molnar为2.6.x版本的内核重写了调度器。Molnar了解桌面PC机市场与服务器市场的不同需求，在此基础上，他设计了他自己的调度器，结果该调度器使得基于2.6.x内核的linux发布版在桌面PC机上的表现得到大幅提升。Linux将目标同时瞄准桌面PC机市场及服务器市场给内核的调度器提出了更高的要求，这样，linux内核调度器成为了一个学习如何平衡来自不同市场的需求的学习用例。
Linux调度器的重要目标就是效率。这意味着，调度器必须在抑制其他请求的同时，尝试完成竟可能多的任务。例如，由于上下文切换的代价高昂，允许任务运行一段较长的时间片就能够提高效率。同样，由于调度器的代码经常被运行，其自身的运行速度也是调度效率的关键因素。作出调度决定的代码必须能运行的尽可能快。效率也会受到其他一些因素的影响，例如出于某些目的的交互，因为交互从本质上就代表了更多的上下文切换。然而，在将所有的请求置于一起考虑时，保证全局效率就是调度器最重要的目标。
保证交互性是linux调度器的一个重要目标，尤其是在linux正着力优化其在桌面系统的表现时。交互性处在效率的表层，但尽管如此他仍非常重要。一次按键，一次鼠标点击都可以是交互性的例子。这样的事件需要进行立即的处理，因为如果计算机不进行立即的处理，用户能够很明显的察觉到，并为每次计算机无法立即响应其操作而厌烦不已。但是，在编译程序或生成高分辨率的图片时，用户并不奢求马上获得响应。他们并不可能察觉到计算机在编译linux内核时是否多花了20秒钟的时间。用于交互性计算的调度器应该被设计成能够在规定时间内对用户交互作出响应。理想情况下，该规定的时间应该是用户无法感知到的时间间隔，从而使用户觉得计算机是立即作出响应的。
CPU对待各不同的任务时保持一定程度的公平是很重要的，这里所谓的公平就包括不让任何一个线程挨饿的约定。当一个线程由于不断有其他比他更高优先级的进程在运行而长时间无法得到运行时，饥饿现象就发生了。饥饿现象是不允许发生的，尽管由于用户定义或触发器设置，一些线程的优先级就是比另外一些的高。无论以何种方式，我们都必须在一些进程即将进入饥饿状态时，给予他们优先级的提升或立即的CPU抢占权。公平并不是意味着每个线程针对使用CPU时间都有相同的所有权及优先级，而是意味着不应该有线程进入到饥饿状态，或者不应该有线程能够欺骗CPU以获得更高的优先级或更多的CPU处理时间。
由于linux内核支持多处理器机制，他的调度器必须能够在多CPU的情况下还能正确地调度任务进行执行。这意味着，调度器必须清楚地了解什么任务在哪个CPU内部执行，确保同一时刻不会有相同的任务在不同的CPU内部被执行，并且能在大体上组织所有的任务在多CPU内有效地被调度。由于所有的CPU通常有权访问相同的内存及系统资源，调度器首要要考虑的是如何更好的利用处理器时间。在选择一个任务应在哪个CPU内被调度时，我们几乎没有理由认为某个CPU比其他CPU会更好。最常见的考虑因素就是超高速缓存区。如果尽可能在同一个CPU上调度一个任务，那么CPU对该任务进行高速缓存的可能性就大幅提升。
Linux支持在一块对称多线程(SMT)芯片上进行多线程调度。虽然SMT这个概念我们早已知晓，但是Intel公司的HT技术才使得SMT技术成为业界主流。本质上，每块SMT可以拥有多个共享固定资源的虚拟处理器。由于那些被共享的资源，虚拟处理器不应该被当做普通的处理器来对待。
Linux内核支持非一致内存访问(Non-Uniform Memory Access)，这意味着如果硬件允许，他能够在多个节点上跑一个单独的系统镜像。从硬件层次上讲，一个节点就好比是一台传统的单处理机或多处理机，他拥有他自己的CPU及内存。然而，NUMA系统将各节点视作一个有单一系统镜像的系统的一部分。这通常利用某种高速内联技术来实现，这种技术更像是在主板层面上连接各点，而非网络层面。这意味着，所有的CPU都有权利执行任何一个线程，所有节点的内存都可以通过同一个内存空间进行访问。NUMA帮助包括了解与SMP调度中类似的高速缓存问题，但同样也包括内存位置问题（当CPU正在执行的线程需要获取内存空间时，在系统内部移动线程的效率是很低的，因为内存操作需要花更多的时间去完成）。或许支持NUMA的调度器需要处理的最大的问题在于，系统内可能存在比大多SMP系统要多的多的CPU。普通的SMP系统大致会拥有2到8个CPU，但NUMA系统可能拥有成百上千个CPU。在这篇文章还未定稿时，SGI正运行着拥有512个处理器的NUMA系统。这是有史以来，在单一的linux系统镜像下能运行的处理器的最大数目。这也是2.6.8.1内核调度器的处理极限。
Linux调度器支持软实时调度。这意味着他能够有效地调度具有严格时间要求的任务。然而，虽然linux2.6.x内核有能力使那些对时间有严格要求的任务按期完成，但他也并不能保证所有的任务都能按期完成。实时任务被分配以特殊的调度模式，同时调度器给予他们比其他普通任务更高的优先级。实时调度模式包括先进先出模式，该模式基于先来先服务，允许实时任务一直被运行直至完成；同时实时调度模式还包括循环调度模式，该模式循环调度实时任务，从本质上其忽略系统中的非实时任务。
从调度器的角度而言，没有一个唯一的可以满足所有人要求的调度器性能的定义；也就是说，linux调度器没有一个唯一的性能指标。对好的调度器性能的定义经常导致一种相互妥协的情况出现，在某个方面提高其性能就会导致其其他方面的性能下降。一些linux调度器的改进能够提高其各方面的性能，但是这样的改进越来越少发生了。一个很好的关于性能妥协问题的例子就是，台式机，服务器及高性能计算时的性能平衡。
对于台式机用户而言，最重要的性能指标就是感知性能，就是机器对用户请求能多快作出响应，例如鼠标点击或按键事件。如果一个用户正在后台编译内核代码，在前台使用字处理器，该用户将很难感知到内核编译是否由于CPU需要对字处理程序按键的中断进行处理而多花了些许时间。对用户而言，此时最重要的是，当其按下一个按键时，计算机是否能够尽快的插入并显示出其希望输入的字符。这就要求CPU在用户按下按键时能够迅速地进行上下文切换，处理用户的请求。为了能够实现这些操作，要么当前运行的线程必须在其所用的时间片用完之前主动放弃处理器，要么CPU的时间片必须足够的短，以使得用户按下按键到当前时间片用完之间的这段延时不被用户所感知。由于上下文切换的代价高昂，上下文切换必须被最少化，然而还必须保证其能够足够频繁地进行，从而为用户提供良好的感知性能。更少的上下文切换意味着更高的效率，因为这样，更多的CPU时间被用于完成真正的工作，更少的时间被用于任务切换。更多的上下文切换意味着系统对用户输入作出更多的回应。在交互式的桌面系统中，我们希望调度器做到的是，让上下文切换足够频繁的进行以使用户能够在某种程度上获得计算机立即的响应，同时上下文切换的频率必须控制在一定的程度以防止系统变得效率低下。
服务器系统通常会比桌面系统更少的关注感知性能。他们更加关注的是系统的实际性能，也就是，减少一组工作所需要消耗的时间总和。由于用户通常能够容忍一个更长时间的响应延时，更多的重点被放在通过减少上下文切换从而提高全局效率上。如果三个复杂的访问一个被加载进内存的数据库的请求同时发生，最好是能让他们所花的总体时间最少，从而减少平均响应时间，而不是为了让结果同时返回而降低执行效率。向计算机提交数据库查询请求的个人或程序通常比往字处理程序中输入字符的个人对计算机响应时间的期望要低。但是，如果用户从FTP服务器上请求两个非常大的文件时，计算机在第一个文件传输完成后才开始传输第二个文件，这样通常会令人难以接受。因此，针对服务器系统而言，虽然人们对其的响应时间要求并不如台式机那么严格，但是其也同样被期待能尽可能地达到人们的响应期望。
HPC系统通常在处理需要几天几夜去解决的大型问题时要求最少的立即响应次数。当系统被授予了一组工作，完成这组工作的全局效率是最重要的因素，这意味着出于响应目的的上下文切换必须被最小化。HPC系统的响应时间期望是所有系统中最低的，这代表着他的性能期望与桌面计算机系统的性能期望完全背道而驰。而服务器系统处在两者之间。
上述的比喻阐明了一个观点：对于调度器性能而言，没有普遍的理想情况。对于台式机而言非常优秀的调度器，对于跑HPC应用程序的机器而言就是噩梦。Linux调度器努力地改进以适应任何情况，尽管他不可能对于所有情况来说都是完美的。在台式机用户不断要求计算机响应能够满足他们要求的同时，HPC用户正不断推进对他们而言的性能理想状态的优化。
5.1.1 linux 2.6.8.1调度器的起源
在Linux2.5.x开发的过程中，出现了一个新的调度器算法，他是对内核的最重要的改进之一。尽管2.4.x的内核被广泛应用，他很稳定同时在许多方面也表现良好，但是他仍有许多不受人欢迎的特性。那些不受欢迎的特性与其最原始的设计息息相关，所以当Ingo Molnar想要修复那些特性的时候，他编写了一个全新的调度器，而非在原有的老版本基础上做任何修改。Linux2.4.x内核调度算法包括O(n)算法这个事实可以说是其最大的瑕疵，而随后新调度器使用的O(1)算法成为了其最受欢迎的改进。
5.1.2 什么是O(1)算法
一个算法会对系统输入进行操作，而输入的规模则影响其运行时间。O符号是用以表示算法的执行时间随输入规模变大的增长率。例如，O(n)算法的执行时间随着输入规模n的增大而线性增大，O(n^2)算法是平方增长的。如果有办法获得算法运行的常量上限范围，那就是O(1)。也就是说O(1)算法能够在一个固定的时间段内完成，无论输入的规模有多大。
5.1.3 什么使得linux2.6.8.1的调度器能够实现O(1)时间运行
Linux2.6.8.1调度器并不包含任何比O(1)算法更耗时的算法。也就是说，无论系统内有多少任务同时运行，调度器的任何部分都必须能在常量的时间内运行完成。这允许linux内核能有效地处理大量任务而不会使其随着任务数目的增多而增加额外开销。在linux2.6.8.1调度器有两个重要的结构体能够使其在O(1)时间内完成职责，调度器的设计就是围绕着他们进行设计的，这两个结构体分别是：运行队列，优先级数组。
5.2.1 概述
运行队列数据结构是linux2.6.8.1调度器中最基础的数据结构；他是整个算法建立起来的基础。本质上，一个运行队列记录着所有被分配到特定CPU上的可运行的任务。正因如此，系统中的每个CPU都创建并维护着自己的运行队列。每个运行队列都包含两个优先级数组。在CPU中的所有任务都会从一个优先级数组中开始，即活动优先级数组，而后，随着他们用完了他们的时间片，他们被移动到过期优先级数组。在移动的过程中，会计算新的时间片并分配给相应任务。当活动优先级数组内已经没有可运行的任务时，内核简单地将活动优先级数组与过期优先级数组进行交换(仅在指针上进行更新就可以完成操作)。运行队列的工作就是记录CPU特殊线程的信息，同时控制他的两个优先级数组。
5.2.2 数据结构
运行队列数据结构在 kernel/sched.c 中定义为一个结构。他没被定义在 kernel/sched.h 是因为从调度器的公共接口抽象其内部工作是一项重要的体系结构目标。运行队列结构包含以下变量：
l spin_lock_t lock
这是保护运行队列的锁。任何时候只有一个任务可以对特定的运行队列进行修改。
l unsigned long nr_running
运行队列上可运行的任务数。
l unsigned long cpu_load
运行队列表现出的CPU负载。无论何时，只要rebalance_tick()函数被调用，负载就要被重新计算。重新计算出的负载是旧负载与现有负载(nr_running * SHCED_LOAD_SCALE)的平均值。
l unsigned long long nr_switches
自运行队列创建起的上下文切换次数。这个值在内核中并无什么用处，他仅在proc文件系统中用作统计数据。
l unsigned long expired_timestamp
自上次两数组切换至当前的时间。
l unsigned long nr_uninterruptible
在运行队列中不可中断的任务的个数。
l unsigned long long timestamp_last_tick
上次调度器滴答的时间戳。主要用在task_hot宏内，该宏用于判定一个任务是否用到了高速缓存存储器。
l task_t *curr
指向当前工作任务的指针。
l task_t *idle
指向CPU理想任务的指针。
l struct mm_struct *prev_mm
指向先前已经运行过的任务的虚拟内存映像的指针，这用于在高速缓存存储器方面高效地处理虚拟内存映像。
l prio_array_t *active
活动优先级数组指针。该数组包含那些仍然拥有时间片的任务。
l prio_array_t *expired
过期优先级数组指针。该数组包含那些时间片用完了的任务。
l prio_array_t arrays[2]
两优先级数组的数组。活动与过期数组指针在其间进行交换。
l int best_expired_prio
过期的所有任务中的最高优先级。用在EXPIRED_STARVING宏中以确定是否有比当前运行任务更高优先级的任务已过期。
l atomic_t nr_iowait
运行队列中等待IO操作的任务数目。用于判定内核状态。
l struct sched_domain *sd
运行队列所属的调度器域。本质上说，这是一组相互间可以共享任务的CPU。
l int active_balance
移动线程用以判断运行队列是否需要被平衡的标志。
l int push_cpu
当被平衡时，运行队列应将任务转移向的CPU。
l task_t *migration_thread
CPU的移动线程。移动线程是寻找任务转移问题的线程。
l struct list_head migration_queue
需要被转移到其他CPU的任务列表。
5.2.3 上锁
任何时刻，只有一个任务能修改特定CPU的运行队列，因此，其他想要修改运行队列的任务必须首先获得运行队列锁。获取多个运行队列锁必须按照运行队列升序的顺序来完成，以防止死锁情况发生。一个方便地获取两个运行队列锁的函数是double_rq_lock(rq1,rq2)，该函数自己处理上锁顺序。相反的，函数double_rq_unlock(rq1,rq2)为两运行队列解锁。给某任务所在队列上锁可以利用以下函数：task_rq_lock(task,&flag)。
5.3.1 概述
该数据结构是大多数linux2.6.8.1调度器有益操作的基础，尤其是其常量时间性能。Linux2.6.8.1调度器总是调度系统中最高优先级的任务，同时，如果有多个任务处在同一个优先级上，则他们将被循环调度。优先级数组能够让寻找系统中最高优先级任务的工作成为一个时间恒定的操作。而且，同时使用两个优先级数组使得新时间点过度成为时间恒定的操作。新时间点是指所有的任务都拥有新时间片时，或所有的任务都用完时其间片时。
5.3.2 数据结构
l unsigned int nr_active
在优先级数组中可活动任务的数目。
l unsigned long bitmap[BITMAP_SIZE]
位图显示出存在在优先级数组中的活动任务的属性。例如，有三个活动任务，两个优先级为0，一个优先级为5，那么在位图中，比特0和5应该被置位。这使得在优先级数组中寻找可运行的最高优先级的任务只需要简单地调用恒时函数__ffs()，该函数是个在程序字中寻找最高次序比特的被高度优化过的函数。
l struct list_head queue[MAX_PRIO]
一个连接列表数组。每个优先级在数组中都拥有一个列表。这些列表包含任务，无论何时当其中某个列表的大小大于0时，在优先级数组位图中的对应优先级的比特位将被置位。当一个任务被加入到优先级数组，他将被根据他的优先级被分配到指定的数组队列中。在优先级数组中的最高优先级的任务总是被最先被调度，同时处于同一优先级的任务将被循环调度。
5.3.3 如何使用优先级数组
在所有仍有时间片剩余的任务中，调度器总是最先调度优先级最高的任务。优先级数组使得调度器算法能够在常量时间内找到最高优先级的任务。
优先级数组是一组链接的列表，每个优先级拥有一个列表。当一个任务被加入优先级数组时，他被加入到与其优先级相符的列表中。长度为MAX_PRIO+1的位图的比特位将为拥有活动任务的优先级置位。为了找到优先级数组中最高优先级的任务，我们只需要找到位图中第一个被置位的比特位。同个优先级的任务被循环调度；一个时间片运行完成后，任务将被置于其优先级列表的末端。因为在一个有限长度的位图中寻找第一个被置位的比特位与在一个有限长度的列表中寻找第一个元素都是在有限空间内的操作，所以，这个部份的调度器算法的时间性能是常量的，也就是用了O(1)时间。
当一个任务的时间片被用完，他将从活动优先级数组中被移出，同时被放置进过期优先级数组。在移动过程中，会计算一个新的时间片。当活动优先级数组中已经没有活动任务时，我们只将指向活动优先级数组与指向过期优先级数组的指针简单地进行交换就完成了两优先级数组间的交换操作。由于每当一个任务在用完时间片时都会被重新计算并移出活动数组，所以当两数组交换后，任务就无需再计算时间片。也就是说，内核将统一为每个任务重新计算时间片的迭代过程分解为一个个常量时间的操作。交换两数组的操作也是常量时间操作，简单的交换指针避免了将一个数组中的元素移动到另一个数组中的O(n)时间的操作。
因为所有在优先级数组上发生的操作都是常量时间O(1)的操作，linux调度器表现地挺好。无论系统中有多少任务存在，linux2.6.8.1调度器都会在相同的极少的时间内完成其任务。
5.4.1 静态任务优先级及nice()系统调用
所有的任务都有一个静态的优先级，经常被称作nice值。在linux中nice值的范围是从-20到19，越大的数字代表越低的优先级。默认情况下，任务一开始时，其静态优先级为0，但是该优先级是可以通过nice()系统调用进行改变的。除了系统对任务优先级进行初始化时赋值的0及通过nice()系统调用对静态优先级进行的修改，调度器从不在除此之外的情况修改任务的静态优先级。修改静态优先级就是用户修改任务优先级的途径，而调度器则会选择尊重用户的输入。
任务的静态优先级被存于其staic_prio变量中。当p是一个任务时，p->static_prio就是其静态优先级。
5.4.2 动态任务优先级
Linux2.6.8.1调度器利用增加静态优先级的方式奖励IO受限的任务，利用降低静态优先级的方式惩罚CPU受限的任务。被调整的优先级被称为任务的动态优先级，同时他可以通过任务的prio变量获得。如果一个任务是交互式任务，他的优先级就会被提高。如果一个任务极其占用CPU，他就会受到惩罚。在linux2.6.8.1调度器中，最大的优先级奖励为5，最大的优先级惩罚也是5。由于调度器使用奖励与惩罚制度，对任务的静态优先级进行调整受到了重视。一个轻微占用CPU的nice值为-2的任务可能拥有值为0的动态优先级，就像其他许多非大量占用CPU或IO的任务一样。如果用户利用nice()系统调用调整了两个任务中任意一个的静态优先级，系统会对这两个任务进行相应的调整。
5.4.3 I/O受限 vs. CPU受限 启发式教学
动态优先级奖励与惩罚机制是基于交互性启发法。这种启发法是利用记录任务运行与休眠的时间来实现的。IO受限的任务趋向于在大多时间内进行休眠，然而CPU受限的任务由于他们很少被IO阻塞，所以他们很少休眠。大多情况下，任务都处于上述两者之间，任务并非完全CPU受限，也并非完全IO受限。这样的情况使得启发法产生范围这一概念来代替简单的比特标志（标志任务为IO受限或CPU受限）。在linux2.6.8.1调度器中，当一个任务从休眠中醒来，其全部的休眠时间会被加入到sleep_avg变量中。当一个任务自愿地或非自愿地放弃CPU，系统或从其sleep_avg变量中减去任务运行的时间。任务的sleep_avg变量越大，任务的动态优先级就会变得越大。由于这种启发法同时记录了任务运行与休眠的时间，他也显得相对精确。由于休眠很长时间的任务也有可能会用完其时间片，所以，必须阻止休眠很长时间后大量占用CPU时间的任务获取大量的交互性奖励。Linux2.6.8.1调度器的交互性启发法已防止了此类形象的发生，因为很长的运行时间会抵消很长的休眠时间。
5.4.4 effective_prio()函数
该函数用以计算任务的动态优先级。他被线程与进程的唤醒调用函数recalc_task_prio()与scheduler_tick()函数调用。该函数会在任务的sleep_avg变量被改变后被调用，因为sleep_avg是任务动态优先级最主要的启发法。
Effective_prio函数做的第一件事就是，如果任务是实时任务，则返回任务的当前优先级。该函数不会对实时任务进行奖励或惩罚。以下的两行是关键：
bonus = CURRENT_BONUS(p) - MAX_BONUS / 2；
prio = p->static_prio - bonus；
CURRENT_BONUS是被如下定义的：
#define CURRENT_BONUS(p) /
NS_TO_JIFFIES((p)->sleep_avg)*MAX_BONUS/ AX_SLEEP_AVG)
本质上，CURRENT_BONUS将任务的休眠平均值映射到0-10的区间上，MAX_BONUS就是10。如果一个任务的sleep_avg很高，那么CURRENT_BONUS的返回值就会很高，反之亦然。由于MAX_BONUS是任务优先级可增减的最大范围的两倍，他被除以2，同时被从前者CURRENT_BONUS(p)中减去。如果一个任务有非常高的sleep_avg，那么此时CURRENT_BONUS(p)返回10，所以bonus就会是5。接着任务的静态优先级会被减去5，该值是一个任务能获得的最大奖励了。如果一个任务的sleep_avg是0，那么此时CURRENT_BONUS(p)返回0。在这种情况下，bonus会是-5，任务静态优先级会被减去-5，也就是加上5。静态优先级加上5是对那些长期占用CPU而不休眠的任务的最大的惩罚。
一旦一个新的动态优先级被计算出来，effective_prio函数能做的最好一件事就是确保任务优先级处在非实时优先级范围内。例如，当一个高度交互的任务拥有-20的静态优先级，他就无法再获得5的奖励，因为他已经拥有最高的非实时优先级。
5.4.5 计算时间片
我们只要简单地在时间片范围内映射一个任务的静态优先级就可以计算出时间片，同时必须保证该时间片处在确定的最大与最小值之间。任务的静态优先级越高，他就会获得越多的时间片。Task_timeslice()函数只是一个对BASE_TIMESLICE宏的简单调用，该宏被定义如下：
#define BASE_TIMESLICE(p) (MIN_TIMESLICE + /
((MAX_TIMESLICE - MIN_TIMESLICE) * /
(MAX_PRIO-1 - (p)->static_prio) / (MAX_USER_PRIO - 1)))
实际上，这就是最小的时间片加上任务的静态优先级映射进时间片范围的值，时间片范围是(MAX_TIMESLICE - MIN_TIMESLICE)。
还有一关键点在于，一个交互性任务的时间片有可能基于调度器的TIMESLICE_GRANULARITY值被分解成一块一块。Schedular_tick()函数是用以验证是否当前运行的任务从其他相同动态优先级的任务手中抢占CPU太长的时间。若一个任务运行了TIMESLICE_GARANULARITY的时间，并且存在其他相同优先级的任务时，那么就会在其他相同优先级的任务中进行一次循环转换。
5.4.6 生成新任务时的公平性
生成新任务时，wake_up_forked_thread()和wake_up_forked_process()两函数会减少父子任务的sleep_avg变量。这是为了防止高交互性任务产生其他高交互性的任务。如果没有这两个函数，那么高交互性任务可以不断产生高交互性的任务用以占用CPU。有了这个两个函数，sleep_avg变量以及随后的优先级都会被降低，这样就增加了父子任务被更高优先级进程抢占CPU的可能性。我们还需要知道的是，父子任务的时间片并不会减少，因为时间片是基于静态优先级，而非基于被sleep_avg变量影响的动态优先级的。
5.4.7 重新插入交互性任务
每隔一毫秒，一个时钟中断就会调用schedular_tick()函数。如果一个任务时间片已经被用完，通常情况下，他会被给予另外一个新的时间片并被置于其所在运行队列的过期优先级数组中。然而，schedular_tick()函数会将获得新时间片的交互性任务重新插入到活动优先级数组中，只要过期优先级数组中没有出现饥饿现象。通过阻止有非交互性任务能成功用完其时间片而交互性任务却处在过期优先级数组中这种情况发生，有助于交互性任务的运行。
5.4.8 互动性评分
互动性评分帮助控制任务交互性状态的上升与下降比率。事实上，当任务休眠长时间后，其会获得一分的互动性分数；当任务运行长时间后，其会失去一分的互动性分数。一个任务的交互性评分分数被存储在其interactive_credit变量中。如果一个任务拥有超过100分的互动性评分，我们认为他有很高的互动性评分。如果一个任务拥有低于-100分的互动性评分，我们认为他有很低的互动性评分。
5.5.1 为什么要休眠？
任务并不总是在运行，当他们不运行时，他们就休眠。任务由于许多原因会进入休眠状态；但是总归是一个原因，他们都在等待某些事件发生。有些时候，任务进行休眠是因为他需要等待从设备上读入数据，有些时候，任务进行休眠是因为他在等待从程序的另外一个片段发来的信号，有些时候他就是要休眠一个固定的时间。
休眠是一个很特殊的状态，在这个状态下，任务不能被调度，也不能被运行。这很重要，因为如果休眠的任务能够被调度或执行，那么程序执行会在不该继续的时候继续，这使得休眠必须被实现为忙循环。例如，如果一个任务在他请求设备传输数据后可以立即继续执行，而此时无法确认设备数据是否传输完毕，那么任务就必须不断地通过循环检测来确定数据传输是否完成。
5.5.2 可中断与不可中断的状态
当一个任务进入休眠状态，他仍会处于两种情况：可中断与不可中断。在可中断的休眠状态下的任务可以比预期更早地醒来来对发给他的信号进行响应，而处于不可中断的睡眠状态下的任务则不能如此。例如，一个用户会使用kill命令来结束一个任务，kill命令会尝试向任务发送SIGTERM信号来完成他的工作。如果任务此时处于不可中断的状态，他会简单地忽略发送来的信号，直到他所等待的事件发生。然而处于可中断状态的任务就会立即对传给他的信号作出响应。
5.5.3 等待队列
一个等待队列实际上就是等待一些事件或情况发生的任务列表。当该事件发生，该事件的控制代码会将该等待队列中的所有任务全部唤醒。这就相当于是个事件通告发布的集中地。准备要休眠的任务会在休眠之前加入到一个等待队列当中，以便在其等待的事件发生时能够得到通知。
5.5.4 休眠
任务通过系统调用来进入休眠状态，这些系统调用通常会利用以下几步来保证任务进入安全和成功的休眠期：
1) 通过DECLARE_WAITQUEUE()来创建一个等待队列；
2) 通过add_wait_queue()函数将任务加入到等待队列。该等待队列在其等待的事件发生时会唤醒所有处于该队列中的任务。无论如何，事件发生时，事件代码必须在合适的时机对等待队列调用wake_up()函数；
3) 利用TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE来标示任务进入休眠状态；
4) 开启一个循环来调用schedule()函数及一个测试来判断状态是否为真。如果其初始就为真，则不需要调用schedule()函数，因为在这种情况下，任务不需要进行休眠。否则，任务需要调用schedule()函数来放弃CPU占有权。由于该任务已经被标记为休眠，他就不会再被CPU进行调度。
5) 当任务被唤醒，循环的状态检测会被再次执行。这样会防止可能发生的虚假唤醒。如果等待的事件真的发生了，循环会跳出。否则该循环会继续进行，并调用schedule()函数。
6) 一旦事件发生，用TASK_RUNNING来标记任务，并通过remove_wait_queue()函数将其从等待队列中移除。
5.5.5 唤醒
try_to_wake_up()函数负责唤醒任务。当一个等待队列被告知要唤醒，在该等待队列中的所有任务都会执行try_to_wake_up()函数，同时任务会从等待队列中被移除。任务会被标记为TASK_RUNNING，并被加入回合适的运行队列等待被调度。
5.6.1 概述
schedule()函数就是主调度函数。他的工作就是选择一个应该被调度运行的任务，并将CPU切换到运行该任务。当一个任务自愿地放弃CPU时，该函数就会被调用。同时如果scheduler_tick()函数因为任务用完其时间片而设置了他的TIF_NEED_RESCHED标志，那么当优先权被重新激活时，schedule()函数也会得到调用。scheduler_tick()是一个通过时钟中断在每个系统时钟滴答都会被调用的函数。他检查正在运行的任务及在CPU运行队列中的其他任务来判断调度与负载均衡是否需要被执行。
5.6.2 schedule()函数
该函数做的第一件事就是确认他不是在不该被调用的情况下被调用的。在那之后，他关闭优先权抢占操作，并判断该被调度出CPU的任务运行的时间长度。如果该任务有个高的交互性评分，那么这个时间长度会被剪短，因为一个经常等待IO的任务不希望由于其一次长时间使用CPU而丢失交互性状态。接下来，如果该函数进入了内核优先级的抢占，等待一个信号的可中断任务会得到TASK_RUNNING状态，不可中断任务会从运行队列中被移除。这是因为，如果一个任务可中断同时他在等待一个信号，他需要处理该信号。不可中断的任务不应该存在在运行队列中。
到达这里之后，就需要寻找下一个应该被执行的任务了。如果在运行队列中没有可以被运行的程序，系统会进行一次负载均衡。如果负载均衡没有带来任何可运行的工作，那么系统会向理想任务进行上下文切换。如果在运行队列中存在可运行任务，当他们并不在活动优先级数组中，那么活动优先级数组与过期优先级数组就会进行对换。
到了这步，活动优先级数组中就会存在可运行任务。那么，系统就会检查活动优先级数组的位图来找出所有可运行任务优先级中最高的优先级。在那之后，在SMT CPU上的从属休眠任务有可能得到运行的机会。如果存在一个从属的休眠任务，当前的CPU会被切换至理想任务从而使从属的休眠任务可以醒来完成他应该完成的工作。
如果此时由于种种原因没有执行到理想任务的切换，那么系统就会执行一次检查来判断下个被选中执行的程序是否是非实时且已被唤醒的。如果该任务是非实时且已被唤醒，他会被给予一个稍高的sleep_avg值，同时其动态优先级会被重新计算。这是给休眠任务另一种微小奖励的方法。一旦该检查被执行并且奖励被发放，唤醒标志就会被清除。
现在，schedule()函数已经准备好进行真正的上下文切换。此时，算法会进行目标跳转，不论被下一个变量指向的任务是什么，都会执行到该目标任务的上下文切换。之前要调度理想任务的决定也只是简单地将next变量指向理想任务，并跳至该点。在这里，先前的任务将其TIF_NEED_RESCHED标志清除，上下文切换的统计数据变量被更新，先前的任务从其sleep_avg变量中扣除运行时间。同样，如果任务的sleep_avg变量低于0且其交互评分不高也不低，那么任务就会扣除一个交互性评分。这是因为，如果任务的sleep_avg变量小于0则他一定不常休眠。这步完成后，只要先前的任务与新任务不是同个任务，那么就会进行上下文切换。在上下文切换后，调度算法中被停用的优先级抢占被重新激活。schedule()函数的最后一步是检查优先级抢占在调度算法执行过程中是否被请求，如果有则重新调度。
5.7.1 为什么要进行负载均衡？
任务经常性地会处于CPU的一些特定部分。这是为了更好地利用高速缓冲存储器及内存。但是，有些时候，一个CPU处理的任务要比系统中其他CPU要多。例如，在一个dual处理器系统中，有可能存在这样的情况：所有的任务都被分配给一个CPU，而另外一个CPU则一直处于理想状态。很显然，这并非最好的状态。这个问题的解决办法就是将一部分任务从拥有很多任务的CPU移到另外一个CPU来平衡系统。负载均衡是任何控制多CPU的内核的一个重要组成部分。
5.7.2 调度器域
每个在系统中的节点都有调度器域，该调度器域指向其父调度器域。一个节点可以是一个单处理器系统，一个SMP系统，或者一个NUMA系统。对于NUMA系统的情况，一个节点的域的父调度器域包括在系统中的所有CPU。
每个调度器域将CPU分成不同的组。在一个单处理器系统或一个SMP系统中，每个CPU就形成一个组。包含系统中所有CPU的最高级别的调度器域会将每个节点分成一组，该组包含节点上的所有CPU。所有组被作为环形连接表进行维护，而所有组的组合等价于域。没有CPU可以同时处在两个组中。
一个域的负载只能在该域中被平衡。只有在域中组的负载变得不平衡时，任务才有可能在组间进行移动。组的负载是组中所有CPU负载的综合。
5.7.3 CPU负载
由于每个可运行的CPU都只存在一个运行队列，所以利用该结构体进行CPU负载的记录是合理的。每个运行队列维护一个叫做cpu_load的变量，该变量反应出CPU负载的状况。当运行队列被初始化时，该变量被设置为0，同时他在每次系统调用rebalance_tick()时被更新。上述函数在scheduler_tick()的末尾被调用，如果CPU处于理想状态，则他会被调用的更早些。在rebalance_tick()函数中，当前运行队列的cpu_load变量被设置为当前负载与旧负载的平均值。当前负载是由当前运行队列中获得任务的数目与SCHED_LOAD_SCALE的乘积决定的。上述宏是个大数128，他仅仅是用以增大负载计算的结果。
5.7.4 均衡逻辑
负载均衡是通过rebalance_tick()函数被调用的，其在scheduler_tick()函数中被调用。Rebalance_tick()首先更新CPU的负载变量，然后上升到CPU的调度域层尝试重新进行负载均衡。如果CPU的调度器域在比其均衡间隔还长的时间段内没有进行过负载均衡，则上述函数只尝试均衡调度器域。这点非常重要，因为所有的CPU共享顶级调度器域，我们不希望在每次CPU时钟滴答发生时就对顶级域进行负载均衡。我们可以想象，如果不这么做的话，在拥有512个处理器的NUMA系统中，对顶级域的负载均衡会多么经常发生。
如果rebalance_tick()函数判断出一个调度器域需要进行负载均衡，那么他会对该调度器域调用load_balance()函数。load_balance()函数会寻找域中最繁忙的组，如果没有最繁忙的组，他会退出。如果有最繁忙的组，他会判断是否该最忙的组包含当前CPU，如果包含他同样会退出。load_balance()函数会将任务拉进低负荷的组，而非将任务从高负荷的组中推出。一旦最繁忙的组被选出，load_balance()函数会尝试通过move_task()函数将任务从最繁忙的组的运行队列移动到当前CPU的运行队列中。load_balanc()剩余部分的工作致力于根据负载均衡是否成功来更新启发法，并且清理锁。
move_task()函数尝试将一定数量的任务从最繁忙的组中移动到当前组中。该函数会尝试先移走目标运行队列中过期优先级数组中的任务，在过期优先级数组中，该函数会尝试先移走最低优先级的任务。任务通过调用pull_task()被移走。pull_task()函数将任务从当前运行队列中出队，而后让其入队到目标运行队列中。该操作简短且简单，是调度器设计简洁的证明。
5.7.5 移动线程
每个CPU都拥有一个移动线程，该线程是一个高优先级的内核线程，他保证运行队列的均衡性。该线程migration_thread()函数中的循环直到由于某些原因被叫停。如果有任务移动请求，那么移动线程会发现该请求并处理他。
Linux2.6.8.1调度器提供对软实时调度的支持。“软”这个形容词来源于这样一个事实：虽然调度器在使任务如期完成上做的很好，但他并不保证所有的任务都能如期完成。
5.8.1 优先的实时任务
实时任务拥有从0到99的优先级，而非实时任务优先级被映射到内部优先级范围100-140。因为实时任务有比非实时任务低的优先级值，实时任务总是会比非实时任务更容易优先执行。只要实时任务是可运行的，就没有其他的任务可以运行，因为实时任务利用两种不同的调度策略在执行，分别为SCHED_FIFO和SCHED_RR。非实时任务被标识为SCHED_NORMAL，遵循普通调度操作。
5.8.2 SCHED_FIFO调度
SCHED_FIFO任务根据先进先出进行调度。如果系统中有这样的任务，那么他会一直占用CPU运行他想要的时间长度，没有任何任务可以抢占CPU。这样的任务没有时间片。多个SCHED_FIFO任务的情况下，高优先级的任务会抢先于低优先级的任务进行执行。
5.8.3 SCHED_RR调度
SCHED_RR任务与SCHED_FIFO任务相似，但他拥有自己的时间片，并且总是被SCHED_FIFO抢先执行。SCHED_RR任务根据优先级来确定执行顺序，在同一优先级内他们会被循环调度。每个在固定优先级下的SCHED_RR任务运行完其指定的时间片后会回到其优先级数组列表的末端。
5.9.1 调度器域/组管理
调度器域系统是linux2.6.8.1 NUMA支持中的一个重要组件。NUMA体系结构区别于单处理机系统与SMP系统的地方在于NUMA系统可以包含多节点。最典型的特征就是，系统中每个节点都有本地内存库及某些其他资源，这些资源能够很好地被物理上近邻的CPU利用。例如，虽然NUMA系统中的某个CPU可以利用系统中任何节点上的内存，但访问本地内存总比访问物理上20码远或好几个NUMA链接远的节点上的内存要快的多。简而言之，由于NUMA系统物理上可以非常的大，且其节点间的连接也并不是非常理想，所有临近资源就成为一个问题。相邻问题使得将资源组织成组的形式变得非常重要，这也就是调度器域系统所要做的事情了。
在一个NUMA系统上，顶级调度器域包括系统中所有的CPU。顶级调度器域对每个节点都分有一个组；组的CPU包括所有在节点上的CPU。顶级域为每个节点分有子调度器域，每个子域可以有一组CPU。该调度器域结构是由调度器中的特殊域初始化函数进行设置的，这些函数只有在CONFIG_NUMA为真的时候才会被编译。
5.9.2 NUMA任务移动
当scheduler_tick()运行时，他会判断在当前CPU基础域中的组是否平衡。如果不平衡，他会对域中的组进行负载均衡处理。一旦域进入平衡状态，其父域就平衡了。这意味着，NUMA系统中每个节点的基础调度器域允许节点保有任务，这由于资源临近性等原因而受到欢迎。由于调度器在调度器域的组之间进行平衡以及非必要的独立CPU，当顶级域平衡时，只有任一节点负载过重才会在节点间进行任务移动。NUMA系统中的独立CPU在顶级域平衡操作时并不被考虑在内。一旦任务成为新节点的一个部分，他会持续呆在节点内部直到该节点负载过重。这些平衡操作等级不鼓励非必要的节点接任务移动。
5.10.1 调整的原因
拥有一些基础linux开发能力的linux用户总希望能够优化调度器以满足某个方面的特殊要求。这样的人可能包括那些希望能够牺牲整体效率换取系统响应时间的台式机用户，或者包括那些为了系统整体效率而牺牲响应时间的系统管理员。
5.10.2 调度器调整可能性
在文件kernel/sched.c的顶端，有一系列以MIN_TIMESLICE开头的宏，这些宏的定义可以被调整以满足用户特殊需求。这些值可以被合理地进行修改，同时调度器会稳定地工作。在改变了需要的宏定义后，就如一般情况一样，用户需要重新编译内核。在已被编译的内核中修改这些值是没有任何意义的，并且运行中系统的这些值是不能修改的。另外一些可以被调整的值我们会在5.10.3 - 5.10.6中进行讨论。
我们重点要明白的是，调度器代码及调度器可以处理的工作拥有太多的变量，以至于对调度器做出的修改没有任何保证。最好的进行调度器调试的方式是利用调度器会处理的工作来进行实验和排错。
5.10.3 MIN_TIMESLICE和MAX_TIMESLICE
MIN_TIMESLICE是调度器可得的最小的时间片。MAX_TIMESLICE是调度器可得的最大的时间片。平均时间片大小是由上述两宏的平均值决定的，所以增加上述两值中任意一值都会增加通用时间片长度。增加时间片长度就会增加全局效率，因为更长的时间片长度意味着更少的上下文切换，但是这会减少系统响应次数。然而，由于IO受限任务通常都比CPU受限任务拥有更高的动态优先级，交互性任务比其他任务更可能抢占CPU，无论该任务的时间片有多长；这意味着，交互性受来自长时间片的影响会更少些。如果在系统中有很多的任务，例如在一个高端服务器上，更长的时间片会导致低优先级的任务要花更多时间等待。如果大多数任务都处在相同的优先级上，响应时间会受到更大的影响，因为没有任何一个任务可以抢占其他任务的CPU以尝试给用户提供更多的响应次数。
5.10.4 PRIO_BONUS_RATIO
这是在动态优先级计算中可作为奖励或惩罚被任务所得到的优先级上升或下降范围的比例值。默认情况下，该值为25，所以任务可以从0值上移或下降25%。由于在0上下分别有20个优先级，所以默认情况下，任务可以获得5个优先级的奖励或惩罚。
事实上，这个值控制着静态用户定义的优先级有效的程度。当这个值很高时，利用nice()系统调用将一个任务设置为高优先级的效果就并不明显，因为此时动态优先级在进行计算时允许更多的弹性。当这个值很低时，静态优先级就更起作用。
5.10.5 MAX_SLEEP_AVG
MAX_SLEEP_AVG的值越大，一个任务被作为活动任务前所需要进行休眠的时间就越长。增加该值会降低系统交互性，但是对于非交互性的工作而言，所有任务的平等性才是他想要的。全局效率此时会得到提升，因为动态优先级更少的增加意味着更少的CPU抢占及上下文切换。
5.10.6 STARVATION_LIMIT
交互性任务在用光时间片时会被重新插入到活动优先级数组中，但这会引起其他任务出现饥饿状态。如果另一个任务没有运行够比STARVATION_LIMIT更长的时间，那么交互性任务会暂停运行以让饥饿的任务获得CPU时间。降低该值会影响交互性，因为这样会导致交互性任务经常性地被强迫放弃CPU，转而让饥饿任务进行执行。但是这么做，系统公平性就得到提高。增加该值会提高交互性性能，非交互性任务需为此付出代价。
对linux2.4.x调度器有一个基本的了解会对我们理解在2.6.x内核中对调度器作出的改进有很大帮助。
Linux2.4.x调度器算法将时间分成一个个时间点，这些时间点是一个个时间周期，在这些时间周期中，任一个任务都允许用完其时间片。在时间点开始时，每个任务都会被给予一个时间片，这意味着对时间片计算的调度器算法的执行效率是O(n)，因为他必须对每个任务进行迭代。
每个任务有个基本时间片，其决定于任务的默认或由用户分配的nice值。Nice值被映射为调度器滴答，nice值为0的任务对应获得的时间片为200ms。当计算一个任务真正的时间片时，基本时间片基于任务IO受限的程度得到修改。每个任务有个counter值，该值包含任务被分配的时间片内的调度器滴答数。在时间点的末尾，任务有可能由于等待IO的原因而无法用完其时间片。任务的新时间片会在时间点的末尾用如下的方式进行重新计算：
p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice)；
剩余的调度器滴答计数值向右移动一位，并被加入到基础时间片中。这样就使得那些在上个时间点中由于IO受限原因而无法用完时间片的任务在下个时间点内拥有了更长的时间片。如果一个任务突然成为了CPU受限任务，同时用完其时间片，那么他在下个时间点只能拥有基本时间片。然而，这越来越难实现，因为连续的低时间片利用的时间点会将任务的时间片越垒越长。
当一个任务生成一个新的任务时，父任务的时间片会与其子任务进行分割。这就使得任务无法不断产生子任务而霸占CPU。
Schedule()函数迭代判断所有的可运行任务并调用goodness()函数，从而选择出下一个要运行的任务。引起goodness()函数返回最高值的任务将被选中进行运行。Goodness通常由进程counter值加上其nice值来决定，但是对于实时任务而言，该结果还要加上1000，以使得实时任务总是先于非实时任务被选中。在goodness()函数中有个有趣的优化，如果一个任务与前一个运行的任务共享某些地址空间，那么在计算时他将由于可以利用现有高速缓存页而得到goodness值的轻微提升。Goodness算法事实上是如下执行的：
If(p->policy != SCHED_NORMAL)
Return 1000 + p->tr_priority;
If(p->counter == 0)
Return 0;
If(p->mm == prev->mm)
Return p->counter + p->priority + 1;
Return p->counter + p->priority;
Linux2.4.x调度器算法表现不错，但是他相对平凡，他的优势也仅仅局限于在普通的领域内。
6.2.1 实用
尽管在技术上很含糊，但是linux2.4.x调度器很实用的事实不应该被打折扣。人们对linux调度器的要求很高；linux2.4.x跑在许多非常重要的系统中，从Fortune5000服务器到NASA超级计算机，他都运行地很好。Linux2.4.x调度器已经足够强健及有效，这使得linux成为计算世界的一个重要选手，这些成就都是以往的调度器所无法企及的。
6.2.2 相对简单的逻辑
Linux2.4.x中的kernel/sched.c文件大约是linux2.6.x中该文件的三分之一。该算法是相当简单的，尽管其内在行为和影响都有些无法预测。在linux2.4.x中，调整调度器的行为是相对简单的，然而想不通过彻底检查而改进他就相对困难。
在《Understanding the linux kernel》一书中，作者解释了四个liunx2.4.x调度器的缺点：低拓展性，过大的平均时间片，非最优的IO受阻任务的优先级升级策略，弱的实时应用支持。
6.3.1 可拓展性
Linux2.4.x调度器执行时间效率为O(n)，这意味着在一个拥有非常多任务的系统中进行调度是非常可怕的。在每个调用schedule()函数的期间，任一个任务至少被迭代一次以使得调度器能够完成其任务。这暗示着，系统中存在一段很长的无真正任务被执行的时间区段。交互性感知性能将因此受到重大影响。这个问题在linux2.6.x调度器中已经通过使用效率为O(1)的算法得到解决。Linux2.6.x调度器特别地在每个任务用完其时间片时就重新计算时间片。Linux2.4.x调度器在所有任务都用完时间片时才统一一次性为所有任务重新计算时间片。另外，linux2.6.x调度器的优先级数组使得寻找系统中最高优先级的进程就如在位图中寻找第一个被置位的比特位那么简单。而linux2.4.x调度器却迭代所有的进程去寻找那个最高优先级的进程。
6.3.2 过大的平均时间片
由linux2.4.x调度器分配的平均时间片大致为210ms。这个时间片相对较长，同时，按Bovert和Cesati的说法：“显然对拥有非常高系统负载希望的高端机来说，这个值太大了。”这是因为，这么长的时间片会导致低优先级任务执行时间变得过大。例如，当有100个线程不中断地执行他们各自的210ms长度的时间片时，最低优先级的任务需要等待超过20秒的时间才有可能得到运行。这个问题不会因为执行饥饿检查或在计算时间片时将系统负载考虑在内而得到缓解，这些根本提供不了任何帮助。在重新计算时间片时，只有进程数据字段被使用到：
p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
这个问题在linux2.6.x调度器中通过降低平均时间片长度得到缓解，但并没有完全得到解决。事实上，在linux2.6.x中，系统负载需要多出一倍才会产生上述问题。我们需要重点记住的是，尽管如此，高优先级任务可以抢占其他长时间片的任务，以此来维护可接受的交互性。这并不能帮助那些非交互性的或处于队列末端的，但无法等待超长时间而得不到执行的任务。一个很好的例子就是一个已经从IO源获取到数据，并等待生成HTTP回复的web服务器，用以生成回复信息的长时间等待可能导致客户连接的超时。
6.3.3 IO受限任务的优先级升级
Linux2.4.x调度器对IO受限任务的偏好有一些很明显的缺陷。第一，IO受限的非交互性任务会得到优先级升级，即使他们并不需要。同时，这样对交互但CPU受限的任务不公平，因为由于交互性得到的优先级提高与由于CPU受限而得到的处罚会相互抵消。由于linux2.4.x调度器给任务所分配的时间片是基于任务在上个时间片剩余的时间及一个基于用户nice值的附加值，CPU受阻任务的前者值会很低，并且如果接下来任务碰巧是交互性的，那么他只会得到很小的奖励。
这两个问题都无法得到很好的解决，直到找到比休眠时间更好的度量交互性的标准。由于我们的基本逻辑是，常休眠的任务是交互性的，不常休眠的任务是非交互性的，融合对立的特性总是困难的。针对之前的问题，linux2.6.x将休眠时间过长的任务分类为懒惰任务，以如下的方式给他们分配平均休眠时间：
If(...sleep_time > INTERACTIVE_SLEEP(p)){
p->sleep_avg=JIFFIES_TO_NS(MAX_SLEEP_AVG - AVG_TIMESLICE);
}
这阻止了给予过度休眠的任务大量的奖励。这并不是问题的解决方法，但是这至少限制了问题拓展的范围。
6.3.4 实时应用支持
Linux2.4.x内核是不可抢占的，所以对实时任务的支持就很弱。中断和异常会导致短暂的内核模式执行，在该执行期间，可运行的实时任务无法立即继续执行。这对于有强时间限制的实时任务是不可接受的。内核抢占性给内核代码增加了很高的复杂性，尤其是考虑到加锁问题，而这已被抵触许久。Linux2.6.x是一个可抢占的内核，所有对实时任务的支持会更好。然而在有些情况下，linux2.6.x内核也是无法被抢占的，所以其对实时任务的支持也非完美。还有许多关于实时任务支持的问题，但这些已经超出本文所要叙述的范围。
Linux2.6.x调度器是立体的。在近期他不可能会有大的改动，因为更深入的立体性能提高是很难控制的。大量的不同工作情况让调度器望而却步，这意味着针对一种工作情况作出的调度器调整很可能会影响到调度器在其他工作情况下的表现。
尽管linux2.6.8.1调度器的基本算法与数据结构不大可能会发生大的变化，但事件处理方式仍然会不断得到改进。这不会在算法级上影响性能，这反而会全面地改善调度器性能。有可能会增加一些特性，但总体的调度器结构不会发生重大改变。
7.1.1 调度器模式及可交换调度器
两个未来调度器的有趣的发展方向是调度器模式与可交换的调度器。
调度器模式意味着将调度器工作进行分类，同时允许根用户动态选择系统的调度器行为。例如，有可能有两种模式，服务器模式与台式机模式，此时系统管理员可以通过系统调用让机器进入其中一种模式。台式机模式会更加注重用户交互性，而服务器模式则更加注重效率。实际上的调度器模式可能没有这么简单，但是即使只有这么简单的设置也会给许多人带来便利。实际上，简单性更可能带来愉悦地用户体验及促进系统改进。通过将可调整的宏变成运行时可调整的变量，或维护两组用于不同设置的变量的方式，可以简答地实现调度器模式。虽然这是个有趣的想法，但是这并不大可能会实现。
可交换调度器允许用户选择自己特定的调度器来处理任务。一个基础的内核调度器会在用户间循环切换，同时允许一个用户选择调度器来选择任务进行执行。这样，交互性用户可以选择更适用于处理交互性任务的调度器，而非交互性用户也可以选择适用于他们所处情况的调度器。这是一个对可交换调度器的非常简单的描述，但是这也将其主要思想阐述清楚了。现在已有一些关于拥有可交换性调度器的内核的不同类型的例子，或许最显著的就是GNU HURD内核。
7.1.2 共享的运行队列
近期对linux调度器中SMT支持的添加并非完美的。在一片ARS TECH的报道中，Robert Love介绍了一个拥有四个虚拟处理器的工作站的例子。如果三个虚拟处理器都是懒惰的，第四个处理器有两个工作，此时调度器应该尝试将其中一个任务移动到另外一个物理CPU上，而非将该任务移动到同一芯片内部的另外一个虚拟处理器上。现在，这并没有发生。Love介绍的解决方案是在SMT体系结构下共享运行队列。如果进行了运行队列的共享，负载均衡会现在所有物理CPU之间进行均衡负载，而非先在虚拟处理器之间进行。这样的特性很可能会被加进linux调度器。
作者希望能够感谢下述的人和组织，作者从他们那得到了许多帮助，积极的影响及鼓励：
Professor Libby Shoop
Professor Richard K. Molnar
Jeff Carr
Free Software/OSS Community
Silicon Graphics
Josh Aas是一位美国圣保罗市麦卡利斯特学院的学生，他将获得计算机科学及英语文学的双学位。此前他从未想过会与这两个科目结缘。在写这篇文章时，他正受聘于Silcon Graphic公司，工作在linux系统软件组，从事基于linux的高性能服务器等方面的工作。他空余的大部分时间都工作于开源软件工程，尤其是Mozilla.org。他其他的爱好包括旅游，阅读，跑步等。
译者：WInScar Daemon Huang(西安电子科技大学)
允许在遵循GNU开源文档协议的1.1版本或更高版本的前提下，进行该文档的复制，发布与修改。该协议的副本可以在下述地址找到：
http://www.gnu.org/licenses/fdl.txt
[1] Curt Schimmel, UNIX r Systems for Modern Architectures - Symmetric
Multiprocessing and Caching for Kernel Programmers. Addison-Wesleym
1994.
[2] Andrew S. Woodhull, Andrew S. Tanenbaum. Operating Systems Design
and Implementation, 2nd Edition. Prentice-Hall, 1997.
[3] Andrew S. Tanenbaum. Modern Operating Systems, Second Edition. Prentice
Hall, 2001.
[4] Robert Love. Linux Kernel Development. Sams, 2004.
[5] Daniele Bovet, Marco Cesati. Understanding the Linux Kernel (2nd Edition).
O’Reilly, 2003.
[6] Mel Gorman. Understanding The Linux Virtual Memory Manager. Unpublished,2004.
[7] Bitkeeper source management system, Linux project
[8] Con Kolivas, Linux Kernel CPU Scheduler Contributor, IRC conversations,
no transcript. December 2004.