无锁环形Buffer

无锁环形队列介绍

无锁环形队列提高并发效率主要依赖以下两点：

环形队列本身是个缓冲区，可以将生产者和消费者解耦，天然具备并发读写的条件
采用CAS（Compare And Swap）避免锁竞争带来的线程阻塞

CAS本质是将检查条件和写入新数据封装为了原子操作

CAS的特点：

CAS本身是一种乐观锁机制，加锁粒度比较小
CAS依赖硬件原子指令保证数据一致性，CAS指令通常是非阻塞的，有点类似spin lock，避免线程阻塞带来的上下文切换成本

C++提供了一种CAS机制：即atomic的两个CAS操作，compare_exchange_weak和compare_exchange_strong，但atomic不保证跨进程原子性，因此无法在共享内存中使用

windows同样提供了CAS机制：InterlockedCompareExchange，这个可以在共享内存中跨进程使用

简单的无锁环形队列实现

一写一读实现（可以使用发布订阅模式实现一写多读）

每个buffer都有一个状态字段，有四个值：empty, filled, writting, reading，分别代表无数据，已写入数据，正在写，正在读

环形队列有两个读写指针，分别代表当前可读和可写的位置

只有更新状态会涉及到cas操作，读写指针更新不需要cas（因为只有一个生产者和一个消费者）

读取时的cas操作： 1. loop - 获取tail数据状态，如果不为filled，则loop重试 - 将当前 (状态) 作为预期值 - cas操作，如果状态没变则更新为 reading 3. 读取数据 4. 状态原子更新为 empty 5. tail+1：只有读端会更新tail指针，直接更新即可

写入时的cas操作： 1. loop - 获取head数据状态，如果不为 empty，则loop重试 - 将当前 (状态) 作为预期值 - cas操作，如果状态没变则更新为 writting 2. 写入数据 3. 状态原子更新为 filled 5. head+1，只有写端会更新head指针，直接更新即可

一种特殊场景下的共享内存实现

一写多读
数据块比较大（8MB），单次memcpy的耗时是500~1000us
读取方希望每次读取都尽量读取最新的数据
不怕丢掉旧数据

方案： 1. 不需要读写指针，只需要一个写指针head 2. 写入端每次尝试往head端写入数据，读取端每次尝试读取head前一个buffer中的数据 3. 读取方不需要考虑删除数据的问题，因为读取方永远尝试读取最新buffer，写入时覆盖写即可

在写快读慢的极端场景，可能会出现以下情况，环形队列两端都被read占据

      read1                read2                无                 read3
        ↓                    ↓                  ↓                    ↓
+-------------------+-------------------+-------------------+-------------------+
|    Buffer_1(tail) |     Buffer_2      |    Buffer_3       |   Buffer_4(head)  |
+-------------------+-------------------+-------------------+-------------------+
        ↑
   write block

每个buffer都有一个状态值：empty, filled

每个buffer都有一个读写计数：-1：写，0：未占用，>0: 读

读取时的cas操作： 1. loop - 获取head-1节点读写计数和状态，如果为empty和-1，loop重试 - 将当前 (状态，读写计数) 作为预期值 - cas操作，比较并更新为（状态, 读写计数+1），不修改状态，只修改读写计数 2. 读取数据 3. 读写计数原子-1

写入时的cas操作： 1. loop - 获取head读写计数，如果不为0，直接loop重试 - 将当前 (状态，读写计数) 作为预期值 - cas操作，比较并更新为（状态, 读写计数为-1） 3. 写入数据 4. 状态和读写计数原子更新为（filled, 0）