2004/03/22 by Håkan Sundell, Philippas Tsigas · 46 citations
Computer Science · #Blocking (statistics) #Computer network #Computer science #Concurrency #Concurrency control #Concurrent data structure #Critical section #Distributed computing #Distributed systems and fault tolerance #Dynamic priority scheduling #Implementation #Interconnection Networks and Systems #Lock (firearm) #Mutual exclusion #Operating system #Parallel computing #Priority ceiling protocol #Priority inheritance #Priority queue #Programming language #Quality of service #Queue #Rate-monotonic scheduling #Real-Time Systems Scheduling #Synchronization (alternating current) #Thread (computing)
paper · doi:10.1109/ipdps.2003.1213189
openalex publication_date 2004/03/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We present an efficient and practical lock-free implementation of a concurrent priority queue that is suitable for both fully concurrent (large multi-processor) systems as well as pre-emptive (multi-process) systems. Many algorithms for concurrent priority queues are based on mutual exclusion. However, mutual exclusion causes blocking which has several drawbacks and degrades the system's overall performance. Non-blocking algorithms avoid blocking, and are either lock-free or wait-free. Previously known non-blocking algorithms of priority queues did not perform well in practice because of their complexity, and they are often based on non-available atomic synchronization primitives. Our algorithm is based on the randomized sequential list structure called Skiplist, and a real-time extension of our algorithm is also described. In our performance evaluation we compare our algorithm with some of the most efficient implementations of priority queues known. The experimental results clearly show that our lock-free implementation outperforms the other lock-based implementations in all cases for 3 threads and more, both on fully concurrent as well as on pre-emptive systems.