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

发布时间：2025-11-05 03:16:24 来源：码上建站 作者：域名

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

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

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

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

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

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

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

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

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

有人说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下定义，第二段是解释。

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

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

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

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

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

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

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

template

class Queue {

public:

void push(const T& t) {

q_mutex.lock();

q.push(t);

q_mutex.unlock();

}

private:

std::queueq;

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要求的。

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个参数：

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

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

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

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

do {

T expect_value = *ptr;

第三步是关键，虽然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，第二步比较+存入新值，直到成功。

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

template

struct node {

T data;

node* next;

node(const T& data) : data(data), next(nullptr) {}

};

template

class stack {

std::atomic*> head;

public:

void push(const T& data) {

node* new_node = new node(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));

}

代码解析：

这样的行为逻辑显然符合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-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提供比lock-free更弱的一个非阻塞进度保证，所有lock-free都属于Obstruction-free。

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

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

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

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

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

相关文章