FAAArrayQueue

Navigation

API > API/Runtime > API/Runtime/Core

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) Dequeue algorithm: FAA + CAS(item,taken) Consistency: Linearizable enqueue() progress: lock-free dequeue() progress: lock-free Memory Reclamation: Hazard Pointers (lock-free) Uncontended enqueue: 1 FAA + 1 CAS + 1 HP Uncontended dequeue: 1 FAA + 1 CAS + 1 HP

Lock-Free Linked List as described in Maged Michael and Michael Scott's paper: `http://www.cs.rochester.edu/~scott/papers/1996PODC_queues.pdfSimple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms

The paper on Hazard Pointers is named "Hazard Pointers: Safe Memory Reclamation for Lock-Free objects" and it is available here: http://web.cecs.pdx.edu/~walpole/class/cs510/papers/11.pdf

Pedro Ramalhete

Andreia Correia

Syntax

template<typename T>  
class FAAArrayQueue  
Copy full snippet

template<typename T> class FAAArrayQueue

Constructors

Destructors

Classes

Structs

Constants

Variables

Protected

Functions

Public

Static