前言

为什么需要无锁队列呢？我们知道，多核心优化是现在游戏开发的一个重点课题，无论是工程实践也好，研究算法也罢，将工作并行化交由多线程去做是一个非常普遍的场景。对于这种场景，我们通常会采用线程池+命令队列的方式去实现，其中的命令队列就会使用互斥锁或是无锁队列。并且由于命令队列的读写是较轻量级的操作，采用无锁队列的性能要高于有锁的操作。因此，实现无锁队列等无锁数据结构，可以看作是迈入多线程编程的基石。

推荐视频：https://www.bilibili.com/video/BV1354y1b7nz/

问题描述

无锁队列的典型应用场景是同时存在单（多）线程写入与单（多）线程读取。那么，为什么原始的队列会存在问题呢？我们来看原始队列的入队与出队伪代码（省略了边界判断）

struct Node{
    
    void *data;
    Node *next;
};

void Enqueue(Node *node){
    
    m_Tail->next = node;
    m_Tail = node;
}

Node* Dequeue(){
    
    Node * res = m_Head;
    m_Head = m_Head->next;
    return res;
}

入队与出队皆有两步操作，如果存在两个以上相同的线程同时进行写入或读取，便可能会出现在完成了第一步操作后，其他线程修改了Head或Tail指针，导致完全无法预料的结果。例如下列情况，两个线程同时写入，导致Tail指针失去与队列的链接，后加的节点从Head开始就访问不到了。

//           线程A                     线程B                   实际情况
                                                       nodeC            tail = nodeC
      head->next = nodeA                               nodeC -> nodeA   tail = nodeC
                               tail->next = nodeB      nodeC -> nodeB   tail = nodeC
                               tail = nodeB            nodeC -> nodeB   tail = nodeB
      tail = nodeA                                     nodeC -> nodeB   tail = nodeA

解决方法是在读写之前加锁，确保同一时间只有一个线程在进行读写，或是使用CPU提供的原子操作（atomic operation），一次性完成对Head或Tail指针的读写，实现无锁同步。

原子操作

在质子中子发现之前，人们认为原子就是世界上最基本的粒子了，原子一词便有了“不可分割”的含义。顾名思义，原子操作就是指不可分割的操作，CPU的一个线程在执行原子操作时，不会被其他线程中断或抢占。

典型的原子操作及示意代码如下：

• Load / Store： 读取与保存。
• Test and Set：针对bool变量，如果为true则返回true，如果为false，则将变量置为true并返回false。

bool TestAndSet(bool * flag){
    
    bool res = *flag;
    *flag = true;
    return res;
}

• Clear: 将bool变量设为false。
• Exchange：将指定位置的值设置为传入值，并返回其旧值。

template <typename T>
T Exchange(T* addr, const T& newVal){
    
    T oldVal = *addr;
    *addr = newVal;
    return oldVal;
}

Compare And Swap（CAS）：将指定位置的值与期望值比较，如果相等则赋值为新值，如果不等则将期望值设置为自身。返回是否设置成功。

template <typename T>
bool CompareAndSwap(T* addr, T& expected, const T& desired){
    
    if(*addr == expected){
    
        *addr = desired;
        return true;
    }
    expected = *addr;
    return false;
}

• 注意CAS有weak和strong两种，weak版本在某些情况下即使满足条件也会返回false，所以一般只会在循环判断中使用，其他情况都使用strong版本。
• Fetch And 加减乘除系列：对指定位置的值使用传入参数执行加减乘除，并返回旧值。

这里使用最简单的i++操作来比较说明一下为什么需要原子操作，C++中一条i++语句，会生成三条汇编指令。

int i = 0;
i++;

mov         eax,dword ptr [i]   // 将i加载到eax寄存器
add         eax,1  // eax中的值加一
mov         dword ptr [i],eax  // 将eax中的值赋值到i的地址

如果有两个线程同时对一个变量i=0执行i++操作，最终结果很可能是1而不是2，因为多线程并行时，i的值会加载到不同的寄存器，然后分别对寄存器中的值加一并取出，导致落后的线程覆盖了领先线程的结果。这种现象被称为竞争条件（Race condition）。如果我们使用windows提供的原子自增函数_InterlockedIncrement，生成的汇编代码如下

int i = 0;
_InterlockedIncrement((volatile long *)&i);

mov         eax,1     // eax加载1
lock xadd   dword ptr [i],eax   // xadd的作用是交换两个操作数的值，并将相加结果保存到前者
// 完成对i所在地址数据的自增操作

