17370845950

Lock-Free栈的核心是用CAS等原子操作替代互斥锁实现线程安全；关键难点为ABA问题和内存回收，可通过带版本号指针、Hazard Pointer或std::shared_ptr等方案缓解。

Lock-Free栈的核心思想

Lock-Free栈的关键是避免使用互斥锁，转而用原子操作（如CAS）保证多线程下栈顶指针更新的线程安全。它不阻塞线程，即使某个线程暂停或崩溃，其他线程仍能继续执行。实现难点在于ABA问题和内存回收——C++11起可通过std::atomic和std::atomic_thread_fence配合智能指针或 Hazard Pointer 等技术缓解。

基础单链式Lock-Free栈（无内存回收）

这是教学级实现，忽略内存释放问题，聚焦核心逻辑：

• 用std::atomic维护栈顶指针head
• 压栈（push）：构造新节点 → 原子读取当前head → CAS设置新节点next为旧head → CAS更新head为新节点；失败则重试
• 弹栈（pop）：原子读取当前head → CAS将head更新为head->next → 返回原head节点；失败则重试

注意：pop返回的节点不能立即delete，否则可能被其他线程正在访问（use-after-free）。这是无锁栈最易出错的一环。

解决ABA问题与安全内存回收

ABA问题：head从A→B→A，CAS误判为未修改。C++常用两种方式：

• 带版本号的指针：用std::atomic存储指针+计数器（如低几位存版本），每次CAS前递增版本
• RCU或Hazard Pointer：记录线程当前正在使用的节点指针，确保其他线程不会回收它们
• 基于std::shared_ptr的引用计数方案（适用于简单场景）：用std::atomic<:shared_ptr>>，天然规避ABA（因对象生命周期由引用计数管理），但性能略低、需注意循环引用

一个可用的简化版（带版本号 + shared_ptr辅助）

兼顾正确性与可读性：

• 定义struct Node { T data; std::shared_ptr next; };
• 栈顶用std::atomic<:shared_ptr>> head;
• push时：new_node->next = head.load(); 再用CAS尝试更新head；失败则重试
• pop时：用CAS将head替换为head->next，返回原head；shared_ptr自动管理内存，无需手动delete

该版本不完美（shared_ptr有开销，且严格意义上非纯Lock-Free因引用计数内部有锁），但在多数业务场景中足够安全实用。