C++怎么实现一个无锁队列_C++并发编程与无锁队列实现

胖敏君_1530

胖敏君_1530

2025-11-20

818人浏览

原创

无锁队列通过原子操作实现多线程高效安全的数据共享,避免互斥锁开销。其核心是使用CAS等原子指令更新head和tail指针,确保线程安全。SPSC场景下可用循环缓冲区简化实现,MPMC则常用Michael-Scott链表算法,通过原子操作维护节点连接,并解决ABA问题与内存回收难题。需注意内存序选择、伪共享规避及悬空指针风险,推荐在高竞争场景使用,否则优先考虑带锁队列以降低复杂度。

c++怎么实现一个无锁队列_c++并发编程与无锁队列实现

实现无锁队列(Lock-Free Queue)是C++并发编程中的高级话题,核心目标是在多线程环境下实现高效、安全的数据共享,避免使用互斥锁带来的性能开销和潜在死锁问题。无锁队列依赖原子操作和内存序控制来保证线程安全。

无锁队列的基本原理

无锁数据结构的关键在于使用原子操作(如 compare-and-swap, CAS)来更新共享状态。队列通常采用链表结构,每个节点包含数据和指向下一个节点的指针。通过原子地修改头指针(head)和尾指针(tail),多个线程可以同时进行入队和出队操作。

主要挑战包括:

  • A-B-A问题:某个值被修改后又恢复原值,导致CAS误判。
  • 内存回收困难:无法立即删除出队节点,因为其他线程可能仍在访问。
  • ABA问题可通过引入版本号(如使用双字CAS或tagged pointer)缓解。

单生产者单消费者模型下的简单实现

在SPSC(Single Producer Single Consumer)场景中,可以简化设计。以下是一个基于循环缓冲区的无锁队列框架:

#include <atomic>
#include <vector><p>template<typename t size_t n>
class LockFreeQueue {
std::vector<t> buffer;
std::atomic<size_t> head{0};
std::atomic<size_t> tail{0};</size_t></size_t></t></typename></p>
<p>public:
LockFreeQueue() : buffer(N) {}</p>
<pre class="brush:php;toolbar:false;">bool push(const T& value) {
    size_t current_tail = tail.load();
    size_t next_tail = (current_tail + 1) % N;

    if (next_tail == head.load()) {
        return false; // 队列满
    }

    buffer[current_tail] = value;
    tail.store(next_tail);
    return true;
}

bool pop(T& value) {
    size_t current_head = head.load();

    if (current_head == tail.load()) {
        return false; // 队列空
    }

    value = buffer[current_head];
    size_t next_head = (current_head + 1) % N;
    head.store(next_head);
    return true;
}

};

这个版本适用于SPSC场景,无需强内存序,性能高。但不适用于多生产者或多消费者,因为可能出现写冲突或读脏数据。

多生产者多消费者的无锁队列(Michael-Scott算法)

Michael和Scott提出的链表式无锁队列是经典MPMC实现。核心思想是:

Mailtrap Node.js SDK 用于事务性和沙盒电子邮件
Mailtrap Node.js SDK 用于事务性和沙盒电子邮件

一个基于官方 Mailtrap Node.js SDK 构建的 ASE 技能,用于发送事务邮件并与 Mailtrap 沙盒或生产流程协作。它非常适合需要 API 驱动邮件投递、测试邮箱验证和结构化消息自动化的代理工作流。

下载
  • 使用链表节点,每个节点有data和next指针。
  • head和tail为原子指针。
  • push操作原子更新tail->next和tail本身。
  • pop操作检查head,移动head到next。

关键代码片段:

struct Node {
    T data;
    std::atomic<node> next;
<pre class="brush:php;toolbar:false;">Node(const T& d) : data(d), next(nullptr) {}

};

std::atomic> head; std::atomic> tail;

bool push(const T& value) { Node new_node = new Node(value); Node old_tail = tail.load();

while (!tail.compare_exchange_weak(old_tail, new_node)) {
    // 尝试将新节点接在旧tail后面
    Node* next = old_tail->next.load();
    if (!next) {
        old_tail->next.compare_exchange_strong(next, new_node);
    }
    old_tail = tail.load(); // 更新old_tail
}
old_tail->next.store(new_node); // 连接节点
return true;

}

实际完整实现需处理内存释放(如使用 Hazard Pointer 或 RCU),否则存在悬空指针风险。

注意事项与优化建议

实现无锁队列时需注意:

  • 使用合适的内存序(memory_order_acq_rel等)减少同步开销。
  • 避免伪共享:确保head和tail不在同一缓存行。
  • 考虑使用现成库如abseil、folly中的无锁队列,更稳定高效。
  • 调试困难,建议充分测试边界情况和压力场景。

基本上就这些。无锁队列虽能提升并发性能,但实现复杂,应优先评估是否真的需要。对于多数应用,带锁的队列(如std::queue + mutex)已足够高效。只有在高竞争场景下才考虑无锁方案。不复杂但容易忽略的是内存管理和ABA防护。

C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!

相关文章

