lock-free-multi-producer-single-consumer-ring-buffer

一个无锁的多生产者、单消费者（MPSC）环形缓冲区。针对发送和接收消息“突发”进行了优化。也可以用作环形队列。这是 Mindaugas Rasiukevicius 的 ringbuf 的 Rust 版本。此版本源自的原始 C 代码“版权所有 (c) 2016-2017 Mindaugas Rasiukevicius”。

许可

此项目的许可协议为 BSD-2-Clause。

lib.rs:

lock-free-multi-producer-single-consumer-ring-buffer

用法

extern crate lock_free_multi_produce_single_consume_ring_buffer;

use ::lock_free_multi_produce_single_consume_ring_buffer::*;

let (ring_buffer_consumer, ring_buffer_producers) = RingBuffer::new(capacity, number_of_producers);

// For each producer thread.
let ring_buffer_producer = ring_buffer_producers.get(0);

let result = ring_buffer_producer.acquire(length);
// result is `None` if length was too much; try a shorter length.

let slice_guard = result.unwrap();

// Dereferences to a slice.
// slice_guard[0] = some_value;

// Produce (relinquishes the slice).
drop(slice_guard);

ring_buffer_producer.produce();

// For each consumer thread.
let slice_guard = ring_buffer_consumer.consume();

// Iterate, move out, etc.
println!("should be `some_value`", slice_guard.move_out(slice_guard.len())[0]);

// Releases the slice so producers can now use it.
drop(slice_guard);

一旦所有生产者和消费者都被丢弃，则环形缓冲区底层的内存将被释放，并且其中任何未消费的项都将安全地 Drop。

以下文档的原始版权为“版权所有 (c) 2016-2017 Mindaugas Rasiukevicius”。

原子多生产者单消费者环形缓冲区，支持连续范围操作，便于用于消息传递。

有三个偏移量（“想想时钟的指针”）：

• NEXT：标记可用空间的开始，
• WRITTEN：实际写入数据的点。
• 观察到的 READY：数据准备好写入的点。

生产者

观察并保存“下一个”偏移量，然后通过原子地前进“下一个”偏移量从环形缓冲区请求 N 字节。一旦数据写入到“预留”的缓冲区空间，线程清除保存的值；这些观察到的值用于计算 ready 偏移量。

消费者

在 written 和 ready 偏移量之间写入数据并更新 written 值。消费者线程扫描生产者观察到的最低值。

关键不变性

生产者不能超过已写入的偏移量。

不允许生产者赶上消费者。

只有消费者可以赶上生产者，即设置已写入的偏移量等于下一个偏移量。

循环回绕

如果由于缓冲区末尾空间不足，生产者无法获取请求的长度，则它会进行循环回绕。

在下一个偏移量中的 WrapLockBit 用于锁定 end 偏移量。

如果一个生产者停滞，而一对生产者和消费者都成功回绕并将 next 偏移量设置为第一个生产者的过时值，从而让它执行成功的比较和交换（CAS），这将违反不变性，因此会存在 ABA 问题。在 next 偏移量中有一个计数器（通过 WrapCounter 遮蔽）用于防止这个问题。在回绕时，它会增加。

同样的 ABA 问题也可能导致过时的 ready 偏移量，这可能会被消费者观察到。算法在前进 next 和 seen 值之前设置 WrapLockBit，并在成功前进后清除此位；这确保消费者只能观察到稳定的 ready。