在多线程编程里，“锁” 这东西就像把双刃剑 —— 用好了能保数据安全，用不好就麻烦了：大粒度的锁把并发度压得死死的，稍不注意加错锁还可能搞出死锁，程序直接 “僵住”。
但如果能摆脱锁，搞出支持安全并发访问的数据结构呢？
哎，这就是无锁数据结构的厉害之处！它们靠原子操作和内存顺序保证来搞定并发访问的正确性，能大大减少线程间的阻塞和竞争。
说白了，无锁编程不光是为了性能优化，更藏着人类对 “更快、更靠谱系统” 的执念。今天咱就好好扒一扒这无锁数据结构的设计门道和实现路子。
不过先得提一嘴：设计无锁数据结构，那可得比走钢丝还小心！它的正确实现太难了，一旦出 bug，出错的场景往往没法复现，查起来能让人头秃。
你想啊，基于锁的实现，线程动不动就得阻塞等锁 —— 一个线程拿着锁，其他线程只能干瞪眼。但无锁数据结构不一样，不管多乱，总有至少一个线程能接着干活，不会全卡住。（还有种 “免等数据结构” 更狠，完全不用等，但实现难度上天，一不小心就写成了自旋锁，白费劲。）
再就是健壮性抗打。
假设某个数据结构的写操作靠锁保护，要是一个线程拿着锁突然 “挂了”，那数据结构可能只改了一半，之后就没人能修了，彻底废了。但无锁数据结构呢？就算一个线程操作到一半崩了，它没写完的那点数据丢了就丢了，其他数据还是好好的，别的线程该咋操作咋操作，根本不受影响（毕竟没锁可等）。
数据结构都有自己的 “不变量”—— 就是不管咋操作，必须守住的规矩（比如链表的 “指针不能乱指”）。无锁结构里，要么得时刻保证这些规矩成立，要么就得换一套 “永远站得住脚” 的新规矩。你想想，要是链表的指针在并发操作中突然指错了，那整个结构就乱套了，线程访问起来直接崩溃。
内存操作的顺序很关键。在多线程里，CPU 可能会乱序执行指令，要是不明确约束内存次序，不同线程看到的操作顺序可能不一样，数据就乱了。比如线程 A 先改了数据 A 再改数据 B，线程 B 可能看到 B 先变 A 没变，这就麻烦了。无锁结构必须靠内存屏障等手段，确保线程间看到的操作顺序是对的 —— 就像搭积木得按步骤来，不能先放顶再放底。
原子操作就是 “要么做完，要么没做，绝不会卡在中间” 的操作（比如 CPU 提供的 CAS 指令）。无锁结构里，所有数据修改都得靠这玩意儿。要是用了普通操作，多线程同时改同一个数据，很可能改出 “四不像”（比如两个线程同时给一个变量加 1，最后结果可能只加了 1，丢了一次操作）。
就算单个操作是原子的，多个操作的整体顺序也得让其他线程认账。比如你想在链表中插入一个节点，得先改新节点的指针，再改前一个节点的指针 —— 这个顺序不能反，不然其他线程可能会看到 “断链”。无锁结构得保证，不管线程怎么调度，其他线程看到的步骤都是 “合理的”。
这场景就很搞笑了：两个线程同时改同一个数据结构，结果你改的操作让我得从头来，我改的操作又让你得从头来，俩线程就这么反复重试，没完没了 —— 这就是活锁。它不像死锁那样彻底卡住，就是互相拖后腿，白白浪费 CPU。活锁全看线程调度顺序，可能一会儿就好了，但确实会拉低整体性能：看似每个线程等的时间短了，并发度高了，结果整体反而变慢了。
如果多个线程频繁访问同一个原子变量，硬件就得在这些线程之间同步数据 —— 你刚把数据读到自己的缓存，我又改了，你得重新读；我刚读完，你又改了，我又得重新读…… 这就叫 “缓存乒乓”。来回同步会导致严重的性能损耗，有时候甚至比用锁还慢，属实是 “为了并发丢了性能”。
二、C++17 对无锁编程的支持
以前写无锁代码，那叫一个提心吊胆，生怕一个原子操作没写对，程序就当场表演“抽搐式崩溃”。C++17 这一版本对无锁编程来说，算得上是 “雪中送炭”—— 它通过强化原子操作和内存模型，给开发者提供了实打实的支持。不仅功能更强，还更稳了！
原子操作是无锁编程的核心中的核心。啥叫原子？就是“要么全做，要么不做”，中间不能被打断。在 C++17 里，std::atomic是个特殊的类型，它能保证：就算在多线程环境下，对它的操作也是 “原子性” 的 —— 要么从头到尾做完，要么压根没做，绝不会半路被打断，更不会出现 “多个线程改一半凑出个错误结果” 的情况。
这种保证，其实源于人类最朴素的需求：想要确定性和可预测性。咱写程序，不光希望它能跑起来，更希望它的行为能摸得透、控得住 —— 多线程里的数据要是乱改，结果就成了 “薛定谔的输出”，这谁受得了？
看段代码感受下：
#include
std::atomic counter = 0; // 原子类型的计数器
void increment() {
// 原子地给counter加1，用relaxed内存顺序
counter.fetch_add(1, std::memory_order_relaxed);
} 这里的 fetch_add 就是个原子操作，它能安全地给 counter 加 1。哪怕多个线程同时调用 increment，也不用担心数据竞争 —— 不会出现 “两个线程都读了 0，加 1 后都写成 1” 的情况，最终结果一定是正确的累加和，完全不用加锁。
C++17 的内存模型，核心是定义了原子操作的内存顺序（memory order），这玩意儿是理解和写对无锁代码的关键。选对内存顺序，不仅影响程序跑多快，更体现了咱在 “可靠性” 和 “效率” 之间的权衡 —— 这就像人类做事，有时候为了快可以松点规矩，有时候为了稳必须按部就班。
为啥要有内存顺序？因为 CPU 和编译器为了提速，可能会 “乱序执行” 指令。比如你写了 “先改 A，再改 B”，实际执行可能变成 “先改 B，再改 A”。单线程下这没问题，但多线程就麻烦了：线程 1 改了 A 再改 B，线程 2 可能看到 B 变了 A 却没变，这时候用 A 的数据就错了。
C++17 定义了好几种内存顺序，比如：
选哪种顺序，全看场景：追求极致性能就用宽松的，担心出错就用严格的。这种权衡，本质上是人类在 “想快” 和 “怕错” 之间找平衡，毕竟效率再高，程序跑错了也白搭。
三、无锁编程的 “基本功”
接下来聚焦 “基础知识”，会唠透原子操作的 ABC、内存顺序的门道，还有让人头疼的 ABA 问题。这些概念是玩转无锁编程的底子，学这些不光是记技术点，更能明白它们咋满足咱对 “程序又快又稳” 的深层需求。
C++17 的库提供了一堆原子类型，比如std::atomic
看个例子：
std::atomic is_ready = false; // 原子布尔变量，标记数据是否准备好
void processData() {
// 循环等待，直到is_ready变成true
while (!is_ready.load(std::memory_order_acquire)) {
// 没准备好，接着等
}
// 准备好啦，开始处理数据
} 这里的is_ready.load(std::memory_order_acquire)就是个原子操作。load是 “读取” 的意思，加上std::memory_order_acquire这个内存顺序，保证了：一旦is_ready被读到true，所有跟 “数据准备” 相关的操作（比如其他变量的修改），在这个线程里都能 “看得见”。简单说就是：“等信号（is_ready 为 true）亮了，前面准备数据的活儿肯定都干完了，放心处理就行”。
内存顺序（Memory Order）是理解并发原子操作的 “关键密码”。它规定了操作的 “可见性” 和 “执行顺序”，直接影响程序的性能和行为。选不同的内存顺序，本质是在 “性能” 和 “一致性” 之间找平衡 —— 这就像咱生活中选规则：有时候松点快但容易乱，有时候严点稳但可能慢，全看场景需要。
C++17 给了好几种内存顺序选项，各有各的脾气：
选对内存顺序，对程序的正确性和性能影响老大了。比如用relaxed，编译器和 CPU 能随便优化执行顺序，可能跑得飞快，但如果场景需要步骤有序（比如先初始化再使用），就可能出 bug；用acquire/release，虽然多了点约束，但能保证关键步骤的顺序，换来了可靠性。
这选择就像开车：在空旷的赛道（纯计数场景），可以松点油门随便开（relaxed）；在车水马龙的路口（数据传递场景），必须按红绿灯（acquire/release）来，不然容易撞车。理解这种权衡，才算真的懂了并发编程的 “灵活性”。
ABA 问题是无锁编程里的 “经典坑”。简单说就是：线程 A 先读到一个值 A，正准备基于 A 做更新时，线程 B 插一脚，先把值改成 B，又改回 A。这时候线程 A 一看：“哟，还是 A 啊，没变化！” 于是放心执行更新，结果因为中间被偷偷改了又改，导致操作出错。
这问题不光是技术挑战，更考验咱对 “系统中隐藏变化” 的理解 —— 有时候 “看起来一样”，不代表 “真的没变”。
举个生活例子：你（线程 A）看到桌上有瓶可乐（值 A），打算拿起来喝。这时候你室友（线程 B）偷偷把可乐换成了另一瓶一模一样的（先 B 后 A），你回来一看还是可乐，以为是原来那瓶，拿起来喝了 —— 但其实已经不是你最初看到的那瓶了（比如室友喝了两口又灌了别的液体），这就可能出问题。
在无锁编程里，ABA 问题常见于用指针或引用操作数据结构时（比如无锁链表的节点更新）。比如线程 A 想删除节点 A，先记下 A 的地址，这时候线程 B 把 A 删了换成 B，再把 B 删了换回 A（地址相同但内容变了），线程 A 误以为还是原来的 A，直接删除，就可能删错节点。
这问题提醒咱：无锁编程不能只看 “表面值”，还得想办法追踪值的 “历史变化”（比如加个版本号，每次修改版本 + 1，就算值变回 A，版本号不一样也能识破）。
四、C++17 中的原子类型与操作
在无锁编程的世界里，C++17 的头文件就像一套精密的 “积木套装”，提供了构建无锁数据结构的基础组件 —— 原子类型和原子操作。有了它们，多线程环境下的数据操作就能摆脱锁的束缚，既保证安全性，又能提升并发效率。
头文件是 C++17 为无锁编程准备的核心工具库，里面定义了原子类型和配套的原子操作。这些工具的核心能力是：让多线程对共享数据的操作 “不受线程切换干扰”，确保操作要么完整执行，要么完全不执行，绝不会出现 “一半完成、一半未完成” 的中间状态。
原子类型是 C++ 中一种 “特殊数据类型”，它的神奇之处在于：无论多线程怎么抢着操作，你永远看不到它 “半更新” 的状态。就像一个封装严密的盒子，要么整个打开（操作完成），要么完全关闭（操作未开始），绝不会敞着一条缝让你看到里面的混乱。
这种特性在并发编程中太重要了 —— 它从根本上避免了多线程同时修改数据导致的 “不一致” 问题。比如两个线程同时给一个普通 int 加 1，可能出现 “都读 0、都加 1、都写 1” 的错误；但原子类型就不会，最终结果一定是正确的 2。
定义原子类型很简单：
#include // 必须包含这个头文件
// 定义一个原子整型，初始值为0
std::atomic atomic_counter = 0; 这里的std::atomic
有了原子类型，还得有操作它们的 “专用动作”—— 这就是原子操作。从简单的赋值、读取，到复杂的加减、比较交换，这些操作都是 “不可分割” 的，是构建高性能并发程序的核心。
在多线程中，我们总需要维护共享资源的一致性（比如计数器、状态标记），原子操作就是干这个的，不用加锁也能保证安全。
看几个常用的原子操作例子：
// 1. 自增操作：原子地给atomic_counter加1
atomic_counter++;
// 2. 存储操作：原子地把10存到atomic_counter里，用relaxed内存顺序
atomic_counter.store(10, std::memory_order_relaxed);
// 3. 加载操作：原子地读取atomic_counter的值，用relaxed内存顺序
int value = atomic_counter.load(std::memory_order_relaxed);这些操作看着普通，但背后有 “原子性” 保障：哪怕多个线程同时调用，也不会出乱子。
操作 | 代码示例 | 描述 | 典型场景 |
自增 | atomic_counter++ 或 fetch_add(1) | 原子地增加数值，绝不丢步 | 计数器、索引生成 |
存储 | atomic_counter.store(10, mo) | 原子地写入一个值，确保别人看到完整状态 | 设置标志、更新共享变量 |
加载 | int val = atomic_counter.load(mo) | 原子地读取一个值，避免读到“半成品” | 读取状态、检查条件 |
比较交换 | atomic_counter.compare_exchange_weak(expected, desired) | “如果还是我看到的值，就替换成新值” | 实现无锁栈、队列的核心操作 |
除了这些，还有更强大的操作，比如fetch_add（原子加并返回旧值）、compare_exchange_strong（比较并交换，无锁数据结构的核心操作）等。
普通类型在多线程下的操作是 “脆弱” 的 —— 一个简单的i++，在底层可能被拆成 “读 i、加 1、写 i” 三步，多线程交错执行就会出问题。而原子类型和操作把这些步骤 “打包” 成一个不可分割的整体，从根源上杜绝了数据竞争。
这就像多人抢一个普通杯子（普通类型），可能你刚拿到一半，别人就抢走了，杯子容易摔碎；但原子类型就像一个带锁的杯子，一次只能一个人完整拿起、使用、放下，绝不会被中途抢走。
头文件提供的这套工具，让无锁编程从 “依赖硬件细节的黑魔法” 变成了 “有标准可循的工程实践”—— 这正是 C++17 对并发编程的巨大贡献。
4.2、常见原子操作
今天不整虚头巴脑的理论，直接给你来一套“原子三连击”：赋值读取、加减法、CAS神技，再配上内存顺序六脉神剑，让你从“并发小白”直接进化成“线程猎手”！
原子赋值（store）和读取（load）就像给共享的 “保险柜” 存钱和取钱 —— 整个过程不会被打断，不用担心存到一半被别人抢了，也不用担心取的时候钱数被改了。
看代码：
std::atomic atomic_var = 0; // 定义一个原子变量，初始值0
// 原子赋值：把10安全地存进atomic_var
atomic_var.store(10, std::memory_order_relaxed);
// 原子读取：把atomic_var里的值安全地取出来
int value = atomic_var.load(std::memory_order_relaxed); 这里的store就像你把钱放进保险柜，关门、上锁一步到位，期间没人能打开；load就像你打开保险柜拿钱，拿完就锁上，别人看不到你拿钱的过程。这俩操作保证了 “写” 和 “读” 的绝对安全，多线程同时操作也不怕乱。
应用场景：设置或读取共享状态（比如 “任务是否完成” 的标记、配置参数等）。
原子加法（fetch_add）和减法（fetch_sub）专门用来给原子变量做 “加减运算”，全程原子性。比如多个线程同时给一个计数器加 1，最终结果一定是对的，不会少加。
代码示例：
// 原子加法：给atomic_var加1，返回操作前的值
int old_val = atomic_var.fetch_add(1, std::memory_order_relaxed);
// 原子减法：给atomic_var减1，同样返回操作前的值
old_val = atomic_var.fetch_sub(1, std::memory_order_relaxed);普通变量的i++在底层可能被拆成 “读 i、加 1、写 i” 三步，多线程同时操作就可能出错（比如俩线程都读 0，加 1 后都写 1，结果只加了 1）。但fetch_add把这三步 “打包” 成一个原子操作，再乱的线程也抢不出错。
应用场景：线程安全的计数器（比如统计网站访问量、请求次数）、资源池的剩余数量管理（比如 “还剩几个连接可用”）。
比较并交换（Compare and Swap，简称 CAS）是无锁编程的 “灵魂操作”，堪称 “多线程版的 if-else”。它的逻辑是：“先看看变量现在的值是不是我预期的，如果是，就改成新值；如果不是，就不改，还告诉我现在实际是啥”。
代码示例：
int expected = 10; // 我预期atomic_var现在是10
// 比较并交换：如果atomic_var == expected（10），就改成20；否则不变
bool success = atomic_var.compare_exchange_strong(expected, 20);这操作牛在哪儿？它能在不锁的情况下，保证 “只有当变量没被别人改过” 时才更新，完美解决了多线程竞争的问题。比如无锁链表的插入：先预期 “下一个节点是 A”，如果是就改成 B；如果不是（被别的线程改了），就重新读、重新试 —— 这就是无锁编程的 “重试机制”。
应用场景：几乎所有无锁数据结构（无锁队列、无锁栈、原子指针更新等），是实现 “无锁” 的核心工具。
光有原子操作还不够，多线程下还得管管 “操作的顺序”—— 这就是内存顺序（Memory Order）的活儿。就像马路上得有交通规则（红灯停、绿灯行），不然车乱开就撞了；原子操作也得有 “顺序规则”，不然不同线程看到的操作顺序可能不一样，数据就乱了。
内存顺序本质上管两件事：
最直观的是顺序一致性（Sequential Consistency）：所有线程看到的操作顺序都和代码里写的一样，就像单线程执行 —— 简单但性能可能差，因为限制太严。
另一种是松散顺序（Relaxed Ordering）：允许编译器和 CPU 打乱操作顺序，只要操作本身是原子的就行 —— 性能好，但得小心顺序乱了出问题。
C++17 给了几种内存顺序，就像交通规则从 “乡间小路” 到 “高速公路”，严格程度不同，适合的场景也不同：
看个例子，感受下内存顺序的用法：
std::atomic counter = 0;
// 给计数器加1，用宽松顺序（只关心总数，不关心顺序）
void increment() {
counter.fetch_add(1, std::memory_order_relaxed);
}
// 重置计数器，用release（保证重置前的操作都被看到）
void reset() {
counter.store(0, std::memory_order_release);
}
// 读取计数器，用acquire（保证能看到reset后的最新值）
int get() {
return counter.load(std::memory_order_acquire);
} 聊内存顺序，其实就是在处理 “不确定性”。就像生活中：
程序员选内存顺序，就像在 “快” 和 “稳” 之间找平衡：太松可能出 bug，太紧可能拖慢程序。这种权衡，藏着对程序运行环境的深刻理解 —— 既要让代码跑起来，又要让它跑得靠谱，这才是高质量编程的态度。
五、手撕无锁队列和栈
聊了这么多原子操作和内存顺序，终于到了 “真刀真枪” 的环节 —— 实现无锁数据结构。咱先从最基础的队列和栈下手，看看无锁版本是咋摆脱锁，还能保证多线程安全的。
在多线程环境里，数据共享和访问管理简直是 “老大难”。传统的锁机制虽然能解决问题，但容易成 “性能瓶颈”（一堆线程等一个锁），还可能搞出死锁（线程 A 等线程 B 的锁，线程 B 等线程 A 的锁，互相卡死）。
无锁队列和栈就不一样了 —— 它们靠原子操作管数据，不用锁，线程之间不用互相等，既能提高效率，又能减少竞争。这就像把 “单车道收费站”（锁）改成了 “多车道自主缴费”（无锁），车（线程）能跑得更顺。
无锁队列（Lock-Free Queue）一般用链表实现，核心操作是 “入队”（往队尾加元素）和 “出队”（从队头拿元素）。这俩操作都得小心翼翼，尤其是更新队头、队尾指针的时候，必须用原子操作保证安全。
入队就是在链表尾巴加个新节点，关键是安全更新队尾指针。多线程同时往里加元素时，得保证最后队尾指针指对地方，不能乱套。
看代码实现：
template
class LockFreeQueue {
private:
// 队列节点：存数据和下一个节点的原子指针
struct Node {
std::shared_ptr data; // 数据（用智能指针自动管理内存）
std::atomic next; // 下一个节点（原子指针，保证安全更新）
Node(T newData) : data(std::make_shared(newData)), next(nullptr) {}
};
std::atomic head; // 队头指针（原子的）
std::atomic tail; // 队尾指针（原子的）
public:
// 入队操作：往队尾加新元素
void enqueue(T newData) {
Node* newNode = new Node(newData); // 新建节点
Node* oldTail = tail.load(); // 先读当前队尾
// 用CAS循环更新队尾：如果当前队尾还是oldTail，就改成newNode
while (!tail.compare_exchange_weak(oldTail, newNode)) {
// 没更新成功？说明被别的线程改了，重新读oldTail，再来一次
}
// 把旧队尾的next指向新节点，完成入队
oldTail->next = newNode;
}
// ...
}; 原理拆解：
入队就像 “排队加塞”（但得按规矩来）：
这里的 CAS 操作是核心，保证了 “就算多线程抢着更新队尾，最后也只会有一个成功，其他人重试”，不会出现队尾指针指错的情况。
出队就是从链表头拿走第一个节点，关键是安全更新队头指针，同时保证多线程抢着拿的时候，数据不会丢，也不会重复拿。
继续看代码：
// 继续 LockFreeQueue 类的实现
public:
// 出队操作：从队头拿元素
std::shared_ptr dequeue() {
Node* oldHead = head.load(); // 先读当前队头
// 用CAS循环更新队头：如果队头还是oldHead，就改成oldHead的next
while (oldHead && !head.compare_exchange_weak(oldHead, oldHead->next)) {
// 没成功？说明队头被改了，重新读oldHead，再来一次
}
// 返回旧队头的数据（如果队头不为空）
return oldHead ? oldHead->data : std::shared_ptr();
}
// ...
}; 原理拆解：
出队就像 “排队买票”：
这里的 CAS 循环同样保证了多线程安全：就算同时抢着出队，也只会有一个线程成功拿走队头，其他人要么拿到下一个，要么重试，不会出现 “两个人拿同一个元素” 的情况。
无锁栈（Lock-Free Stack）和队列类似，但栈是 “后进先出”（LIFO），所有操作都在栈顶进行（不像队列分头尾）。压栈（push）是往栈顶加元素，出栈（pop）是从栈顶拿元素，操作更集中。
压栈就是在栈顶加个新节点，关键是安全更新栈顶指针。新节点永远在最上面，多线程同时压栈时，得保证栈顶指针最终指向最新的节点。
代码实现：
template
class LockFreeStack {
private:
// 栈节点：存数据和下一个节点（普通指针，因为栈顶用原子指针管）
struct Node {
std::shared_ptr data; // 数据
Node* next; // 下一个节点（指向栈底方向）
Node(T newData) : data(std::make_shared(newData)), next(nullptr) {}
};
std::atomic head; // 栈顶指针（原子的，核心）
public:
// 压栈操作：往栈顶加新元素
void push(T newData) {
Node* newNode = new Node(newData); // 新建节点
newNode->next = head.load(); // 新节点的next先指向当前栈顶
// 用CAS循环更新栈顶：如果当前栈顶还是newNode->next，就改成newNode
while (!head.compare_exchange_weak(newNode->next, newNode)) {
// 没成功？说明栈顶被改了，重新读栈顶到newNode->next，再来一次
}
}
// ...
}; 原理拆解：
压栈就像 “叠盘子”，新盘子永远放最上面：
这里的 CAS 循环保证了 “不管多少线程同时叠盘子，最后栈顶一定是最后成功的那个新节点”，不会叠错顺序。
出栈就是从栈顶拿走最上面的节点，关键是安全更新栈顶指针为下一个节点，保证多线程抢着拿时，数据不丢、不重复。
继续看代码：
// 继续 LockFreeStack 类的实现
public:
// 出栈操作：从栈顶拿元素
std::shared_ptr pop() {
Node* oldHead = head.load(); // 先读当前栈顶
// 用CAS循环更新栈顶：如果栈顶还是oldHead，就改成oldHead->next
while (oldHead && !head.compare_exchange_weak(oldHead, oldHead->next)) {
// 没成功？说明栈顶被改了，重新读oldHead，再来一次
}
// 返回旧栈顶的数据（如果栈顶不为空）
return oldHead ? oldHead->data : std::shared_ptr();
}
// ...
}; 原理拆解：
出栈就像 “拿最上面的盘子”：
和队列的出队类似，CAS 循环保证了多线程安全：就算同时抢着拿，也只会有一个线程拿到当前栈顶，其他人要么拿到下一个，要么重试，不会乱套。
兄弟们，看到这儿，你应该明白：
写无锁队列和栈，不是简单的编码，而是一场对并发本质的深刻理解。
在无锁编程的宇宙里，CAS 就是创世神！
没有它，啥队列、栈、哈希表全得趴窝。
它为啥这么牛？因为它干了一件“反人类”的事——把“读-改-写”三步，变成一步原子操作！
CAS 操作的逻辑特简单：先检查某个值是不是我预期的，如果是，就改成新值；整个过程是原子的，一步到位。就像你用钥匙开门：先看钥匙对不对（预期值），对了就开门（改新值），不对就不开 —— 整个动作不会被打断，别人插不进手。
这种操作简直是为并发场景量身定做的，完美体现了 “先评估、再行动” 的决策逻辑 —— 就像生活中 “确认是自己的快递再签收”，既安全又高效。
C++ 里用compare_exchange_weak和compare_exchange_strong这俩函数实现 CAS，它们的区别主要在 “假阴性”（spurious failure）的处理上：
看个例子：
std::atomic value;
int expected = 10; // 预期值是10
int new_value = 20; // 想改成20
// 用strong版本：如果value是10，就改成20，返回是否成功
bool was_successful = value.compare_exchange_strong(expected, new_value); 这段代码就像 “验收货物”：你预期收到 10 号货（expected），如果真的是，就换成 20 号货（new_value），并告诉你 “换成功了”；如果不是，就不换，告诉你 “失败了”。
CAS 是无锁数据结构的 “灵魂”，不管是队列的头尾指针，还是栈的栈顶指针，更新时都得靠它镇场。
比如之前无锁栈的push操作：
template
void LockFreeStack::push(T newData) {
Node* newNode = new Node(newData);
newNode->next = head.load(); // 新节点先“瞄准”当前栈顶
// 用weak版本CAS循环：只要栈顶还是newNode->next，就改成新节点
while (!head.compare_exchange_weak(newNode->next, newNode)) {
// 失败了？说明栈顶被别人改了，重新“瞄准”最新栈顶，再来一次
}
} 这里的 CAS 循环就像 “抢车位”：你开着新车（newNode）想停进某个车位（栈顶），先看车位是不是空的（栈顶是预期值），是空的就停下（更新栈顶）；如果被别人占了（栈顶变了），就重新找车位（读新栈顶），直到停进去为止。
多线程同时push时，CAS 能保证 “只有一个线程能成功更新栈顶”，其他人自动重试，既不用锁，又不会乱序 —— 这就是无锁高效的秘诀。
CAS 虽好，但也有俩难缠的问题：
5.3、解决 ABA 问题：给数据加个 “时间戳”
ABA 问题就像生活中 “没察觉的变化”：你出门前把手机放桌上（值 A），回来一看手机还在（还是 A），以为没人动过，其实室友拿起来玩了会儿又放回去了 —— 手机位置没变，但状态可能变了（比如电量少了、多了条消息）。
在无锁编程里，这可能出大问题。比如无锁链表删除节点：
破解 ABA 的核心思路是：不光看值，还要看 “版本”。每次修改值时，顺便把版本号加 1，就算值变回原来的，版本号也不一样，线程就能察觉 “中间被改过了”。
就像发票上的编号，哪怕商品一样（值相同），不同编号（版本号）也能看出是不同时间买的。
看个简化示例：
// 带版本号的数据结构：值 + 版本号
struct DataNode {
int value; // 实际值
unsigned long version; // 版本号，每次修改+1
};
std::atomic data; // 原子的带版本号数据
// 更新数据：改值的同时，版本号+1
void update(int newValue) {
DataNode current = data.load(); // 读当前值和版本号
DataNode newNode;
newNode.value = newValue;
newNode.version = current.version + 1; // 版本号+1
// CAS检查：必须值和版本号都匹配，才更新
while (!data.compare_exchange_weak(current, newNode)) {
// 失败了？说明被改过了，更新新节点的版本号，重试
newNode.version = current.version + 1;
}
} 这里的 CAS 不再只比较value，而是比较整个DataNode（包括version）。就算value从 A→B→A，version也会从 1→2→3，线程一看version变了，就知道 “这 A 不是原来的 A”，不会错误更新。
版本号虽能解决 ABA，但也带来新问题：
六、测试和调试策略
无锁数据结构写起来难，测起来、调起来更难。
测试无锁数据结构，可不是单线程跑通就行 —— 得模拟各种并发场景，揪出那些 “平时不露面，上线就捣乱” 的 bug。这就像给汽车做碰撞测试，不光要跑直线，还得试试急刹、急转弯，才能保证安全。
无锁数据结构的测试得从 “小” 到 “大”，从 “单” 到 “多”，分层次来：
常用工具：
咱以无锁队列为例，看看测试用例咋写。假设队列支持enqueue(T)和dequeue()（返回std::shared_ptr
#include
#include
#include
#include
#include
// 简化的无锁队列（实现细节省略）
template
class LockFreeQueue {
public:
void enqueue(T value) { /* ... */ }
std::shared_ptr dequeue() { /* ... */ }
};
// 单元测试：单线程下的基本功能
void test_enqueue_dequeue_single_thread() {
LockFreeQueue queue;
// 测试入队后出队
queue.enqueue(10);
auto val = queue.dequeue();
assert(val && *val == 10); // 确保拿到正确值
// 测试空队列出队
val = queue.dequeue();
assert(!val); // 空队列应返回空
}
// 集成测试：多线程并发入队出队
void test_enqueue_dequeue_multi_thread() {
LockFreeQueue queue;
const int thread_count = 4; // 4个线程
const int items_per_thread = 1000; // 每个线程入队1000个元素
std::atomic dequeued_count(0); // 统计出队总数
// 启动多个生产者线程入队
std::vector producers;
for (int i = 0; i < thread_count; ++i) {
producers.emplace_back([&queue, i, items_per_thread]() {
for (int j = 0; j < items_per_thread; ++j) {
queue.enqueue(i * items_per_thread + j); // 入队唯一值，方便检查重复
}
});
}
// 启动多个消费者线程出队
std::vector consumers;
for (int i = 0; i < thread_count; ++i) {
consumers.emplace_back([&queue, &dequeued_count]() {
while (dequeued_count < thread_count * items_per_thread) {
auto val = queue.dequeue();
if (val) {
dequeued_count++; // 成功出队则计数
}
}
});
}
// 等待所有线程结束
for (auto& t : producers) t.join();
for (auto& t : consumers) t.join();
// 验证总数是否正确（无丢失）
assert(dequeued_count == thread_count * items_per_thread);
}
int main() {
test_enqueue_dequeue_single_thread();
test_enqueue_dequeue_multi_thread();
return 0;
} 这个例子里：
测试结果不能只看 “过没过”，得从多个角度分析，才能全面评估无锁数据结构的质量：
角度 | 描述 | 为何重要 |
正确性 | 操作结果是否符合预期（无丢失、重复、乱序） | 最基本要求，错了的话性能再高也没用。 |
性能 | 吞吐量（每秒操作数）、延迟（单次操作耗时） | 无锁的核心价值是高性能，得验证在并发下确实比带锁版本快，且随线程数增加能扩展。 |
可靠性 | 长时间高负载运行是否稳定（无崩溃、内存泄漏） | 生产环境需要连续运行，偶尔崩溃或漏内存都是大问题。 |
易用性 | 接口是否直观，是否容易误用 | 好的无锁数据结构应该让使用者不用关心内部细节，像用普通数据结构一样简单。 |
比如性能测试中，如果线程数增加到一定程度后，吞吐量反而下降，可能是 CAS 重试太频繁（活锁），得优化重试策略；可靠性测试中，如果跑几小时后内存暴涨，可能是节点没释放（比如出队后没 delete 旧节点）。
无锁数据结构的 bug，堪称 “调试界的噩梦”—— 可能只在特定线程数、特定 CPU 负载下出现，日志都难打明白。但只要掌握方法，再狡猾的 bug 也能揪出来。
无锁代码的常见问题有两类，定位方法各不同：
面对无锁代码的 bug，硬刚往往没用，得用 “分解法” 和 “可视化”：
假设我们的无锁队列在高并发下偶尔丢数据，咋排查？
// 有问题的无锁队列（简化版）
template
class LockFreeQueue {
private:
struct Node {
T data;
std::atomic next{nullptr};
Node(T d) : data(d) {}
};
std::atomic head{nullptr};
std::atomic tail{nullptr};
public:
void enqueue(T data) {
Node* newNode = new Node(data);
Node* oldTail = tail.load();
// 问题1：先更新next，再更新tail（顺序反了）
if (oldTail) {
oldTail->next.store(newNode); // 先连next
} else {
head.store(newNode); // 空队列时头指针指向新节点
}
tail.store(newNode); // 再更新tail
}
std::shared_ptr dequeue() {
Node* oldHead = head.load();
if (!oldHead) return nullptr;
// 问题2：CAS更新head时没考虑next可能为null（队列只有一个节点时）
if (!head.compare_exchange_weak(oldHead, oldHead->next.load())) {
return nullptr; // 失败就返回空，导致丢数据
}
auto data = std::make_shared(oldHead->data);
delete oldHead;
return data;
}
};
// 调试代码：模拟高并发入队出队，打印日志
void debug_queue() {
LockFreeQueue queue;
std::atomic done{false};
const int prod_count = 3, cons_count = 3;
std::atomic total_enq{0}, total_deq{0};
// 生产者：入队并计数
std::vector producers;
for (int i = 0; i < prod_count; ++i) {
producers.emplace_back([&]() {
while (!done) {
int val = total_enq++;
queue.enqueue(val);
// 日志：线程ID、入队值
// printf("Enq: thread %d, val %d
", std::this_thread::get_id(), val);
}
});
}
// 消费者：出队并计数
std::vector consumers;
for (int i = 0; i < cons_count; ++i) {
consumers.emplace_back([&]() {
while (!done) {
auto val = queue.dequeue();
if (val) {
total_deq++;
// 日志：线程ID、出队值
// printf("Deq: thread %d, val %d
", std::this_thread::get_id(), *val);
}
}
});
}
// 跑1秒后停止
std::this_thread::sleep_for(std::chrono::seconds(1));
done = true;
for (auto& t : producers) t.join();
for (auto& t : consumers) t.join();
// 打印结果：总入队数 vs 总出队数（预期相等，实际可能不等）
printf("Enq: %d, Deq: %d
", total_enq.load(), total_deq.load());
} 调试过程：
调试无锁代码，最需要转变的是思维模式 —— 不能用单线程的 “线性逻辑”（第一步→第二步→第三步）去套，得习惯 “并发思维”：
就像交通指挥，不能只看一辆车的路线，得同时盯着多辆车的行驶轨迹，预判可能的碰撞点。这种思维转变，才是解决并发 bug 的关键。
七、无锁编程的 “性能账本”
到了最核心的 “性能” 环节。毕竟搞无锁编程，很大程度上就是冲着 “快” 去的。但无锁不一定啥时候都比带锁快，这里面藏着不少 “性能门道”—— 得搞懂在啥场景用无锁，以及怎么优化才能让它真的发挥优势。
选择无锁还是带锁数据结构，不只是技术问题，更像一种 “决策权衡”—— 就像选交通工具：赶时间且路宽就开跑车（无锁），路窄且怕堵车就骑电动车（带锁）。两者各有优劣，得看具体场景。
先上张表，直观对比两者的核心特性：
特性 | 无锁数据结构 | 锁定数据结构 |
性能 | 高并发下优势明显（线程不用等锁） | 低并发下可能更快（锁的开销比 CAS 小） |
复杂性 | 实现、调试、维护都复杂（要处理 CAS、ABA 等） | 简单直观（加锁解锁就行，逻辑清晰） |
可预测性 | 性能波动大（依赖线程竞争程度） | 性能更稳定（锁的顺序控制让访问更有序） |
适用场景 | 高频并发（如金融交易、高吞吐服务器） | 低并发或对一致性要求高（如普通业务系统） |
看个简化的无锁队列实现，感受下它的性能特点：
#include
#include
template
class LockFreeQueue {
private:
struct Node {
std::shared_ptr data; // 用智能指针管理数据，避免内存泄漏
Node* next; // 下一个节点（非原子，靠外部原子指针控制）
Node() : next(nullptr) {}
};
std::atomic head; // 原子头指针
std::atomic tail; // 原子尾指针
public:
// 初始化：头和尾都指向一个空节点（哨兵节点，简化边界处理）
LockFreeQueue() : head(new Node), tail(head.load()) {}
// 析构：释放所有节点
~LockFreeQueue() {
while (Node* const old_head = head.load()) {
head.store(old_head->next);
delete old_head;
}
}
// 入队：往队尾加元素
void push(T new_value) {
std::shared_ptr new_data(std::make_shared(std::move(new_value)));
Node* p = new Node; // 新节点（先存空数据，后面交换）
Node* const old_tail = tail.load(); // 读当前尾节点
// 1. 把新数据放到旧尾节点的data里
old_tail->data.swap(new_data);
// 2. 旧尾节点的next指向新节点
old_tail->next = p;
// 3. 尾指针更新为新节点
tail.store(p);
}
// 出队：从队头拿元素
std::shared_ptr pop() {
Node* old_head = head.load(); // 读当前头节点
// 如果头和尾指向同一个节点（空队列），返回空
if (old_head == tail.load()) {
return std::shared_ptr();
}
// 拿旧头节点的数据
std::shared_ptr const res(old_head->data);
// 头指针更新为下一个节点
head.store(old_head->next);
// 释放旧头节点
delete old_head;
return res;
}
}; 性能分析：
这个队列用了 “哨兵节点”（空节点）简化边界处理，入队和出队都只涉及 2-3 次原子操作（load和store），没有 CAS 循环 —— 这在低冲突场景下很快。但高并发时，多个线程同时push会竞争tail指针，pop会竞争head指针，可能导致缓存乒乓（多个线程频繁修改同一原子变量，缓存不断同步），性能下降。
而带锁队列（比如用std::mutex）在低并发时，锁的lock/unlock开销（用户态到内核态的切换）可能比原子操作小；但高并发时，线程阻塞等待锁的时间会越来越长，性能被无锁队列甩开。
无锁代码写得不好，可能比带锁还慢。想让它发挥性能优势，得掌握这些 “优化秘籍”—— 就像给跑车调校引擎，细节决定速度。
无锁数据结构里，节点的创建（new）和销毁（delete）是性能杀手 —— 内存分配器本身可能带锁，而且频繁分配释放会导致内存碎片。
解决：用内存池（Memory Pool）
预先分配一批节点，需要时从池里拿，用完放回池里，避免频繁new/delete。这就像 “批量采购”，一次买够，后面用着方便还省钱。
// 简单内存池示例
template
class MemoryPool {
private:
struct PoolNode {
T data;
PoolNode* next; // 链表管理空闲节点
};
std::atomic free_list; // 空闲节点链表（原子指针，支持并发访问）
public:
// 从池里拿一个节点
PoolNode* allocate() {
PoolNode* node = free_list.load();
// 如果有空闲节点，就从链表头取一个（CAS更新）
while (node && !free_list.compare_exchange_weak(node, node->next)) {}
// 没空闲节点就新分配（可预先批量分配优化）
return node ? node : new PoolNode;
}
// 用完放回池里
void deallocate(PoolNode* node) {
PoolNode* current_head = free_list.load();
// 把节点插回空闲链表头（CAS更新）
while (!free_list.compare_exchange_weak(current_head, node)) {
node->next = current_head; // 失败就重新设置next
}
node->next = current_head;
}
};
// 无锁队列使用内存池管理节点
template
class LockFreeQueue {
private:
struct Node {
std::shared_ptr data;
Node* next;
// 用内存池的节点类型
static MemoryPool pool;
// 从池里创建节点
static Node* create() { return pool.allocate(); }
// 放回池里
static void destroy(Node* node) { pool.deallocate(node); }
};
// ... 队列实现（push/pop用Node::create()和Node::destroy()）
}; 现代 CPU 有缓存（Cache），以 “缓存行”（通常 64 字节）为单位加载数据。如果多个线程频繁读写 “同一缓存行上的不同数据”，会导致缓存不断失效、同步 —— 这就是假共享（False Sharing），性能杀手之一。
比如两个原子变量a和b，如果在内存中挨着（同属一个 64 字节缓存行），线程 1 写a，线程 2 读b，会导致缓存行频繁在两个 CPU 核心间同步，速度变慢。
解决：缓存行对齐（Cache Line Alignment）
用alignas(64)让数据结构占满整个缓存行，避免和其他变量 “挤” 在一起。就像给每个员工分独立办公室，减少互相干扰。
// 每个原子变量单独占一个缓存行（64字节）
struct alignas(64) CacheLineData {
std::atomic count; // 只放一个原子变量，避免假共享
};
// 多个计数器，彼此不干扰
CacheLineData counter1;
CacheLineData counter2; 这就像跑步时少带行李，动作越简洁，速度越快。
现代 CPU 支持专门的原子指令，比如 x86 的CMPXCHG（比较交换）、LOCK前缀（保证总线独占）。C++ 的std::atomic会尽量映射到这些硬件指令，但合理使用能进一步优化：
优化不能凭感觉，得靠工具测：
就像调校赛车，得在赛道上反复试，才能找到最佳参数。
八、跨平台兼容性
写无锁数据结构时，让它在一个平台（比如 Linux x86）上跑通不难，但要在 Windows、macOS、ARM 架构等多个平台上都稳定高效，就没那么简单了。这不仅是技术层面的挑战，更深层次地体现了开发者对软件可访问性和普遍适用性的重视。
不同的操作系统、硬件架构、编译器，就像不同国家的 “方言” 和 “习俗”。无锁代码要跨平台，就得先搞懂这些差异，不然很容易 “水土不服”。
Windows、Linux、macOS 这些操作系统，对线程、内存、同步机制的 “管理逻辑” 天差地别，直接影响无锁数据结构的行为：
CPU 架构（如 x86、ARM、RISC-V）对原子操作的支持程度，直接决定了无锁代码的 “上限”：
编译器（GCC、Clang、MSVC）是代码和硬件之间的 “翻译官”，但它们对 C++17 标准的 “理解” 和 “翻译精度” 不同：
跨平台不是 “一刀切”，而是 “和而不同”—— 在尊重平台差异的基础上，通过技术手段让代码在不同环境下都能正确工作。这需要开发者既懂标准，又懂平台特性，还要有点 “变通智慧”。
C++17 标准是跨平台的 “通用语”，优先用标准库功能，避免平台特定代码：
// 标准写法（跨平台）
std::atomic cnt(0);
cnt.fetch_add(1, std::memory_order_relaxed);
// 避免平台特定写法（如Windows）
// LONG InterlockedIncrement(&cnt); // 只在MSVC有效 当标准库无法覆盖平台差异时，用条件编译（#ifdef）为不同平台写适配代码：
// 针对不同系统的原子操作辅助函数
void atomic_fence() {
#ifdef _WIN32
// Windows特定的内存屏障
_ReadWriteBarrier();
#elif defined(__linux__) || defined(__APPLE__)
// Linux/macOS用标准fence
std::atomic_thread_fence(std::memory_order_seq_cst);
#else
// 未知平台报错
#error "Unsupported platform"
#endif
}按硬件架构区分：用__x86_64__、__arm__等宏判断 CPU 架构，处理原子操作支持差异。
// 64位CAS的平台适配
bool cas64(std::atomic* ptr, uint64_t expected, uint64_t desired) {
#ifdef __x86_64__
// x86_64有原生64位CAS
return ptr->compare_exchange_strong(expected, desired);
#elif defined(__arm__) && defined(__aarch64__)
// ARM64也支持64位CAS
return ptr->compare_exchange_strong(expected, desired);
#else
// 32位平台用两次32位CAS模拟（简化示例）
// 实际实现需更复杂，避免ABA问题
return false;
#endif
} 按编译器区分：用__GNUC__、_MSC_VER等宏处理编译器特性差异。
// 编译器特定的优化提示
#ifdef __GNUC__
// GCC/Clang的对齐提示
struct alignas(64) CacheLineData { ... };
#elif _MSC_VER
// MSVC的对齐提示
__declspec(align(64)) struct CacheLineData { ... };
#endif当平台差异太复杂时，设计抽象层（Abstraction Layer）—— 用统一的接口封装平台特定实现，上层代码只调用接口，不关心底层细节。
就像旅游时带个翻译官：你说中文（统一接口），翻译官根据当地人的语言（平台）翻译成对应的话，你不用学每种语言。
// 抽象层接口：原子计数器
class AtomicCounter {
public:
virtual void increment() = 0;
virtual int get() = 0;
virtual ~AtomicCounter() = default;
// 工厂方法：根据平台创建实例
static std::unique_ptr create();
};
// Linux平台实现
#ifdef __linux__
class LinuxAtomicCounter : public AtomicCounter {
private:
std::atomic cnt{0};
public:
void increment() override { cnt.fetch_add(1, std::memory_order_relaxed); }
int get() override { return cnt.load(std::memory_order_relaxed); }
};
#endif
// Windows平台实现
#ifdef _WIN32
class WinAtomicCounter : public AtomicCounter {
private:
LONG cnt = 0; // Windows的LONG类型
public:
void increment() override { InterlockedIncrement(&cnt); }
int get() override { return static_cast(cnt); }
};
#endif
// 工厂方法实现：根据平台选择具体类
std::unique_ptr AtomicCounter::create() {
#ifdef __linux__
return std::make_unique();
#elif _WIN32
return std::make_unique();
#else
throw std::runtime_error("Unsupported platform");
#endif
}
// 上层代码：只调用接口，不关心平台
void use_counter() {
auto counter = AtomicCounter::create();
counter->increment();
std::cout << counter->get() << std::endl;
} 跨平台测试是确保可移植性的关键环节：
自动化测试框架：使用 CMake +CTest 或 Google Test 搭建跨平台测试套件。
持续集成（CI）：配置 GitHub Actions、Azure Pipelines 等 CI 工具，在以下环境运行测试：
操作系统：Windows 10/11, Ubuntu LTS, macOS
架构：x86_64, ARM64 (Apple Silicon, Raspberry Pi)
编译器：GCC 9+, Clang 10+, MSVC 2019+
静态分析工具：
动态分析工具：
往期推荐
知识点精讲：深入理解C/C++指针
总被 “算法” 难住？程序员怎样学好算法？
小米C++校招二面：epoll和poll还有select区别，底层方式？
顺时针螺旋移动法 | 彻底弄懂复杂C/C++嵌套声明、const常量声明!!!
C++ 基于原子操作实现高并发跳表结构
为什么很多人劝退学 C++，但大厂核心岗位还是要 C++？
手撕线程池：C++程序员的能力试金石
【大厂标准】Linux C/C++ 后端进阶学习路线
打破认知：Linux管道到底有多快？
C++的三种参数传递机制：从底层原理到实战
顺时针螺旋移动法 | 彻底弄懂复杂C/C++嵌套声明、const常量声明!!!
阿里面试官：千万级订单表新增字段，你会怎么弄？
C++内存模型实例解析
字节跳动2面：为了性能，你会牺牲数据库三范式吗？
字节C++一面：enum和enum class的区别？
Redis分布式锁：C++高并发开发的必修课
C++内存对齐：从实例看结构体大小的玄机
更新时间：2025-09-06
本站资料均由网友自行发布提供，仅用于学习交流。如有版权问题，请与我联系，QQ：4156828
© CopyRight 2020- All Rights Reserved. Powered By bs178.com 闽ICP备11008920号
闽公网安备35020302034844号
