无锁队列的实现

无锁队列https://coolshell.cn/articles/8239.html

　　链表实现?? cas

?????????????????? 入队时注意 lock free（锁无关）问题 防止死锁

??????????????????????????? Tail

?????????????????? 出队

?????????????????? ???????? 如果是用了指针小心 aba问题（指针内存重用）

?????????????????? ???????? ???????? 解决?

　　　　　　　　　　　　1、使用double-CAS（双保险的CAS）

　　　　　　　　　　　　　　1）一次用CAS检查双倍长度的值，前半部是指针，后半部分是一个计数器。

　　　　　　　　　　　　　　2）只有这两个都一样，才算通过检查，要吧赋新的值。并把计数器累加1。

　　　　　　　　　　　　2、不让那个地址重用

　　　　　　　　　　　　　　使用结点内存引用计数，就是那块内存的引用加1阻止被回收，搞完后再减一，这两个操作都是原子操作

???????? 数组实现?? 环形数组（求模） cas 原子加减

?????????????????? 声明两个计数器，一个用来计数入队的次数，一个用来计数出队的次数。

?????????????????? 入队

　　　　　　　　定位TAIL的位置，double-CAS方法把(TAIL,EMPTY) 更新成 (x,TAIL)。如果找不到(TAIL,EMPTY)，则说明队列满了。再原子入队加

?????????????????? 出队

　　　　　　　　定位HEAD的位置，把(HEAD,x)更新成(EMPTY,HEAD)，并把x返回。同样需要注意，如果x是TAIL，则说明队列为空。再原子出队加

?

?

?

Linux内核的kfifo[编辑]

在Linux内核文件kfifo.h和kfifo.c中，定义了一个先进先出圆形缓冲区实现。如果只有一个读线程、一个写线程，二者没有共享的被修改的控制变量，那么可以证明这种情况下不需要并发控制。kfifo就满足上述条件。kfifo要求缓冲区长度必须为2的幂。读、写指针分别是无符号整型变量。把读写指针变换为缓冲区内的索引值，仅需要“按位与”操作：（指针值 按位与 （缓冲区长度-1））。这避免了计算代价高昂的“求余”操作。且下述关系总是成立：

读指针 + 缓冲区存储的数据长度 == 写指针

即使在写指针达到了无符号整型的上界，上溢出后写指针的值小于读指针的值，上述关系仍然保持成立（这是因为无符号整型加法的性质）。 kfifo的写操作，首先计算缓冲区中当前可写入存储空间的数据长度：

len = min{待写入数据长度,缓冲区长度 - （写指针 - 读指针）}

然后，分两段写入数据。第一段是从写指针开始向缓冲区末尾方向；第二段是从缓冲区起始处写入余下的可写入数据，这部分可能数据长度为0即并无实际数据写入。