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

从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

引用:

[1]Towards Linux 2.6

[2]Linux内核发布模式与开发组织模式(1)

[3] IBM developworks 上有一篇综述文章,值得一读:Linux调度器发展简述

[4]CFS group scheduling [LWN.net]

[5]http://lse.sourceforge.net/numa/

相关推荐