前言

互斥锁的理解成本很低，带来的收益却很高——可以保证在多线程情况下安全地访问数据结构，而不会产生竞争条件或破坏不变量。
但互斥锁并非完美无缺，不正确地使用可能带来死锁，粗粒度地上锁将影响并发性。
如果能写出一个不使用锁的并发数据结构，则可避免上述互斥锁引入的问题，这样的数据结构被被称为无锁(lock-free)数据结构。
无锁结构的核心是前文提及的内存顺序属性，设计无锁结构时需要万分小心——它不仅很难正确实现，同时其内部bug很难稳定复现与定位原因。

阻塞与非阻塞

使用互斥锁、条件变量，以及期望来同步数据的算法和数据结构被称为阻塞式 (blocking)数据结构和算法——线程在block消失前无法跨越。一般情况下，操作系统会完全挂起一个阻塞的线程(并将其时间片分配给其他线程)，直到另一个线程排除障碍（解锁一个互斥锁、通知一个条件变量，或令期望就绪）。

非阻塞数据结构的3种类型

前文曾用std::atomic_flag实现了一个简单的自旋锁，其代码如下：

class spinlock_mutex {
private:
  std::atomic_flag flag; 
public:
  spinlock_mutex(): flag(ATOMIC_FLAG_INIT) {}
  void lock() {
    while(flag.test_and_set(std::memory_order_acquire)); 
  }
  void unlock() {
    flag.clear(std::memory_order_release); 
  }
};

该实例内没有调用任何阻塞函数，lock不断循环，直到test_and_set返回false，这就是自旋锁（spin lock）名字的由来——代码在循环中“旋转”。
因为不存在阻塞调用，所以使用这个互斥锁来保护共享数据的代码均为非阻塞式，不过并非无锁，毕竟这还是一个只能被一个线程锁住的互斥锁。显然，仅仅定义“阻塞”，“非阻塞”是不够用的，因此为了后续展开详细叙述，这里引入以下定义：

无障碍——若其他线程均处于暂停状态，唯一操作线程都将在有限的步骤内完成其操作。
无锁——若存在多个线程同时对该数据结构进行操作，其中某个线程将在有限的步骤内完成其操作。
无等待——若存在多个线程同时对该数据结构进行操作，每个线程都将在有限步骤内完成其操作。

显然，无障碍算法在实际场景中使用性很低（很少存在其他线程都暂停的场景），因此它主要用于刻画一个失败的无锁实现。

无锁数据结构

无锁数据结构性质：支持多个线程并发访问，这些线程的操作无需相同（例如无锁队列支持一个线程push数据时另一个线程pop数据）。此外，当其中一个正在访问数据的线程被调度器中途挂起时，其他线程必须仍然能够继续完成工作，而无需等待挂起线程。

使用“比较-交换”原子操作的算法，通常都包含一个循环，之所以需要使用“比较-交换”操作，是因为与此同时另一个线程可能已经修改了数据，此时在再次尝试“比较-交换”之前，代码需要重新执行部分操作。若此时其他线程均被挂起，该算法可被称为“无锁”，否则的话等价于持有自旋锁，仅能称之为“非阻塞算法”。

带有循环的无锁算法可能导致某线程处于饥饿状态：若存在某一线程在“错误”时机执行操作，其他线程可能运行良好，但某倒霉线程则可能此时需要不断重复试错。

无等待数据结构

根据前文定义，无等待数据结构是无锁数据结构的子集，其特征在于每个线程都都将在有限步骤内完成其操作（不管其他线程行为如何）。因此，由于与其他线程发生冲突而可能陷入无限次重试的算法并不是无等待的（本章的大多数实例都都具备这一特性——存在一个在compare_exchange_weak或compare_exchange_strong操作上的循环，并且循环次数没有上限）。

显然，正确实现一个“无等待”数据结构极其困难。为了保证每个线程都能在有限的步骤内完成操作，开发者必须保证线程内的所有操作均能一次执行完毕，并且不会给其他线程带来负面影响。这些要求无疑增加了数据结构与算法的复杂程度。

无锁结构的优缺点

在学习无锁结构前我们已经充分强调了其实现复杂性，因此开发者在撰写前必须充分审度开发成本与性能收益。下文将简单叙述无锁结构的优缺点，以供权衡。

优点

并发性

归根结底，使用无锁结构的主要原因在于并发最大化。在使用基于锁的数据结构时，一个线程总会阻塞某个节点并等待另一个线程完成操作（此即为互斥）。无锁结构可以保证某些线程持续性向前推进，而无等待结构则能保证所有线程均能有效向前推进（尽管很难实现）。

鲁棒性

若一个线程在持有锁时死亡，那么数据结构将会遭到永久性破坏。但无锁结构可以规避这一点，仅有当前死亡的线程数据被丢失。

缺点

开发成本

如果不能让线程互斥地访问数据结构，那开发者必须严格地关注与维持不变量。为了避免和数据竞争相关的未定义行为，开发者必须在修改时使用原子操作，并且确保修改以正确的顺序对其他线程可见。上述要求意味着极大的开发成本与心智投入。

性能

无锁编程不会导致死锁，但可能造成活锁（live lock）——多个线程试图同时修改数据结构，此时线程不断循环与重试，导致性能降低。无等待算法不存在活锁问题，但必然其算法复杂性更高（可能需要更多步骤来完成相应操作）。

无锁结构虽然提高了操作并发的潜力，减少了单个线程的等待时间，但其可能会导致整体性能下降，理由如下：

无锁代码中的原子操作比非原子操作要慢得多，并且很可能无锁数据结构中原子操作大大多于基于锁的数据结构中互斥锁锁住的代码。
访问相同原子变量的硬件必须在线程间同步，这会导致严重的性能损耗。