深入理解 C++ 多线程：Lock-Free 与 Wait-Free 编程实践

一个常见的面试题是：如何在不加锁的情况下解决线程安全问题？要回答这个问题，你需要理解 lock-free 和 wait-free 这两个核心概念。在深入探讨它们之前，让我们先从最基础的有锁编程开始。

我们知道，当多个线程同时修改一个共享变量时，会导致数据竞争和不一致的问题。例如，多个线程并发地对一个计数器进行加1操作：

int count;
void add() {
    ++count;
}

如果只有一个线程调用 add 函数，不会有任何问题。但如果有多个线程（例如10个）同时调用它，count 的最终值很可能不是 10。根本原因在于 ++count 这个操作不是原子的。

一个操作是原子操作，意味着 CPU 要么完整执行它，要么完全不执行，不存在中间状态。然而，上面这行简单的 ++count 代码，经过编译器处理后会生成多条机器指令，因此它不是原子的。

那么，如何让它变成原子的呢？最直接的方法是加锁。

int count;
mutex mtx; // 互斥锁
void add() {
    mtx.lock();
    ++count;
    mtx.unlock();
};

现在，我们用一把互斥锁将对 count 的操作保护了起来。你可以将 mtx.lock() 和 mtx.unlock() 之间的代码视为一个原子的操作单元。CPU 要么完整执行对 count 的加1操作，要么完全不执行。这样，程序的运行结果就符合我们的预期了。

这是如何实现的呢？背后的机制相当复杂，因为它涉及到了操作系统。千万不要小看这把 mutex 锁，它的实现依赖于操作系统的深度支持。

假设有三个线程（A、B、C）分别运行在不同的 CPU 核心上。下图展示了它们在几个时间片（T1 到 T5）内的活动情况，紫色方块表示线程正在执行，灰色方块表示线程被阻塞或挂起。

在 T1 时间片，三个线程都在调用 add 函数。线程 A 成功获取了锁，因此可以继续执行。而线程 B 和 C 则不那么幸运，它们尝试获取锁失败。此时，操作系统可能会剥夺线程 B 和 C 继续使用 CPU 的权利，将它们挂起，并将 CPU 分配给其他可以运行的线程。这个过程涉及到用户态与内核态的切换以及线程上下文的切换，开销很大。

来到 T2 时间片，线程 A 继续执行，线程 B 和 C 则处于暂停状态。

在 T3 时间片，一个更糟糕的情况发生了：持有锁的线程 A 因为某些原因（如被更高优先级的线程抢占）也被操作系统挂起。由于线程 A 持有着锁且无法继续执行，这直接导致等待该锁的线程 B 和 C 也完全无法推进。

你会发现，在 T3 时刻，所有线程都停滞了。根本原因在于，我们为解决多线程安全问题而引入的互斥锁，“惊动”了操作系统。这类系统级的锁是由操作系统实现的。那么，解决线程安全问题一定要经过操作系统吗？

答案是否定的。我们可以在更底层的硬件层面解决这个问题，即直接利用 CPU 提供的特定原子指令。实际上，操作系统的互斥锁也正是基于这些指令构建的。既然操作系统能用，我们（在用户态）同样可以使用这些指令。基于此，我们可以对上述代码进行改造：

int count = 0;

void add() {
    int old_value;
    do {
      old_value = count;
    } while (!atomic_compare_exchange(&count, &old_value, old_value + 1));
}

现在，add 函数是线程安全的，我们没有使用传统的锁。无论多少个线程同时调用它，最终 count 的值都是正确的。关键在于，这个函数的执行完全不依赖操作系统来调度和阻塞线程。它直接利用了 CPU 的原子指令，由硬件层面来确保操作的秩序。

上述代码就是所谓的 lock-free（无锁） 实现。它的核心保证是：无论操作系统如何调度线程，在多个竞争线程中，至少有一个线程能够确保取得进展并向前推进。

一个理想的 lock-free 系统运行起来如下图所示，它保证了不存在所有线程都完全停滞的时间片。

可以看到，lock-free 提供了比传统互斥锁更强的进展保证。但请注意，不能简单地通过代码是否使用了 lock()/unlock() 调用来判断是否是 lock-free。例如，自旋锁（Spin Lock）虽然也不调用操作系统的锁函数，但它并不是 lock-free 的。

如果你用原子操作这样实现 add 函数：

int count = 0;
int lock = 0;  // 自旋锁变量
void add () {
    int expected = 0;
    while(!atomic_compare_exchange_weak(&lock, &expected, 1))
        expected = 0;
    count++;
    lock = 0;
}

这就是一个典型的自旋锁。如果某个线程在持有自旋锁后被操作系统挂起，那么其他所有试图获取锁的线程都会陷入忙等待（死循环），除了白白消耗 CPU 周期外，它们都无法取得任何进展。显然，在高负载下，这种程序的性能会急剧下降。

理解了 lock-free 之后，我们可以更进一步优化代码。在现代 C++ 中，我们可以直接使用原子类型：

std::atomic<int> count;
void add(){
    ++count;
}

这段代码没有锁，也无需在循环中反复尝试。无论操作系统如何调度线程，每个线程都能在有限的操作步骤内完成自己的任务。此时，我们说该程序是 wait-free（无等待） 的。

Wait-free 系统的理想运行状态如下图所示，它在任意时间片内都保证了所有线程能够向前推进。

Wait-free 的要求比 lock-free 更加严格。由于 wait-free 的程序保证每个线程都能在有限步骤内完成，因此它具有最好的可预测性和实时性，适用于对实时响应要求极高的场景。当然，实现 wait-free 算法的难度通常也远高于 lock-free。

值得注意的是，无论是 wait-free 还是 lock-free 的程序，其正确实现通常都不简单，需要深入理解内存模型和硬件细节。它们是在高并发场景下提升性能的利器，但使用不当会引入极其难以调试的问题。如果你对这些底层并发技术感兴趣，可以在云栈社区的计算机基础板块找到更多相关的深度讨论。