1. 无锁编程的动机
多线程共享数据时，最直观的做法是加互斥锁。但锁在高竞争场景下会暴露三类问题：阻塞导致的延迟抖动、优先级反转（低优先级持锁线程被高优先级线程抢占，而高优先级线程又在等这把锁）、以及持锁线程崩溃或死锁导致的全局停摆。无锁（Lock-Free）数据结构的目标，是让至少一个线程总能在有限步内推进，从而消除「一个线程挂起导致全体等待」的失败模式。
1.1 锁的代价
| 维度 | 互斥锁 | 无锁 |
|---|---|---|
| 无竞争开销 | 一次原子操作 + 系统调用可能 | 单次 CAS |
| 竞争行为 | 睡眠/唤醒、上下文切换 | 自旋重试 |
| 失败模式 | 死锁、优先级反转 | 活锁、饥饿（理论上可避免） |
| 可组合性 | 差（锁顺序敏感） | 好（单点原子） |
| 实现难度 | 低 | 高（内存回收是核心难点） |
1.2 无锁不是银弹
无锁算法通常比加锁版本更难写、更难调试，且在低竞争场景下未必更快。经验法则是：只有当锁的争用被 profiling 证实为瓶颈，且临界区极短（几十条指令）时，才值得引入无锁结构。真实系统里，更多时候是「无锁 + 有界等待」的混合方案。
2. 原子操作与内存序
原子性只保证「读改写不可分割」，不保证其他内存访问的可见顺序。现代 CPU 与编译器都会重排指令，因此必须显式声明内存序（Memory Order）。
2.1 六种内存序
C++11 与 C11 定义了六种内存序，强度递增：
| 内存序 | 语义 | 典型用途 |
|---|---|---|
memory_order_relaxed | 只保证原子性，不保证顺序 | 计数器、统计量 |
memory_order_consume | 数据依赖顺序（实践中多被当作 acquire） | 极少使用 |
memory_order_acquire | 之后的读写不能上移 | 读端加锁 |
memory_order_release | 之前的读写不能下移 | 写端解锁 |
memory_order_acq_rel | 同时具备 acquire 与 release | 读改写（RMW） |
memory_order_seq_cst | 全局单一总顺序 | 默认、最易推理 |
2.2 release/acquire 配对
#include <atomic>
#include <thread>
std::atomic<bool> ready{false};
int data = 0;
void producer() {
data = 42; // 普通写
ready.store(true, std::memory_order_release); // 之前的写不能下移
}
void consumer() {
while (!ready.load(std::memory_order_acquire)) { // 之后的读不能上移
// 自旋等待
}
// 此处一定能看到 data == 42
assert(data == 42);
}
如果把 release/acquire 换成 relaxed，assert 可能失败：编译器与 CPU 都可能把 data = 42 重排到 ready.store 之后。
2.3 seq_cst 的代价
seq_cst 在所有原子操作间建立单一全局顺序，代价是在 x86 上需要 MFENCE（或 LOCK 前缀），在 ARM/POWER 上需要更重的屏障。仅在确实需要「多变量之间的一致顺序」时才使用；单纯的生产者-消费者可见性用 release/acquire 即可。
3. CAS 与 ABA 问题
3.1 CAS 语义
比较并交换（Compare-And-Swap，CAS）是大多数无锁算法的基石，语义为：
// 伪代码：若 *ptr == expected，则 *ptr = desired，返回 true
bool compare_exchange_weak(T* ptr, T& expected, T desired);
注意 weak 版本允许伪失败（spurious failure），必须放在循环里；strong 版本只在值不等时失败。x86 对应 CMPXCHG，ARM 对应 LDXR/STXR 循环（LL/SC）。
// 经典 CAS 循环：原子自增
void atomic_increment(std::atomic<int>& x) {
int old = x.load(std::memory_order_relaxed);
while (!x.compare_exchange_weak(old, old + 1,
std::memory_order_release,
std::memory_order_relaxed)) {
// 失败时 old 已被更新为当前值，直接重试
}
}
3.2 ABA 问题
考虑一个无锁栈：线程 A 读到栈顶 p，准备 CAS 前被挂起；线程 B 弹出 p、弹出 p->next、再把 p 压回。A 恢复后 CAS 成功，但 p->next 已经指向了被弹出的节点——栈结构被破坏。
ABA 的本质：CAS 只比较「值」，无法区分「值相同但对象已换」。解法有三：
- Tagged Pointer：把版本号与指针打包进一个机器字，CAS 比较整个字。
- Hazard Pointer：让回收器知道某节点仍被引用，禁止复用地址。
- 不释放内存：用 GC 或 epoch 延迟回收，从根上消除地址复用。
// Tagged pointer：低 48 位存指针，高 16 位存版本号
struct TaggedPtr {
uintptr_t raw; // [ version:16 | pointer:48 ]
Node* ptr() const { return reinterpret_cast<Node*>(raw & 0x0000FFFFFFFFFFFFULL); }
uint16_t tag() const { return static_cast<uint16_t>(raw >> 48); }
};
// 每次成功修改都递增 tag，ABA 时 tag 不同，CAS 自然失败
4. 无锁栈与无锁队列
4.1 Treiber 栈
Treiber 栈是最简单的无锁栈，push 用 CAS 换头，pop 用 CAS 换头并返回旧头：
template <typename T>
class TreiberStack {
struct Node { T value; Node* next; };
std::atomic<Node*> head_{nullptr};
public:
void push(const T& v) {
Node* n = new Node{v, nullptr};
n->next = head_.load(std::memory_order_relaxed);
while (!head_.compare_exchange_weak(n->next, n,
std::memory_order_release,
std::memory_order_relaxed)) {
// n->next 被更新为最新 head，重试
}
}
bool pop(T& out) {
Node* h = head_.load(std::memory_order_acquire);
while (h && !head_.compare_exchange_weak(h, h->next,
std::memory_order_acquire,
std::memory_order_relaxed)) {
}
if (!h) return false;
out = h->value;
delete h; // ⚠️ 危险：其他线程可能仍持有 h，ABA 就在这里
return true;
}
};
Treiber 栈的 delete h 是 ABA 的高发点，必须配合第 5 节的内存回收方案才能安全。
4.2 Michael-Scott 队列
Michael-Scott 队列用**哑节点（dummy node）**分离头尾，入队改 tail->next 再推进 tail，出队推进 head：
// 简化结构
struct Node { T value; std::atomic<Node*> next; };
std::atomic<Node*> head_, tail_;
void enqueue(const T& v) {
Node* n = new Node{v, nullptr};
while (true) {
Node* last = tail_.load(std::memory_order_acquire);
Node* next = last->next.load(std::memory_order_acquire);
if (last != tail_.load(std::memory_order_acquire)) continue; // tail 已变
if (next == nullptr) {
if (last->next.compare_exchange_weak(next, n,
std::memory_order_release, std::memory_order_relaxed))
break; // 挂接成功
} else {
// 帮助其他线程推进 tail（helping）
tail_.compare_exchange_weak(last, next,
std::memory_order_release, std::memory_order_relaxed);
}
}
tail_.compare_exchange_weak(/*last*/nullptr, n, std::memory_order_release);
}
关键设计是 helping：当发现 tail 落后时，任何线程都可帮它推进，从而保证整体无锁进度。
5. 安全内存回收
无锁结构的最大难点不是 CAS 循环，而是何时可以安全释放一个刚被摘除的节点。四种主流方案：
5.1 引用计数
每个节点维护原子引用计数，摘除时递减，归零才释放。
| 优点 | 缺点 |
|---|---|
| 语义直观、可组合 | 每次访问都要原子自增/自减 |
| 无全局同步 | 无法处理环形引用 |
| 计数溢出风险 |
5.2 Hazard Pointer
每个线程公布自己正在访问的指针（hazard pointer）。回收线程扫描所有 hazard pointer，只有不被任何线程引用的节点才能释放。
// 线程 A：访问前先公布
hp[tid].store(node, std::memory_order_seq_cst);
// 重新校验 node 仍是 head（防止公布前已被摘除）
if (head_.load() != node) { /* 重试 */ }
// ... 使用 node ...
hp[tid].store(nullptr, std::memory_order_release); // 用完撤销
5.3 Epoch-Based Reclamation（EBR）
维护一个全局 epoch 计数器，每个线程声明自己处于哪个 epoch。线程内的延迟释放队列，只有在「所有线程都已越过该 epoch」时才真正回收。相比 hazard pointer，EBR 的读端开销极低（只读一个 epoch 变量），但需要线程周期性进入「静默态」（quiescent state）来推进 epoch。
5.4 RCU
读-复制-更新（Read-Copy-Update，RCU）是 EBR 的特化：读端零开销（甚至无需原子操作），写端复制出新版本、原子替换指针，再等待宽限期（grace period）后释放旧版本。
| 方案 | 读端开销 | 写端开销 | 内存放大 | 适用场景 |
|---|---|---|---|---|
| 引用计数 | 高 | 中 | 低 | 通用、无环结构 |
| Hazard Pointer | 中 | 高 | 中 | 无锁栈/队列 |
| EBR | 低 | 中 | 中高 | 高频读、低频写 |
| RCU | 极低 | 中 | 高 | 内核链表、路由表 |
Linux 内核的 list_for_each_entry_rcu 与 synchronize_rcu() 就是 RCU 的经典实现。
6. 无锁哈希表与动态扩容
数组与链表能无锁化，哈希表则要面对**扩容（resize）**这个全局操作。扩容期间旧桶到新桶的映射会变化，若用一把大锁保护整表，就退化成了有锁实现。
6.1 分段锁 vs 无锁
| 方案 | 并发度 | 扩容代价 | 实现复杂度 |
|---|---|---|---|
| 单锁哈希表 | 1 | 全局停顿 | 低 |
| 分段锁（ConcurrentHashMap 思路） | 段数 | 逐段迁移 | 中 |
| 无锁 + 跳表（Split-Ordered List） | 全并发 | 增量迁移 | 高 |
6.2 Split-Ordered List
Split-Ordered List 的核心技巧是把「桶下标 + 桶内序号」通过位反转（bit reversal）映射到一个递归可拆分的序上。这样新桶只会在已有桶的相邻位置插入，扩容时无需整体重建链表，只需把新增的哨兵节点用 CAS 挂进去：
// 递归拆分用的位反转哈希：保证新桶紧邻旧桶
static size_t reverse_bits(size_t x, int n) {
size_t r = 0;
for (int i = 0; i < n; ++i) {
r = (r << 1) | (x & 1);
x >>= 1;
}
return r;
}
// bucket = reverse_bits(hash, bits)，bits 从 0 递增到 log2(capacity)
扩容线程只需按 bits 逐层插入新桶，读线程通过「先查新桶、未命中再查旧桶」也能正确命中，从而实现无停顿扩容。
6.3 内存序在扩容中的角色
扩容时新桶的初始化必须先于其被其他线程可见，否则读者可能读到「半初始化」的桶。标准做法是用 release 发布桶指针、acquire 读取桶指针，并在读者侧做双重检查（double-checked locking 的无锁版本）。
7. 活锁、饥饿与公平性
无锁只保证「系统整体有进展」，不保证「每个线程都有进展」。
- 活锁（Livelock）：多个线程 CAS 反复互相击败，CPU 空转。缓解手段是指数退避：失败后随机延时或让出 CPU。
- 饥饿（Starvation）：某线程长期 CAS 失败。严格的**无等待（Wait-Free）**算法能杜绝，但实现难度极高，实践中罕见。
- 进度层级：阻塞（Blocking）< 无锁（Lock-Free）< 无等待（Wait-Free），无锁是工程上的性价比甜点。
// 指数退避：降低活锁概率
#include <random>
#include <thread>
void backoff(int& attempt) {
if (++attempt < 8) {
for (volatile int i = 0; i < (1 << attempt); ++i) { /* 自旋 */ }
} else {
std::this_thread::yield(); // 让出 CPU
}
}
8. 实战建议与常见陷阱
- 先测量再加锁改无锁：
perf、mutex争用计数、futex唤醒次数都是判断依据。 - 默认用 seq_cst，确认热点后再降级：内存序降级是纯性能优化，必须配合压力测试与 TSan/ASan。
- 用工具而非肉眼：
ThreadSanitizer能抓数据竞争，Relacy、CDSChecker可穷举内存序模型。 - 警惕伪共享（False Sharing）：两个原子变量落在同一 cache line 会互相失效，用
alignas(64)填充。 - 有界重试兜底：即使算法理论无锁，工程上仍应设置重试上限并降级到锁，避免活锁拖垮整机。
// 伪共享修复
struct alignas(64) PaddedCounter {
std::atomic<long> value{0};
char pad[64 - sizeof(std::atomic<long>)];
};
9. 小结
无锁数据结构的正确性由三根支柱共同支撑：原子操作保证单点不可分割，内存序保证跨变量的可见顺序，安全内存回收保证节点不会在使用中被复用。CAS 循环负责无阻塞推进，ABA 由 tagged pointer 或延迟回收消解，而回收方案的选择取决于读写比例与内存预算。它与https://plumephp.com/cs-concurrency-synchronization/中的锁原语互为补充，理解其底层还需回到https://plumephp.com/cs-cache-coherence/的缓存一致性协议。
参考文章
- 内存分配与回收机制：https://plumephp.com/cs-memory-management/
- 线程模型与调度：https://plumephp.com/cs-process-thread/
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。