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/16 13:25:39

iOS系统定制新境界：无需越狱实现个性化iPhone的终极方案

iOS系统定制新境界&#xff1a;无需越狱实现个性化iPhone的终极方案 【免费下载链接】CowabungaLite iOS 15 Customization Toolbox 项目地址: https://gitcode.com/gh_mirrors/co/CowabungaLite 为什么你的iPhone需要个性化定制&#xff1f; 你是否曾经感到困惑&#…

作者头像 李华
网站建设 2026/4/16 13:25:39

ResNet18性能优化：TensorRT加速指南

ResNet18性能优化&#xff1a;TensorRT加速指南 1. 背景与挑战&#xff1a;通用物体识别中的效率瓶颈 在当前AI应用广泛落地的背景下&#xff0c;通用物体识别已成为智能监控、内容审核、辅助驾驶等场景的核心能力。基于ImageNet预训练的ResNet-18模型因其结构简洁、精度适中…

作者头像 李华
网站建设 2026/4/16 11:25:54

纪念币预约神器：5分钟搞定全自动预约流程

纪念币预约神器&#xff1a;5分钟搞定全自动预约流程 【免费下载链接】auto_commemorative_coin_booking 项目地址: https://gitcode.com/gh_mirrors/au/auto_commemorative_coin_booking 还在为纪念币预约时手速不够快而烦恼吗&#xff1f;auto_commemorative_coin_bo…

作者头像 李华
网站建设 2026/4/16 3:05:44

E-Hentai漫画资源批量获取技术解决方案

E-Hentai漫画资源批量获取技术解决方案 【免费下载链接】E-Hentai-Downloader Download E-Hentai archive as zip file 项目地址: https://gitcode.com/gh_mirrors/eh/E-Hentai-Downloader 面对海量漫画资源难以高效获取的困境&#xff0c;传统的手动保存方式已无法满足…

作者头像 李华
网站建设 2026/4/15 4:47:54

超详细版：Verilog实现一位全加器全流程解析

从零开始&#xff1a;用 Verilog 实现一位全加器的完整实践在数字电路的世界里&#xff0c;有些模块看似简单&#xff0c;却是整个系统大厦的地基。一位全加器&#xff08;Full Adder&#xff09;正是这样的存在——它只处理三个比特的加法&#xff0c;却支撑起了从计算器到CPU…

作者头像 李华
网站建设 2026/4/14 15:34:39

PCL2-CE社区版启动器：打造你的专属Minecraft游戏管家

PCL2-CE社区版启动器&#xff1a;打造你的专属Minecraft游戏管家 【免费下载链接】PCL2-CE PCL2 社区版&#xff0c;可体验上游暂未合并的功能 项目地址: https://gitcode.com/gh_mirrors/pc/PCL2-CE 还在为繁琐的Minecraft启动流程而烦恼吗&#xff1f;想要一款既稳定又…

作者头像 李华