MPMCQueue 是一个用C ++ 11编写的有界多生产者多用户无锁队列。
示例代码
MPMCQueueq(10); auto t1 = std::thread([&] { int v; q.pop(v); std::cout << "t1 " << v << "\n"; }); auto t2 = std::thread([&] { int v; q.pop(v); std::cout << "t2 " << v << "\n"; }); q.push(1); q.push(2); t1.join(); t2.join();
使用
-
MPMCQueue(size_t capacity); Constructs a new
MPMCQueueholding items of typeTwith capacitycapacity. -
void emplace(Args &&... args);Enqueue an item using inplace construction. Blocks if queue is full.
-
bool try_emplace(Args &&... args);Try to enqueue an item using inplace construction. Returns
trueon success andfalseif queue is full. -
bool push(const T &v);Enqueue an item using copy construction. Blocks if queue is full.
-
templatebool push(P &&v); Enqueue an item using move construction. Participates in overload resolution only if
std::is_nothrow_constructible. Blocks if queue is full. -
bool try_push(const T &v);Try to enqueue an item using copy construction. Returns
trueon success andfalseif queue is full. -
templatebool try_push(P &&v); Try to enqueue an item using move construction. Participates in overload resolution only if
std::is_nothrow_constructible. Returnstrueon success andfalseif queue is full. -
void pop(T &v);Dequeue an item by copying or moving the item into
v. Blocks if queue is empty. -
bool try_pop(T &v);Try to dequeue an item by copying or moving the item into
v. Returntrueon sucess andfalseif the queue is empty.
所有操作都是线程安全的，除了构造和析构函数。
实际原理
Enqeue:
- Acquire next write ticket from head.
- Wait for our turn (2 * (ticket / capacity)) to write slot (ticket % capacity).
- Set turn = turn + 1 to inform the readers we are done writing.
Dequeue:
- Acquire next read ticket from tail.
- Wait for our turn (2 * (ticket / capacity) + 1) to read slot (ticket % capacity).
- Set turn = turn + 1 to inform the writers we are done reading.
参考资料:
- Dave Dice. PTLQueue : a scalable bounded-capacity MPMC queue.
- Dmitry Vyukov. Bounded MPMC queue.
- Massimiliano Meneghin et al. Performance evaluation of inter-thread communication mechanisms on multicore/multithreaded architectures.
- Oleksandr Otenko. US 8607249 B2: System and method for efficient concurrent queue implementation.
- Paul E. McKenney. Memory Barriers: a Hardware View for Software Hackers.
