关于多线程同步的一切：lock-free/wait-free

锁是操作系统提供的一种同步原语，通过在访问共享资源前加锁，结束访问共享资源后解锁，让任何时刻只有一个线程访问共享，本质是做串行化。

程序对共享资源的访问任务，一般包括三步骤，读原值，修改值，将新值写回，用锁同步的话，就是在确保这3个步骤，不会被打断，访问共享资源的临近代码区只有一个线程在同时运行，第一个获得锁的线程能往前推进，其他线程只能等着直到持有锁的线程释放锁。

线程同步分为阻塞型同步和非阻塞型同步。

互斥量、信号、条件变量这些系统提供的机制都属于阻塞型同步，在争用资源的时候，会导致调用线程阻塞。

而非阻塞型同步是在无锁的情况下，通过某种算法和技术手段实现不用阻塞而同步。

锁是阻塞（Blocking）同步机制，阻塞同步机制的缺陷是可能挂起你的程序，如果持有锁的线程crash，则锁永远得不到释放，而其他线程则将陷入无限等待，另外，它也可能导致优先级倒转等问题。

所以，我们需要非阻塞（Non-Blocking）的同步机制。

什么是lock-free？

lock-free没有锁同步的问题，所有线程无阻碍的执行原子指令，而不是等待。

比如一个线程读atomic类型变量，一个线程写atomic变量，它们没有任何等待，硬件原子指令确保不会出现数据不一致，写入数据不会出现半完成，读取数据也不会读一半。

那到底什么是lock-free？

有人说lock-free就是不使用mutex / semaphores之类的无锁（lock-Less）编程，这句话严格来说并不对。

我们先看一下wiki对Lock-free的描述:

Lock-freedom allows individual threads to starve but guarantees system-wide throughput. An algorithm is lock-free if, when the program threads are run for a sufficiently long time, at least one of the threads makes progress (for some sensible definition of progress). All wait-free algorithms are lock-free.

In particular, if one thread is suspended, then a lock-free algorithm guarantees that the remaining threads can still make progress. Hence, if two threads can contend for the same mutex lock or spinlock, then the algorithm is not lock-free. (If we suspend one thread that holds the lock, then the second thread will block.)

第一段：lock-free允许单个线程饥饿但保证系统级吞吐。如果一个程序的线程执行足够长的时间，那么至少一个线程会往前推进，那么这个算法就是lock-free的。

​​​第二段：尤其是，如果一个线程被暂停，lock-free算法保证其他线程依然能够往前推进。

第一段是给lock free下定义，第二段是解释。

因此，如果2个线程竞争同一个互斥锁或者自旋锁，那它就不是lock-free的。

因为如果我们暂停持有锁的线程，那么另一个线程会被阻塞。

wiki的这段描述很抽象，它不够直观，稍微再解释一下：

lock-free描述的是代码逻辑的属性，不使用锁的代码，大部分具有这种属性。所以，我们经常会混淆这lock-free和无锁这2个概念。

其实，lock-free是对代码（算法）性质的描述，是属性，而无锁是说代码如何实现，是手段。

lock-free的关键描述是：如果一个线程被暂停，那么其他线程应能继续前进，它需要有系统级（system-wide）的吞吐。

我们从反面举例来看，假设我们要借助锁实现一个无锁队列，我们可以直接使用线程不安全的std::queue + std::mutex来做：

template <typename T>
class Queue {
public:
   void push(const T& t) {
       q_mutex.lock();
       q.push(t);
       q_mutex.unlock();
   }
private:
   std::queue<T> q;
   std::mutex q_mutex;
};

如果有线程A/B/C同时执行push方法，最先进入的线程A获得互斥锁。

线程B和C因为获取不到互斥锁而陷入等待。

这个时候，线程A如果因为某个原因（如出现异常，或者等待某个资源）而被永久挂起，那么同样执行push的线程B/C将被永久挂起，系统整体（system-wide）没法推进。这显然不符合lock-free的要求。

因此：所有基于锁（包括spinlock）的并发实现，都不是lock-free的。

因为它们都会遇到同样的问题：即如果永久暂停当前占有锁的线程/进程的执行，将会阻塞其他线程/进程的执行。

而对照lock-free的描述，它允许部分process（理解为执行流）饿死但必须保证整体逻辑的持续前进，基于锁的并发显然是违背lock-free要求的。

CAS loop实现lock-free

Lock-Free同步主要依靠CPU提供的read-modify-write原语，著名的“比较和交换”CAS（Compare And Swap）在X86机器上是通过cmpxchg系列指令实现的原子操作，CAS逻辑上用代码表达是这样的：

