Two ends, two pointers
A concurrent linked queue stores elements in a singly linked list with a head pointer for dequeues and a tail pointer for enqueues. Because enqueue touches the tail and dequeue touches the head, the two operations usually work on different nodes and need not block each other.
Non blocking progress
Instead of locks, the queue uses compare and swap to publish changes:
- An enqueuer links a new node off the last node, then swings the tail forward with a compare and swap
- A dequeuer reads the head, advances it past the first real node with a compare and swap, and returns the value
- If a compare and swap fails because another thread won the race, the loser simply retries with the fresh state
The sentinel trick
A permanent dummy node sits at the head so the head and tail never become null. This removes special cases for the empty queue and lets head and tail advance without ever pointing at nothing.
Key idea
A concurrent linked queue uses compare and swap on separate head and tail pointers with a sentinel node, so enqueue and dequeue progress without locks.