ConcurrentLinkedQueue
ConcurrentLinkedQueue is a high-performance, non-blocking queue based on the Maged M. Michael and Michael L. Scott algorithm for lock-free FIFO queues.
Source Code #
Mechanism: The “Lock-Free” Node Algorithm #
In a ConcurrentLinkedQueue, threads do not use a ReentrantLock. Instead, they use atomic CAS (Compare-And-Swap) operations on the head, tail, and next pointers to update the queue. This is a crucial difference from BlockingQueue implementations: it never blocks.
// In ConcurrentLinkedQueue, these never block
queue.offer(e); // Always succeeds (returns true)
queue.poll(); // Returns null if empty (never blocks)
The algorithm is complex because it allows the tail pointer to be “lazy”—it doesn’t always point to the actual last node. It only updates the tail after several insertions, which reduces contention on the tail pointer itself.
Canonical Usage #
When to use: Use ConcurrentLinkedQueue when you have many threads performing high-frequency insertions and removals and you don’t need to block if the queue is empty. It is ideal for “sharing” work among threads when you can afford to poll and retry.
Common Patterns:
- Work Sharing: In systems where a producer is much faster than consumers and can afford to “dump” work into a high-speed, non-blocking queue.
- Unordered Processing: It is excellent for “worker thread” pools that check for new work and proceed if it’s available.
// Unbounded non-blocking queue
Queue<Integer> work = new ConcurrentLinkedQueue<>();
// Fast put (never blocks)
work.offer(5);
// Fast take (returns null if empty, never blocks)
Integer item = work.poll();
if (item != null) {
process(item);
}
Performance Trade-offs #
- Pros: Outstanding scalability on multi-core systems. No thread suspension or context switching due to locking.
- Cons:
size()is anO(n)operation (linear scan). Every insertion allocates aNode. It cannot block, so if you need a consumer to wait for work, you must implement the waiting logic manually (e.g., polling or using aSemaphore).