bool CAS(T* ptr, T expect_value, T new_value) {
  if (*ptr != expect_value) {
     return false;
  }
  *ptr = new_value;
  return true;
}

CAS接受3个参数：

1. - 内存地址
2. - 期望值，这个值通常传第一个参数所指内存地址中的旧值
3. - 新值

逻辑描述：CAS比较内存地址中的值和期望值，如果不相同就返回失败，如果相同就将新值写入内存并返回成功。

当然这个C函数描述的只是CAS的逻辑，这个函数操作不是原子的，因为它可以划分成几个步骤：读取内存值、判断、写入新值，各步骤之间是可以插入其他操作的。

不过前面讲了，原子指令相当于把这些步骤打包，它可能是通过lock; cmpxchg实现的，但那是实现细节，程序员更应该注重在逻辑上理解它的行为。

通过CAS实现Lock-free的代码通常借助循环，代码如下：

do {
   T expect_value = *ptr;
} while (!CAS(ptr, expect_value, new_value));

1. 创建共享数据的本地副本，expect_value

2. 根据需要修改本地副本，从ptr指向的共享数据里load后赋值给expect_value

3. 检查共享的数据跟本地副本是否相等，如果相等，则把新值复制到共享数据

第三步是关键，虽然CAS是原子的，但加载expect_value跟CAS这2个步骤，并不是原子的。

所以，我们需要借助循环，如果ptr内存位置的值没有变（*ptr == expect_value），那就存入新值返回成功；否则说明加载expect_value后，ptr指向的内存位置被其他线程修改了，这时候就返回失败，重新加载expect_value，重试，直到成功为止。

CAS loop支持多线程并发写，这个特点太有用了，因为多线程同步，很多时候都面临多写的问题，我们可以基于cas实现Fetch-and-add(FAA)算法，它看起来像这样：

T faa(T& t) {
   T temp = t;
   while (!compare_and_swap(x, temp, temp + 1));
}

第一步加载共享数据的值到temp，第二步比较+存入新值，直到成功。

lock-free栈

下面是C++ atomic compare_exchange_weak()实现的一个lock-free堆栈（来自CppReference）

template <typename T>
struct node {
   T data;
   node* next;
   node(const T& data) : data(data), next(nullptr) {}
};

template <typename T>
class stack {
   std::atomic<node<T>*> head;
public:
   void push(const T& data) {
     node<T>* new_node = new node<T>(data);
     new_node->next = head.load(std::memory_order_relaxed);
     while (!head.compare_exchange_weak(new_node->next, new_node,
                                       std::memory_order_release,
                                       std::memory_order_relaxed));
   }
};

代码解析：

• - 节点（node）保存T类型的数据data，并且持有指向下一个节点的指针
• - std::atomic<node<T>\*>类型表明atomic里放置的是Node的指针，而非Node本身，因为指针在64位系统上是8字节，等于机器字长，再长没法保证原子性
• - stack类包含head成员，head是一个指向头结点的指针，头结点指针相当于堆顶指针，刚开始没有节点，head为NULL
• - push函数里，先根据data值创建新节点，然后要把它放到堆顶
• - 因为是用链表实现的栈，所以，如果新节点要成为新的堆顶（相当于新节点作为新的头结点插入），那么新节点的next域要指向原来的头结点，并让head指向新节点
• - new\_node->next = head.load把新节点的next域指向原头结点，然后head.compare\_exchange\_weak(new\_node->next, new\_node)，让head指向新节点
• - C++ atomic的compare_exchange_weak()跟上述的CAS稍有不同，head.load()不等于new_node->next的时候，它会把head.load()的值重新加载到new_node->next
• - 所以，在加载head值和cas之间，如果其他线程调用push操作，改变了head的值，那没有关系，该线程的本次cas失败，下次重试便可以了
• - 多个线程同时push时，任一线程在任意步骤阻塞/挂起，其他线程都会继续执行并最终返回，无非就是多执行几次while循环

这样的行为逻辑显然符合lock-free的定义，注意用cas+loop实现自旋锁不符合lock-free的定义，注意区分。

ABA问题

CAS经常伴随ABA问题，考虑前面的CAS逻辑，CAS里会做判等，判等的2个操作数，一个是前步加载的内存地址的值，另一个是再次从内存地址读取的值，如果2个操作数相等，它便认为内存位置的值没变。

但实际上，如果“两次读取一个内存位置的值相同，则说明该内存位置没变”，这个假设不一定成立，为什么呢？

假设线程1在前面一步从内存位置加载数据后。

线程2切入，将该内存位置的数据从A修改为B，然后又修改为A。

等到线程1继续执行CAS的时候，它观测到的内存位置值未变（依然是A），因为线程2将数据从A修改到B，再修改成A。

