File MPMCQueue.h

↰ Parent directory (ADS/concurrent)

A bounded queue of many producers and many consumers, beyond the book: the circular vector of Vyukov, whose places carry a sequence number besides the item.

Definition (ADS/concurrent/MPMCQueue.h)

Detailed Description

The place of the index i, i mod C for a capacity C that is a power of 2, holds the sequence i when it is free for the push of index i, i + 1 when it holds the item of index i, and i + C when that item has been taken and the place waits for the push of index i + C. A producer reads the tail p and the sequence s of its place: if s = p it claims the index by a compare-and-swap of the tail from p to p + 1, builds the item and publishes it by the sequence p + 1 (a release); if s < p the queue is full; if s > p another producer took p, and it reads the tail again. A consumer does the same on the head h with the sequence h + 1, and frees the place by the sequence h + C. The tail and the head sit on lines of cache of their own, so that producers and consumers meet only at the places they share, one read-modify-write per operation; no item is ever read before its producer published it, nor a place reused before its consumer freed it. As in the queue of Vyukov, a thread that stops between its compare-and-swap and its publication holds up the others when they come round to that place. The contracts [see File Contract.h]: the capacity is a power of 2, at least 2. D. Vyukov, Bounded MPMC queue, 2010, https://www.1024cores.net/home/lock-free-algorithms/queues/ bounded-mpmc-queue

  1. Nikolaev, A scalable, portable, and memory-efficient lock-free FIFO queue, International Symposium on Distributed Computing (DISC), LIPIcs 146, 28:1-28:16, 2019, doi:10.4230/LIPIcs.DISC.2019.28 (the rings with a cycle per place)

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Classes