背景
我们处在技术快速发展的时代，竞争变得前所未有的激烈，不仅要十八般武艺俱全，还得选对正确的技术，跟上发展的脚步，并贴上精研某个专业方向的标签。我们不仅要面对多线程和并发，还要考虑多核时代的并行计算，无锁编程或许是一种选择，可能会提升性能，也可能避免锁的使用引起的错误，同时会带来编程习惯的变革。
不可否认，无锁技术是目前各种并发解决方案中比较受争议的一种，尽管它基于最基本的编程技术，不依赖于任何语言和平台，但是这项技术有些诡异，掌握起来颇有难度，有点曲高和寡，所以没有大面积应用在编程中。
技术本身没有对错，仁者见仁，智者见智，选择和实际match的方法，并不断的进行深入和优化。不管你是否在项目中使用无锁技术，了解和研究这项技术本身都会对理解并发编程有很大的帮助。
lock-free-data-structures.jpg
与无锁结缘
一年前，我参与一个新项目的开发。当我准备开发定时器功能时，教练建议先开发一个无锁队列。这是我第一次听说“无锁”这个词，感觉很酷很时髦，于是病(bing)了一把，才发现无锁(lock-free)技术在Linux内核2.6版本中就已经有了应用。我们不得不佩服内核开发者的智慧，为了提高内核性能，一直不断的进行各种优化。
对于循环队列算法的开发和测试，一般在一个工作日内就可以交付，而笔者开发和测试无锁队列，用了至少一个星期的时间，而且测试对于多线程并发的场景还没有覆盖全，可见无锁编程很有挑战，非常烧脑，对维护人员的技能又较高的要求。
尽管github上已经开源了很多无锁算法，但是分析后发现和自己的想法有一些gap，所以决定参考既有论文和实现开发一些自己能hold住的match当前场景的无锁算法。从无锁队列（限定大小）开始，在几个月的时间里跟着项目的节奏顺便开发了无锁双向链表、无锁队列（不限定大小）和无锁哈希等算法，并在项目中大量使用。
什么是无锁?
无锁，英文一般翻译为lock-free，是利用处理器的一些特殊的原子指令来避免传统并行设计中对锁的使用。
如果一个共享数据结构的操作不需要互斥，那么它是无锁的。如果一个进程或线程在操作中间被中断，其他进程或线程的操作不受影响。[Herlihy 1991]
笔者对于无锁的实践都是在一个进程下关于多线程并发的，所以后面我们只讨论多线程。
为什么要无锁?
首先是性能考虑。
通信项目一般对性能有极致的追求，这是我们使用无锁的重要原因。当然，无锁算法如果实现的不好，性能可能还不如使用锁，所以我们选择比较擅长的数据结构和算法进行lock-free实现，比如Queue，对于比较复杂的数据结构和算法我们通过lock来控制，比如Map（虽然我们实现了无锁Hash，但是大小是限定的，而Map是大小不限定的）。
对于性能数据，后续文章会给出无锁和有锁的对比。
其次是避免锁的使用引起的错误和问题。
- 死锁(dead lock)：两个以上线程互相等待
- 锁护送(lock convoy)：多个同优先级的线程反复竞争同一个锁，抢占锁失败后强制上下文切换，引起性能下降
- 优先级反转(priority inversion)：低优先级线程拥有锁时被中优先级的线程抢占，而高优先级的线程因为申请不到锁被阻塞
如何无锁?
在现代的 CPU 处理器上，很多操作已经被设计为原子的，比如对齐读（Aligned Read）和对齐写（Aligned Write）等。Read-Modify-Write（RMW）操作的设计让执行更复杂的事务操作变成了原子操作，当有多个写入者想对相同的内存进行修改时，保证一次只执行一个操作。
RMW 操作在不同的 CPU 家族中是通过不同的方式来支持的：
- x86/64 和 Itanium 架构通过 Compare-And-Swap (CAS) 方式来实现
- PowerPC、MIPS 和 ARM 架构通过 Load-Link/Store-Conditional (LL/SC) 方式来实现
笔者都是在x64下进行实践的，用的是CAS操作，CAS操作是lock-free技术的基础，我们可以用下面的代码来描述：
template <class T>
bool CAS(T* addr, T expected, T value)
{
if (*addr == expected)
{
*addr = value;
return true;
}
return false;
}
在GCC中，CAS操作如下所示：
bool __sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)
type __sync_val_compare_and_swap (type *ptr, type oldval type newval, ...)
这两个函数提供原子的比较和交换，如果*ptr == oldval，就将newval写入*ptr，第一个函数在相等并写入的情况下返回true，第二个函数的内置行为和第一个函数相同，只是它返回操作之前的值。
后面的可扩展参数(...)用来指出哪些变量需要memory barrier，因为目前gcc实现的是full barrier，所以可以略掉这个参数。
除过CAS操作，GCC还提供了其他一些原子操作，可以在无锁算法中灵活使用：
type __sync_fetch_and_add (type *ptr, type value, ...)
type __sync_fetch_and_sub (type *ptr, type value, ...)
type __sync_fetch_and_or (type *ptr, type value, ...)
type __sync_fetch_and_and (type *ptr, type value, ...)
type __sync_fetch_and_xor (type *ptr, type value, ...)
type __sync_fetch_and_nand (type *ptr, type value, ...)
type __sync_add_and_fetch (type *ptr, type value, ...)
type __sync_sub_and_fetch (type *ptr, type value, ...)
type __sync_or_and_fetch (type *ptr, type value, ...)
type __sync_and_and_fetch (type *ptr, type value, ...)
type __sync_xor_and_fetch (type *ptr, type value, ...)
type __sync_nand_and_fetch (type *ptr, type value, ...)
__sync_*系列的built-in函数，用于提供加减和逻辑运算的原子操作。这两组函数的区别在于第一组返回更新前的值，第二组返回更新后的值。
笔者开发无锁算法感触最深的是复杂度的分解，比如多线程对于一个双向链表的插入或删除操作，如何能一步一步分解成一个一个串联的原子操作，并能保证事务内存的一致性。
ABA问题
ABA问题可以俗称为“调包问题”，我们先看一个生活化的例子：
你拿着一个装满钱的手提箱在飞机场，此时过来了一个火辣性感的美女，然后她很暖昧地挑逗着你，并趁你不注意的时候，把用一个一模一样的手提箱和你那装满钱的箱子调了个包，然后就离开了，你看到你的手提箱还在那，于是就提着手提箱去赶飞机了。
我们再看一个CAS化的例子：
若线程对同一内存地址进行了两次读操作，而两次读操作得到了相同的值，通过 "值相同" 来判定 "值没变"是不可靠的。因为在这两次读操作的时间间隔之内，另外的线程可能已经多次修改了该值，这样就相当于欺骗了前面的线程，使其认为 "值没变"，实际上值已经被篡改过了。
下面是 ABA 问题发生的过程：
- T1 线程从共享的内存地址读取值 A；
- T1 线程被抢占，线程 T2 开始运行；
- T2 线程将共享的内存地址中的值由 A 改成 B，然后又改成 A；
- T1 线程继续执行，读取共享的内存地址中的值 A，认为没有改变，然后继续执行
由于 T1 并不知道两次读取的值 A 已经被 "隐性" 的修改过，所以可能产生无法预期的结果。
当 CAS操作循环执行时，存在多个线程交错地对共享的内存地址进行处理，如果实现的不正确，将有可能遇到 ABA 问题。
小结
本文简要介绍了无锁编程的基础，我们知道了什么是lock-free，为什么要lock-free以及如何lock-free，最后提出了ABA问题。我们将在下一篇文章《无锁队列》中实例化ABA问题，并给出解决方法。
网友评论