algorithm

Fetch-And-Add Array Queue

Choose your operating system:

Windows

macOS

Linux

Syntax

Dequeue algorithm

Remarks

Fetch-And-Add Array Queue

Each node has one array but we don't search for a vacant entry. Instead, we use FAA to obtain an index in the array, for enqueueing or dequeuing.

There are some similarities between this queue and the basic queue in YMC: http://chaoran.me/assets/pdf/wfq-ppopp16.pdf but it's not the same because the queue in listing 1 is obstruction-free, while our algorithm is lock-free. In FAAArrayQueue eventually a new node will be inserted (using Michael-Scott's algorithm) and it will have an item pre-filled in the first position, which means that at most, after BUFFER_SIZE steps, one item will be enqueued (and it can then be dequeued). This kind of progress is lock-free.

Each entry in the array may contain one of three possible values:

  • A valid item that has been enqueued;

  • nullptr, which means no item has yet been enqueued in that position;

  • taken, a special value that means there was an item but it has been dequeued;

Enqueue algorithm: FAA + CAS(null,item) /**