 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
Linux内核进程调度schedule深入理解
下载积分：500
内容提示：Linux内核进程调度schedule深入理解一 说明本文以linux 2 4 10..
文档格式：PDF|
浏览次数：68|
上传日期： 06:43:35|
文档星级：
该用户还上传了这些文档
Linux内核进程调度schedule深入理解
官方公共微信Linux 调度器_百度百科
Linux 调度器
本词条缺少概述、名片图，补充相关内容使词条更完整，还能快速升级，赶紧来吧！
Linux 调度器简介：
器（BFS ）是一款专门为 Linux 所设计的调度器，它基于 Staircase Deadline和 EEVDF 算法，支持 Linux 2.6.31之后的内核。它提供了前所未有的流畅桌面性能，不仅得到了用户的认可，也为一些商业系统所采用。
Linux 调度器概述
BFS 是一个进程调度器，可以解释为“脑残调度器”。这古怪的名字有多重含义，比较容易被接受的一个说法为：它如此简单，却如此出色，这会让人对自己的思维能力产生怀疑。
BFS 不会被合并进入 Linus 维护的 Linux mainline，BFS 本身也不打算这么做。但 BFS 拥有众多的拥趸，这只有一个原因：BFS 非常出色，它让用户的达到了前所未有的流畅。在硬件越来越先进，系统却依然常显得迟钝的时代，这实在让人兴奋。
进入 2010 年，Android 开发一个分支使用 BFS 作为其操作系统的标准器，这也证明了 BFS 的价值。后来放弃。
Linux 调度器作者信息
作者名字： CK，
职业：资深
众所周知， 是聚集了一帮天才蠢才和暴君怪胎的地方，CK 貌似最适合这种地方的人。是真的貌似，一张电影里面典型高智商通缉犯的脸。
几年前编译 Linux kernel，ck 补丁集就是系统提速的代名词。当时编译的三部曲是下 kernel 源码，打上 ck 补丁集，编译安装。后来上游将 ck 补丁集稳定的部分不断吸收，它的影响力也渐渐消失。
CK 本身对任务有很深的造诣，他聪明而经典地实现了 fair scheduling，而实现模式被 Igor 借鉴改进最终写出了现在 kernel 用的管理器 CFS (Completely Fair Scheduler)。不得不顺便介绍一下任务。Kernel 的主要是将 CPU 资源分配给各种驱动、进程等等。你可能听说过，一般人的大脑使用率不足 20% 这种科学或者伪科学言论。但事实是，你电脑上的从来就没有真正被 100% 的利用过（别跟我说你在里面看到过 CPU 100%，我还见过 101% 呢）。如何将各种运算任务一刻不停又有条不紊的塞给 CPU 处理是一门严肃的科学，绝不是电视购物导购能解决的问题。一次塞的运算量少了，CPU 闲着，运算时间增长，电脑慢了；而一次塞的运算多了，CPU 忙不过来，运算又要在门口排队，电脑也慢了。主要是用算法解决这个问题，而现在 Linux Kernel 用的 CFS 据说非常经典，在不同情况下都可达到相当高的 CPU 利用率。而现用 CFS 也是在 2.6.23 才加入的，取代原来 O(1)，直接将 Linux 桌面速度从 XX 时代带入了 XX+N 时代。
两年前，CK 淡出了开发，忽然从江湖中蒸发。几周前，CK 重出江湖，两年磨一剑，带来了 BFS ，全称 Brain F u c k Scheduler （只认识中间那个单词的请参考谷歌翻译），声称专为低端硬件设计（我的理解是不超过 10 个 CPU 的电脑游戏机都算低端机），说白了就是比 Kernel 默认要更加山崩地裂海枯石烂房价上涨油价飞升的快。BFS 为什么叫这个名字？为了中文用户，不能三个词让他们一个也不懂吧？ ，这名字有点不雅，不过算是直爽。对了，据说 CK 也是看到上面我提到的漫画才开始剑走偏锋。真正有几个人用有上千 CPU 的电脑呢？为什么要为这种扩展性牺牲桌面性能。BFS 就在其间做了取舍，仅仅支持最多 16 个 CPU ，把问题外沿做小，让算法更简单精悍高效。作为原理来讲，这足够解释速度的来源。对于其它废问题， CK 专门写了一个 FAQ。在可以预见的将来，BFS 也不会进入 mainline kernel，说白了是取向问题。
Linux 调度器对比
讥讽 Linux 调度器的 xkcd 漫画
BFS vs CFS，设计上的不同 白天 Con Kolivas 在医院里当麻醉师，为人们解除痛苦，业余的时候借 Linux 解除自己的痛苦。额，Kolivas 学习 Linux 并不是为了解决痛苦，我臆测而已。但据 Kolivas 自述，他接触 Linux 时连 C 语言也没有学习过。这个事实证明，语言只是一项工具，对问题本质的深入理解才是写程序的关键。可能还有执着，CFS 和 RSDL 之争导致 Kolivas 离开 Linux 社区，此去经年，当 Kolivas 再次开始看的时候，他立即发现 CFS 存在以下几个设计上的问题：
CFS 的目标是支持从到高端服务器的所有应用场景，这种大而全的设计思路导致其必须做一些实现上的折中，此外，那些只有在高端机器中才需要的特性将引入不必要的复杂。
其次，为了维护多 CPU 上的公平性，CFS 采用了机制，Kolivas 认为，这些复杂抵消了 per
queue 曾带来的好处。
最后，主流的 CFS 还是对睡眠存在一些偏好，这意味着“不公平”。
Linux 调度器设计目标的不同
在现实中，类似一个处境尴尬的主妇，满足孩子对晚餐的要求便有可能伤害到老人的食欲。Linux 一直试图做出一道让全家老少都喜欢的菜，在这方面，CFS 已经做的很好。但一道能被所有人接受的菜，或许就意味着稍许平淡。而 BFS 只打算满足一种口味，以便将这种口味发展到极限。
根据 Linux Magazine的说法，是看到了下面这则来自 xkcd 的漫画而开始思考 BFS 的。
事情源于一些 Linux 用户，他们发现 Linux 虽然号称能够充分发挥 4096 颗 CPU 系统的计算能力，但在普通的 laptop 上却无法流畅地播放
这让人们开始思考，对于 Desktop 环境来讲，CFS 哪些复杂的特性究竟是否还有意义？人们是否有必要在自己的个人电脑中使用一个支持 4096 个 CPU 的器？
BFS 正是对这种质疑的自然反应。它不打算支持 4096 个 CPU 的庞然大物，BFS 的目标是普通人使用的桌面电脑。此外，BFS 还删除了那些只有在服务器上才需要的特性。比如，BFS 抛弃了 CFS 的组调度特性，类似 CGROUP 这样的特性对于普通的桌面用户是多余的技术。
这很容易理解：在只有一个 CPU 的系统中，谁还会设计多个 ，哪里还能用到 NUMA domain等概念呢？
此外 BFS 使用单一的 run queue，不再需要复杂的机制。由于不再有 CGROUP 概念，也不再需要 Group 间的。
这些简单的裁剪使得 BFS 的极大地简化，简化的意味着执行一次所需要的数减少了，相应的 footprint 自然也减少了。
当然简化只是一个显而易见的方面，更重要的是，这种理念的不同会对最终的器实现产生更加深远的影响，这实在是难以尽述。
Linux 调度器多队列 vs 单一队列
在 Linux 进入 2.6 时，器采用 per
run queue 从而克服了单一 run queue 的局限。在多 CPU 系统中，单一 run queue 意味着 run queue 成为了系统的瓶颈，因为在同一时刻，一个 CPU 访问 run queue 时，其他的 CPU 即使空闲也必须等待。当使用 per CPU 的 run queue 之后，每个 CPU 不必再使用大锁，从而能够并行地处理。
但很多事情都不像第一眼看上去那样简单。
Kolivas 发现，采用 per
run queue 所带来的好处会被追求公平性的 load balance 所抵消。在目前的 CFS 器中，每颗 CPU 只维护本地 run queue 中所有的公平性，为了实现跨 CPU 的调度公平性，CFS 必须定时进行 load balance，将一些进程从繁忙的
的 run queue 中移到其他空闲的 run queue 中。
这个 load balance 的过程需要获得其他 run queue 的锁，这种操作降低了多运行队列带来的。
并且在复杂情况下，这种因 load balance 而引入的 footprint 将非常可观。
当然，load balance 引入的加锁操作依然比全局锁的代价要低，这种代价差异随着 CPU 个数的增加而更加显著。但请您注意，BFS 并不打算为那些拥有 1024 个 CPU 的系统工作，假若系统中的 CPU 个数有限时，多 run queue 的优势便不明显了。
而 BFS 采用单一之后，每一个需要的新都可以在全局范围内查找最合适的 CPU，而无需 CFS 那样等待 load balance 来决定，这减少了多 CPU 之间裁决的延迟，最终的结果是更小的调度延迟。
向前看还是向后看？
多年来 Kolivas 一直关注着 Linux 在
上的表现。对于
的用户，最注重的不是系统的吞吐量，而是交互性程序的流畅体验。从
开始，Kolivas 就告诉们，完全公平能够从根本上保证交互性。他始终坚持一个基本观点：器应该 forward look only。决不要去考虑一个的过去。
CFS 却偏偏要考虑的过去。2.6.23 的时候，CFS 记录并使用 sleep time。之后不久，在 2.6.24 发布的时候，CFS 合并了“Real Fair Scheduler”，删除了 sleep time。因此在 2.6.24 之后的中，CFS 终于也不再考虑过去的睡眠时间。
但 CFS 还是保留了 sleeper fairness 的思想，当 wakeup 的时候，在 place_entity() 函数中，CFS 将对 sleeper 进行奖励，以便其能尽快得到 CPU。这个策略是非常微妙的，我们在 2.1 节中详细介绍了 sleeper fairness 的演进过程。假如您花些时间回头再看看，就会发现 sleeper fairness 曾造成怎样严重的延迟问题。虽然 Ingo 自称 Gentle fairness 解决了延迟问题，但从上看，Gentle Fairness 只是对 sleeper 的奖励减半而已。因此我们可以说，CFS 依然对 Sleeper 进行奖励，这代表着一种偏好，一种“不公平”。而这，正是 BFS 所反对的。
BFS 中，当一个 wakeup 时，器将根据进程的 deadline 来进行选择（关于 deadline 本文将在第 4 章中详细描述），其结果是，更早睡眠的进程能更快地得到调度；CFS 的 sleeper fairness 则意味着要根据 wakeup 的时间来选择下一个被调度的，更早 wakeup 的进程会更快得到。
这种不同究竟会对桌面应用造成何种影响尚没有理论依据可以参考。但我个人认为，BFS 的策略更加合理。
您现在可能已经读得有些烦躁了 ( 这些英文加中文的说些啥啊 )，所以我还是尽快介绍一下 BFS 的实现细节吧。然后或许您会理解我，有些词还是不翻译更好。
Linux 调度器BFS 实现原理
器是非常复杂的话题，尤其是
调度器，想要描述清楚，需要一支非凡的笔，我还没有找到。但 BFS 非常简单，所以我才有勇气在这里写点儿 BFS 的实现原理什么的。首先介绍几个关键概念。
虚拟 Deadline ( Virtual Deadline )
当一个被创建时，它被赋予一个固定的，和一个虚拟 Deadline。该虚拟 deadline 的计算公式非常简单：
Virtual Deadline = jiffies + (user_priority * rr_interval)
其中 jiffies 是当前时间 , user_priority 是的优先级，rr_interval 代表 round-robin interval，近似于一个进程必须被的最后期限，所谓 Deadline 么。不过在这个 Deadline 之前还有一个形容词为 Virtual，因此这个 Deadline 只是表达一种愿望而已，并非很多领导们常说的那种 deadline。
虚拟 Deadline 将用于器的 picknext 决策，这将在后续章节详细描述。
Linux 调度器进程队列的表示方法和调度策略
在操作系统内部，所有的 Ready 都被存放在进程队列中，器从进程队列中选取下一个被调度的进程。因此如何设计队列是我们研究器的一个重要话题。BFS 采用了非常传统的队列表示方法，即 bitmap 加 queue。
BFS 将所有分成 4 类，分别表示不同的策略 :
Realtime，实时 SCHED_ISO，isochronous 进程，用于交互式任务 SCHED_NORMAL，普通进程 SCHED_IDELPRO，低优先级任务 实时进程总能获得 CPU，采用 Round Robin 或者 FIFO 的方法来选择同样优先级的实时进程。他们需要 superuser 的权限，通常限于那些占用 CPU 时间不多却非常在乎 Latency 的。
SCHED_ISO 在主流中至今仍未实现，Con 早在 2003 年就提出了这个 patch，但一直无法进入主流内核，这种策略是为了那些 near-realtime 的设计的。如前所述，实时需要用户有 superuser 的权限，这类进程能够独占 CPU，因此只有很少的进程可以被配置为实时进程。对于那些对交互性要求比较高的，又无法成为实时的进程，BFS 将采用 SCHED_ISO，这些进程能够抢占 SCHED_NORMAL 进程。他们的优先级比 SCHED_NORMAL 高，但又低于实时。此外当 SCHED_ISO 占用 CPU 时间达到一定限度后，会被降级为 SCHED_NORMAL，防止其独占整个系统资源。
SCHED_NORMAL 类似于主流器 CFS 中的 SCHED_OTHER，是基本的分时调度策略。
SCHED_IDELPRO 类似于 CFS 中的 SCHED_IDLE，即只有当 CPU 即将处于 IDLE 状态时才被的进程。
在这些不同的策略中，实时分成 100 个不同的优先级，加上其他三个调度策略，一共有 103 个不
经常调度策略示意图
同的进程类型。对于每个类型，系统中都有可能有多个进程同时 Ready，比如很可能有两个优先级为 10 的 RT 进程同时 Ready，所以对于每个类型，还需要一个来存储属于该类型的 ready 进程。
BFS 用 103 个 bitmap 来表示是否有相应类型的准备进行。如图所示：
当任何一种类型的进程队列非空时，即存在 Ready 时，相应的 bitmap 位被设置为 1。
器如何在这样一个 bitmap 加 queue 的复杂结构中选择下一个被调度的的问题被称为 Task Selection 或者 pick next。
Task Selection i.e. Pick Next
当器决定进行的时候，BFS 将按照下面的原则来进行任务的选择：
首先查看 bitmap 是否有置位的比特。比如上图，对应于 SCHED_NORMAL 的 bit 被置位，表明有类型为 SCHED_NORMAL 的 ready。如果有 SCHED_ISO 或者 RT task 的比特被置位，则优先处理他们。
选定了相应的 bit 位之后，便需要遍历其相应的子。假如是一个 RT 进程的子，则选取其中的第一个进程。如果是其他的，那么就采用 EEVDF 算法来选取合适的。
EEVDF，即 earliest eligible virtual deadline first。BFS 将遍历该子队列，一个双向列表，比较队列中的每一个的 Virtual Deadline 值，找到最小的那个。最坏情况下，这是一个 O(n) 的算法，即需要遍历整个双向列表，假如其中有 n 个，就需要进行 n 此读取和比较。
但实际上，往往不需要遍历整个 n 个，这是因为 BFS 还有这样一个搜索条件：
当某个的 Virtual Deadline 小于当前的 jiffies 值时，直接返回该进程。并将其从就绪队列中删除，下次再 insert 时会放到队列的尾部，从而保证每个都有可能被选中，而不会出现饥饿现象。
这条规则对应于这样一种情况，即已经睡眠了比较长的时间，以至于已经睡过了它的 Virtual Deadline，
T1 本来的 virtual deadline 为 t1，它 sleep 之后，其他的比如 T2 开始运行，等到 T1 再次 wakeup 的时候，当时的 jiffies 已经大于 t1，在这种情况下，T1 无需和其他进程的 virtual deadline 相比较，而直接被 BFS 器选取。
Linux 调度器基本的调度场景
三个基本的 scenario 可以概括多数的情景。系统中发生的每一次都属于以下三种情景之一。
wakeup：Insertion
睡眠 wakeup 时，器需要执行 task insertion 的操作，将该到 run queue 中。BFS 将进程插入相应的操作就是执行一个双向队列的插入操作，计算机常用算法结构告诉我们，这个操作是 O(1) 的。不过，BFS 在执行插入操作之前需要首先查看当前是否可以抢占当前正在系统中运行的进程。因此它会用新的 virtual deadline 值和当前在每个 CPU 上正在运行的进程的 virtual deadline 值进行比较，如果新进程的值小，则直接抢占该 CPU 上正在运行的进程。这个算法是 O(m) 的，其中 m 是 CPU 的个数，假如系统中有 16 个 CPU，那么每次都需要进行 16 次比较。但这个设计却保证了非常好的 low-latency 特性。
当前正在运行的有可能主动睡眠，此时，器需要将该从 run queue 中移除，并选择另外一个进程运行。但该的 virtual deadline 的值保持不变。
这样该 wakeup 时，其 virtual deadline 将相对较小，因为 jiffies 随着时间流逝而不断增加。较小的 Virtual Deadline 可以保证该能更快得到调度。
仍然以图 8 为例，系统中有两个，T1 和 T2，T1 进入 sleep 状态后其 virtual deadline 仍然为 t1。T2 此时被，根据公式一，计算得出其 virtual deadline 为 t2。此后，T1
wakeup 了，此时虽然 T2 的尚未用完，但由于 T1 的 virtual deadline 小于 T2 的，（t1&t2），因此 T1 立即得到。
用完自己的
每个都拥有自己的，即使不被其他进程抢占，假如属于自己的时间片用完时，当前进程也一定会被剥夺 CPU 时间，以便让别的进程有机会执行。
当前进程的用完后就必须让出 CPU, 此时将它的 virtual deadline 按照公式一重新计算。
这保证了一个特性：只有其他就绪都获得 CPU 之后，用完当前的进程才可以再次得到运行，这避免了饥饿。
企业信用信息IBM Bluemix
点击按钮，开始云上的开发！
developerWorks 社区
Linux® 内核继续不断发展并采用新技术，在可靠性、可伸缩性和性能方面获得了长足的发展。2.6 版本的内核最重要的特性之一是由 Ingo Molnar 实现的调度器。这个调度器是动态的，可以支持负载均衡，并以恒定的速度进行操作 ——
O(1)。本文将介绍 Linux 2.6 调度器的这些属性以及更多内容。
(), 顾问工程师, Emulex
Tim Jones 是一名嵌入式软件工程师，他是 GNU/Linux Application Programming、AI Application Programming 以及 BSD Sockets Programming from a Multilanguage Perspective 等书的作者。他的工程背景非常广泛，从同步宇宙飞船的内核开发到嵌入式架构设计，再到网络协议的开发。Tim 是 Emulex Corp. 的一名顾问工程师。
本文将回顾一下 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) 的过程，因为调度时间既是固定的，而且也不会受到活动任务个数的影响。更好地支持 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 操作完成上面花费更多的时间。这会提高其交互性指标。有一点值得注意，优先级的调整只会对用户任务进行，对于实时任务来说并不会对其优先级进行调整。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 中对在这个文件中可以找到的一些有用的函数进行了总结。表 1. Linux 2.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 都提供了很多数据，包括负载均衡和进程迁移的统计信息。展望Linux 2.6 调度器从早先的 Linux 调度器已经跨越了一大步。它极大地改善了最大化利用 CPU 的能力，同时还为用户提供了很好的响应体验。抢占和对多处理器体系架构的更好支持使整个系统更接近于多桌面和实时系统都非常有用的操作系统。Linux 2.8 版本的内核现在谈论还为时尚早，但是从 2.6 版本的变化中，我们可以期望会有更多的好东西。
参考资料 您可以参阅本文在 developerWorks 全球站点上的
“”（developerWorks，2003 年 1 月）解释了如何确定 Linux 内核系统的性能，这样我们就可以对系统进行评测和调优（包括调度器调优）。
Open Source Development Labs 上的
文章给出了 2.6 版本的调度器对 2.4 版本的调度器在各种多处理器系统配置上的改进。
“”（Linux Journal，2004 年 3 月）简要介绍了 2.6 版本内核的一些重要特性，包括调度器及其在嵌入式系统中的影响。
“”（developerWorks，2004 年 2 月）对让 2.6 版本更好的工具、测试和技术进行了介绍。
IBM 红皮书 （2004 年 7 月）重点介绍了围绕着实际应用程序和 Linux 2.6 框架周围的与可伸缩性和性能有关的问题。
“”（developerWorks，2004 年 7 月）重点介绍了 2.4 版本和 2.6 版本的 Linux 内核在 POWER 架构上的区别。
“”（RTC Magazine，2003 年 11 月）讨论了具有实时属性的嵌入式系统如何从 2.6 版本的调度器中获得最多优势。
在 （Ulrich Weigand 博士的一篇演示文稿），我们可以看到 Linux 2.6 是如何帮助 IBM zSeries 开发的。
可以找到为 Linux 开发人员准备的更多资源。
随时关注 。
上，查找最新的 Linux 内核。
在您的下一个开发项目中采用 ，这可以从 developerWorks 上直接下载。
加入 developerWorks 社区。
developerWorks: 登录
标有星（*）号的字段是必填字段。
保持登录。
单击提交则表示您同意developerWorks 的条款和条件。 查看条款和条件。
在您首次登录 developerWorks 时，会为您创建一份个人概要。您的个人概要中的信息（您的姓名、国家/地区，以及公司名称）是公开显示的，而且会随着您发布的任何内容一起显示，除非您选择隐藏您的公司名称。您可以随时更新您的 IBM 帐户。
所有提交的信息确保安全。
选择您的昵称
当您初次登录到 developerWorks 时，将会为您创建一份概要信息，您需要指定一个昵称。您的昵称将和您在 developerWorks 发布的内容显示在一起。昵称长度在 3 至 31 个字符之间。
您的昵称在 developerWorks 社区中必须是唯一的，并且出于隐私保护的原因，不能是您的电子邮件地址。
标有星（*）号的字段是必填字段。
(昵称长度在 3 至 31 个字符之间)
单击提交则表示您同意developerWorks 的条款和条件。 .
所有提交的信息确保安全。
文章、教程、演示，帮助您构建、部署和管理云应用。
立即加入来自 IBM 的专业 IT 社交网络。
为灾难恢复构建应用，赢取现金大奖。
static.content.url=/developerworks/js/artrating/SITE_ID=10Zone=LinuxArticleID=157985ArticleTitle=Linux 调度器内幕publish-date=