一条指令便完成了i++的操作，并且lock指令还会锁定操作的内存地址，避免了可能存在的竞争条件。（同时也可以看出，原子操作在CPU内部的实现还是加锁，不过是硬件层面的加锁，开销较小）

使用CAS实现无锁队列

现在我们开始实现无锁队列吧。先定义数据结构

#pragma once
#include <windows.h>
#include <windef.h>
#include <intrin.h>
#include <emmintrin.h>

using AtomicWord = intptr_t;

struct AtomicNode
{
    
    volatile AtomicWord _next;
    void* data;
};

class AtomicQueue
{
    
    volatile AtomicWord _tail;
    volatile AtomicWord _head;
public:
    AtomicQueue();
    ~AtomcQueue();
    void Enqueue(AtomicNode* node);
    AtomicNode* Dequeue();
}

使用intptr_t保存我们的指针变量，每个节点使用指针保存数据，队列包含一个头指针和一个尾指针。会用到两种原子操作（PS：本文基于64位环境，指针长度为64位，如需在32位环境下使用请自行替换为32位版本函数）：

static inline AtomicWord AtomicExchangeExplicit(volatile AtomicWord* p, AtomicWord val)
{
    
    return (AtomicWord)_InterlockedExchange64((volatile LONGLONG*)p, (LONGLONG)val);
}

static inline bool AtomicCompareExchangeStrongExplicit(volatile AtomicWord* p, AtomicWord* oldval, AtomicWord newval)
{
    
    return _InterlockedCompareExchange64((volatile LONGLONG*)p, (LONGLONG)newval, (LONGLONG)*oldval) != 0;
}

我们使用一个dummy节点，这样可以省去许多的边界判断

AtomicQueue() {
    
        AtomicNode* dummy = new AtomicNode();
        dummy->_next = 0;
        _tail = (AtomicWord)dummy;
        _head = (AtomicWord)dummy;
    }
    ~AtomicQueue() {
    
        AtomicNode* dummy = (AtomicNode*)_head;
        delete dummy;
    }

入队使用Exchange，出队使用CAS自旋

 void Enqueue(AtomicNode* node) {
    
        AtomicNode* prev;
        node->_next = 0;
        prev = (AtomicNode*)AtomicExchangeExplicit(&_tail, (AtomicWord)node);
        prev->_next = (AtomicWord)node;
    }

    AtomicNode* Dequeue() {
    
        AtomicNode* res, * next;
        void* data;
        AtomicWord head = _head;
        AtomicWord newHead;
        do
        {
    
            // 出队的时候最后剩下的是最后一次入队的节点
            res = (AtomicNode*)head;
            next = (AtomicNode*)res->_next;
            if (next == nullptr)
                return nullptr;
            data = next->data;
            newHead = (AtomicWord)next;
            //  比较_head指针是否是我们之前获取的，成功则设置newHead，失败则自旋
        } while (!AtomicCompareExchangeStrongExplicit(&_head, &head, newHead));

        res->data = data;
        return res;
    }

从原理上来说并不难理解，入队就是使用新的节点与原来的尾节点交换，出队就是使用CAS判断我们缓存的头节点是否与队列头节点相同（不同的话说明被其他线程修改了）。

不过我们的Head与Tail指针都加了volatile关键字，这是什么意思呢？

volatile与常量优化

C++编译器会为我们做许多优化，但某些时候这些优化会造成意外的结果。我们在出队时使用了循环判断

do{
    
    res = head;
    newHead = res->next;
}
while(!CAS(_head, head, newHead));

也就是说我们一直在判断_head 是否等于head，而head最初也是等于_head的。编译器并不知道可能有另外的线程在修改_head的值，因此可能会将_head与head的比较优化掉，只从内存中读取一次_head的值存放进寄存器，随后便一直使用寄存器中的数据，使得我们的自旋等待失效。这便是常量优化。

常量优化的原因是寄存器的读写速度远高于内存，编译器会减少从内存读取数据的次数。而volatile关键字就是告诉编译器，不要对这个变量进行常量优化，每次都去内存中读取。

ABA问题

虽然上面我们已经实现了可用的无锁队列，但还有一个潜在的问题没有解决，那就是ABA问题。什么是ABA问题呢，照样用一个例子来说明

//         线程A                    线程B                        队列
                                                       A(0x114)->B(0x514)  Head = B
   head = B, newhead = C                            
                                出队B， delete B         
                                出队A， delete A
                                new D(0x514), 入队D
                                new E(0x810), 入队E    E(0x810)->D(0x514)  Head = D
CAS(Head, head, newhead)通过                           E(0x810)->D(0x514)  Head = C

