Fast and lock-free concurrent priority queues for multi-thread systems

Håkan Sundell

doi:10.1016/j.jpdc.2004.12.005

Fast and lock-free concurrent priority queues for multi-thread systems

2005-05-01

72

PRE

AI

DOI：10.1016/j.jpdc.2004.12.005

Original

Original request for help

Save

Abstract

En 中文

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 overall performance of the system. Non-blocking algorithms avoid blocking, and several implementations have been proposed. 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 a well-representable set of earlier known implementations of priority queues. The experimental results clearly show that our lock-free implementation outperforms the other lock-based implementations in practical scenarios for 3 threads and more, both on fully concurrent as well as on pre-emptive systems. (c) 2005 Elsevier Inc. All rights reserved.

Keywords:

priority queue

skip list

non-blocking

lock-free

shared data structure

real-time

multi-thread

concurrent

Fast and lock-free concurrent priority queues for multi-thread systems

Abstract

AI Summary

Journal

Organization