MPMCQueue有界多生产者多用户无锁队列

MPMCQueue 是一个用C ++ 11编写的有界多生产者多用户无锁队列。

示例代码

MPMCQueue<int> q(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<T>(size_t capacity);

  Constructs a new MPMCQueue holding items of type T with capacity capacity.

• 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 true on success and false if queue is full.

• bool push(const T &v);

  Enqueue an item using copy construction. Blocks if queue is full.

• template <typename P> bool push(P &&v);

  Enqueue an item using move construction. Participates in overload resolution only if std::is_nothrow_constructible<T, P&&>::value == true. Blocks if queue is full.

• bool try_push(const T &v);

  Try to enqueue an item using copy construction. Returns true on success and false if queue is full.

• template <typename P> bool try_push(P &&v);

  Try to enqueue an item using move construction. Participates in overload resolution only if std::is_nothrow_constructible<T, P&&>::value == true. Returns true on success and false if 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. Return true on sucess and false if the queue is empty.

所有操作都是线程安全的，除了构造和析构函数。

实际原理

Enqeue:

1. Acquire next write ticket from head.
2. Wait for our turn (2 * (ticket / capacity)) to write slot (ticket % capacity).
3. Set turn = turn + 1 to inform the readers we are done writing.

Dequeue:

1. Acquire next read ticket from tail.
2. Wait for our turn (2 * (ticket / capacity) + 1) to read slot (ticket % capacity).
3. 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.