无锁数据结构(Lock-Free)

定义

无锁数据结构(Lock-Free Data Structure)指并发访问时不使用互斥锁,而是通过 CAS(Compare-And-Swap)等硬件原子指令协调线程的结构。无锁(lock-free)的严格含义是:任意时刻至少有一个线程能在有限步内取得进展,即使其他线程被挂起。

原理

典型套路是"读取-计算-CAS 提交":线程先读共享状态,本地计算新值,再用 CAS 原子地替换,失败则重试。经典实现包括 Treiber 栈、Michael-Scott 无锁队列等。难点在于 ABA 问题(指针被释放又复用导致 CAS 误判,常用带版本号的指针解决)和安全内存回收(hazard pointer、epoch-based reclamation、RCU)。

应用

Java 的 ConcurrentLinkedQueue 基于 Michael-Scott 队列,java.util.concurrent 大量使用 CAS;Linux 内核的 RCU、高频交易系统的无锁环形队列(如 Disruptor)都是代表性应用。

优缺点

优点是无死锁、无优先级反转、高争用下伸缩性好;缺点是设计与验证极其困难,内存回收复杂,低争用时未必快于精细锁。