momo zone

调核人的blog

关于大内核锁

大内核锁这个简单且不常用的内核加锁机制一直是内核开发者之间颇具争议的话题。它在早期linux版本里的广泛使用,从2.4内核开始逐渐被各种各样的自旋锁替代,可是直到现在还不能完全将它抛弃;它曾经使用自旋锁实现,到了2.6.11版修改为信号量,可是在2.6.26-rc2又退回到使用自旋锁的老路上;它甚至引发了linux的创始人Linus Torvalds和著名的完全公平调度(CFS)算法的贡献者Ingo Molnar之间的一场争议。这究竟是怎么回事呢?

1.1         应运而生,特立独行

使用过自旋锁或信号量这些内核互斥机制的人几乎不会想到还有大内核锁这个东西。和自旋锁或信号量一样,大内核锁也是用来保护临界区资源,避免出现多个处理器上的进程同时访问同一区域的。但这把锁独特的地方是,它不象自旋锁或信号量一样可以创建许多实例或者叫对象,每个对象保护特定的临界区。事实上整个内核只有一把这样的锁,一旦一个进程获得大内核锁,进入了被它保护的临界区,不但该临界区被锁住,所有被它保护的其它临界区都将无法访问,直到该进程释放大内核锁。这看似不可思议:一个进程在一个处理器上操作一个全局的链表,怎么可能导致其它进程无法访问另一个全局数组呢?使用两个自旋锁,一个保护链表,另一个保护数组不就解决了吗?可是如果你使用大内核锁,效果就是这样的。

大内核锁的产生是有其历史原因的。早期linux版本对对称多处理(SMP)器的支持非常有限,为了保证可靠性,对处理器之间的互斥采取了‘宁可错杀三千,不可放过一个’的方式:在内核入口处安装一把‘巨大’的锁,一旦一个处理器进入内核态就立刻上锁,其它将要进入内核态的进程只能在门口等待,以此保证每次只有一个进程处于内核态运行。这把锁就是大内核锁。有了大内核锁保护的系统当然可以安全地运行在多处理器上:由于同时只有一个处理器在运行内核代码,内核的执行本质上和单处理器没有什么区别;而多个处理器同时运行于进程的用户态也是安全的,因为每个进程有自己独立的地址空间。但是这样粗鲁地加锁其缺点也是显而易见的:多处理器对性能的提示只能体现在用户态的并行处理上,而在内核态下还是单线执行,完全无法发挥多处理器的威力。于是内核开发者就开始想办法逐步缩小这把锁保护的范围。实际上内核大部分代码是多处理器安全的,只有少数全局资源需要需要在做互斥加以保护,所以没必要限制同时运行于内核态处理器的个数。所有处理器都可随时进入内核态运行,只要把这些需要保护的资源一一挑出来,限制同时访问这些资源的处理器个数就可以了。这样一来,大内核锁从保护整个内核态缩小为零散地保护内核态某些关键片段。这是一个进步,可步伐还不够大,仍有上面提到的,‘锁了卧室厨房也没法进’的毛病。随着自旋锁的广泛应用,新的内核代码里已经不再有人使用大内核锁了。

1.2      食之无味,挥之不去

既然已经有了替代物,大内核锁应该可以‘光荣下岗’了。可事实上没这么简单。如果大内核锁仅仅是‘只有一个实例’的自旋锁,睿智的内核开发者早就把它替换掉了:为每一种处于自旋锁保护下的资源创建一把自旋锁,把大内核锁加锁/解锁替换成相应的自旋锁的加锁/解锁就可以了。但如今的大内核锁就象一个被宠坏的孩子,内核在一些关键点给予了它许多额外关照,使得大内核锁的替换变得有点烦。下面是Ingo Molnar在一封名为 ’kill the Big Kernel Lock (BKL)’的邮件里的抱怨:

The biggest technical complication is that the BKL is unlike any other lock: it “self-releases” when schedule() is called. This makes the BKL spinlock very “sticky”, “invisible” and viral: it’s very easy to add it to a piece of code (even unknowingly) and you never really know whether it’s held or not. PREEMPT_BKL made it even more invisible, because it made its effects even less visible to ordinary users.

这段话的大意是:最大的技术难点是大内核锁的与众不同:它在调用schedule()时能够‘自动释放’。这一点使得大内核锁非常麻烦和隐蔽:它使你能够非常容易地添加一段代码而几乎从不知道它锁上与否。PREEMPT_BKL选项使得它更加隐蔽,因为这导致它的效果在普通用户面前更加‘遁形’。

翻译linux开发者的话比看懂他们写的代码更难,但有一点很明白:是schedule()函数里对于大内核锁的自动释放导致了问题的复杂化。那就看看schedule()里到底对大内核锁执行了什么操作:

1 /*

2  * schedule() is the main scheduler function.

3  */

4 asmlinkage void __sched schedule(void)

