framework-nd之读写线程隔离的FIFO队列

2019-01-02

1. 设计

1.1. 想法

设计框架(背景见链接)的时候，经常会碰到生产者消费者模型，当时就想整型以机器字长对齐，其赋值和读取都是原子的。举个例子

1 2	size_t i = 0; i = 0xFFFF;

在机器字长对齐的情况下，任何时候，a要么是0，要么是0xFFFF，不会出现0xFF00。（如果是pack（1），上面就不成立了）

因此就有个很天然的想法，如果生产者和消费者各一个，分属不同线程，生产者只修改写偏移量，消费者只改读偏移量，两个偏移量设为volatile保证其只能从内存读取(volatile不能保证线程安全，这里的安全是通过内存总线保证偏移量的完整性实现的)，是不是能实现一个FIFO的循环队列，不加锁的情况下也能保证队列内数据的完整性。

1.2. 读写分析

设想一下，如果生产者写偏移量不更新，消费者首先判断当前无数据可读；
w=r

生产者将数据写入，然后才更新写偏移量，整个过程只有写偏移量修改修改后，消费者才能开始读。

1.3. 偏移量的处理

以上写/读流程都工作得很好，直到写偏移量>buffer大小

因为写之前要判断剩下多少空间可写

1 2	size_t usedSize = writeIndexM - readIndexM; size_t leftSize = sizeM - usedSize;

如果将writeIndexM限制于[0, sizeM)，因为readIndexM只能由消费者改，那么下次写，这条公式就不对了。

怎么处理呢？与其做复杂的判断，不如不限偏移量的范围，就让writeIndexM和readIndexM只增不减，即使是溢出，因为sizeM远小于量偏移量的取值范围，上面的公式还是成立的。

这样子，带来另外一个问题，如何将writeIndexM映射回buffer的偏移量呢？很简单，对sizeM取余就好。这样对sizeM会有限制，比如32bit，因为有溢出的问题，推导要求 (0xFFFFFFFF + 1) % sizeM = 0 % sizeM = 0，即

fomula

也就是说sizeM必须是2的倍数

至此，这个循环的buffer就成型了，一个线程读一个线程写，不用加锁，互不干扰。如果多个生产者，需要在生产者侧加锁。消费者类似。

2. 实现

源代码，32位及以上适用：

3. 后记

当时查过，size_t的赋值在机器字长对齐的情况下，部分平台可能会由多条指令实现的，这种平台(网上也没说是什么平台，估计比较小众)不适用。根据笔者的测试，x86/x64是ok的，arm的默认thumb指令集也ok。请测试使用。