无锁编程的探索与研究

郭加盛 李健北京工业大学计算机学院 北京 100124

0 前言

在计算机多核技术迅速发展的时代，线程的优势越来越明显，多线程的学习成为每个程序员必备的基础。但在实际开发过程中，越来越多的异常，越来越多的死锁现象让每个程序员崩溃不已，线程与锁的问题凸显在每个程序员的面前。

线程和进程的区别在于，子进程和父进程有不同的代码和数据空间，而多个线程则共享数据空间，每个线程有自己的执行堆栈和程序计数器为其执行上下文。多线程主要是为了节约CPU时间，发挥利用，根据具体情况而定。线程的运行中需要使用计算机的内存资源和CPU。

在多道程序设计的环境下，多个进程竞争同一资源的现象时有发生。当进程申请的资源被其他进程占用时，就有可能发生死锁。死锁的概念比较抽象，简单理解，每个汽车都是一个资源，他们都在申请路口这个资源，错误！未找到引用源。就生动的描述了死锁的现象。

1 基于锁的传统编程技术

作为一个程序员，我们对基于锁的多线程解决方案并不陌生。经典基于锁的多数据操作必须以原子操作的形式出现，这样才能保证在本线程执行的过程中没有其它线程来破坏相应数据的一致性，即便像“++count”这样的简单操作也得加锁，因为增量操作实际上是分三步进行的：读、改、写(回)，而这显然不是原子的。

简而言之，在基于锁的多线程编程中，你需要确保任何针对共享数据的、且有可能导致竞争条件的操作都被做成了原子操作(通过对一个 mutex或 lock进行加锁解锁，参见Semaphore与Mutex的关系)。从好的一面来说，只要mutex是在锁状态，你就可以放心地进行任何操作，不用担心其它线程会闯进来破坏你共享数据的一致性。

2 基于锁的传统编程技术的缺点

正是这种在mutex的锁状态下可以随心所欲操作内存的情况带来了问题。例如，你可以在锁期间读键盘或进行某些耗时较长的I/O操作，这便意味着其他需要某些共享资源的“互斥”的线程只能被block掉。当然，死锁的问题也很严重，严重到我们甚至无法在很短的篇幅中描述它的危害。

基于锁编程的另一个缺点是，在多处理器、多内存通道的环境中，CPU计算和内存读取都并非必须是串行化的。因此，基于锁编程的强行串行化极大影响了这些程序在并行环境中的性能表现，因为内存控制器根本无法将这种程序自动处理成为并行的。

3 无锁编程(lock-free)技术

对于线程加锁一般分为四个级别，根据庞杂程度、加锁力度、运行速度等进行划分，结构如图1死锁层级图。我们可以看到lock-free技术复杂度较高。

Lock-free这个单词和基于锁(lock-base)相对应，中文翻译的话，lock-free可以翻译成为“无锁编程”或者“锁无关”，当然，国外的研究也经常使用low-lock这个单词。这是因为真正的完全“无锁”几乎是不可能的，所以，lock-free更多的是强调减少锁的使用。

既然是减少锁的使用，那么少到什么程度呢？事实上，在实现良好的lock-free系统中，只有极少的系统级组件才不得不使用锁，而用户级的组件，则使用不同的算法和逻辑抽象，将锁的数量减少到零。

图1 死锁层级图

4 无锁编程技术的优缺点

在锁无关的多线程编程中，几乎任何操作都是无法原子地完成的。这带来了很多好处。

（1）对于并行环境极其有利，不需要过多的改进就能够在并行环境中得到很好的性能提升；

（2）基本消除了死锁带来的问题；

（3）线程间通讯变得极其便利，因为不需考虑共享数据的访问是否会被block掉。

当然，带来的缺点也是显而易见的，对于我们这些习惯于基于锁技术处理多线程共享数据问题的程序员来说，lock-free编程带来的难度很大，很多程序员几乎无法在第一次就将一个lock-free程序写正确。

另一个问题是，在系统级组件中，终究需要一些原子操作，那么，多大的一个操作闭包才是满足lock-free编程的最小集呢？对于这个问题，Maurice Herlihy在1991年发表了论文“Wait-Free Synchronization”提出了CAS原语操作，当然这些问题超出了本文的范畴。

5 无锁编程技术与其他锁概念的比较

这样一些概念常见于编程中：等待无关(wait-free)、锁无关(lock-free)与基于锁(lock-base)。

一个“等待无关”的程序可以在有限步之内结束，而不管其它线程的相对速度如何。

一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。这便意味着有些线程可能会被任意地延迟，然而在每一步都至少有一个线程能够往下执行。因此这个系统作为一个整体总是在“前进”的，尽管有些线程的进度可能不如其它线程来得快。

一个“基于锁”的程序则无法提供上述的任何保证。一旦任何线程持有了某个mutex并处于等待状态，那么其它任何想要获取同一mutex的线程就必须block；一般来说，基于锁的算法无法摆脱死锁的可能，因此，除去程序员自己保证不发生死锁以及系统内核态部分加入死锁检测外，对于死锁没有其他任何处置的方法。

等待无关和锁无关算法的定义意味着它们有更多的优点：

（1）线程终止免疫：一般情况下，杀掉系统中的任何线程都不会导致其它线程被延迟；

（2）信号免疫：C和C++标准禁止在信号或异步中断中调用某些系统例程(如 malloc)。如果中断与某个被中断线程同时调用malloc的话，结果就会导致死锁。而锁无关例程则没有这一问题：线程可以自由地互相穿插执行；

（3）优先级倒置免疫：所谓“优先级倒置”就是指一个低优先级线程持有了一个高优先级线程所需要的互斥体。这种微妙的冲突必须由OS内核来解决。而等待无关和锁无关算法则对此免疫。

6 总结

在开发过程中注重无锁编程，减少多线程程序的死锁情况，开发出更加优雅的多线程程序，需要不断地进行学习、训练。随着多核处理器的发展，多核多线程程序将更多的受到人们的追捧，而无锁编程作为多核多线程中的热点话题，也将越来越受到程序员的重视。

[1](孟加拉)阿克特(Akhter，S.),(美)罗伯茨(Roberts，J.)著,李宝峰,富弘毅,李韬译.多核程序设计技术——通过软件多线程提升性能.电子工业出版社.2007.

[2](美)Abraham Silberschatz, Peter Baer Galvin 著,郑扣根译操作系统概念.2004.

[3]周伟明.多核计算与程序设计.华中科技大学出版社.2009.

[4](美)仁达敬(Reinders,J)著.聂雪军等译.Intel Threading Building Blocks编程指南.机械工业出版社.2009.

[5](美)瓦格纳著,陈黎夫译.More Effective C#中文版——改善C#程序的50个具体办法人民邮电出版社.2010.

[6](美)休斯著，周良忠译. C++面向对象多线程编程.人民邮电出版社.2003.