线程1两次读到了相同的值，它便断定内存位置没有被修改，实际并非如此，线程2改了内存位置。

基于上述逻辑行事，就有可能出现未定义的结果。

这就是经典的ABA问题，会不会出问题，完全取决于你的程序逻辑，有些逻辑可以容忍ABA问题，而有些不可以。

ABA问题很多时候由内存复用引起，比如一块内存被回收后又被分配，地址值不变，但这个对象已经不是之前的那个对象了，有很多解决ABA问题的技术手段，比如增加版本号等等，目的无非是去识别这种变化。

何为wait-free？

wiki关于wait-free的词条解释：

Wait-freedom is the strongest non-blocking guarantee of progress, combining guaranteed system-wide throughput with starvation-freedom

An algorithm is wait-free if every operation has a bound on the number of steps the algorithm will take before the operation completes.[15] This property is critical for real-time systems and is always nice to have as long as the performance cost is not too high

翻译过来就是：wait-free有着最强的非阻塞进度保证，wait-free有系统级吞吐兼具无饥饿特征。

如果一个算法的每个操作完成都只有有限操作步数，那么这个算法就是wait-free的。

这个特征对于实时系统非常关键，且它的性能成本不会太高。

wait-free比lock-free更严格，所有wait-free算法都是lock-free的，反之不成立，wait-free是lock-free的子集。

wait-free的关键特征是所有步骤都在有限步骤完成，所以前面的cas + loop实现的lock-free栈就不是wait-free的。

因为理论上，如果调用push的线程是个倒霉蛋，一直有其他线程push且恰好又都成功了，则这个倒霉蛋线程的cas会一直失败，一直循环下去，这与wait-free每个操作都必须在有限步骤完成的要求相冲突。wait-free的尝试次数通常跟线程数有关，线程数越多，则这个有限的上限就越大。

但前面讲的atomic fetch_add则是wait-free的，因为它不会失败。

简单点说，lock-free可以有循环，而wait-free连循环都不应该有。

wait-free非常难做，以前一直看不到wait-free的数据结构和算法实现，直到2011才有人搞出了一个wait-free队列，虽然这个队列也用到了cas，但是它为每一步发送的操作提供了一个state array，为每个操作赋予一个number，从而保证有限步完成入队出队操作，论文链接：

(wait-free queue)

[http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf]

何为Obstruction-free？

Obstruction-free提供比lock-free更弱的一个非阻塞进度保证，所有lock-free都属于Obstruction-free。

Obstruction-free翻译过来叫无障碍，是指在任何时间点，一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争，线程就可以持续运行，一旦共享数据被修改，Obstruction-free要求中止已经完成的部分操作，并进行回滚，obstruction-free是并发级别更低的非阻塞并发，该算法在不出现冲突性操作的情况下提供单线程式的执行进度保证。

obstruction-freedom要求可以中止任何部分完成的操作并且能够回滚已做的更改，为了内容完备性，把obstruction-free列在这里。

无锁数据结构

一些无锁（阻塞）数据结构不需要特殊原子操作原语即可实现，例如：

- 支持单线程读和单线程写的Ring Buffer先进先出队列，通过把容量设置为2^n，利用整型回绕特点+内存屏障就可以实现，参考linux内核的kfifo

- 带单写线程和任意数读线程的读拷贝更新（RCU），通常，读无等待（wait-free），写无锁（lock-free）

- 带多写线程和任意数读线程的读拷贝更新（RCU），通常，读无等待（wait-free），写用锁做串行化

无锁数据结构实现起来比较困难，非必要不要自己去实现。

自旋锁

在cpu核上自旋，粘着cpu不停的测试，直到其他cpu解锁，这是一种消耗cpu的加锁方式，适合持有锁的时间非常短的情况，它基于一种假设：睡眠导致的调度开销大于在cpu上自旋测试的开销。

- 自旋锁也叫优雅粒度的锁，跟操作系统提供的阻塞机制的粗粒度锁（mutex和信号量）对应。

- 自旋锁一般不应该被长时间持有，如果持有锁的时间可能比较长，那就用操作系统为你提供的粗粒度的锁就好了。

- 线程持有自旋锁的时候，线程一般不应该被调度走，内核层可以禁中断禁调度保障这一点，但应用层程序一般无法避免线程被调度走，所以应用层使用自旋锁其实得不到保障。

- 自旋锁不可递归。

- 自旋锁常用来追求低延时，而不是为了提升系统吞吐，因为自旋锁，不会把执行线程调度走，不会阻塞（睡眠）。

[关于多线程的一切：原子操作]

[关于多线程同步的一切：伪共享]