存储技术原理分析:基于Linux 2.6内核源代码

linux调度器(BFS )是一款专门为 Linux 桌面环境所设计的内核调度器，它基于 Staircase Deadline和 EEVDF 算法，支持 Linux 2.6.31之后的内核。它提供了前所未有的流畅桌面性能，不仅得到了用户的认可，也为一些商业系统所采用。

BFS vs CFS，设计上的不同 白天 Con Kolivas 在医院里当麻醉师，为人们解除痛苦，业余的时候借 Linux 解除自己的痛苦。额，Kolivas 学习 Linux 并不是为了解决痛苦，我臆测而已。但据 Kolivas 自述，他接触 Linux 内核时连 C 语言也没有学习过。。。这个事实证明，语言只是一项工具，对问题本质的深入理解才是写程序的关键。可能还有执着，CFS 和 RSDL 之争导致 Kolivas 离开 Linux 社区，此去经年，当 Kolivas 再次开始看内核代码的时候，他立即发现 CFS 存在以下几个设计上的问题:

CFS 的目标是支持从桌面到高端服务器的所有应用场景，这种大而全的设计思路导致其必须做一些实现上的折中，此外，那些只有在高端机器中才需要的特性将引入不必要的复杂代码。

其次，为了维护多 CPU 上的公平性，CFS 采用了负载平衡机制，Kolivas 认为，这些复杂代码抵消了 per cpu queue 曾带来的好处。

最后，主流内核的 CFS 还是对睡眠进程存在一些偏好，这意味着"不公平"。

在现实中，调度算法类似一个处境尴尬的主妇，满足孩子对晚餐的要求便有可能伤害到老人的食欲。Linux 内核一直试图做出一道让全家老少都喜欢的菜，在这方面，CFS 已经做的很好。但一道能被所有人接受的菜，或许就意味着稍许平淡。而 BFS 只打算满足一种口味，以便将这种口味发展到极限。

根据 Linux Magazine的说法，Con Kolivas是看到了下面这则来自 xkcd 的漫画而开始思考 BFS 的。

事情源于一些 Linux 用户，他们发现 Linux 虽然号称能够充分发挥 4096 颗 CPU 系统的计算能力，但在普通的 laptop 上却无法流畅地播放 Youtube 视频。

这让人们开始思考，对于 Desktop 环境来讲，CFS 哪些复杂的特性究竟是否还有意义?人们是否有必要在自己的个人电脑中使用一个支持 4096 个 CPU 的调度器?

BFS 正是对这种质疑的自然反应。它不打算支持 4096 个 CPU 的庞然大物，BFS 的目标是普通人使用的桌面电脑。此外，BFS 还删除了那些只有在服务器上才需要的特性。比如，BFS 抛弃了 CFS 的组调度特性，类似 CGROUP 这样的特性对于普通的桌面用户是多余的技术。

这很容易理解:在只有一个 CPU 的系统中，谁还会设计多个 CGroup，哪里还能用到 NUMA domain等概念呢?

此外 BFS 使用单一的 run queue，不再需要复杂的负载均衡机制。由于不再有 CGROUP 概念，也不再需要 Group 间的负载均衡。

这些简单的裁剪使得 BFS 的代码极大地简化，简化的代码意味着执行一次调度所需要的指令数减少了，相应的 footprint 自然也减少了。

当然简化代码只是一个显而易见的方面，更重要的是，这种理念的不同会对最终的调度器实现产生更加深远的影响，这实在是难以尽述。

多队列 vs 单一队列

​在 Linux 内核进入 2.6 时，调度器采用 per cpu run queue 从而克服了单一 run queue 的局限。在多 CPU 系统中，单一 run queue 意味着 run queue 成为了系统的瓶颈，因为在同一时刻，一个 CPU 访问 run queue 时，其他的 CPU 即使空闲也必须等待。当使用 per CPU 的 run queue 之后，每个 CPU 不必再使用大锁，从而能够并行地处理调度。

但很多事情都不像第一眼看上去那样简单。

Kolivas 发现，采用 per cpu run queue 所带来的好处会被追求公平性的 load balance 代码所抵消。在目前的 CFS 调度器中，每颗 CPU 只维护本地 run queue 中所有进程的公平性，为了实现跨 CPU 的调度公平性，CFS 必须定时进行 load balance，将一些进程从繁忙的 CPU 的 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 在 desktop 上的表现。对于 desktop 的用户，最注重的不是系统的吞吐量，而是交互性程序的流畅体验。从 SD 开始，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 的实现细节吧。然后或许您会理解我，有些词还是不翻译更好。

内核是操作系统最内核最基础的构件，因而，内核结构往往对操作系统的外部特性以及应用领域有着一定程度的影响。尽管随着理论和实践的不断演进，操作系统高层特性与内核结构之间的耦合有日趋缩小之势，但习惯上，内核结构仍然是操作系统分类之常用标准。

内核的结构可以分为单内核、微内核、混合内核、外内核等。

单内核（Monolithic kernel），又称为宏内核。单内核结构是操作系统中各内核部件杂然混居的形态，该结构于1960年代（亦有1950年代初之说，尚存争议），历史最长，是操作系统内核与外围分离时的最初形态。

微内核（Microkernel），又称为微核心。微内核结构是1980年代产生出来的较新的内核结构，强调结构性部件与功能性部件的分离。20世纪末，基于微内核结构，理论界中又发展出了超微内核与外内核等多种结构。尽管自1980年代起，大部分理论研究都集中在以微内核为首的“新兴”结构之上，然而，在应用领域之中，以单内核结构为基础的操作系统却一直占据着主导地位。

混合内核（Hybrid kernel）像微内核结构，只不过它的组件更多的在核心态中运行，以获得更快的执行速度。

外内核（Exokernel）的设计理念是尽可能的减少软件的抽象化，这使得开发者可以专注于硬件的抽象化。外核心的设计极为简化，它的目标是在于同时简化传统微内核的讯息传递机制，以及整块性核心的软件抽象层。

在众多常用操作系统之中，除了QNX和基于Mach的UNIX等个别系统外，几乎全部采用单内核结构，例如大部分的Unix、Linux，以及Windows（微软声称Windows NT是基于改良的微内核架构的，尽管理论界对此存有异议）。 微内核和超微内核结构主要用于研究性操作系统，还有一些嵌入式系统使用外核。

基于单内核的操作系统通常有着较长的历史渊源。例如，绝大部分UNIX的家族史都可上溯至1960年代。该类操作系统多数有着相对古老的设计和实现（例如某些UNIX中存在着大量1970年代、1980年代的代码）。另外，往往在性能方面略优于同一应用领域中采用其他内核结构的操作系统（但通常认为此种性能优势不能完全归功于单内核结构）。