Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms
📜 Abstract
We present a new practical non-blocking queue algorithm. Our algorithm is a significant improvement over previous algorithms in terms of simplicity (more comprehensible code, meeting more intuitive specifications) and practicality (faster than previous queue algorithms across a broad range of performance). In addition, our algorithm provides support for both blocking and non-blocking operation and is distinguished by its ability to allow block-free implementations of queue operations based on shared memory. Finally, the algorithms are easy to prove correct and naturally lend themselves to a performance improvement technique called 'memory garbage collection'.
✨ Summary
This paper presents significant advancements in the design of concurrent data structures, specifically focusing on queues. The proposed algorithms provide a more straightforward and efficient approach to implementing both non-blocking and blocking queue operations. Their key contribution is the simplicity and practicality they offer compared to previous queue algorithms, achieving better performance metrics across various benchmarks.
In particular, the algorithms allow operations to proceed without blocking, leveraging shared memory effectively. This makes them particularly useful in contexts where thread contention could otherwise degrade performance. The paper’s influence on concurrent data structure research and applications is evident in multiple subsequent works that reference it: 1. Moir, M., & Nussbaum, D. (1999). Composite syncronization. ACM Digital Library. 2. Harris, T. L. (2001). A pragmatic implementation of non-blocking linked lists. SpringerLink. 3. Herlihy, M., & Shavit, N. (2008). The Art of Multiprocessor Programming. This book refers to the algorithms introduced by Michael and Scott.
The practical applications of these algorithms extend to improving the efficiency of systems that rely heavily on concurrent operations, making them a staple in the study of concurrent programming.