c++怎么实现一个无锁队列(lock-free queue)_c++原子操作实现无锁并发结构

秋敏同学_2628

秋敏同学_2628

2025-10-29

470人浏览

原创

无锁队列通过原子操作实现线程安全的并发访问,使用 std::atomic 管理 head 和 tail 指针,结合内存序控制与虚拟头节点简化边界处理,在高并发下需解决 ABA 问题与内存回收难题。

c++怎么实现一个无锁队列(lock-free queue)_c++原子操作实现无锁并发结构

实现一个无锁队列(lock-free queue)需要利用 C++ 的原子操作(atomic operations)来避免使用互斥锁,从而提升多线程环境下的性能。核心思想是通过原子指针操作和内存顺序控制,确保多个线程可以安全地并发执行入队(enqueue)和出队(dequeue)操作。

基本原理:基于链表的无锁队列

最常见的无锁队列实现是基于单向链表的结构,使用两个原子指针:head 和 tail,分别指向队列的头和尾。每个节点包含数据和指向下一个节点的指针。

关键点在于所有对指针的操作都必须是原子的,并且要正确处理 ABA 问题和内存重排序。

以下是一个简化但可运行的无锁队列实现:

#include <atomic>
#include <memory>

template<typename t>
class LockFreeQueue {
private:
    struct Node {
        std::shared_ptr<t> data;
        std::atomic<node> next;

        Node() : data(nullptr), next(nullptr) {}

        Node(const T& d) : data(std::make_shared<t>(d)), next(nullptr) {}
    };

    std::atomic<node> head;
    std::atomic<node> tail;

    // 辅助函数:尝试释放已出队的节点
    void free_if_need(Node* old_head) {
        if (old_head) {
            delete old_head;
        }
    }

public:
    LockFreeQueue() {
        Node* dummy = new Node();
        head.store(dummy, std::memory_order_relaxed);
        tail.store(dummy, std::memory_order_relaxed);
    }

    ~LockFreeQueue() {
        while (Node* h = head.load()) {
            head.store(h->next.load());
            delete h;
        }
    }

    void enqueue(const T& data) {
        Node* new_node = new Node(data);
        Node* old_tail = nullptr;
        Node* next = nullptr;

        while (true) {
            old_tail = tail.load(std::memory_order_acquire);
            next = old_tail->next.load(std::memory_order_acquire);

            // 检查 tail 是否滞后
            if (old_tail != tail.load(std::memory_order_acquire)) {
                continue; // 重新尝试
            }

            // 如果 tail 没有指向最后一个节点,尝试推进 tail
            if (next != nullptr) {
                tail.compare_exchange_weak(old_tail, next, std::memory_order_release, std::memory_order_acquire);
                continue;
            }

            // 尝试将新节点链接到 tail 后
            if (old_tail->next.compare_exchange_weak(next, new_node, std::memory_order_release, std::memory_order_acquire)) {
                break; // 成功链接
            }
        }

        // 尝试更新 tail 指向新节点
        tail.compare_exchange_weak(old_tail, new_node, std::memory_order_release, std::memory_order_acquire);
    }

    std::shared_ptr<t> dequeue() {
        Node* old_head = nullptr;
        while (true) {
            old_head = head.load(std::memory_order_acquire);
            Node* old_tail = tail.load(std::memory_order_acquire);
            Node* next = old_head->next.load(std::memory_order_acquire);

            // 判断队列是否为空
            if (old_head == old_tail) {
                if (next == nullptr) {
                    return std::shared_ptr<t>(); // 队列空
                }
                // tail 滞后,尝试推进
                tail.compare_exchange_weak(old_tail, next, std::memory_order_release, std::memory_order_acquire);
                continue;
            }

            // 读取数据并尝试移动 head
            if (head.compare_exchange_weak(old_head, next, std::memory_order_release, std::memory_order_acquire)) {
                std::shared_ptr<t> res = next->data;
                // 延迟释放 old_head(注意:生产环境应使用 hazard pointer 或 RCU)
                free_if_need(old_head);
                return res;
            }
        }
    }
};</t></t></t></node></node></t></node></t></typename></memory></atomic>