因为我们使用CAS比较的是地址，而使用new和delete管理内存，内存地址在删除后可能被操作系统回收后重新分配，这样就会出现先获取了Head地址，在CAS的时候由于新的Head是回收后重新分配出来的相同地址，比较通过，但指向地址的内容却不同，因而出错的情况。

解决ABA问题有两种思路，一种是使用环形缓冲，其实就是预先分配了内存的数组，将Head和Tail指针替换为下标来移动，避免内存重复分配。另一种则是使用Double CAS。

Double CAS

Double CAS的思想是为地址增加引用计数，使用双倍大小的头指针，在原指针后附加一个计数器，每次出队时将计数器加一。这样即使出现ABA问题，由于计数器对不上，CAS也就不会通过了。

//         线程A                         线程B                        队列
                                                            A(0x114)->B(0x514)  Head = (B,0)
   head = (B,0), newhead = (C,1)                            
                                     出队B， delete B         
                                     出队A， delete A
                                     new D(0x514), 入队D
                                     new E(0x810), 入队E    E(0x810)->D(0x514)  Head = (D,2)
   CAS(Head, head, newhead) 失败   

Double CAS 无锁队列

PS：下面实现基于64位环境，如需在32位环境使用请替换为64位版函数

// 必须16字节对齐，否则_InterlockedCompareExchange128会报错
struct alignas(16) AtomicWord2
{
    
    AtomicWord lo, hi;
};

static inline bool AtomicCompareExchangeStrongExplicit(volatile AtomicWord2* p, AtomicWord2* oldval, AtomicWord2 newval)
{
    
    return _InterlockedCompareExchange128((volatile LONGLONG*)p, (LONGLONG)newval.hi, (LONGLONG)newval.lo, (LONGLONG*)oldval) != 0;
}

static inline AtomicWord2 AtomicExchangeExplicit(volatile AtomicWord2* p, AtomicWord2 newval)
{
    AtomicWord2 oldval;
    oldval.lo = 0;
    oldval.hi = newval.hi - 1;
    // 没有128位的Exchange函数了，只能用CAS封装一下
    while (!AtomicCompareExchangeStrongExplicit(p, &oldval, newval));
    return oldval;
}

修改后的队列操作

class AtomicQueue
{
    
    volatile AtomicWord _tail;
    volatile AtomicWord2 _head;
    ......
}

    AtomicQueue() {
    
        AtomicNode* dummy = new AtomicNode();
        AtomicWord2 w;
        w.lo = (AtomicWord)dummy;
        w.hi = 0;
        dummy->_next = 0;
        _head = w;
        _tail = (AtomicWord)dummy;
    }

    void Enqueue(AtomicNode* node) {
    
        AtomicNode* prev;
        node->_next = 0;
        prev = (AtomicNode*)AtomicExchangeExplicit(&_tail, (AtomicWord)node);
        prev->_next = (AtomicWord)node;
    }

    AtomicNode* Dequeue() {
    
        AtomicNode* res, * next;
        void* data;
        AtomicWord2 head = _head;
        AtomicWord2 newHead;
        do
        {
    
            res = (AtomicNode*)head.lo;
            next = (AtomicNode*)res->_next;
            if (next == nullptr)
                return nullptr;
            data = next->data;
            newHead.lo = (AtomicWord)next;
            newHead.hi = head.hi + 1;

        } while (!AtomicCompareExchangeStrongExplicit(&_head, &head, newHead));

        res->data = data;
        return res;
    }

大功告成！

仍然存在的一些问题

我们使用了dummy节点，这样可以省去一些边界条件的判断，但代价是每次出队的节点并不是入队的那一个，而是数据指针装在前一个入队的节点里出队。因此我们不能太快回收节点使用的内存，否则就会造成访问冲突。比较好的方法是使用对象池来缓存节点，不够用的时候就申请新节点，每次出队使用完成后将旧节点放回池中等待下一次使用。

结语

实现了无锁队列，只是迈向多线程开发的第一步。一通研究下来，最大的感触就是计算机的基础知识真的是非常重要，尤其是计算机体系结构、操作系统等方向的知识。

整理了一些最新LinuxC/C++服务器开发/架构师面试题、学习资料、教学视频和学习路线脑图（资料包括C/C++，Linux，golang技术，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒体，CDN，P2P，K8S，Docker，TCP/IP，协程，DPDK，ffmpeg等），免费分享有需要的可以自行添加学习交流群960994558或VX:lingsheng_1314领取！~

希望这篇文章能够帮到你，如果有写的不对的地方，也欢迎在评论区指出和交流。