展开菜单
首页 精品内容 本月促销 装机必备 Windows PDF教程 macOS软件 IOS软件 Android AI 专题
全部分类

当前位置:

首页 > 编程开发 > 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++
    相关文章 更多
    精品专题 更多
    装机必备

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

    Windows

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

    PDF教程

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

    macOS软件

    正软商城macOS软件专区,精选适用于Mac电脑的办公、设计、影音、效率、开发和系统工具,提供软件功能介绍、macOS兼容版本、正版授权及购买下载服务。

    IOS软件

    正软商城iOS软件专区,精选适用于iPhone和iPad的办公、学习、影音、设计、效率及AI应用,提供功能介绍、适用设备、系统要求和正版获取方式等信息。

    AI

    正软商城AI软件专区,汇集AI写作、AI绘画、AI视频、AI办公、AI编程、AI翻译、智能客服和数据分析等人工智能工具,提供功能介绍、适用平台、收费方式及正版购买信息。

    Mac软件 更多
    Adobe Acrobat Pro macOS版
    Adobe Acrobat Pro macOS版

    Adobe Acrobat Pro 是面向办公、法务、财务、教育及出版用户的专业PDF处理软件,可在Mac上创建、编辑、转换、合并和保护文档,并提供OCR文字识别、表单、批注、内容比较、敏感信息遮盖及电子签名功能。

    Blender
    Blender

    Blender 是一款免费开源、跨平台的专业 3D 创作软件,集建模、动画、渲染、视频编辑与视觉合成等功能于一体,广泛应用于影视动画、游戏设计和建筑可视化等领域。软件支持 Cycles 物理渲染器与 Eevee 实时渲染引擎,并提供多边形建模、骨骼绑定、物理模拟等专业工具。Blender 兼容 Windows、macOS 和 Linux 系统,安装包轻巧、运行流畅,依托活跃的全球开发者社区持续更新,是从初学者到专业创作者都值得选择的正版 3D 创作工具。

    Shapr3D macOS版
    Shapr3D macOS版

    Shapr3D是一款面向工业设计、机械工程、建筑概念和三维打印工作流的CAD软件。Mac版采用Parasolid建模内核,支持草图约束、实体建模、工程图、可视化渲染及常见CAD格式交换,并可通过账户在多台设备之间同步项目。

    Adobe Illustrator macOS版
    Adobe Illustrator macOS版

    Adobe Illustrator 是 Adobe 推出的专业矢量图形设计软件,适合在 Mac 上制作标志、图标、插画、包装、信息图及印刷版面。它以路径和锚点构建可无损缩放的图形,并提供钢笔、形状、文字、图像描摹、渐变、画板及生成式功能。

    Adobe InDesign macOS版
    Adobe InDesign macOS版

    Adobe InDesign 是面向印刷品与数字出版物的专业版面设计软件,可在 Mac 上制作书籍、杂志、宣传册、海报、报告及交互式文档。它提供精细的文字样式、网格、母版、长文档管理和印前输出能力。

    Affinity Designer macOS版
    Affinity Designer macOS版

    Affinity Designer 的矢量设计能力现已整合进 Affinity by Canva,可在 Mac 上进行标志、图标、插画、界面原型及印刷品设计。个人用户使用免费 Canva 账户即可使用完整的矢量、像素和版面工具。

    Archicad macOS版
    Archicad macOS版

    Archicad是Graphisoft推出的建筑信息模型设计软件,可在Mac上完成概念设计、参数化建模、图纸编制、工程量统计、渲染展示及团队协同。模型与平立剖面、明细表和布局保持关联,适合建筑师、室内设计师、BIM团队及相关专业学生使用。

    AutoCAD LT macOS版
    AutoCAD LT macOS版

    AutoCAD LT是Autodesk推出的专业二维CAD设计与文档编制软件,Mac版本提供原生界面、多点触控及分屏查看体验。用户可精确创建和编辑DWG图形,完成图层管理、尺寸标注、表格、PDF参考、外部参照及打印输出。

    AutoCAD macOS版
    AutoCAD macOS版

    AutoCAD for Mac 是 Autodesk 面向 macOS 提供的专业计算机辅助设计软件,支持精确的二维绘图、标注、布局输出以及实体、曲面和网格建模。软件采用适配 Mac 操作习惯的界面,可处理 DWG 图纸。

    Autodesk Fusion macOS版
    Autodesk Fusion macOS版

    Autodesk Fusion 是面向产品设计与制造的一体化云连接平台,在 Mac 上提供参数化建模、自由曲面、装配、工程图、仿真、PCB 设计和 CAM 加工等工具。它适合机械工程师、工业设计师、创客及制造团队使用。

    Autodesk Maya macOS版
    Autodesk Maya macOS版

    Autodesk Maya是一套面向影视动画、游戏开发和视觉特效制作的专业三维创作软件,集多边形与曲面建模、角色绑定、关键帧动画、动力学模拟、程序化特效及Arnold渲染于一体,并提供脚本、插件和开放式制作管线支持。

    Blender macOS版
    Blender macOS版

    Blender是一款免费开源的综合三维创作软件,可在Mac上完成建模、数字雕刻、材质制作、角色绑定、动画、物理模拟、渲染、合成及视频剪辑。软件提供Cycles与Eevee渲染工具,并支持几何节点、蜡笔绘制和Python扩展。

    WINDOWS 更多
    AutoCAD Windows版
    AutoCAD Windows版

    AutoCAD 是 Autodesk 推出的专业计算机辅助设计软件,Windows 版支持精确二维绘图、三维实体与曲面建模、图纸标注、布局发布和任务自动化,并包含多套行业专业化工具组合,适用于建筑、机械、电气、工程建设及制造设计人员。

    Adobe Acrobat Pro Windows版
    Adobe Acrobat Pro Windows版

    Adobe Acrobat Pro 是面向专业 PDF 工作的综合解决方案,可在 Windows 中创建、编辑、转换、比较、整理和保护文档,并支持表单、电子签名、扫描件文字识别及敏感信息永久遮盖。订阅还包含网页、移动服务和云端协作能力,

    Blender
    Blender

    Blender 是一款免费开源、跨平台的专业 3D 创作软件,集建模、动画、渲染、视频编辑与视觉合成等功能于一体,广泛应用于影视动画、游戏设计和建筑可视化等领域。软件支持 Cycles 物理渲染器与 Eevee 实时渲染引擎,并提供多边形建模、骨骼绑定、物理模拟等专业工具。Blender 兼容 Windows、macOS 和 Linux 系统,安装包轻巧、运行流畅,依托活跃的全球开发者社区持续更新,是从初学者到专业创作者都值得选择的正版 3D 创作工具。

    3dmax(3ds max)
    3dmax(3ds max)

    Autodesk 3ds Max 是一款专业的三维建模、动画与渲染软件,广泛应用于建筑可视化、游戏开发、影视动画、广告设计和产品展示等领域。

    Adobe InDesign Windows版
    Adobe InDesign Windows版

    Adobe InDesign 是面向印刷与数字出版的专业页面排版工具,可制作书籍、杂志、宣传册、海报、交互式 PDF 和电子书。它提供精细的文字样式、多页面管理、印前检查及多格式输出能力,并能与 Photoshop、Illustrator

    Adobe Illustrator Windows版
    Adobe Illustrator Windows版

    Adobe Illustrator 是用于绘制矢量图形、插画、图标、徽标和版式的专业设计工具。它以路径和锚点为核心,作品放大后仍能保持清晰,并提供画板、文字、渐变、图像描摹及精确变换等功能,适合品牌视觉、印刷物料、数字界面和商业插画创作。

    Figma Windows版
    Figma Windows版

    Figma 是面向产品设计与开发团队的云端协作平台,可在 Windows 桌面客户端中完成界面绘制、组件管理、交互原型、评论评审和开发交付。文件保存在云端,多名成员能够同步编辑并共享设计系统;官方同时提供免费 Starter 方案及按席位计

    Affinity Designer Windows版
    Affinity Designer Windows版

    Affinity Designer 是面向矢量图形、数字插画和界面设计的专业创作工具,可在矢量、像素与导出工作区之间快速切换。它提供曲线编辑、形状构建、画板、排版、图层和专业色彩管理,并支持常见设计文件的导入及多种印刷、网页格式输出。

    Cinema 4D Windows版
    Cinema 4D Windows版

    Cinema 4D是Maxon推出的专业三维创作软件,将建模、动画、MoGraph动态图形、粒子与动力学模拟、材质灯光及Redshift渲染整合在统一工作环境中,适用于广告包装、影视特效、产品和建筑可视化、游戏素材等制作场景。

    Blender Windows版
    Blender Windows版

    Blender 是免费开源的三维创作套件,在 Windows 上提供建模、雕刻、材质、动画、物理模拟、合成、跟踪、视频剪辑及 Cycles、EEVEE 渲染工具。它适合个人创作者、学生和小型工作室,

    Autodesk Maya Windows版
    Autodesk Maya Windows版

    Autodesk Maya 是面向影视、电视、动画和游戏行业的专业三维制作软件,集多边形与 NURBS 建模、角色绑定、关键帧和动作捕捉动画、Bifrost 特效模拟、材质开发及 Arnold 渲染于一体,

    SketchUp Pro Windows版
    SketchUp Pro Windows版

    SketchUp Pro 是面向建筑、室内、景观、施工和产品设计等专业场景的三维建模工具,提供桌面建模、LayOut 二维文档、模型资源库、扩展程序及云端协作能力。其操作逻辑直观,适合从概念推敲、空间规划到图纸表达和方案汇报的完整工作流程。