关键点解析

1. 原子指针操作: 使用 `std::atomicnode>` 来保证 head 和 tail 的读写是原子的,防止数据竞争。

2. 内存顺序(memory order):

logos-node
logos-node

在 Linux x86_64 上安装、更新或检查 Logos 区块链测试网验证节点。用于用户需要搭建 Logos 节点时使用。

下载
  • memory_order_acquire 用于读操作,确保后续读写不会被重排到该操作之前。
  • memory_order_release 用于写操作,确保前面的读写不会被重排到该操作之后。
  • compare_exchange_weak 在循环中使用,允许失败后重试。

3. 虚拟头节点(dummy node): 构造时创建一个空节点作为初始 head 和 tail,简化边界判断。

4. tail 滞后处理: 其他线程可能在修改 next,但还没更新 tail,此时需要帮助完成 tail 推进。

存在的问题与改进方向

上述实现虽然能工作,但在高并发下仍可能遇到问题:

  • ABA 问题: 虽然指针值没变,但中间可能已被释放并重用。可通过双字 CAS(如 __int128 包装指针+计数器)解决。
  • 内存回收困难: 直接 delete 可能导致其他线程访问已释放内存。应使用 Hazard Pointer、RCU 或 epoch-based reclamation。
  • 性能: 多线程竞争 tail 时可能频繁失败。可考虑 Michael-Scott 队列的优化版本。

使用示例

```cpp #include #include #include

int main() { LockFreeQueue queue;

std::vector<:thread> producers;
std::vector<:thread> consumers;

for (int i = 0; i <p>}</p>
<pre class="brush:php;toolbar:false;">

基本上就这些。无锁队列实现复杂,调试困难,建议在真正需要极致性能时才使用,否则优先考虑互斥锁 + 条件变量的方案。

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

相关文章

c++速学教程(入门到精通)
c++速学教程(入门到精通)

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

下载

相关标签:

node c++ 并发访问

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

相关专题

更多
string转int
string转int

在编程中,我们经常会遇到需要将字符串(str)转换为整数(int)的情况。这可能是因为我们需要对字符串进行数值计算,或者需要将用户输入的字符串转换为整数进行处理。php中文网给大家带来了相关的教程以及文章,欢迎大家前来学习阅读。

2023.08.02

7739

3

int占多少字节
int占多少字节

int占4个字节,意味着一个int变量可以存储范围在-2,147,483,648到2,147,483,647之间的整数值,在某些情况下也可能是2个字节或8个字节,int是一种常用的数据类型,用于表示整数,需要根据具体情况选择合适的数据类型,以确保程序的正确性和性能。本专题为大家提供相关的文章、下载、课程内容,供大家免费下载体验。

2024.08.29

3665

6

c++怎么把double转成int
c++怎么把double转成int

本专题整合了 c++ double相关教程,阅读专题下面的文章了解更多详细内容。

2025.08.29

4828

10

C++中int的含义
C++中int的含义

本专题整合了C++中int相关内容,阅读专题下面的文章了解更多详细内容。

2025.08.29

3205

10

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

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

2026.04.23

399

31

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

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

2023.08.10

4978

6

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

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

2025.12.24

1389

20

java多线程相关教程合集
java多线程相关教程合集

本专题整合了java多线程相关教程,阅读专题下面的文章了解更多详细内容。

2026.01.21

463

30

C++多线程相关合集
C++多线程相关合集

本专题整合了C++多线程相关教程,阅读专题下面的的文章了解更多详细内容。

2026.01.21

599

24

热门下载

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

精品课程

更多
相关推荐
/
热门推荐
/
最新课程
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万人学习