MPMCQueue有界多生產(chǎn)者多用戶無鎖隊列

MPMCQueue 是一個用C ++ 11編寫的有界多生產(chǎn)者多用戶無鎖隊列。

示例代碼

MPMCQueue 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(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 bool push(P &&v);

  Enqueue an item using move construction. Participates in overload resolution only if?std::is_nothrow_constructible::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 bool try_push(P &&v);

  Try to enqueue an item using move construction. Participates in overload resolution only if?std::is_nothrow_constructible::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.

所有操作都是線程安全的，除了構(gòu)造和析構(gòu)函數(shù)。

實際原理

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.