各位听众，下午好！欢迎来到今天的技术讲座。我是您的主讲人，一名在并发编程领域深耕多年的编程专家。今天，我们将共同深入探讨一个在并发世界中具有至高无上地位的概念：等待无关（Wait-Free）算法。这个话题不仅充满理论深度，更在某些极端场景下展现出无与伦比的实践价值。
在现代多核处理器架构下，并发编程已成为软件开发的核心挑战。我们追求的不仅仅是程序能够同时运行，更是它们能够高效、正确、可预测地协同工作。然而，实现这一目标并非易事。死锁、活锁、饥饿、优先级反转等一系列并发陷阱无时无刻不在威胁着我们的系统稳定性。传统的并发控制手段，如锁（Mutexes）、信号量（Semaphores），虽然解决了互斥访问的问题，却也引入了阻塞（Blocking）的固有缺陷。一个线程持有锁时，其他试图获取该锁的线程必须停下来等待，直到锁被释放。在某些情况下，这种等待可能导致不可预测的延迟，甚至整个系统陷入停滞。
正是在这样的背景下，非阻塞（Non-Blocking）算法应运而生，而等待无关（Wait-Free）算法，作为非阻塞算法家族中的最强成员，承诺了一个几乎完美的并发世界：每一个线程，无论其他线程运行得有多慢，甚至突然崩溃，都能够保证在有限的步骤内完成自己的操作。这是一种极致的公平性和鲁棒性保证，是并发编程领域的“圣杯”之一。
今天，我将带领大家从并发控制的基本概念出发，逐步理解等待无关算法的强大之处，探索其背后的核心技术，并通过具体的代码示例来剖析其实现原理。我们还将讨论等待无关算法的实际应用场景、面临的挑战以及未来的发展方向。
一、 并发控制的谱系：从阻塞到等待无关
在深入探讨等待无关算法之前，我们有必要先回顾一下并发控制的各种保证级别，它们构成了一个从弱到强的谱系。理解这些不同的级别，有助于我们更好地认识等待无关算法的独特价值。
1. 阻塞（Blocking）
这是最常见的并发控制方式，例如使用互斥锁（Mutex）或信号量（Semaphore）。
- 特点： 当一个线程尝试访问被另一个线程持有的资源时，它会被阻塞，暂停执行，直到资源可用。
- 优点： 相对容易理解和实现，提供了强大的互斥保证。
- 缺点：
- 死锁（Deadlock）： 两个或多个线程相互等待对方释放资源，导致所有线程都无法继续执行。
- 活锁（Livelock）： 线程反复尝试获取资源但总是失败，不断重试，消耗CPU但无实际进展。
- 饥饿（Starvation）： 某些线程可能长时间无法获取到所需的资源，导致其任务无法完成。
- 优先级反转（Priority Inversion）： 低优先级线程持有的锁被高优先级线程等待，导致高优先级线程被间接阻塞。
- 性能瓶颈： 在高竞争环境下，锁的开销（上下文切换、缓存失效）可能导致性能急剧下降。
- 不可预测的延迟： 线程的暂停和恢复受调度器影响，可能导致系统响应时间不稳定。
示例：使用互斥锁的计数器（C++）
#include <iostream>
#include <thread>
#include <mutex>
#include <vector>
class BlockingCounter {
public:
BlockingCounter() : count_(0) {}
void increment() {
std::lock_guard<std::mutex> lock(mtx_); // Acquire lock, blocks if held by another thread
count_++;
}
int get() {
std::lock_guard<std::mutex> lock(mtx_);
return count_;
}
private:
int count_;
std::mutex mtx_;
};
void run_blocking_counter(BlockingCounter& counter, int num_increments) {
for (int i = 0; i < num_increments; ++i) {
counter.increment();
}
}
// int main() {
// BlockingCounter counter;
// std::vector<std::thread> threads;
// int num_threads = 4;
// int increments_per_thread = 100000;
// for (int i = 0; i < num_threads; ++i) {
// threads.emplace_back(run_blocking_counter, std::ref(counter), increments_per_thread);
// }
// for (auto& t : threads) {
// t.join();
// }
// std::cout << "Blocking Counter final value: " << counter.get() << std::endl;
// // Expected: num_threads * increments_per_thread
// return 0;
// }这个简单的例子展示了阻塞计数器。当多个线程同时调用 increment() 时，它们会竞争 mtx_。只有一个线程能成功获取锁，其他线程将被阻塞，直到锁被释放。
2. 非阻塞（Non-Blocking）
非阻塞算法旨在消除上述阻塞算法的缺点，其核心思想是：没有一个线程能够被其他线程的暂停或失败所阻塞。 这意味着即使一个线程突然停止，其他线程也能继续执行它们的操作。非阻塞算法又可以细分为几个级别：
a. 自由阻塞（Obstruction-Free）
- 特点： 如果一个线程在足够长的时间内能够单独运行（即没有其他线程干扰），那么它就能在有限的步骤内完成其操作。
- 优点： 比传统的阻塞算法更健壮，对死锁免疫。
- 缺点： 仍然可能发生活锁。在高竞争环境下，所有线程都可能反复回滚并重试，导致系统整体进展缓慢。
b. 免锁（Lock-Free）
- 特点： 保证系统范围内的进展。在有限的步骤内，至少有一个线程能够完成其操作。
- 优点： 确保系统整体不会停滞，对死锁和活锁免疫。
- 缺点： 单个线程仍可能遭遇饥饿。 理论上，一个线程可能无限次地尝试操作但总是失败，因为其他线程总是在它之前成功。
- 实现： 通常依赖于原子操作，如比较并交换（Compare-And-Swap, CAS）。
示例：使用CAS的免锁计数器（C++）
#include <atomic>
// ... (includes from above)
class LockFreeCounter {
public:
LockFreeCounter() : count_(0) {}
void increment() {
int old_val = count_.load(std::memory_order_relaxed); // Read current value
while (!count_.compare_exchange_weak(old_val, old_val + 1,
std::memory_order_release,
std::memory_order_relaxed)) {
// If CAS fails, old_val is updated with the current value of count_
// so we can retry with the fresh value.
}
}
int get() {
return count_.load(std::memory_order_acquire);
}
private:
std::atomic<int> count_; // std::atomic provides atomic operations
};
void run_lock_free_counter(LockFreeCounter& counter, int num_increments) {
for (int i = 0; i < num_increments; ++i) {
counter.increment();
}
}
// int main() {
// LockFreeCounter counter;
// std::vector<std::thread> threads;
// int num_threads = 4;
// int increments_per_thread = 100000;
// for (int i = 0; i < num_threads; ++i) {
// threads.emplace_back(run_lock_free_counter, std::ref(counter), increments_per_thread);
// }
// for (auto& t : threads) {
// t.join();
// }
// std::cout << "Lock-Free Counter final value: " << counter.get() << std::endl;
// // Expected: num_threads * increments_per_thread
// return 0;
// }在这个免锁计数器中，increment() 方法使用 compare_exchange_weak (CAS) 循环。如果CAS失败，说明 count_ 在 load 和 compare_exchange_weak 之间被其他线程修改了，old_val 会被自动更新为 count_ 的新值，然后线程会重试。这个循环保证了最终会有一个线程成功更新计数器，从而确保系统整体的进展。然而，一个特定的线程可能会因为频繁的CAS失败而长时间无法完成其操作，这就是饥饿。
c. 等待无关（Wait-Free）
- 特点： 最强的非阻塞保证。它保证每一个线程都能在有限的步骤内完成其操作，无论其他线程的执行速度如何，也无论它们是否暂停或崩溃。
- 优点：
- 无饥饿： 每个线程都能保证最终完成任务。
- 无死锁、无活锁： 继承了非阻塞算法的优点。
- 可预测的性能： 由于每个操作的步数是有限的，因此可以更好地预测最坏情况下的执行时间，这在实时系统中至关重要。
- 容错性： 即使部分线程崩溃，也不会影响其他线程的正常执行。
- 缺点：
- 实现复杂： 设计和实现等待无关算法远比免锁算法更具挑战性。
- 性能开销： 在低竞争环境下，等待无关算法的开销可能比免锁或阻塞算法更高，因为它们通常涉及更复杂的协调机制（例如“帮助”其他线程完成操作）。
| 特性/算法类型 | 阻塞 (Blocking) | 自由阻塞 (Obstruction-Free) | 免锁 (Lock-Free) | 等待无关 (Wait-Free) |
|---|---|---|---|---|
| 死锁免疫 | 否 | 是 | 是 | 是 |
| 活锁免疫 | 否 | 否 | 是 | 是 |
| 饥饿免疫 | 否 | 否 | 否 | 是 |
| 系统进展 | 否 (可能死锁) | 仅隔离时 | 是 | 是 |
| 单个线程进展 | 否 (可能饥饿/阻塞) | 仅隔离时 | 否 (可能饥饿) | 是 |
| 复杂度 | 低 | 中 | 高 | 极高 |
| 最坏情况性能 | 不可预测 | 不可预测 | 有界（系统） | 有界（每个线程） |
二、 等待无关的基石：原子原语
要构建任何非阻塞算法，我们都离不开硬件提供的原子操作。这些操作在执行过程中是不可中断的，因此在多线程环境下能够保证其完整性。它们是实现无锁和等待无关算法的基石。
1. 比较并交换（Compare-And-Swap, CAS）
CAS 是最常用也是最重要的原子原语之一。
- 操作：
CAS(address, expected_value, new_value) - 行为： 原子地检查
address处的当前值是否等于expected_value。如果是，则将address处的值更新为new_value，并返回true。否则，不进行任何操作，并返回false。 - 思想： “如果我看到的值仍然是我期望的值，那么就修改它。”
CAS的伪代码表示：
bool CAS(Address* addr, Value expected, Value new_val) {
if (*addr == expected) {
*addr = new_val;
return true;
} else {
return false;
}
}C++中std::atomic的compare_exchange_weak/_strong方法就是CAS的体现。 _weak版本可能在条件满足时也返回false（例如，在某些平台上由于虚假失败，Spurious Failure），通常用在循环中；_strong版本保证只有在条件不满足时才返回false。
CAS虽然强大，但它本身并不能直接构建等待无关算法。如我们前面在免锁计数器中看到的，CAS循环可能会导致饥饿。
2. 取并加（Fetch-And-Add, FAA）
FAA 是另一个常用的原子原语。
- 操作：
FAA(address, value_to_add) - 行为： 原子地将
value_to_add添加到address处的值，并返回address处的原始值。 - 用途： 常见于原子计数器、生成唯一ID等场景。
FAA的伪代码表示：
Value FAA(Address* addr, Value increment) {
Value old_val = *addr;
*addr = old_val + increment;
return old_val;
}C++的std::atomic提供了fetch_add方法，实现类似FAA的功能。
3. 加载链接/存储条件（Load-Link/Store-Conditional, LL/SC）
LL/SC 是一对原子原语，比CAS更强大，能够实现更复杂的原子操作。
- Load-Link (LL)：
LL(address)返回address处的值，并“链接”该地址。 - Store-Conditional (SC)：
SC(address, new_value)尝试将new_value写入address。只有在address处的值自上次LL操作以来没有被其他处理器修改过时，写入才会成功，并返回true。否则，写入失败，返回false。
LL/SC的伪代码表示：
Value LoadLink(Address* addr) {
// Record that this address is "linked" by the current thread
return *addr;
}
bool StoreConditional(Address* addr, Value new_val) {
// If the address has been modified since the last LoadLink by this thread, return false.
// Otherwise, update *addr = new_val and return true.
}优点：
- 灵活性： LL/SC 允许在 LL 和 SC 之间执行任意复杂的计算，而不会像 CAS 那样要求计算结果必须是单个值。这使得实现多字原子操作或更复杂的数据结构更新变得更容易。
- 避免ABA问题： LL/SC 的语义通常能够自然地避免 ABA 问题（我们稍后会讨论）。如果链接的地址在 LL 和 SC 之间被修改过，即使最终值又变回了原始值，SC 也会失败。
LL/SC 示例：原子递增
// 假设有硬件支持的LL/SC指令
Value atomic_increment_llsc(Address* addr) {
Value old_val;
do {
old_val = LoadLink(addr);
// Perform arbitrary computation here, e.g., old_val + 1
} while (!StoreConditional(addr, old_val + 1)); // Retry if SC fails
return old_val; // Or new value, depending on desired return
}尽管LL/SC在理论上更强大，但并非所有硬件都直接暴露这些指令，在C++等高级语言中，我们通常仍然主要依赖CAS。
三、 等待无关算法的核心策略：互助机制（Helping Mechanism）
等待无关算法最核心的思想在于：如果一个线程观察到另一个线程正在尝试执行一个操作但似乎陷入停滞（例如，它宣布了一个操作意图，但长时间未完成），那么这个观察者线程可以“帮助”它完成那个操作。 这种互助机制是确保每个线程都能在有限步内完成任务的关键。
为了实现互助，算法通常需要满足以下几个条件：
- 操作可公开： 每个线程在开始一个操作之前，必须将其意图（操作类型、参数、当前状态等）公开发布到一个共享的可访问位置。
- 操作可线性化： 尽管可能涉及多个步骤和多个线程的帮助，但从外部观察，每个操作都必须看起来像是在某个单一的、瞬间的时间点完成的。
- 操作可重启或可重入： 如果一个线程在帮助另一个线程时中断，或者在自己的操作中被帮助，它必须能够从中断点继续，或者重新开始而不会导致不一致状态。
- 状态可见性： 线程的操作状态必须是其他线程可见的，以便它们能够判断是否需要提供帮助，以及如何提供帮助。
1. 操作描述符（Operation Descriptor）
互助机制通常通过操作描述符（Operation Descriptor）来实现。每个线程在执行一个等待无关操作时，都会创建一个或复用一个操作描述符。这个描述符包含了：
- 操作类型： 例如，读取、写入、入队、出队等。
- 操作参数： 例如，要写入的值、要插入的元素等。
- 操作状态： 例如，待处理（Pending）、进行中（InProgress）、已完成（Completed）、已失败（Failed）等。
- 结果： 操作完成后，可能存储结果的地方。
这些描述符通常存储在一个全局的、大小固定的数组中，每个线程都有一个专属的槽位（slot）。线程通过其ID来索引自己的描述符。
2. 帮助逻辑
当一个线程执行其操作时，它的核心逻辑通常包含以下步骤：
- 发布意图： 将自己的操作信息写入其专属的操作描述符，并将其标记为“活动”（Active）或“待处理”（Pending）。
- 尝试执行自己的操作： 尝试完成自己的操作。这可能涉及一次或多次原子操作，例如CAS。
- 扫描并帮助： 如果自己的操作未能一次性完成，或者在等待其他操作完成时，它会扫描其他线程的操作描述符。
- 提供帮助： 如果发现某个线程的描述符处于“活动”状态但未完成，它会尝试帮助那个线程完成其操作。帮助的过程通常就是模拟那个线程接下来会执行的原子操作。
- 循环直到完成： 线程会重复步骤2-4，直到自己的操作被标记为“完成”为止。由于每个帮助操作都保证推进了某个线程的进度，而每个线程最终都会被帮助，因此保证了等待无关性。
关键点：
- 幂等性（Idempotence）或可安全重试： 被帮助的操作必须能够安全地被多次尝试或被多个线程同时帮助而不会导致不一致。
- 状态更新： 帮助线程在成功帮助后，必须原子地更新被帮助操作的描述符状态为“完成”。
四、 构造等待无关算法：以原子值更新为例
现在，让我们通过一个具体的例子来演示如何构建一个等待无关的算法。我们将实现一个简化的WaitFreeAtomicValue类，它支持一个等待无关的update操作。这个update操作类似于CAS，但额外引入了互助机制以保证等待无关性。
为了简化，我们假设：
- 线程ID是预先分配的，从0到
numThreads-1。 WaitFreeAtomicValue在创建时知道最大线程数。
核心思想：
每个线程都有一个OpDescriptor来记录它当前尝试执行的更新操作。当一个线程执行update时，它会首先尝试完成自己的操作。如果未能立即完成，它会遍历所有线程的OpDescriptor，并尝试帮助那些正在进行中的操作。
#include <atomic>
#include <vector>
#include <thread>
#include <iostream>
#include <functional> // For std::ref
// 前向声明，为了在OpDescriptor中使用WaitFreeAtomicValue
template<typename T>
class WaitFreeAtomicValue;
// 1. 操作描述符 (Operation Descriptor)
template<typename T>
struct OpDescriptor {
enum Type { NONE, UPDATE }; // 操作类型：无操作，更新
Type type;
T expectedValue; // 期望的旧值 (用于UPDATE)
T newValue; // 要设置的新值 (用于UPDATE)
std::atomic<bool> completed; // 操作是否已完成
std::atomic<bool> active; // 描述符是否被某个线程激活并正在使用
OpDescriptor() : type(NONE), expectedValue(T{}), newValue(T{}), completed(false), active(false) {}
// 初始化一个更新操作
void initUpdate(T expVal, T newVal) {
type = UPDATE;
expectedValue = expVal;
newValue = newVal;
completed.store(false, std::memory_order_release); // 刚开始，未完成
active.store(true, std::memory_order_release); // 标记为活动
}
// 清理描述符，以便下次复用
void clear() {
type = NONE;
expectedValue = T{};
newValue = T{};
completed.store(false, std::memory_order_release);
active.store(false, std::memory_order_release);
}
};
// 2. 等待无关原子值 (WaitFreeAtomicValue)
template<typename T>
class WaitFreeAtomicValue {
private:
std::atomic<T> value; // 实际共享的原子值
std::vector<OpDescriptor<T>> opDescriptors; // 操作描述符数组，每个线程一个槽位
int numThreads; // 最大线程数
// 辅助函数：帮助完成一个指定索引的操作
// 这是一个内部函数，用于实现互助机制
void help(int opIndex) {
OpDescriptor<T>& desc = opDescriptors[opIndex];
// 检查描述符是否真的活跃且未完成
if (!desc.active.load(std::memory_order_acquire) || desc.completed.load(std::memory_order_acquire)) {
return; // 描述符不活跃或已完成，无需帮助
}
if (desc.type == OpDescriptor<T>::UPDATE) {
T currentVal = value.load(std::memory_order_acquire); // 获取当前值
// 如果当前值与操作描述符中期望的旧值一致，则尝试CAS
if (currentVal == desc.expectedValue) {
if (value.compare_exchange_strong(currentVal, desc.newValue,
std::memory_order_release,
std::memory_order_relaxed)) {
// CAS成功，说明这个更新操作已被应用
desc.completed.store(true, std::memory_order_release);
}
// 如果CAS失败，说明在加载currentVal后，value已被其他线程修改
// 此时，本线程（作为帮助者）不应该再次尝试CAS，
// 因为desc.expectedValue不再是当前value。
// 此时，有两种处理方式：
// 1. 标记desc.completed为true，表示本次帮助尝试结束，但未成功应用。
// 原始线程会发现未成功应用，然后重新读取value并创建新的描述符重试。
// 2. 什么都不做，让原始线程或另一个帮助线程用新的expectedValue来尝试。
// 为了保证等待无关性，通常选择第一种，表示“该描述符的任务已处理完毕，无论成功与否”。
// 原始线程看到completed为true但值不对时，会重新开始。
else {
desc.completed.store(true, std::memory_order_release); // 帮助尝试完成，但未成功应用
}
} else {
// 当前值与期望的旧值不一致。
// 这意味着原始线程的期望值已经过时。
// 此时，该操作描述符已经无法成功应用其预期的更新。
// 标记为完成，以便原始线程可以重新读取并重试。
desc.completed.store(true, std::memory_order_release); // 帮助尝试完成，但未成功应用
}
}
// 对于其他类型的操作，这里可以添加相应的帮助逻辑。
// 例如，一个wait-free queue的dequeue操作，帮助可能意味着移动head指针。
}
// 每个操作前都会扫描并帮助所有活跃的描述符
void scanAndHelp() {
for (int i = 0; i < numThreads; ++i) {
if (opDescriptors[i].active.load(std::memory_order_acquire)) {
help(i);
}
}
}
public:
// 构造函数
WaitFreeAtomicValue(T initialValue, int maxThreads)
: value(initialValue), numThreads(maxThreads) {
// 为每个线程预留一个操作描述符槽位
opDescriptors.resize(numThreads);
}
// 等待无关的更新操作
// threadId: 调用线程的唯一ID (0 到 numThreads-1)
// expected: 期望的当前值
// desired: 要设置的新值
// 返回值表示：本次尝试是否成功将值从expected更新为desired。
// 注意：等待无关保证的是操作最终会完成，如果update返回false，
// 调用者需要重新读取当前值并再次尝试。
bool update(int threadId, T expected, T desired) {
OpDescriptor<T>& myOp = opDescriptors[threadId];
myOp.clear(); // 确保描述符是干净的
myOp.initUpdate(expected, desired); // 初始化自己的操作描述符
bool success = false;
// 循环直到自己的操作被标记为完成
while (!myOp.completed.load(std::memory_order_acquire)) {
// 1. 首先尝试完成自己的操作
help(threadId);
// 2. 扫描并帮助其他可能正在进行的线程
// 这一步是等待无关性的关键：确保即使我的操作失败，
// 我也在帮助其他线程推进，从而保证了系统整体和个体线程的进展。
scanAndHelp();
// 如果我的操作描述符被标记为已完成
if (myOp.completed.load(std::memory_order_acquire)) {
// 检查是否成功将值更新为desired
// 只有当当前值就是我期望设置的desired值时，才算成功。
// 否则，说明我的expected值已过时，或者在帮助过程中被其他线程修改。
if (value.load(std::memory_order_acquire) == desired) {
success = true;
} else if (expected == desired) {
// 特殊情况：如果期望值和目标值相同，即使没有实际CAS，也算作成功。
success = true;
}
break; // 操作描述符已处理，退出循环
}
}
myOp.clear(); // 清理描述符，为下次操作做准备
return success;
}
// 等待无关的读取操作
// 尽管读取通常是原子的，但在Wait-Free上下文中，
// 读取操作也需要扫描并帮助其他未完成的写操作，
// 以确保读取到的是一致且最新的状态，并且不会因为其他线程的写操作而延迟。
T read(int threadId) {
scanAndHelp(); // 帮助其他线程完成他们的操作，确保状态一致性
return value.load(std::memory_order_acquire);
}
};
// 模拟线程函数
void run_wait_free_atomic_value(int id, WaitFreeAtomicValue<int>& val, int increments) {
std::cout << "Thread " << id << " starting." << std::endl;
for (int i = 0; i < increments; ++i) {
int currentVal;
do {
currentVal = val.read(id); // 读取当前值
// 尝试更新，如果失败则循环重试，直到成功
} while (!val.update(id, currentVal, currentVal + 1));
// std::cout << "Thread " << id << " updated to " << currentVal + 1 << std::endl;
}
std::cout << "Thread " << id << " finished. Final value seen: " << val.read(id) << std::endl;
}
int main() {
const int NUM_THREADS = 4;
const int INCREMENTS_PER_THREAD = 100000; // 每个线程执行10万次递增
// 初始化WaitFreeAtomicValue，初始值为0，最大支持NUM_THREADS个线程
WaitFreeAtomicValue<int> sharedValue(0, NUM_THREADS);
std::vector<std::thread> threads;
for (int i = 0; i < NUM_THREADS; ++i) {
threads.emplace_back(run_wait_free_atomic_value, i, std::ref(sharedValue), INCREMENTS_PER_THREAD);
}
for (auto& t : threads) {
t.join();
}
int finalValue = sharedValue.read(0); // 任何线程都可以读取最终值
std::cout << "nFinal shared value: " << finalValue << std::endl;
std::cout << "Expected value: " << NUM_THREADS * INCREMENTS_PER_THREAD << std::endl;
if (finalValue == NUM_THREADS * INCREMENTS_PER_THREAD) {
std::cout << "Wait-free update operation successful and consistent!" << std::endl;
} else {
std::cout << "Wait-free update operation failed or had unexpected behavior. Final value: " << finalValue << ", Expected: " << NUM_THREADS * INCREMENTS_PER_THREAD << std::endl;
}
return 0;
}
这个WaitFreeAtomicValue的例子虽然简单，但它清晰地展示了等待无关算法的核心机制：
- 发布意图：
update函数开始时，通过myOp.initUpdate(...)将自己的操作意图记录在共享的opDescriptors数组中。 - 自力更生与互助：
while (!myOp.completed.load(...))循环是关键。在每次迭代中，线程首先尝试通过help(threadId)来完成自己的操作。紧接着，它会调用scanAndHelp()遍历所有其他线程的描述符，尝试帮助它们完成其操作。 - 保证进展： 无论哪个线程的CAS操作成功，都会导致某个
OpDescriptor被标记为completed。由于每个线程都在不断尝试完成自己的操作并帮助其他线程，因此保证了在有限步内，它自己的操作最终也会被完成（或者被发现为已过时而需要重试）。这种重试机制结合帮助机制，共同构成了等待无关的保证。
五、 实际考量与挑战
等待无关算法虽然提供了最强的并发保证，但在实际应用中，它也带来了一系列挑战和权衡。
1. 实现的复杂性
- 设计难度极高： 从头设计一个正确的等待无关数据结构需要深厚的理论知识和对并发语义的精确理解。
- 调试困难： 并发错误本身就难以重现和调试，而等待无关算法中复杂的互助逻辑使得问题追踪变得更加棘手。错误可能隐藏在状态转换、内存序、ABA问题等多个层面。
- 正确性验证： 形式化验证是确保等待无关算法正确性的有效手段，但这本身就是一项专业的任务。
2. 性能开销
- 低竞争下的劣势： 在并发竞争不激烈的情况下，等待无关算法通常比锁或免锁算法有更高的开销。这是因为它们需要维护额外的状态（如操作描述符），并执行扫描和帮助其他线程的逻辑，这会增加内存访问（可能导致更多的缓存失效）和指令数量。
- 高竞争下的优势： 然而，在高竞争环境下，尤其是在线程可能被操作系统调度器任意暂停或抢占时，等待无关算法的性能优势就显现出来了。它们避免了上下文切换、死锁和饥饿，提供了更稳定的延迟和吞吐量。
- 缓存一致性开销： 频繁地读写共享的
OpDescriptor数组会导致大量的缓存行失效和同步流量，这在高核CPU上可能成为瓶颈。
3. 内存占用
- 操作描述符： 每个线程一个操作描述符，如果数据结构复杂，描述符的大小也会增加。对于支持大量线程的系统，这会增加内存消耗。
- 版本管理/垃圾回收： 复杂的等待无关数据结构可能需要更复杂的版本管理或非阻塞的垃圾回收机制（例如，为消除ABA问题而引入的标记），这也会增加内存和CPU开销。
4. ABA问题
- 问题描述： CAS操作只能检测值是否从A变成了B，但无法检测值是否从A变成了B，然后又变回了A。如果一个线程读取A，然后其他线程将A改为B又改回A，此时原始线程执行CAS(A, C)可能会成功，但其基于A值的假设可能已不再成立。
- 解决方案： 最常见的解决方案是使用带标记的指针（Tagged Pointers）。这通常通过在指针或值中添加一个版本号（或计数器）来实现。当值被修改时，版本号也随之递增。这样，即使值变回A，版本号也会不同（例如A1 -> B2 -> A3），CAS就能检测到这种变化。
- C++中的实践： 可以使用
std::atomic<std::pair<T, int>>或std::atomic<struct VersionedPtr { T* ptr; int version; }>来模拟带标记的指针。
带标记指针的ABA问题解决示例（概念性）：
struct Node {
int data;
// other fields
};
struct TaggedNodePtr {
Node* ptr;
int version; // Version counter to prevent ABA problem
bool operator==(const TaggedNodePtr& other) const {
return ptr == other.ptr && version == other.version;
}
};
std::atomic<TaggedNodePtr> head;
void update_head_atomically(Node* new_node) {
TaggedNodePtr old_head_tagged = head.load(std::memory_order_acquire);
TaggedNodePtr new_head_tagged = {new_node, old_head_tagged.version + 1}; // Increment version
while (!head.compare_exchange_strong(old_head_tagged, new_head_tagged,
std::memory_order_release,
std::memory_order_relaxed)) {
// old_head_tagged is updated by CAS on failure
new_head_tagged.version = old_head_tagged.version + 1; // Update new_head_tagged's version
}
}5. 适用场景
鉴于其复杂性和开销，等待无关算法并非适用于所有并发场景。它们最适合以下情况：
- 硬实时系统： 需要可预测的最坏情况执行时间，任何阻塞都可能导致灾难性后果。
- 高可用系统/容错系统： 线程失败不能导致整个系统停滞。
- 操作系统内核、虚拟机管理程序： 在这些底层组件中，阻塞可能引发深远的负面影响。
- 安全关键系统： 例如航空电子设备、医疗设备，要求极高的可靠性和可预测性。
- 超高竞争的共享数据结构： 在某些特定场景下，如果共享数据结构的竞争异常激烈，以至于锁机制的开销变得无法忍受，等待无关算法能够提供更好的吞吐量和延迟保证。
六、 展望：高级议题与未来方向
等待无关算法的研究和实践仍在不断演进，一些高级议题和新兴技术也在推动这一领域的发展。
1. 通用构造（Universal Construction）
由Herlihy在1991年提出的通用构造理论证明，如果一个系统拥有足够强大的原子原语（例如，具有共识数（Consensus Number）至少为2的CAS或LL/SC），那么原则上任何顺序数据结构都可以被转换为等待无关的并发数据结构。
- 基本思想： 通常涉及一个共享的“操作日志”或“意图数组”。每个线程在执行操作时，首先将其操作意图原子地添加到日志中。然后，它会遍历日志，执行所有未完成的操作（包括自己的和被帮助的）。
- 实践意义： 尽管这些通用构造在理论上很有趣，但它们通常在实践中效率低下，因为它们涉及大量的内存访问和复杂的协调。因此，通常只有在没有特定等待无关算法的情况下，才会考虑使用通用构造。
2. 事务内存（Transactional Memory, TM）
事务内存是一种旨在简化非阻塞并发编程的技术。它允许程序员将一系列内存操作声明为一个“事务”，然后系统会尝试乐观地执行这个事务。如果检测到冲突（即其他线程修改了事务读取或写入的数据），事务会被回滚并重试。
- 硬件事务内存（HTM）： 由处理器直接提供支持，通常性能更高，但容量有限。
- 软件事务内存（STM）： 在软件层面实现，灵活性高但通常开销较大。
- 与等待无关的关系： 某些STM实现可以提供等待无关的保证，但并非所有TM系统都如此。等待无关的TM通常需要更复杂的冲突解决策略和帮助机制。TM的吸引力在于它极大地简化了非阻塞算法的编写，让程序员可以像编写顺序代码一样编写并发代码，而底层系统负责处理并发问题。
3. 更简单的等待无关设计模式
学术界和工业界一直在探索更简单、更高效的等待无关设计模式和库。目标是降低实现复杂性，同时保持高性能。例如，一些基于特殊硬件特性或特定数据结构的等待无关队列、栈等。
4. 与数据结构无关的等待无关性
除了构建特定的等待无关数据结构，还有研究关注如何让任何函数调用变得等待无关，这通常涉及到更底层的操作系统调度和内存管理。
七、 展望并发编程的未来
等待无关算法代表了并发编程的最高境界。它解决了传统并发控制中几乎所有令人头痛的问题：死锁、活锁、饥饿以及不可预测的延迟。在追求极致性能、高可用性和可预测性的场景中，等待无关算法是不可或缺的工具。
尽管其实现复杂性和潜在的性能开销限制了其普遍应用，但随着硬件原子原语的不断发展、编程语言和编译器对并发模型的更好支持，以及对并发理论的深入理解，我们期待未来能有更多易于使用、高性能的等待无关解决方案出现。理解并掌握等待无关算法的原理，不仅能够帮助我们解决最严苛的并发挑战，更能提升我们对并发系统本质的深刻洞察。这是一场没有终点的探索之旅，但每一步都充满了挑战与收获。
感谢大家的聆听！