Practical Concurrent Priority Queues

Priority queues are abstract data structures which store a set of key/value pairs and allow efficient access to the item with the minimal (maximal) key. Such queues are an important element in various areas of computer science such as algorithmics (i.e. Dijkstra's shortest path algorithm) and operating system (i.e. priority schedulers). The recent trend towards multiprocessor computing requires new implementations of basic data structures which are able to be used concurrently and scale well to a large number of threads. In particular, lock-free structures promise superior scalability by avoiding the use of blocking synchronization primitives. Concurrent priority queues have been extensively researched over the past decades. In this paper, we discuss three major ideas within the field: fine-grained locking employs multiple locks to avoid a single bottleneck within the queue; SkipLists are search structures which use randomization and therefore do not require elaborate reorganization schemes; and relaxed data structures trade semantic guarantees for improved scalability.