lock-free 编程介绍

这篇文章收集整理了lock free的编程概念。
如果在一个共享的数据结构上的操作都不需要互斥,那么它是无锁的。如果一个进程在操作中间被中断,其它进程不受影响。

lock free(翻译成 无锁或者锁无关)的优势

  • 通过减少阻塞和等待,来改进并发性和可扩展性。
  • 消除条件竞争(race condition)、死锁、可组合性不足带来的潜在问题。
  • 避免优先级反转

但是无锁编程不是万能药,因为无锁算法实现起来更复杂,它也有潜在问题,比如竞争(contention),这会极大地影响性能。从这一点出发,Herb引出了他的第一条强烈建议:

  • 在使用无锁技术前,你必须先测试你的程序,确定它有性能或可扩展性问题。
  • 实现无锁算法后,再次测试你的程序,确定结果得到了有效的改进。

Jeff Preshing在他的文章 An Introduction to Lock-Free Programming详细介绍了无锁编程的概念。

什么才叫做无锁编程

如果不使用锁(mutex或lock),是不是就是lock-free了呢?大部分情况下是这样子的。 学术上的定义会更严格。一个定义就是:

一个“锁无关”的程序能够确保执行它的所有线程中至少有一个能够继续往下执行。

检查你的程序是不是lock-free的,可以遵循下面的图:

像我们平常用的互斥锁,当一个线程获得锁,其他线程就被阻塞掉了,这里的问题就是如果获得锁的线程一直休眠,锁没有释放,那么整个程序其实就被block在那了,而如果程序是lock free的那么即使有线程挂掉,也不影响整个程序继续向下进行,也就是系统在整体上而言是一直前进的。

这里的锁比比较广泛的概念, 不仅仅指mutex对象。 比如下面的例子

1
2
3
while (x == 0) {
x = 1-x;
}

在这里x由两个线程共享,如果两个线程同时执行,可能同时进入while循环,然后x在两个线程中分别改变一次,依然是0,那么两个线程就会一直互相在这里阻塞掉了,所以这里虽然没有锁,依然不是lock free的。

写lock free的时候一般都会使用CAS(compare and set)操作来写,因为现在很多的cpu都是支持CAS操作并作为原子操作来处理的,CAS操作一般是这样的

1
2
3
4
5
6
7
bool compare_and_swap (int *oldval, int *dest, int newval) {
if (*oldval == *dest) {
*dest = newval;
return true;
}
return false;
}

参考

  1. http://preshing.com/20120612/an-introduction-to-lock-free-programming/
  2. Lock-Free Programming
  3. http://www.infoq.com/cn/news/2014/11/cpp-lock-free-programming
  4. 一种高效无锁内存队列的实现
  5. 无锁队列的实现
评论