共计 1072 个字符,预计需要花费 3 分钟才能阅读完成。
导读 | 无锁队列是 lock-free 中最基本的数据结构,一般应用在需要一款高性能队列的场景下。 |
对于多线程用户来说,无锁队列的入队和出队操作是线程安全的,不用再加锁控制。
队列每个开发者都知道,那么什么又是无锁队列呢?字面理解起来就是一个无锁状态的队列,多个线程(消费者)同时操作数据的时候不需要加锁,因为加 / 解锁都是一个很消耗资源的动作。
我们先看一下无锁队列的底层实现数据结构。
无锁队列底层的数据结构实现方式主要有两种:数组 和 链接。
在首次初始化时,需要申请一块连接的大的内存。读写数据直接从数据的指定位置操作即可,时间复杂度为 O(1)。
缺点:数组长度有限,一旦数组索引位置写满,则无法继续写入,即队列有上限。
不用像数组一样,刚开始就申请一块连接的大的内存空间。只有在每次写时数据的时候,申请这个数据节点大小的内存即可,这样就可以实现无限的写入,没有长度限制问题。
缺点:每次写数据都要申请内存,在写的场景,最差的情况是多少个数据就申请多少次内存,而每次申请都是一个消耗资源的动作。
可以看到无锁底层的实现的不同各有优势。多数据情况下,我们都采用链表来实现无锁队列,主要原因就是写入可以没有长度的限制。相比每次申请都要费时来说,满足前面的条件是我们最基本的要求。当然主要还是真正的使用场景。
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 汇编指令。有了这个操作,我们就可以用其来实现各种无锁的数据结构。
无锁队列也属于队列的一种,所以大部分队列的使用场景都可以使用它来代替其它有锁队列, 无锁队列通过不加锁的方式提高队列性能。
![post-qrcode](https://www.xgss.net/wp-content/uploads/2023/07/二维码-微信公众号256x256.jpg)