template<
typename T>
class FAAArrayQueue< T >
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/1996_PODC_queues.pdf Simple, 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
- Author
- Pedro Ramalhete
-
Andreia Correia
1.9.8