news 2026/4/16 0:55:19

C++：无锁链表（附带源码）

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
C++：无锁链表（附带源码）

项目背景详细介绍

在现代高并发系统中，锁（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. 功能需求

  1. 使用 C++ 实现无锁单向链表

  2. 支持多线程并发插入

  3. 支持多线程并发删除

  4. 不使用 mutex / lock

  5. 基于 CAS 原子操作

2. 技术要求

  1. 使用std::atomic

  2. 使用 Compare-And-Swap

  3. 正确处理并发竞争

  4. 代码可在 C++17 环境下编译

3. 教学与工程要求

  1. 代码结构清晰

  2. 明确展示“失败重试”模型

  3. 注释解释每一步并发语义

  4. 为后续复杂无锁结构打基础

相关技术详细介绍

1. 什么是无锁（Lock-Free）

无锁并不意味着：

“没有任何同步”

而是意味着：

系统整体始终向前推进，不会因某个线程阻塞而停滞

Lock-Free 的核心保证是：

  • 至少有一个线程可以在有限步内完成操作

2. CAS（Compare-And-Swap）

CAS 是无锁算法的基石，其语义是：

if (*addr == expected) *addr = desired;

在 CPU 层面，这是一条不可中断的原子指令。

3. Treiber 链表思想

Treiber 在 1986 年提出了一种：

  • 基于 CAS

  • 无需锁

  • 支持并发 push / pop

的单向链表（也常被称为无锁栈）。

它的核心思想是：

永远只修改“头指针”，失败就重试

4. ABA 问题（概念说明）

在无锁结构中，可能出现：

  • 指针值从 A → B → A

  • CAS 误以为“没变”

本文示例用于教学理解，未引入复杂的 Hazard Pointer / Epoch GC，这是后续扩展方向。

实现思路详细介绍

整体设计思路如下：

  1. 定义链表节点 Node

  2. 使用std::atomic<Node*>作为头指针

  3. 插入时：

    • 新节点指向当前 head

    • CAS 更新 head

  4. 删除时：

    • 读取 head

    • CAS 将 head 指向 next

  5. 所有失败操作进入自旋重试

该模型是所有无锁链表 / 无锁栈的核心模板。

完整实现代码

/**************************************************** * File: LockFreeList.h ****************************************************/ #pragma once #include <atomic> template<typename T> class LockFreeList { private: struct Node { T data; Node* next; Node(const T& value) : data(value), next(nullptr) {} }; // 原子头指针 std::atomic<Node*> head; public: LockFreeList(); ~LockFreeList(); void push_front(const T& value); bool pop_front(T& result); }; /**************************************************** * File: LockFreeList.cpp ****************************************************/ #include "LockFreeList.h" template<typename T> LockFreeList<T>::LockFreeList() { head.store(nullptr, std::memory_order_relaxed); } template<typename T> LockFreeList<T>::~LockFreeList() { // 单线程环境下清理 Node* node = head.load(); while (node) { Node* next = node->next; delete node; node = next; } } template<typename T> void LockFreeList<T>::push_front(const T& value) { Node* newNode = new Node(value); // 自旋 CAS do { // 读取当前头指针 Node* oldHead = head.load(std::memory_order_acquire); newNode->next = oldHead; // 尝试将 head 从 oldHead 更新为 newNode // 如果失败，说明被其他线程抢先修改，继续重试 } while (!head.compare_exchange_weak( newNode->next, newNode, std::memory_order_release, std::memory_order_relaxed )); } template<typename T> bool LockFreeList<T>::pop_front(T& result) { Node* oldHead = nullptr; do { oldHead = head.load(std::memory_order_acquire); if (!oldHead) return false; // 尝试将 head 指向下一个节点 } while (!head.compare_exchange_weak( oldHead, oldHead->next, std::memory_order_release, std::memory_order_relaxed )); result = oldHead->data; delete oldHead; return true; } /**************************************************** * File: main.cpp ****************************************************/ #include "LockFreeList.h" #include <iostream> #include <thread> #include <vector> int main() { LockFreeList<int> list; // 多线程并发插入 std::vector<std::thread> threads; for (int i = 0; i < 4; i++) { threads.emplace_back([&list, i]() { for (int j = 0; j < 10; j++) { list.push_front(i * 100 + j); } }); } for (auto& t : threads) t.join(); // 单线程弹出查看结果 int value; while (list.pop_front(value)) { std::cout << value << std::endl; } return 0; }

