A lock-free FIFO queue

A FIFO (first in, first out) queue is a data structure where the elements are popped out in the same order in which they were inserted. This is in contrast to a stack, where the order is LIFO (last in, first out). In case you need to refresh your memory of these terms, head to https://www.geeksforgeeks.org/queue-data-structure/.

One obvious way for making a queue safer is to use a single lock to make it thread-safe. We could use either an explicit lock (a ReentrantLock) or an intrinsic lock by just making the methods synchronized. 

This will, of course, work; however, it will hurt concurrencyAt any point, only one thread will be able to push or pop the queue. 

Our goal is to increase the concurrency while at the same ...

Get Concurrent Patterns and Best Practices now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.