锁是操作系统提供的一种同步原语。通过访问共享资源前加锁，访问共享资源后解锁，只有一个Thread访问共享，本质上是序列化。程序对共享资源的访问任务一般包括三个步骤：读取原值、修改值、写回新值。如果使用锁进行同步，就是保证这三个步骤不会被打断，接近共享资源的访问。代码区只有一个线程同时运行，第一个获得锁的线程可以继续前进，其他线程只能等待持有锁的线程释放锁。线程同步分为阻塞同步和非阻塞同步。系统提供的互斥锁、信号、条件变量等机制都是阻塞同步，会导致调用线程在竞争资源时阻塞。非阻塞同步就是在没有锁的情况下，通过一定的算法和技术手段实现不阻塞的同步。锁是一种阻塞（Blocking）同步机制。阻塞同步机制的缺陷是你的程序可能会被挂起。如果持有锁的线程崩溃了，锁永远不会被释放，其他线程就会陷入无限等待。此外，它还会导致优先级倒置等问题。因此，我们需要一种非阻塞（Non-Blocking）的同步机制。什么是无锁？Lock-free没有锁同步问题，所有线程无阻碍地执行原子指令，而不是等待。比如一个线程读一个原子类型的变量，一个线程写一个原子变量，没有任何等待。硬件原子指令保证不会出现数据不一致，写数据不会读到一半，读数据不会读到一半。那么什么是无锁呢？有人说无锁就是不使用互斥/信号量等无锁（lock-Less）编程，严格来说是不正确的。我们先看看wiki对Lock-free的描述：>Lock-freedom允许单个线程饿死但保证系统范围的吞吐量。如果当程序线程运行足够长的时间时，至少有一个线程取得进展（对于某些合理的进展定义），则该算法是无锁的。所有无等待算法都是无锁的。>特别是，如果一个线程被挂起，那么无锁算法保证其余线程仍然可以继续进行。因此，如果两个线程可以争用同一个互斥锁或自旋锁，则该算法不是无锁的。（如果我们挂起一个持有锁的线程，那么第二个线程就会阻塞。）第一段：无锁允许单个线程饥饿但保证系统级吞吐量。如果一个程序的线程执行时间足够长以至于至少有一个线程前进，则该算法是无锁的。第二段：特别是，如果一个线程被挂起，无锁算法保证其他线程仍然可以继续前进。第一段是lockfree的定义，第二段是解释。因此，如果2个线程竞争同一个互斥锁或自旋锁，就不是无锁的。因为如果我们挂起持有锁的线程，那么另一个线程就会被阻塞。这个wiki的描述很抽象，不够直观。我稍微解释一下：lock-free描述的是代码逻辑的属性，大部分不使用锁的代码都有这个属性。因此，我们经常混淆无锁和无锁这两个概念。其实无锁是对代码（算法）性质的描述，是一种属性，而无锁是指代码是如何实现的，是一种手段。无锁的关键描述是：如果一个线程被挂起，那么其他线程应该可以继续前进，它需要有系统范围（system-wide）的吞吐量。我们举个反面的例子。假设我们想借助锁来实现一个无锁队列。我们可以直接使用线程不安全的std::queue+std::mutex来做：q.push(t);q_mutex.unlock();}私有：std::queueq；std::mutexq_mutex;};如果有线程A/B/C同时执行push方法，先进入的线程A获得mutex。线程B和C因无法获取互斥量而陷入等待状态。这时候，如果线程A因为某种原因（比如异常，或者等待某个资源）被永久挂起，那么同样执行push的线程B/C也会被永久挂起，整个系统（system-wide)没有法律进展。这显然不符合无锁的要求。因此：所有基于锁（包括自旋锁）的并发实现都不是无锁的。因为它们都遇到了同一个问题：即如果当前持有锁的线程/进程的执行被永久挂起，其他线程/进程的执行就会被阻塞。相对于lock-free的描述，它允许部分流程（理解为执行流程）饿死但必须保证整体逻辑的持续进行。基于锁的并发显然违背了无锁的要求。CAS循环实现lock-freeLock-Free同步主要依赖于CPU提供的read-modify-write原语。著名的“比较与交换”CAS（CompareAndSwap）是在X86机器上通过cmpxchg系列指令实现的原子操作。用代码逻辑表达是这样的：boolCAS(T*ptr,Texpect_value,Tnew_value){if(*ptr!=expect_value){returnfalse;}*ptr=new_value;returntrue;}CAS接受3个参数：内存地址的期望值，这个值通常传递第一个参数指向的内存地址中的旧值和新值逻辑说明：CAS将内存地址中的值与期望值，如果不相同则返回失败，如果相同则将新值写入内存并返回成功。当然，这个C函数只是描述了CAS的逻辑。这个函数操作不是原子的，因为它可以分为几个步骤：读取内存值，判断，写入新值，每个步骤之间可以插入其他操作。但是，如前所述，原子指令相当于封装了这些步骤。可以通过`lock;来实现cmpxchg`，但那是一个实现细节，程序员应该多注意从逻辑上理解它的行为。通过CAS实现Lock-free的代码通常使用循环。代码如下：do{Texpect_value=*ptr;}while(!CAS(ptr,expect_value,new_value));创建共享数据的本地副本，expect_value根据需要修改本地副本，从ptr指向的共享数据加载并赋值给expect_value，检查共享数据是否等于本地副本。如果它们相等，则将新值复制到共享数据。第三步是关键。虽然CAS是原子的，但是loadexpect_value和CAS的两个步骤不是原子的。因此，我们需要使用循环。如果ptr内存位置的值没有改变（*ptr==expect_value），则存储新值并成功返回；否则加载expect_value后，ptr指向的内存位置已经被其他线程修改。当它失败时，重新加载expect_value并重试，直到它成功。CAS循环支持多线程并发写入。这个特性非常有用，因为多线程同步经常会面临多次写入的问题。我们可以基于cas实现Fetch-and-add(FAA)算法，如下所示：Tfaa(T&t){Ttemp=t;while(!compare_and_swap(x,temp,temp+1));}第一步是将共享数据的值加载到temp，第二步是比较+存储新值，直到成功。无锁栈下面是一个C++atomiccompare_exchange_weak()实现的无锁栈（来自CppReference）：templatestructnode{Tdata;下一个节点*；node(constT&data):data(data),next(nullptr){}};templateclassstack{std::atomic*>头；public:voidpush(constT&data){node*new_node=newnode(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类型的数据，并保存了一个指向下一个节点的指针`std::atomic*>`类型表示Node的指针是放在atomic中的，不是Node本身，因为指针在64位系统上是8个字节，等于机器字的长度。无论多长，都不能保证原子栈类包含头成员。head是指向头节点的指针，头节点指针相当于堆顶指针，一开始没有节点，head为NULL在push函数中，先根据数据值新建一个节点，然后放到堆顶，因为栈是用链表实现的，所以如果新节点要成为新的堆顶（相当于插入一个新节点作为新的头节点），那么新节点的next字段要指向原来的头节点，让head指向新的节点`new_node->next=head.load`将新节点的next字段指向原头节点，然后`head.compare_exchange_weak(new_node->next,new_node)`，让head指向新节点C++atomiccompare_exchange_weak()和上面的CAS略有不同。当head.load()不等于new_node->next时，会重新加载head.load()的值给new_node->next。因此，在加载head值和cas之间，如果其他线程调用push操作改变了head的值，没关系，本次线程的cas失败，下次重试就可以了。当多个线程同时push时，任何一个线程在任何一步阻塞/挂起，其他线程会继续执行最后返回，无非就是执行几次while循环。行为逻辑显然符合无锁的定义。注意使用cas+loop实现自旋锁不符合无锁的定义。注意区分ABA问题。CAS往往伴随着ABA问题，考虑到前面的CAS逻辑，CAS会进行判断，判断的两个操作数，一个是上一步加载的内存地址的值，一个是从内存地址读取的值再次，如果2个操作数相等，则假定内存位置的值没有改变。但实际上，如果“两次读取一个内存位置的值相同，说明该内存位置没有变化”，这个假设不一定成立，为什么呢？在上一步从内存位置加载数据后假设线程1。线程2切入修改内存位置的数据，从A到B，再到A。当线程1继续执行CAS时，它观察到的内存位置的值保持不变（仍然是A），因为线程2修改了数据从A传到B，再传到A。线程1两次读取同一个值，就断定内存位置没有被修改，事实并非如此，线程2改变了内存位置。按照上述逻辑进行操作，可能会出现未定义的结果。这是经典的ABA问题。会不会出问题完全取决于你的程序逻辑。有些逻辑可以容忍ABA问题，有些则不能。ABA问题通常是由内存重用引起的。比如一块内存被回收再分配后，地址值没有变，但是这个对象已经不是之前的对象了。解决ABA问题的技术手段有很多，比如增加版本号等等，目的无非就是为了识别这个变化。什么是免等待？关于免等待的Wiki词条解释：>免等待是最强大的非阻塞进程保证，将保证系统范围的吞吐量与免饥饿相结合>如果每个操作都对步骤数有限制，则该算法是免等待的该算法将在操作完成之前进行。[15]此属性对于实时系统至关重要，只要性能成本不是太高，它总是很好的。翻译过来就是：wait-free有最强的Non-blocking进度保证，wait-free有系统级的吞吐量，没有饥饿感。如果算法的每个操作只需要完成有限的步骤，那么该算法就是无等待的。这个特性对于实时系统来说是非常关键的，它的性能成本也不会太高。wait-free比lock-free更严格，所有wait-free算法都是无锁的，反之亦然，wait-free是lock-free的一个子集。wait-free的关键特点是所有的步骤都在有限的步骤中完成，所以之前的`cas+loop`实现的无锁栈并不是wait-free。因为理论上，如果调用push的线程运气不好，一直有其他线程push，都成功了，那么这个运气不好的线程的cas总会失败，循环下去。这与免等待不同。每个操作都必须在有限的步骤中完成的冲突要求。无等待尝试次数通常与线程数有关。线程越多，限制上限越大。但是前面提到的atomicfetch_add是wait-free的，因为它不会失败。简单的说，lock-free可以有环路，而wait-free应该连环路都没有。免等待是很难做到的。之前没有看过wait-free的数据结构和算法实现。直到2011年，才有人想出了免等待队列。这个队列虽然也用了cas，但是每一步都是发送的。该操作提供了一个状态数组，为每个操作分配一个编号，以确保入队和出队操作可以在有限的步骤中完成。论文链接：（无等待队列）：[http://www.cs.technion.ac.il/~erez/Papers/wfquque-ppopp.pdf]什么是无障碍？Obstruction-free提供了比lock-free弱的非阻塞进度保证，所有lock-free都属于Obstruction-free。Obstruction-free译为无障碍，意思是在任何时间点，一个孤立运行的线程的每个操作都可以在有限的步数内结束。只要没有竞争，线程就可以继续运行。一旦共享数据被修改，Obstruction-free需要暂停一些已经完成的操作并回滚。无阻塞是一种非阻塞并发，并发级别较低。算法不出现在出现冲突操作的情况下提供单线程执行进度保证。无障碍要求可以中止任何部分完成的操作，并且可以回滚所做的更改。为了完整起见，这里列出了无障碍。无锁数据结构一些无锁（阻塞）数据结构可以在没有特殊原子操作原语的情况下实现，例如：支持单线程读取和单线程写入的RingBufferFIFO队列，通过设置容量为2^n，可以利用整数环绕特性+内存屏障来实现。参考linux内核中kfifo的readcopyupdate(RCU)，单线程写线程，任意数量的读线程。通常，读取无需等待（wait-free），写入无需锁定（lock-free）读取副本更新（RCU），具有多个写入线程和任意数量的读取线程，通常，读取无需等待（wait-free），写入锁定作为序列化的无锁数据结构很难实现，没必要自己动手。自旋锁在cpu核上自旋，粘附在cpu上，一直检测，直到其他cpu解锁。这是一种消耗cpu的加锁方式。它适用于持有锁的时间很短。它基于一个假设：睡眠造成的调度开销大于CPU上自旋测试的开销。自旋锁也称为优雅粒度锁，对应于操作系统提供的粗粒度锁（互斥量和信号量）。一般情况下，自旋锁不宜长时间持有。如果锁可能会持有很长时间，那么使用操作系统为你提供的粗粒度锁。当线程持有自旋锁时，一般不应将线程调度掉。内核层可以禁止中断和调度来保证这一点，但是应用层程序一般无法阻止线程被调度走，所以应用层使用了自旋锁。保证。自旋锁不是递归的。自旋锁通常用于追求低延迟，而不是为了提高系统吞吐量，因为自旋锁不会调度执行线程，不会阻塞（睡眠）。
