校招C++20并发系列10-理解线程安全等级：Lock-Free与Wait-Free实战辨析

在并发编程中，我们常听到“无锁（Lock-Free）”和“无等待（Wait-Free）”这两个术语。它们都属于非阻塞（Non-blocking）算法的范畴，但在系统保证和性能表现上有着本质的区别。理解这两者的差异，对于设计高并发数据结构至关重要。

非阻塞算法的分类

非阻塞算法的核心特征是：如果一个线程被挂起或崩溃，其他线程仍能继续执行。在此基础上，我们可以根据“系统层面进度推进”的保证程度，将其进一步细分为无锁和无等待两类。

什么是无锁（Lock-Free）？

宏观来说，无锁实现必须保证：在任何时刻，至少有一个线程能成功完成其有效工作。

这意味着，虽然单个线程可能会因为竞争失败而反复重试，甚至陷入死循环空转，但整个系统不会停滞。只要有一个线程在推进，系统的整体进度就在向前发展。这是无锁算法的最低保障。

什么是无等待（Wait-Free）？

无等待是比无锁更严格的约束。它要求：每个线程都能在有限步骤内完成其操作，无论其他线程如何调度或干扰。

在无等待算法中，没有任何一个线程会被迫无限期地等待或重试。每个线程都能独立、确定性地取得进展。这通常意味着更高的实时性保证，但也往往伴随着更复杂的实现难度。

无锁实现：CAS 循环的陷阱

为了深入理解，我们首先看一个典型的无锁计数器实现。该实现使用 compare_exchange_weak（或强版本）来更新共享原子变量。

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>

std::atomic<int> sync{0}; // 共享原子计数器

void lock_free_increment() {
    int expected = sync.load();
    do {
        // 期望当前值为 expected，目标值为 expected + 1
        // 如果期间有其他线程修改了 sync，比较会失败，返回 false
    } while (!sync.compare_exchange_weak(expected, expected + 1));
}

int main() {
    const int num_threads = 8;
    const int iterations_per_thread = (1 << 25); // 2^25 次迭代
    
    std::vector<std::thread> threads;
    for (int i = 0; i < num_threads; ++i) {
        threads.emplace_back([iterations_per_thread]() {
            for (int j = 0; j < iterations_per_thread; ++j) {
                lock_free_increment();
            }
        });
    }

    for (auto& t : threads) {
        t.join();
    }
    
    std::cout << &#34;Final value: &#34; << sync.load() << std::endl;
    return 0;
}

为什么它是无锁的？

在上述代码中，compare_exchange_weak 是一个原子操作。如果多个线程同时执行此操作，硬件或编译器会保证只有一个线程能成功更新值，其他线程会收到失败信号。因此，总有一个线程能成功执行更新，满足无锁的定义。

为什么它不是无等待的？

关键在于 do-while 循环。假设线程 A 加载了 expected 值，但在执行 compare_exchange 之前，线程 B 也加载了相同的 expected 并成功更新了 sync。此时，线程 A 的比较操作会失败，导致它重新加载最新值并再次尝试。

在高竞争场景下，运气差的线程可能陷入 自旋（Spin） 状态，即在 do-while 循环中空转，耗费大量 CPU 时间却无法取得实质性的逻辑进展。这种不确定性使得该算法不具备无等待特性。

易错点：无锁不等于高性能。频繁的 CAS 失败会导致缓存行失效（Cache Line Invalidations），引发严重的性能抖动。

无等待实现：原子递增的本质

接下来，我们对比一个基于内置原子操作的无等待实现。

void wait_free_increment() {
    // fetch_add 是原子的，且保证每个调用者都能直接完成一次递增
    sync.fetch_add(1, std::memory_order_relaxed);
}

逻辑分析

非阻塞：如果某个线程休眠，其他线程依然可以执行 fetch_add，互不干扰。

无锁：任何时刻都有线程在执行原子递增，系统进度持续推进。

无等待：fetch_add 是一条单一的指令序列（或在硬件层面保证完成的原子块）。线程 A 无法通过“失败重试”的方式去阻塞或干扰线程 B 的递增操作。每个线程都能在固定步数内完成工作。

虽然现代 CPU 的缓存一致性协议会导致缓存行在不同核心间跳跃（Cache Line Bouncing），带来一定的性能开销，但从算法逻辑上看，线程之间没有相互强制重试的关系，因此符合无等待定义。

性能对比与选型建议

在实际测试中（如视频中所示，编译标志为 -O3 -std=c++20 -lpthread），两者表现出显著的性能差异：

无锁实现（CAS 循环）：耗时通常在 2.0 ~ 3.0 秒 之间。由于存在竞争导致的重试和缓存一致性风暴，性能波动较大。

无等待实现（Atomic Fetch-Add）：耗时通常在 0.5 ~ 0.6 秒 之间。开销主要限于缓存行的同步，几乎没有额外的逻辑重试成本。

何时选择哪种方案？

尽管无等待实现在此例中性能更优，但这并不意味着它总是更好的选择：

实现复杂度：许多复杂的数据结构（如链表、树）很难用无等待方式实现，而无锁实现往往能通过重试机制简化逻辑。

实时性需求：如果你需要严格的确定性延迟（例如嵌入式系统或高频交易），无等待是必须的，因为它消除了最坏情况下的等待时间。

通用场景：对于大多数通用并发容器，无锁实现已经足够高效且易于维护。

小结

无锁关注的是“系统整体不卡死”，允许个别线程重试；无等待关注的是“每个个体不等待”，保证所有线程都能快速完成。在选择时，不仅要考虑吞吐量，还要权衡实现的复杂度和对实时性的要求。

速查表