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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.