编程速学教程(入门课程)
编程速学教程(入门课程)

编程怎么学习?编程怎么入门?编程在哪学?编程怎么学才快?不用担心,这里为大家提供了编程速学教程(入门课程),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

node c++ 并发编程

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
c语言const用法
c语言const用法

const是关键字,可以用于声明常量、函数参数中的const修饰符、const修饰函数返回值、const修饰指针。详细介绍:1、声明常量,const关键字可用于声明常量,常量的值在程序运行期间不可修改,常量可以是基本数据类型,如整数、浮点数、字符等,也可是自定义的数据类型;2、函数参数中的const修饰符,const关键字可用于函数的参数中,表示该参数在函数内部不可修改等等。

2023.09.20

2498

7

c语言const用法
c语言const用法

const是关键字,可以用于声明常量、函数参数中的const修饰符、const修饰函数返回值、const修饰指针。详细介绍:1、声明常量,const关键字可用于声明常量,常量的值在程序运行期间不可修改,常量可以是基本数据类型,如整数、浮点数、字符等,也可是自定义的数据类型;2、函数参数中的const修饰符,const关键字可用于函数的参数中,表示该参数在函数内部不可修改等等。

2023.09.20

2498

7

C++ 智能指针与现代内存管理
C++ 智能指针与现代内存管理

深入讲解 C++ 现代内存管理的核心工具——智能指针,涵盖 unique_ptr 独占所有权语义、shared_ptr 引用计数机制与循环引用问题、weak_ptr 弱引用的应用场景、make_unique/make_shared 工厂函数的性能优势、自定义删除器的编写、RAII 资源管理思想的实践,以及从裸指针迁移到智能指针的重构策略,帮助开发者编写安全无泄漏的现代 C++ 代码。

2026.04.23

399

31

treenode的用法
treenode的用法

​在计算机编程领域,TreeNode是一种常见的数据结构,通常用于构建树形结构。在不同的编程语言中,TreeNode可能有不同的实现方式和用法,通常用于表示树的节点信息。更多关于treenode相关问题详情请看本专题下面的文章。php中文网欢迎大家前来学习。

2023.12.01

2961

7

C++ 高效算法与数据结构
C++ 高效算法与数据结构

本专题讲解 C++ 中常用算法与数据结构的实现与优化,涵盖排序算法(快速排序、归并排序)、查找算法、图算法、动态规划、贪心算法等,并结合实际案例分析如何选择最优算法来提高程序效率。通过深入理解数据结构(链表、树、堆、哈希表等),帮助开发者提升 在复杂应用中的算法设计与性能优化能力。

2025.12.22

416

20

深入理解算法:高效算法与数据结构专题
深入理解算法:高效算法与数据结构专题

本专题专注于算法与数据结构的核心概念,适合想深入理解并提升编程能力的开发者。专题内容包括常见数据结构的实现与应用,如数组、链表、栈、队列、哈希表、树、图等;以及高效的排序算法、搜索算法、动态规划等经典算法。通过详细的讲解与复杂度分析,帮助开发者不仅能熟练运用这些基础知识,还能在实际编程中优化性能,提高代码的执行效率。本专题适合准备面试的开发者,也适合希望提高算法思维的编程爱好者。

2026.01.06

437

22

C++ 数据结构与算法实现教程合集
C++ 数据结构与算法实现教程合集

以 C++ 为实现语言,系统讲解核心数据结构与算法,涵盖链表(单链表/双链表/环检测)、栈与队列(单调栈/优先队列)、二叉树(遍历/BST/AVL/红黑树)、哈希表(开地址法/链地址法)、图(邻接表/BFS/DFS/Dijkstra/拓扑排序)、常见排序算法(快排/归并/堆排/计数排序)的实现与复杂度分析,同时分享 LeetCode 刷题技巧、竞赛编程常用模板(二分/前缀和/滑动窗口/动态规划),帮助开发者夯实算法基础。

2026.05.09

512

25

线程和进程的区别
线程和进程的区别

线程和进程的区别:线程是进程的一部分,用于实现并发和并行操作,而线程共享进程的资源,通信更方便快捷,切换开销较小。本专题为大家提供线程和进程区别相关的各种文章、以及下载和课程。

2023.08.10

4938

6

Python 多线程与异步编程实战
Python 多线程与异步编程实战

本专题系统讲解 Python 多线程与异步编程的核心概念与实战技巧,包括 threading 模块基础、线程同步机制、GIL 原理、asyncio 异步任务管理、协程与事件循环、任务调度与异常处理。通过实战示例,帮助学习者掌握 如何构建高性能、多任务并发的 Python 应用。

2025.12.24

1389

20

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
WebSocket手册
WebSocket手册

共0课时 | 0人学习

HTML5/CSS3/JavaScript/ES6入门课程
HTML5/CSS3/JavaScript/ES6入门课程

共102课时 | 11.2万人学习

前端基础到实战(HTML5+CSS3+ES6+NPM)
前端基础到实战(HTML5+CSS3+ES6+NPM)

共162课时 | 29.2万人学习