代码详细解读（仅解读方法作用）

Node 结构体

表示链表节点，包含数据和指向下一个节点的指针。

std::atomic<Node*> head

无锁链表的核心，所有并发竞争都集中在头指针。

push_front

通过 CAS 循环将新节点插入链表头部。

pop_front

通过 CAS 循环安全地移除链表头节点。

compare_exchange_weak

执行原子比较交换，失败即重试，是无锁算法核心。

main

通过多线程并发插入验证无锁链表正确性。

项目详细总结

通过本项目，你可以真正理解：

  • 无锁并发的设计哲学

  • CAS 在真实代码中的使用方式

  • 为什么无锁算法需要“自旋 + 重试”

  • 锁与无锁在性能与复杂度上的权衡

这是迈向高性能并发编程的重要一步。

项目常见问题及解答

Q1：这是完整的无锁链表吗？
A：这是无锁链表的经典教学模型（Treiber 思想）。

Q2：ABA 问题怎么解决？
A：需要引入版本号、Hazard Pointer 或 Epoch GC。

Q3：生产环境能直接用吗？
A：需要更完善的内存回收机制。

扩展方向与性能优化

  1. 引入 ABA 保护（Tagged Pointer）

  2. Hazard Pointer 内存回收

  3. Epoch-Based Reclamation

  4. Harris-Michael 无锁链表

  5. 无锁队列（Michael-Scott Queue）

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/12 23:44:54

OpenSpeedy终极指南：如何用开源工具掌控游戏时间流速

OpenSpeedy终极指南&#xff1a;如何用开源工具掌控游戏时间流速 【免费下载链接】OpenSpeedy 项目地址: https://gitcode.com/gh_mirrors/op/OpenSpeedy 厌倦了游戏中无聊的等待&#xff1f;想要自由调节游戏节奏&#xff1f;OpenSpeedy这款完全免费的开源游戏变速工具…

作者头像 李华
网站建设 2026/4/15 3:30:24

BBDown终极指南：5分钟掌握免费B站视频下载神器

BBDown终极指南&#xff1a;5分钟掌握免费B站视频下载神器 【免费下载链接】BBDown Bilibili Downloader. 一款命令行式哔哩哔哩下载器. 项目地址: https://gitcode.com/gh_mirrors/bb/BBDown 想要轻松保存B站视频却苦于找不到合适的工具&#xff1f;BBDown这款专业级B站…

作者头像 李华
网站建设 2026/4/15 10:48:38

小米运动步数自动同步工具2025：智能多平台数据管理完整指南

小米运动步数自动同步工具2025&#xff1a;智能多平台数据管理完整指南 【免费下载链接】mimotion 小米运动刷步数&#xff08;微信支付宝&#xff09;支持邮箱登录 项目地址: https://gitcode.com/gh_mirrors/mimo/mimotion 在当今数字化健康管理时代&#xff0c;如何高…

作者头像 李华
网站建设 2026/4/15 10:50:13

iOS个性化定制终极指南：无需越狱打造完全专属iPhone体验

iOS个性化定制终极指南&#xff1a;无需越狱打造完全专属iPhone体验 【免费下载链接】CowabungaLite iOS 15 Customization Toolbox 项目地址: https://gitcode.com/gh_mirrors/co/CowabungaLite 还在为千篇一律的iOS界面感到乏味吗&#xff1f;想要让iPhone真正成为你的…

作者头像 李华
网站建设 2026/4/15 10:50:44

ResNet18优化实战：模型量化与加速的实践

ResNet18优化实战&#xff1a;模型量化与加速的实践 1. 引言&#xff1a;通用物体识别中的ResNet-18价值 在当前AI应用广泛落地的背景下&#xff0c;轻量级图像分类模型成为边缘设备、嵌入式系统和低延迟服务的核心需求。ResNet-18作为深度残差网络中最经典的轻量版本之一&am…

作者头像 李华
网站建设 2026/4/15 10:50:28

DoL-Lyra整合包终极使用手册：5分钟快速精通秘籍

DoL-Lyra整合包终极使用手册&#xff1a;5分钟快速精通秘籍 【免费下载链接】DoL-Lyra Degrees of Lewdity 整合 项目地址: https://gitcode.com/gh_mirrors/do/DoL-Lyra 还在为Degrees of Lewdity游戏的各种Mod安装烦恼吗&#xff1f;DoL-Lyra整合包彻底改变了传统Mod管…

作者头像 李华