news 2026/4/23 14:43:53

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/23 14:41:46

BooruDatasetTagManager：从图片标注小白到高手的进阶指南

BooruDatasetTagManager&#xff1a;从图片标注小白到高手的进阶指南 【免费下载链接】BooruDatasetTagManager 项目地址: https://gitcode.com/gh_mirrors/bo/BooruDatasetTagManager 还在为海量图片标注而头疼吗&#xff1f;传统手工标注不仅效率低下&#xff0c;还容…

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

2025零基础实战：三步搞定视频字幕智能提取

2025零基础实战&#xff1a;三步搞定视频字幕智能提取 【免费下载链接】video-subtitle-extractor 视频硬字幕提取&#xff0c;生成srt文件。无需申请第三方API&#xff0c;本地实现文本识别。基于深度学习的视频字幕提取框架&#xff0c;包含字幕区域检测、字幕内容提取。A GU…

作者头像 李华
网站建设 2026/4/21 21:09:15

从零实现基于电路仿真circuits网页版的稳压电源项目应用

用指尖搭建电源&#xff1a;在电路仿真网页版中从零实现一个稳压电源系统你有没有过这样的经历&#xff1f;想做个单片机小项目&#xff0c;却卡在“怎么给它稳定供电”这一步。买模块太贵&#xff0c;自己搭又怕烧板子——别急&#xff0c;今天我们不焊一根线、不插一块芯片&a…

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

StructBERT模型比较：选择最佳分类方案

StructBERT模型比较&#xff1a;选择最佳分类方案 1. 引言&#xff1a;AI 万能分类器的时代来临 在自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;文本分类是构建智能系统的核心能力之一。无论是客服工单自动归类、用户意图识别&#xff0c;还是舆情监控与新闻分类…

作者头像 李华
网站建设 2026/4/23 12:21:51

6个超实用内容解锁技巧：轻松实现付费墙绕过的方法详解

6个超实用内容解锁技巧&#xff1a;轻松实现付费墙绕过的方法详解 【免费下载链接】bypass-paywalls-chrome-clean 项目地址: https://gitcode.com/GitHub_Trending/by/bypass-paywalls-chrome-clean 你是否曾经遇到这样的情况&#xff1a;一篇看似精彩的文章&#xff…

作者头像 李华
网站建设 2026/4/16 14:21:23

mermaid ER图终极指南：从零绘制专业级实体关系图

mermaid ER图终极指南&#xff1a;从零绘制专业级实体关系图 【免费下载链接】mermaid 项目地址: https://gitcode.com/gh_mirrors/mer/mermaid 本文教你如何使用mermaid快速创建清晰易懂的实体关系图&#xff0c;适合数据库设计者和系统分析师。无论你是初学者还是有经…

作者头像 李华