by smallnest

lock-free 编程介绍

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

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

但是无锁编程不是万能药，因为无锁算法实现起来更复杂，它也有潜在问题，比如竞争（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操作一般是这样的

bool compare_and_swap (int *oldval, int *dest, int newval) {
  if (*oldval == *dest) {
      *dest = newval;
      return true;
  }
  return false;
}