从2.x到4.x，Linux内核这十年经历了哪些重要变革

 Linux内核现在已经进入4.x时代了，但是据说从版本2.6升到3.0，以及3.19升到4.0这之间都没什么太大的变革。事实如此吗?内核版本间的区别有多大?

说实话，这个问题挺大的。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]