认识无锁队列

无锁队列lock-free 中最基本的数据结构,一般应用在需要一款高性能队列的场景下。

对于多线程用户来说,无锁队列的入队和出队操作是线程安全的,不用再加锁控制

什么是无锁队列

队列每个开发者都知道,那么什么又是无锁队列呢?字面理解起来就是一个无锁状态的队列,多个线程(消费者)同时操作数据的时候不需要加锁,因为加/解锁都是一个很消耗资源的动作。

实现原理

我们先看一下无锁队列的底层实现数据结构。

数据结构

无锁队列底层的数据结构实现方式主要有两种:数组链接

数组

在首次初始化时,需要申请一块连接的内存。读写数据直接从数据的指定位置操作即可,时间复杂度为O(1)。

缺点:数组长度有限,一旦数组索引位置写满,则无法继续写入,即队列有上限。

链表

不用像数组一样,刚开始就申请一块连接的大的内存空间。只有在每次写时数据的时候,申请这个数据节点大小的内存即可,这样就可以实现无限的写入,没有长度限制问题。

缺点:每次写数据都要申请内存,在写的场景,最差的情况是多少个数据就申请多少次内存,而每次申请都是一个消耗资源的动作。

可以看到无锁底层的实现的不同各有优势。多数据情况下,我们都采用链表来实现无锁队列,主要原因就是写入可以没有长度的限制。相比每次申请都要费时来说,满足前面的条件是我们最基本的要求。当然主要还是真正的使用场景。

CAS

CAS 是 Compare And Swap 的简称, 属于 乐观锁,这是一个并发同步原语. 伪代码如下:

bool compare_and_swap(int *reg, int oldval, int newval)
{
    int reg_val = *reg;
    if(reg_val == oldval)
    {
        *reg = newval;
        return true;
    }
    return false;
}

CAS操作有三个参数,分别表示 内存值V旧的预期值A 和 修改后的更新值B

判断变量内存某个位置的值是否为预期值,如果是则更改为新的值,并返回true,这个过程是原子性操作。如果修改失败,可能需要重试再次执行CAS操作,直到修改成功,一般称此过程为自旋。可以看到每次调用 CAS 命令前需要先读取旧值 oldval。

现在几乎所有的CPU指令都支持CAS的原子操作,X86下对应的是 CMPXCHG 汇编指令。有了这个操作,我们就可以用其来实现各种无锁的数据结构。

使用场景

无锁队列也属于队列的一种,所以大部分队列的使用场景都可以使用它来代替其它有锁队列,无锁队列通过不加锁的方式提高队列性能。

参考资料