5 {

19     release_kernel_lock(prev);

55         context_switch(rq, prev, next); /* unlocks the rq */

67     if (unlikely(reacquire_kernel_lock(current) < 0)) {

68         prev = rq->curr;

69         switch_count = &prev->nivcsw;

70         goto need_resched_nonpreemptible;

71     }

code 1.2‑1 linux_2.6.34/kernel/sched.c

在第19行release_kernel_lock(prev)函数释放当前进程(prev)所占据的大内核锁,接着在第55行执行进程的切换,从当前进程prev 切换到了下一个进程next。context_switch()可以看做一个超级函数,调用它不是去执行一段代码,而是去执行另一个进程。系统的多任务切换就是依靠这个超级函数从一个进程切换到另一个进程,从另一个进程再切换下一个进程,如此连续不断地轮转。只要被切走的进程还处于就绪状态,总有一天还会有机会调度回来继续运行,效果看起来就象函数context_switch()运行完毕返回到了schedule()。继续运行到第67行,调用函数reacquire_kernel_lock()。这是和release_kernel_lock()配对的函数,将前面释放的大内核锁又重新锁起来。If语句测试为真表示对大内核锁尝试加锁失败,这时可以做一些优化。正常的加锁应该是‘原地踏步’,在同一个地方反复查询大内核锁的状态,直到其它进程释放为止。但这样做会浪费宝贵的处理器时间,尤其是当运行队列里有进程在等待运行时。所以release_lernel_lock()只是做了’try_lock’的工作,即假如没人把持大内核锁就把它锁住,返回0表示成功;假如已经被锁住就立即返回-1表示失败。一旦失败就重新执行一遍schedule()的主体部分,检查运行队列,挑选一个合适的进程运行,等到下一次被调度运行时可能锁就解开了。这样做利用另一个进程(假如有进程在排队等候)的运行代替了原地死等,提高了处理器利用率。

除了在schedule()中的‘照顾’,大内核锁还有另外的优待:在同一进程中你可以对它反复嵌套加锁解锁,只要加锁个数和解锁个数能配上对就不会有任何问题,这是自旋锁望尘莫及的,同一进程里自旋锁如果发生嵌套加锁就会死锁。为此在进程控制块(PCB)中专门为大内核锁开辟了加锁计数器,即task_struct中的lock_depth域。该域的初始值为-1,表示进程没有获得大内核锁。每次加锁时lock_depth都会加1,再检查如果lock_depth为0就执行真正的加锁操作,这样保证在加了一次锁以后所有嵌套的加锁操作都会被忽略,从而避免了死锁。解锁过程正好相反,每次都将lock_depth减1,直到发现其值变为-1时就执行真正的解锁操作。

内核对大内核锁的偏袒导致开发者在锁住了它,进入被它保护的临界区后,执行了不该执行的代码却还无法察觉。其一:程序在锁住临界区后必须尽快退出,否则会阻塞其它将要进入临界区的进程。所以在临界区里绝对不可以调用schedule()函数,否则一旦发生进程切换何时能解锁就变得遥遥无期。另外在使用自旋锁保护的临界区中做进程切换很容易造成死锁。比如一个进程锁住了一把自旋锁,期间调用schedule()切换到另一个进程,而这个进程又要获得这把锁,这是系统就会挂死在这个进程等待解锁的自旋处。这个问题在大内核锁保护的临界区是不存在的,因为schedule()函数在调度到新进程之前会自动解锁已经获得的大内核锁;在切回该进程时又会自动将大内核锁锁住。用户在锁住了大内核锁后,几乎无法察觉期间是否用过schedule()函数。这一点就是上面Ingo Molnar提到的’technical complication’:将大内核锁替换成自旋锁后,万一在加锁过程中调用了schedule(),会造成不可预估的,灾难性的后果。当然作为一个训练有素的程序员,即使大内核锁放宽了约束条件,也不会在临界区中有意识地调用schedule()函数的。可是如果是调用陌生模块的代码,再高超的程序员也无法保证其中不会调用到该函数。其二就是上面提到的,在临界区中不能再次获得保护该临界区的锁,否则会死锁。可是由于大内核锁有加锁计数器的保护,怎样嵌套也不会有事。这也是一个’technical complication’:将大内核锁替换成自旋锁后,万一发生了同一把自旋锁的嵌套加锁后果也是灾难性的。同schedule()函数一样,训练有素的程序员是不会有意识地多次锁住大内核锁,但在获得自旋锁后调用了陌生模块的代码就无法保证这些模块中不会再次使用大内核锁。这种情况在开发大型系统时非常常见:每个人都很小心地避免自己模块的死锁,可谁也无法避免当调用其它模块时可能引入的死锁问题。

Ingo Molnar还提到了大内核锁的另一弊端:大内核锁没有被lockdep所覆盖。lockdep是linux内核的一个调试模块,用来检查内核互斥机制尤其是自旋锁潜在的死锁问题。自旋锁由于是查询方式等待,不释放处理器,比一般的互斥机制更容易死锁,故引入lockdep检查以下几种情况可能的死锁(lockdep将有专门的文章详细介绍,在此只是简单列举):

  • 同一个进程递归地加锁同一把锁;
  • 一把锁既在中断(或中断下半部)使能的情况下执行过加锁操作,又在中断(或中断下半部)里执行过加锁操作。这样该锁有可能在锁定时由于中断发生又试图在同一处理器上加锁;
  • 加锁后导致依赖图产生成闭环,这是典型的死锁现象。

由于大内核锁游离于lockdep之外,它自身以及和其它互斥机制之间的依赖关系没有受到监控,可能会导致死锁的场景也无法被记录下来,使得它的使用越来越混乱,处于失控状态。

如此看来,大内核锁已经成了内核的鸡肋,而且不能与时俱进,到了非整改不可的地步。可是将大内核锁完全从内核中移除将要面临重重挑战,对于那些散落在‘年久失修’,多年无人问津的代码里的大内核锁,更是没人敢去动它们。既然完全移除希望不大,那就想办法优化它也不失为一种权宜之计。

1.3      一改再改:无奈的选择

早些时候大内核锁是在自旋锁的基础上实现的。自旋锁是处理器之间临界区互斥常用的机制。当临界区非常短暂,比如只改变几个变量的值时,自旋锁是一种简单高效的互斥手段。但自旋锁的缺点是会增大系统负荷,因为在自旋等待过程中进程依旧占据处理器,这部分等待时间是在做无用功。尤其是使用大内核锁时,一把锁管所有临界区,发生‘碰撞’的机会就更大了。另外为了使进程能够尽快全速‘冲’出临界区,自旋锁在加锁的同时关闭了内核抢占式调度。因此锁住自旋锁就意味着在一个处理器上制造了一个调度‘禁区’:期间既不被其它进程抢占,又不允许调用schedule()进行自主进程切换。也就是说,一旦处理器上某个进程获得了自旋锁,该处理器就只能一直运行该进程,即便有高优先级的实时进程就绪也只能排队等候。调度禁区的出现增加了调度延时,降低了系统实时反应的速度,这与大家一直努力从事的内核实时化改造是背道而驰的。于是在2.6.7版本的linux中对自旋锁做了彻底改造,放弃了自旋锁改用信号量。信号量没有上面提到的两个问题:在等待信号量空闲时进程不占用处理器,处于阻塞状态;在获得信号量后内核抢占依旧是使能的,不会出现调度盲区。这样的解决方案应该毫无争议了。可任何事情都是有利有弊的。信号量最大的缺陷是太复杂了,每次阻塞一个进程时都要产生费时的进程上下文切换,信号量就绪唤醒等待的进程时又有一次上下文切换。除了上下文切换耗时,进程切换造成的TLB刷新,cache冷却等都有较大开销。如果阻塞时间比较长,达到毫秒级,这样的切换是值得的。但是大部分情况下只需在临界区入口等候几十上百个指令循环另一个进程就可以交出临界区,这时候这种切换就有点牛刀杀鸡了。这就好象去医院看普通门诊,当医生正在为病人看病时,别的病人在门口等待一会就会轮到了,不必留下电话号码回家睡觉,直到医生空闲了打电话通知再匆匆赶往医院。

由于使用信号量引起的进程频繁切换导致大内核锁在某些情况下出现严重性能问题, Linus Torvalds不得不考虑将大内核锁的实现改回自旋锁,自然调度延时问题也会跟着回来。这使得以‘延时迷(latency junkie)’自居的Ingo Molnar不太高兴。但linux还是Linus Torvalds说了算,于是在2.6.26-rc2版大内核锁又变成了自旋锁,直到现在。总的来说Linus Torvalds的改动是有道理的。使用繁琐,重量级的信号量保护短暂的临界区确实不值得;而且Linux也不是以实时性见长的操作系统,不应该片面追求实时信而牺牲了整体性能。

1.4      日薄西山:谢幕在即

改回自旋锁并不意味着Linus Torvalds不关心调度延时,相反他真正的观点是有朝一日彻底铲除大内核锁,这一点他和Ingo Molnar是英雄所见略同。可是由于铲除大内核锁的难度和风险巨大,Ingo Molnar觉得‘在当前的游戏规则下解决大内核锁是不现实的’必须使用新的游戏规则。他专门建立一个版本分支叫做kill-the-BLK,在这个分支上将大内核锁替换为新的互斥机制,一步一步解决这个问题:

  • 解决所有已知的,利用到了大内核锁自动解锁机制的临界区;也就是说,消除使用大内核锁的代码对自动解锁机制的依赖,使其更加接近普通的互斥机制;
  • 添加许多调试设施用来警告那些在新互斥机制下不再有效的假设;
  • 将大内核锁转换为普通的互斥体,并删除遗留在调度器里的自动解锁代码;
  • 添加lockdep对它的监控;
  • 极大简化大内核锁代码,最终将它从内核里删除。

 

Advertisements

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: