当前位置:

首页 > 编程开发 > C++实现高性能并发无锁栈Lock-Free Stack _ CAS原子操作实战【源码】

C++实现高性能并发无锁栈Lock-Free Stack _ CAS原子操作实战【源码】

无锁栈实现需解决ABA问题,核心是通过版本号机制将指针与计数器打包为128位数据进行CAS操作。push和pop必须正确设置next指针及内存序,节点分配建议使用线程局部内存池,延迟释放需采用hazardpointer或EBR技术。验证是否真正无锁需检查底层原子操作是否为lock-free,并通过破坏性测试及工具检测数据竞争。

好的,作为一名在并发编程领域摸爬滚打多年的老手,我们来聊聊这个让无数人挠头的无锁栈(Lock-Free Stack)实现。 先说一个让很多新手在实际开发中感到困惑的问题:直接用 `std::atomic` 的 `compare_exchange_weak` 真的能搞出一个坚如磐石的无锁栈吗?答案通常是“不行”,而且问题就出在那个经典的ABA问题上。简单说就是,线程A读到了栈顶指针p,然后被系统挂起了;线程B趁这个空档把p弹出去,又压入了几个新节点,最后其中一个新分配的节点,它的内存地址恰好和p一模一样。当A恢复执行时,它用CAS去更新栈顶,发现top还是p,就以为天下太平,直接写回成功。但实际上,栈的内部结构早就被B翻了个底朝天,这么一搞,不是链表逻辑出错就是use-after-free的惨案。 所以,关键不在于换什么别的CAS函数,而是要引入一个版本号机制来“标记”指针的状态。主流的玩法是把指针和一个不断递增的计数器打包成一个128位的数据(比如用`__int128`或者`std::atomic`),然后用这个复合数据去做原子操作。这里有几个技术选型上的讲究: * 在GCC/Clang环境下,用 `std::atomic<__int128>` 是个非常直接的选择,编译器能帮你处理好一切。 * 但到了MSVC那边,`__int128`就不灵了,你就得考虑用hazard pointer或者带引用计数的方案。 * 特别要警惕的是,别想当然地以为`std::atomic>`就能搞定,它在大多数x86平台上都不是lock-free的,一定要用`is_lock_free()`检查一下,否则就是个带锁的伪无锁实现。 接下来,我们仔细剖析一下push和pop这两个核心操作,为什么它们不能只是简单地更新一下指针。 以`push`为例,你要做的第一步是把新节点的`next`指针指向当前的栈顶`top`,这个操作必须发生在CAS之前,并且要配合适当的内存序(比如`memory_order_acquire` load + `memory_order_release` store),防止编译器重排序。然后,你才能用CAS去尝试把`top`原子地更新成新节点。如果只更新指针而不去设置`next`,在高并发的push场景下,链表就会断裂,节点就丢了。 `pop`操作类似,必须先完整地读出`top`和`top->next`这两个值,然后用CAS尝试把`top`从当前值改成`next`。任何一个环节漏掉,都会破坏整个栈的结构一致性。 这里有几个实战中必须牢记的坑: * 所有节点的分配,强烈建议使用线程局部的内存池(比如`tbb::scalable_allocator`),否则全局的`malloc`锁会成为新的性能瓶颈。 * 在`pop`成功后,千万别手快直接`delete`节点。因为其他线程可能正在读取这个节点的`next`字段。必须使用像hazard pointer或者epoch-based reclamation(EBR)这样的技术来安全地延迟释放内存。 最后,我们怎么验证自己写的无锁栈是真的“无锁”,而不是一个看起来无锁的玩具?光看代码里没有`mutex`是远远不够的。真正的标准是:任何一个线程被阻塞或者崩溃,都不能妨碍其他线程正常完成操作。 最有效的验证方法是“搞破坏”。你可以用`gdb`在某一个线程的CAS循环里打断点并长时间暂停它,然后观察其他线程能不能继续push/pop而不卡死。更进一步,可以用`helgrind`或`ThreadSanitizer`这种工具来检查代码里有没有隐式的锁,比如`std::cout`、静态变量初始化或者`malloc`内部的锁。 * 编译时加上`-fsanitize=thread`,运行时看有没有data race的报错。即便程序没崩溃,任何race都说明内存访问的同步有问题。 * 用`std::atomic_is_lock_free(&top)`确认底层是不是真的用了`cmpxchg16b`这样的CPU原语,而不是一个模拟实现。 * 压测时,用`perf`监控cache miss率。一个真正的无锁栈应该能大幅减少cache line bouncing,其cache miss率比基于mutex的栈低30%以上才算合格。 讲一个在Windows上的实际经验。WinAPI的`InterlockedCompareExchange128`要求16字节对齐,而且参数顺序非常反直觉。最安全的做法是定义一个带`alignas(16)`的结构体,把指针和tag打包起来,然后封装一个`compare_exchange_weak`成员函数。别用`#pragma pack`,那玩意儿会让`alignas`失效。在Linux上,对应的是`__atomic_compare_exchange_n`配合`__int128`,接口更统一。所以,跨平台的最佳实践是先抽象出一层自己的CAS接口。 说实话,ABA问题不是一个理论上的杞人忧天,而是每秒几万次push/pop操作下必定会重现的崩溃。内存释放的时机,也绝不是“感觉没人用了就能删”,而是要精确追踪到每一个指针的最后一次可见读。这些细节,不亲手用`perf`看看分配热点,不挂`gdb`看CAS的失败率,你很难真正体会到其中的微妙之处。
本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
作者最新文章
编程开发 C++
相关文章 更多
C++动态数组初始化怎么写?常用语句与代码示例
C++动态数组初始化怎么写?常用语句与代码示例

深入解析C++中动态数组的初始化机制,涵盖new操作符的不同用法、基本类型与类对象的初始化差异,以及为何在现代C++开发中应优先使用std::vector。

C++类构造与析构函数详解
C++类构造与析构函数详解

C++类构造与析构函数详解 C++这门语言,可以说是从C语言这棵大树上衍生出的高级果实,如今的应用普及度有目共睹。作为一种静态类型的通用编程语言,它厉害的地方在于融合了多种编程哲学——无论是传统的面向过程,还是主流的面向对象,乃至数据抽象、泛型编程这些高级概念,它都能很好地支持。正因为这份卓越的扩展

C++中std::upper
C++中std::upper

C++中std::upper_bound用法解析 在C++标准模板库(STL)的算法工具箱里,upper_bound() 绝对算得上是一把精准的“探针”。它的核心任务很明确:在一个已经排好序的区间 [first, last) 内,帮你快速定位到第一个**严格大于**指定值 value 的那个元素。这

C++常对象与成员解析
C++常对象与成员解析

C++中“常”概念全景解析:从对象、成员到指针与引用 在C++的世界里,“常量性”是一个强大的保障机制。它不仅仅是一个const关键字那么简单,而是构建健壮、安全程序的重要基石。今天,我们就来系统梳理一下围绕“常”的一系列概念:常成员、常对象、常指针与常引用。理解它们,是写出高质量C++代码的关键一

c++如何将结构体写入SQLite数据库_对象关系映射方案【进阶】
c++如何将结构体写入SQLite数据库_对象关系映射方案【进阶】

直接用SQLiteCAPI绑定结构体需要手动处理字段展平与顺序对齐,ORM库虽省代码但存在隐式行为风险。小项目建议原生绑定,中大型项目可搭配编译期校验使用轻量ORM。绑定std::string需传指针与长度,注意生命周期;浮点字段比较需设误差范围。

什么是编程,学习编程的意义是?
什么是编程,学习编程的意义是?

编程是编写程序指令,让设备按意图运行,常用Python、C等语言或Scratch图形化编程。学习编程能跟上科技时代,锻炼自学与解决问题能力,提升逻辑思维,代表行动力,推动事物前进。各司其职,编程者尽本分。

编程是门艺术_是编程艺术吗?
编程是门艺术_是编程艺术吗?

编程被争论是否为艺术。从定义看,编程是技能表达,但并非所有编程都是应用开发。写代码如音乐、文章,有独特风格。好代码需耐心与逻辑能力。编程是艺术,但应用开发不等同于编程艺术。

【编程的感受】
【编程的感受】

很多人提起编程,总觉得这是一门“不起眼”的学问——不就是写写代码嘛,能有多深?但真走进去了才会发现,编程里头的门道,远比表面看上去要丰富得多。 学习编程的过程中,最容易卡住的往往是那些基础语法。就拿那个常见的 for 循环来说吧,刚开始时怎么都绕不过弯来:为什么这么写能循环?循环条件到底怎么控制?一

对于懂得编程的人来说,编程对你来说有什么乐趣?编程大概是什么感觉?
对于懂得编程的人来说,编程对你来说有什么乐趣?编程大概是什么感觉?

解决编程问题后的痛快、完成作品的成就感、获取知识的满足感,以及用代码实现简化生活的惊喜与踏实,这些是编程独有的乐趣,只有真正写代码的人才能体会其中的酸甜苦辣、惊喜与满足,令人回味无穷。

趣味编程:少儿编程思维的启蒙之旅
趣味编程:少儿编程思维的启蒙之旅

Scratch图形化编程以拖拽积木块方式启蒙少儿编程思维,无需记忆代码语法。通过素材库、即时反馈和社区协作,帮助孩子在创作中理解顺序执行、条件判断等核心概念,锻炼逻辑、创造力和问题解决能力。

查看更多
精品专题 更多
装机必备
装机必备

正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

Windows
Windows

正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

PDF教程
PDF教程

正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

Mac软件 更多
Postman macOS版
Postman macOS版
Mac

Postman是一套面向API全生命周期的开发与测试平台,可在Mac上发送和调试多种协议请求,管理集合、环境及认证信息,并完成脚本测试、模拟服务、监控、文档发布和团队协作。它适合开发、测试及运维人员使用,提供个人免费方案。

Docker Desktop macOS版
Docker Desktop macOS版
Mac

Docker Desktop 是 Docker 官方为 Mac 提供的容器开发环境,集成 Docker Engine、命令行工具、Compose、Build、Kubernetes 与图形化管理界面。

Android Studio macOS版
Android Studio macOS版
Mac

Android Studio 是 Google 面向安卓应用开发提供的官方集成开发环境,基于 IntelliJ IDEA 构建。它整合智能代码编辑、Gradle 构建、界面预览、设备模拟、性能分析、调试测试及 APK 分析等工具。

WINDOWS 更多
Postman Windows版
Postman Windows版
Windows

Postman 是面向 API 全生命周期的开发与协作平台。Windows 桌面版可用于构建和发送 HTTP、GraphQL、gRPC、WebSocket、MQTT 等请求,并提供环境变量、集合、脚本测试、模拟服务、监控、文档及团队工作区等

Docker Desktop Windows版
Docker Desktop Windows版
Windows

Docker Desktop 为 Windows 开发者提供集成式容器环境,内置 Docker Engine、命令行工具、Compose、Build 与 Kubernetes 等组件,可在本机完成镜像构建、容器运行、日志查看和资源管理。

Android Studio Windows版
Android Studio Windows版
Windows

Android Studio 是 Google 面向 Android 应用开发提供的官方集成开发环境,以 IntelliJ IDEA 为基础,集成智能代码编辑、Gradle 构建、设备模拟、界面预览、调试测试及性能分析工具,