从2.x到4.x，Linux内核这十年经历了哪些重要变革
说实话，这个问题挺大的。Linux内核的2.6 时代跨度非常大，从2.6.1 (2003年12月发布) 到 2.6.39(2011年5月发布)，跨越了39 个大版本。3.0(原计划的2.6.40，2011年7月发布) 到 3.19(2015年2月发布)，经历了20个版本。4.0(2015年4月发布)到4.2(2015年8月底发布)，又有3个版本。
总的来说，从进入2.6之后，每个大版本跨度开发时间大概是 2 - 3 个月。2.6.x , 3.x, 4.x，数字的递进并没有非常根本性，引人注目的大变化，但每个大版本中都有一些或大或小的功能改变。主版本号只是一个数字而已。不过要直接从 2.6.x 升级 到 3.x, 乃至 4.x，随着时间间隔增大，出问题的机率当然大很多。
个人觉得 Linux 真正走入严肃级别的高稳定性，高可用性，高可伸缩性的工业级别内核大概是在 2003 年之后吧!一是随着互联网的迅速普及，更多的人使用、参与开发。二是社区经过11年发展，已经慢慢摸索出一套很稳定的协同开发模式，一个重要的特点是社区开始使用版本管理工具进行管理，脱离了之前纯粹手工(或一些辅助的简陋工具)处理代码邮件的方式，大大加快了开发的速度和力度。
因此，本文汇总分析一下从 2.6.12 (2005年6月发布，也就是社区开始使用 git 进行管理后的第一个大版本)，到 4.2 (2015年8月发布)这中间共 51个大版本，时间跨度10年的主要大模块的一些重要的变革。
1.抢占支持(preemption): 2.6 时代开始支持(具体时间难考，是在 2.5 这个奇数版本中引入，可看此文章[1]，关于 Linux 版本规则，可看我文章[2])。
可抢占性，对一个系统的调度延时具有重要意义。2.6 之前，一个进程进入内核态后，别的进程无法抢占，只能等其完成或退出内核态时才能抢占，这带来严重的延时问题，2.6 开始支持内核态抢占。
2.普通进程调度器(SCHED_OTHER)之纠结进化史
Linux一开始，普通进程和实时进程都是基于优先级的一个调度器，实时进程支持 100 个优先级，普通进程是优先级小于实时进程的一个静态优先级，所有普通进程创建时都是默认此优先级，但可通过 nice() 接口调整动态优先级(共40个)。实时进程的调度器比较简单，而普通进程的调度器，则历经变迁[3]：
(1) O(1) 调度器：2.6 时代开始支持(2002年引入)。顾名思义，此调度器为O(1)时间复杂度。该调度器以修正之间的O(n) 时间复杂度调度器，以解决扩展性问题。为每一个动态优先级维护队列，从而能在常数时间内选举下一个进程来执行。
(2) 夭折的 RSDL(The Rotating Staircase Deadline Scheduler)调度器，2007 年4 月提出，预期进入2.6.22，后夭折。
O(1) 调度器存在一个比较严重的问题：复杂的交互进程识别启发式算法-为了识别交互性的和批处理型的两大类进程，该启发式算法融入了睡眠时间作为考量的标准，但对于一些特殊的情况，经常判断不准，而且是改完一种情况又发现一种情况。
Con Kolivas (八卦：这家伙白天是个麻醉医生)为解决这个问题提出RSDL(The Rotating Staircase Deadline Scheduler)算法。该算法的亮点是对公平概念的重新思考：交互式(A)和批量式(B)进程应该是被完全公平对待的，对于两个动态优先级完全一样的 A，B 进程，它们应该被同等地对待，至于它们是交互式与否(交互式的应该被更快调度), 应该从他们对分配给他们的时间片的使用自然地表现出来，而不是应该由调度器自作高明地根据他们的睡眠时间去猜测。这个算法的核心是Rotating Staircase，它是一种衰减式的优先级调整，不同进程的时间片使用方式不同，会让它们以不同的速率衰减(在优先级队列数组中一级一级下降，这是下楼梯这名字的由来)，从而自然地区分开进程是交互式的(间歇性的少量使用时间片)和批量式的(密集的使用时间片)。具体算法细节可看这篇文章：The Rotating Staircase Deadline Scheduler [LWN.net]
(3) 完全公平的调度器(CFS), 2.6.23(2007年10月发布)
Con Kolivas 的完全公平的想法启发了原O(1)调度器作者Ingo Molnar，他重新实现了一个新的调度器，叫CFS。新调度器的核心同样是完全公平性，即平等地看待所有普通进程，让它们自身行为彼此区分开来，从而指导调度器进行下一个执行进程的选举。
具体说来，此算法基于一个理想模型。想像你有一台无限个相同计算力的 CPU，那么完全公平很容易，每个 CPU 上跑一个进程即可。但是，现实的机器 CPU 个数是有限的，超过 CPU 个数的进程数不可能完全同时运行。因此，算法为每个进程维护一个理想的运行时间，及实际的运行时间，这两个时间差值大的，说明受到了不公平待遇，更应得到执行。
至于这种算法如何区分交互式进程和批量式进程，很简单。交互式的进程大部分时间在睡眠，因此它的实际运行时间很小，而理想运行时间是随着时间的前进而增加的，所以这两个时间的差值会变大。与之相反，批量式进程大部分时间在运行，它的实际运行时间和理想运行时间的差距就较小。因此，这两种进程被区分开来。
CFS 的测试性能比 RSDS 好，并得到更多的开发者支持，所以它最终替代了 RSDL 在 2.6.23 进入内核，一直使用到现在。可以八卦的是，Con Kolivas 因此离开了社区，不过他本人否认是因为此事，心生龃龉。后来，2009 年，他对越来越庞杂的 CFS 不满意，认为 CFS 过分注重对大规模机器，而大部分人都是使用少 CPU 的小机器，开发了 BFS 调度器[4]，这个在 Android 中有使用，没进入 Linux 内核。
3.有空时再跑 SCHED_IDLE, 2.6.23(2007年10月发布)
此调度策略和 CFS 调度器在同一版本引入。系统在空闲时，每个 CPU 都有一个 idle 线程在跑，它什么也不做，就是把 CPU 放入硬件睡眠状态以节能(需要特定CPU的driver支持)，并等待新的任务到来，以把 CPU 从睡眠状态中唤醒。如果你有任务想在 CPU 完全 idle 时才执行，就可以用sched_setscheduler() API 设置此策略。
4.吭哧吭哧跑计算 SCHED_BATCH, 2.6.16(2006年3月发布)
概述中讲到 SCHED_BATCH 并非 POSIX 标准要求的调度策略，而是 Linux 自己额外支持的。
它是从 SCHED_OTHER 中分化出来的，和 SCHED_OTHER 一样，不过该调度策略会让采用策略的进程比 SCHED_OTHER 更少受到调度器的重视。因此，它适合非交互性的，CPU 密集运算型的任务。如果你事先知道你的任务属于该类型，可以用 sched_setscheduler() API 设置此策略。
在引入该策略后，原来的 SCHED_OTHER 被改名为 SCHED_NORMAL，不过它的值不变，因此保持API 兼容，之前的 SCHED_OTHER 自动成为 SCHED_NORMAL，除非你设置 SCHED_BATCH。
5.十万火急，限期完成 SCHED_DEADLINE, 3.14(2014年3月发布)
此策略支持的是一种实时任务。对于某些实时任务，具有阵发性(sporadic)，它们阵发性地醒来执行任务，且任务有deadline 要求，因此要保证在deadline 时间到来前完成。为了完成此目标，采用该 SCHED_DEADLINE 的任务是系统中最高优先级的，它们醒来时可以抢占任何进程。
如果你有任务属于该类型，可以用 sched_setscheduler() 或 sched_setattr() API 设置此策略。
更多可参看此文章：Deadline scheduling: coming soon? [LWN.net]
6.普通进程的组调度支持(Fair Group Scheduling), 2.6.24(2008年1月发布)
2.6.23 引入的 CFS 调度器对所有进程完全公平对待。但这有个问题，设想当前机器有2个用户，有一个用户跑着9个进程，还都是CPU 密集型进程;另一个用户只跑着一个 X 进程，这是交互性进程。从 CFS 的角度看，它将平等对待这 10 个进程，结果导致的是跑 X 进程的用户受到不公平对待，他只能得到约 10% 的 CPU 时间，让他的体验相当差。
基于此，组调度的概念被引入[6]。CFS 处理的不再是一个进程的概念，而是调度实体(sched entity)，一个调度实体可以只包含一个进程，也可以包含多个进程。因此，上述例子的困境可以这么解决：分别为每个用户建立一个组，组里放该用户所有进程，从而保证用户间的公平性。
该功能是基于控制组(control group, cgroup)的概念，需要内核开启 CGROUP 的支持才可使用。关于 CGROUP ，以后可能会写。
7.实时进程的组调度支持(RT Group Scheduling), 2.6.25(2008年4月发布)
该功能同普通进程的组调度功能一样，只不过是针对实时进程的。
8.组调度带宽控制((CFS bandwidth control)，3.2(2012年1月发布)
组调度的支持，对实现多租户系统的管理是十分方便的，在一台机器上，可以方便对多用户进行 CPU 均分。然后，这还不足够，组调度只能保证用户间的公平，但若管理员想控制一个用户使用的最大CPU 资源，则需要带宽控制。3.2 针对 CFS组调度，引入了此功能[6]，该功能可以让管理员控制在一段时间内一个组可以使用 CPU 的最长时间。
9.极大提高体验的自动组调度(Auto Group Scheduling)，2.6.38(2011年3月发布)
试想，你在终端里熟练地敲击命令，编译一个大型项目的代码，如Linux内核，然后在编译的同时悠闲地看着电影等待，结果电脑却非常卡，体验一定很不爽。
2.6.38 引入了一个针对桌面用户体验的改进，叫做自动组调度.短短400多行代码[7]，就很大地提高了上述情形中桌面使用者体验，引起不小轰动。
其实原理不复杂，它是基于之前支持的组调度的一个延伸。Unix 世界里，有一个会话(session) 的概念，即跟某一项任务相关的所有进程，可以放在一个会话里，统一管理。比如你登录一个系统，在终端里敲入用户名，密码，然后执行各种操作，这所有进程，就被规划在一个会话。
因此，在上述例子里，编译代码和终端进程在一个会话里，你的浏览器则在另一个会话里。自动组调度的工作就是，把这些不同会话自动分成不同的调度组，从而利用组调度的优势，使浏览器会话不会过多地受到终端会话的影响，从而提高体验。
该功能可以手动关闭。
10.基于调度域的负载均衡，2.6.7(2004年6月发布)
计算机依靠并行度来突破性能瓶颈，CPU个数也是与日俱增。最早的是 SMP(对称多处理)，所以 CPU共享内存，并访问速度一致。随着 CPU 个数的增加，这种做法不适应了，因为 CPU 个数的增多，增加了总线访问冲突，这样 CPU 增加的并行度被访问内存总线的瓶颈给抵消了，于是引入了 NUMA(非一致性内存访问)的概念。机器分为若干个node，每个node(其实一般就是一个socket)有本地可访问的内存，也可以通过 interconnect 中介机构访问别的 node 的内存，但是访问速度降低了，所以叫非一致性内存访问。Linux 2.5版本时就开始了对NUMA 的支持[5]。
而在调度器领域，调度器有一个重要任务就是做负载均衡。当某个 CPU 出现空闲，就要从别的 CPU 上调整任务过来执行;当创建新进程时，调度器也会根据当前负载状况分配一个最适合的 CPU 来执行。然后，这些概念是大大简化了实际情形。
在一个 NUMA 机器上，存在下列层级：
◆每一个NUMA node 是一个 CPU socket(你看主板上CPU位置上那一块东西就是一个socket)。
◆每一个socket上，可能存在两个核，甚至四个核。
◆每一个核上，可以打开硬件多纯程(HyperThread)。
如果一个机器上同时存在这三个层级，则对调度器来说，它所见的一个逻辑 CPU其实是一个HyperThread。处理同一个core 中的CPU，可以共享L1，乃至 L2 缓存，不同的 core 间，可以共享 L3 缓存(如果存在的话)。
基于此，负载均衡不能简单看不同 CPU 上的任务个数，还要考虑缓存，内存访问速度。所以，2.6.7 引入了调度域(sched domain) 的概念，把 CPU 按上述层级划分为不同的层级，构建成一棵树，叶子节点是每个逻辑 CPU，往上一层，是属于 core 这个域，再往上是属于 socket 这个域，再往上是 NUMA 这个域，包含所有 CPU。
当进行负载均衡时，将从最低一级域往上看，如果能在 core 这个层级进行均衡，那最好;否则往上一级，能在socket 一级进行均衡也还凑合;最后是在 NUMA node 之间进行均衡，这是代价非常大的，因为跨 node 的内存访问速度会降低，也许会得不偿失，很少在这一层进行均衡。
这种分层的做法不仅保证了均衡与性能的平衡，还提高了负载均衡的效率。
关于这方面，可以看这篇文章：Scheduling domains [LWN.net]
11.更精确的调度时钟(HRTICK), 2.6.25(2008年4月发布)
CPU的周期性调度，和基于时间片的调度，是要基于时钟中断来触发的。一个典型的 1000 HZ 机器，每秒钟产生 1000 次时间中断，每次中断到来后，调度器会看看是否需要调度。
然而，对于调度时间粒度为微秒(10^-6)级别的精度来说，这每秒 1000 次的粒度就显得太粗糙了。
2.6.25引入了所谓的高清嘀哒(High Resolution Tick)，以提供更精确的调度时钟中断。这个功能是基于高清时钟(High Resolution Timer)框架，这个框架让内核支持可以提供纳秒级别的精度的硬件时钟(将会在时钟子系统里讲)。
12.自动 NUMA 均衡(Automatic NUMA balancing)，3.8(2013年2月发布)
NUMA 机器一个重要特性就是不同 node 之间的内存访问速度有差异，访问本地 node 很快，访问别的 node 则很慢。所以，进程分配内存时，总是优先分配所在 node 上的内存。然而，前面说过，调度器的负载均衡是可能把一个进程从一个 node 迁移到另一个 node 上的，这样就造成了跨 node 的内存访问;Linux 支持 CPU 热插拔，当一个 CPU 下线时，它上面的进程会被迁移到别的 CPU 上，也可能出现这种情况。
调度者和内存领域的开发者一直致力于解决这个问题.由于两大系统都非常复杂，找一个通用的可靠的解决方案不容易，开发者中提出两套解决方案，各有优劣，一直未能达成一致意见。3.8内核中，内存领域的知名黑客 Mel Gorman 基于此情况，引入一个叫自动 NUMA 均衡的框架，以期存在的两套解决方案可以在此框架上进行整合;同时，他在此框架上实现了简单的策略：每当发现有跨 node 访问内存的情况时，就马上把该内存页面迁移到当前 node 上。
不过到 4.2 ，似乎也没发现之前的两套方案有任意一个迁移到这个框架上，倒是，在前述的简单策略上进行更多改进。
如果需要研究此功能的话，可参考以下几篇文章：
◆介绍 3.8 前两套竞争方案的文章：A potential NUMA scheduling solution [LWN.net]
◆介绍 3.8 自动 NUMA 均衡 框架的文章：NUMA in a hurry [LWN.net]
◆介绍 3.8 后进展的两篇文章，细节较多，建议对调度/内存代码有研究后才研读：
NUMA scheduling progress [LWN.net]
https://lwn.net/Articles/591995/
13.CPU 调度与节能
从节能角度讲，如果能维持更多的 CPU 处于深睡眠状态，仅保持必要数目的 CPU 执行任务，就能更好地节约电量，这对笔记本电脑来说，尤其重要。然而，这不是一个简单的工作，这涉及到负载均衡，调度器，节能模块的并互，Linux 调度器中曾经有相关的代码，但后来发现问题，在3.5, 3.6 版本中，已经把相关代码删除.整个问题需要重新思考。
在前不久，一个新的 patch 被提交到 Linux 内核开发邮件列表，这个问题也许有了新的眉目，到时再来更新此小节.可阅读此文章：Steps toward power-aware scheduling
引用：
[3] IBM developworks 上有一篇综述文章，值得一读：Linux调度器发展简述
[4]CFS group scheduling [LWN.net]