要求: 实现一个 single-producer single-consumer 的 lock-free ring buffer
思路:
因为只有一个生产者和一个消费者,我们可以通过想办法保证生产者和消费者互不影响对方的状态来消除数据竞争。
设计 ring buffer 时需要考虑如何代表 empty
状态。通常来说我们会使用 start = end = -1
来代表空状态,但是这样的设计会使得 push
和 pop
操作存在同时修改 start
和 end
的可能性。
我们采用留空一个 slot
的方式(始终有一个 slot
不存放元素;为空时,start = end = indexSlot
)来表示空状态。start
永远指向被留空的slot
,而(end + 1) % capacity
永远指向新元素将被存储的位置。