背景介绍
在现代高并发系统中,锁(mutex / spinlock)并不是免费的。
随着 CPU 核心数不断增加,传统'加锁保护共享数据'的方式,会逐渐暴露出一系列问题:
- 线程频繁阻塞、唤醒,系统调用开销巨大
- 锁竞争严重,CPU 利用率下降
- 容易产生死锁、优先级反转
- 高并发下吞吐量急剧下降
因此,在以下场景中,人们开始大量使用 无锁(Lock-Free)数据结构:
- 高性能服务器
- 实时系统
- 游戏引擎
- 网络库 / 中间件
- 内存分配器
- 并发容器
而在所有无锁数据结构中,无锁链表(Lock-Free Linked List) 是最经典、也是最具教学价值的例子之一。
它几乎涵盖了并发编程中所有核心思想:
- CAS(Compare-And-Swap)
- 原子操作
- ABA 问题
- 内存可见性
- 失败重试(Retry Loop)
本项目的目标不是'造一个工业级 STL 容器',而是:
用最清晰、最易理解的方式,手写一个 C++ 无锁链表,彻底理解 Lock-Free 的本质
为了保证教学可控性,本文实现的是:
- 基于 Treiber 思想的无锁单向链表(头插 / 头删)
- 本质上是'无锁链表的一种典型特例'
这是学习 Harris-Michael 无锁链表、无锁队列、无锁栈 的必经之路。
需求
1. 功能需求
- 使用 C++ 实现无锁单向链表
- 支持多线程并发插入
- 支持多线程并发删除
- 不使用 mutex / lock
- 基于 CAS 原子操作
2. 技术要求
- 使用
std::atomic - 使用 Compare-And-Swap
- 正确处理并发竞争
- 代码可在 C++17 环境下编译
3. 教学与工程要求
- 代码结构清晰
- 明确展示'失败重试'模型
- 注释解释每一步并发语义
- 为后续复杂无锁结构打基础
技术原理
1. 什么是无锁(Lock-Free)
无锁并不意味着:
'没有任何同步'
而是意味着:
系统整体始终向前推进,不会因某个线程阻塞而停滞
Lock-Free 的核心保证是:
- 至少有一个线程可以在有限步内完成操作
2. CAS(Compare-And-Swap)
CAS 是无锁算法的基石,其语义是:
if (*addr == expected) *addr = desired;
在 CPU 层面,这是一条不可中断的原子指令。
3. Treiber 链表思想
Treiber 在 1986 年提出了一种:

