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

锁是操作系统提供的一种同步原语，通过在访问共享资源前加锁，结束访问共享资源后解锁，让任何时刻只有一个线程访问共享，本质是做串行化。,程序对共享资源的访问任务，一般包括三步骤，读原值，修改值，将新值写回，用锁同步的话，就是在确保这三个步骤，不会被打断，访问共享资源的临近代码区只有一个线程在同时运行，第一个获得锁的线程能往前推进，其他线程只能等着直到持有锁的线程释放锁。,线程同步分为阻塞型同步和非阻塞型同步。,,互斥量、信号、条件变量这些系统提供的机制都属于阻塞型同步，在争用资源的时候，会导致调用线程阻塞。,而非阻塞型同步是在无锁的情况下，通过某种算法和技术手段实现不用阻塞而同步。,锁是阻塞（Blocking）同步机制，阻塞同步机制的缺陷是可能挂起你的程序，如果持有锁的线程crash，则锁永远得不到释放，而其他线程则将陷入无限等待，另外，它也可能导致优先级倒转等问题。,所以，我们需要非阻塞（Non-Blocking）的同步机制。,lock-free没有锁同步的问题，所有线程无阻碍的执行原子指令，而不是等待。,比如一个线程读atomic类型变量，一个线程写atomic变量，它们没有任何等待，硬件原子指令确保不会出现数据不一致，写入数据不会出现半完成，读取数据也不会读一半。,,有人说lock-free就是不使用mutex / semaphores之类的无锁（lock-Less）编程，这句话严格来说并不对。,我们先看一下wiki对Lock-free的描述:,第一段是给lock free下定义，第二段是解释。,因此，如果2个线程竞争同一个互斥锁或者自旋锁，那它就不是lock-free的。,因为如果我们暂停持有锁的线程，那么另一个线程会被阻塞。,wiki的这段描述很抽象，它不够直观，稍微再解释一下：,lock-free描述的是代码逻辑的属性，不使用锁的代码，大部分具有这种属性。所以，我们经常会混淆这lock-free和无锁这2个概念。,其实，lock-free是对代码（算法）性质的描述，是属性，而无锁是说代码如何实现，是手段。,lock-free的关键描述是：如果一个线程被暂停，那么其他线程应能继续前进，它需要有系统级（system-wide）的吞吐。,我们从反面举例来看，假设我们要借助锁实现一个无锁队列，我们可以直接使用线程不安全的std::queue + std::mutex来做：,如果有线程A/B/C同时执行push方法，最先进入的线程A获得互斥锁。,线程B和C因为获取不到互斥锁而陷入等待。,这个时候，线程A如果因为某个原因（如出现异常，或者等待某个资源）而被永久挂起，那么同样执行push的线程B/C将被永久挂起，系统整体（system-wide）没法推进。这显然不符合lock-free的要求。,因此：所有基于锁（包括spinlock）的并发实现，都不是lock-free的。,因为它们都会遇到同样的问题：即如果永久暂停当前占有锁的线程/进程的执行，将会阻塞其他线程/进程的执行。,而对照lock-free的描述，它允许部分process（理解为执行流）饿死但必须保证整体逻辑的持续前进，基于锁的并发显然是违背lock-free要求的。,Lock-Free同步主要依靠CPU提供的read-modify-write原语，著名的“比较和交换”CAS（Compare And Swap）在X86机器上是通过cmpxchg系列指令实现的原子操作，CAS逻辑上用代码表达是这样的：,CAS接受3个参数：,逻辑描述：CAS比较内存地址中的值和期望值，如果不相同就返回失败，如果相同就将新值写入内存并返回成功。,当然这个C函数描述的只是CAS的逻辑，这个函数操作不是原子的，因为它可以划分成几个步骤：读取内存值、判断、写入新值，各步骤之间是可以插入其他操作的。,不过前面讲了，原子指令相当于把这些步骤打包，它可能是通过`lock; cmpxchg`实现的，但那是实现细节，程序员更应该注重在逻辑上理解它的行为。,通过CAS实现Lock-free的代码通常借助循环，代码如下：,第三步是关键，虽然CAS是原子的，但加载expect_value跟CAS这2个步骤，并不是原子的。,所以，我们需要借助循环，如果ptr内存位置的值没有变（*ptr == expect_value），那就存入新值返回成功；否则说明加载expect_value后，ptr指向的内存位置被其他线程修改了，这时候就返回失败，重新加载expect_value，重试，直到成功为止。,CAS loop支持多线程并发写，这个特点太有用了，因为多线程同步，很多时候都面临多写的问题，我们可以基于cas实现Fetch-and-add(FAA)算法，它看起来像这样：,第一步加载共享数据的值到temp，第二步比较+存入新值，直到成功。,下面是C++ atomic compare_exchange_weak()实现的一个lock-free堆栈（来自CppReference）：,代码解析：,这样的行为逻辑显然符合lock-free的定义，注意用cas+loop实现自旋锁不符合lock-free的定义，注意区分。,CAS经常伴随ABA问题，考虑前面的CAS逻辑，CAS里会做判等，判等的2个操作数，一个是前步加载的内存地址的值，另一个是再次从内存地址读取的值，如果2个操作数相等，它便认为内存位置的值没变。,但实际上，如果“两次读取一个内存位置的值相同，则说明该内存位置没变”，这个假设不一定成立，为什么呢？,假设线程1在前面一步从内存位置加载数据后。,线程2切入，将该内存位置的数据从A修改为B，然后又修改为A。,等到线程1继续执行CAS的时候，它观测到的内存位置值未变（依然是A），因为线程2将数据从A修改到B，再修改成A。,线程1两次读到了相同的值，它便断定内存位置没有被修改，实际并非如此，线程2改了内存位置。,基于上述逻辑行事，就有可能出现未定义的结果。,这就是经典的ABA问题，会不会出问题，完全取决于你的程序逻辑，有些逻辑可以容忍ABA问题，而有些不可以。,ABA问题很多时候由内存复用引起，比如一块内存被回收后又被分配，地址值不变，但这个对象已经不是之前的那个对象了，有很多解决ABA问题的技术手段，比如增加版本号等等，目的无非是去识别这种变化。,wiki关于wait-free的词条解释：,翻译过来就是：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提供比lock-free更弱的一个非阻塞进度保证，所有lock-free都属于Obstruction-free。,Obstruction-free翻译过来叫无障碍，是指在任何时间点，一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争，线程就可以持续运行，一旦共享数据被修改，Obstruction-free要求中止已经完成的部分操作，并进行回滚，obstruction-free是并发级别更低的非阻塞并发，该算法在不出现冲突性操作的情况下提供单线程式的执行进度保证。,obstruction-freedom要求可以中止任何部分完成的操作并且能够回滚已做的更改，为了内容完备性，把obstruction-free列在这里。,一些无锁（阻塞）数据结构不需要特殊原子操作原语即可实现，例如：,无锁数据结构实现起来比较困难，非必要不要自己去实现。,在cpu核上自旋，粘着cpu不停的测试，直到其他cpu解锁，这是一种消耗cpu的加锁方式，适合持有锁的时间非常短的情况，它基于一种假设：睡眠导致的调度开销大于在cpu上自旋测试的开销。,