C++无锁队列

越甲八千

于 2025-03-19 14:35:15 发布

阅读量384

点赞数 3

分类专栏：【道阻且长C++】文章标签： c++

本文链接：https://blog.csdn.net/doubleintfloat/article/details/146370385

版权

【道阻且长C++】专栏收录该内容

202 篇文章

订阅专栏

无锁队列是一种在多线程环境下实现高效数据共享的队列数据结构，它不使用传统的锁机制（如互斥锁）来保证线程安全，而是通过原子操作和内存屏障等技术来实现并发访问的正确性。以下是关于无锁队列的详细介绍：

特点

高性能：由于避免了锁的开销，减少了线程上下文切换和阻塞等待的时间，因此在高并发场景下，无锁队列的性能通常优于使用锁的队列。
低延迟：线程可以无阻塞地访问队列，不会因为等待锁而产生延迟，能够快速地进行入队和出队操作。
实现复杂：无锁队列的实现需要深入理解原子操作和内存模型，处理好数据竞争和并发访问的问题，代码的复杂度较高。
无死锁风险：由于不使用锁，不存在死锁的问题，提高了系统的稳定性。

实现原理

无锁队列通常基于原子操作来实现，例如使用 std::atomic 类型的变量来表示队列的头指针和尾指针。通过原子操作（如 compare_and_swap，简称 CAS）来确保在多线程环境下对头指针和尾指针的修改是原子的，从而避免数据竞争。

C++ 实现示例

以下是一个简单的基于链表的无锁队列的 C++ 实现示例：

#include <iostream>
#include <atomic>
#include <thread>
#include <vector>

// 定义队列节点
template<typename T>
struct Node {
    T data;
    std::atomic<Node*> next;
    Node(const T& value) : data(value), next(nullptr) {}
};

// 定义无锁队列
template<typename T>
class LockFreeQueue {
private:
    std::atomic<Node<T>*> head;
    std::atomic<Node<T>*> tail;

public:
    LockFreeQueue() {
        Node<T>* dummy = new Node<T>(T());
        head.store(dummy);
        tail.store(dummy);
    }

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

    // 入队操作
    void enqueue(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        Node<T>* oldTail = tail.load(std::memory_order_relaxed);
        while (!tail.compare_exchange_weak(oldTail, newNode, std::memory_order_release, std::memory_order_relaxed)) {}
        oldTail->next.store(newNode, std::memory_order_release);
    }

    // 出队操作
    bool dequeue(T& value) {
        Node<T>* oldHead = head.load(std::memory_order_relaxed);
        Node<T>* next = oldHead->next.load(std::memory_order_acquire);
        if (next == nullptr) {
            return false;
        }
        value = next->data;
        if (head.compare_exchange_strong(oldHead, next, std::memory_order_release, std::memory_order_relaxed)) {
            delete oldHead;
            return true;
        }
        return false;
    }
};

// 测试代码
void producer(LockFreeQueue<int>& queue) {
    for (int i = 0; i < 10; ++i) {
        queue.enqueue(i);
        std::this_thread::sleep_for(std::chrono::milliseconds(100));
    }
}

void consumer(LockFreeQueue<int>& queue) {
    int value;
    for (int i = 0; i < 10; ++i) {
        while (!queue.dequeue(value)) {
            std::this_thread::yield();
        }
        std::cout << "Consumed: " << value << std::endl;
    }
}

int main() {
    LockFreeQueue<int> queue;

    std::thread producerThread(producer, std::ref(queue));
    std::thread consumerThread(consumer, std::ref(queue));

    producerThread.join();
    consumerThread.join();

    return 0;
}

代码解释

Node 结构体：表示队列中的节点，包含一个数据元素 data 和一个指向下一个节点的原子指针 next。
LockFreeQueue 类：实现了无锁队列的主要功能，包含头指针 head 和尾指针 tail。
- 构造函数：创建一个虚拟节点，并将头指针和尾指针都指向该节点。
- 析构函数：释放队列中所有节点的内存。
- enqueue 函数：将新元素插入到队列尾部，使用 compare_exchange_weak 原子操作来更新尾指针。
- dequeue 函数：从队列头部移除一个元素，使用 compare_exchange_strong 原子操作来更新头指针。
producer 函数：模拟生产者线程，向队列中插入元素。
consumer 函数：模拟消费者线程，从队列中取出元素。