CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems

Håkan Sundell (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers)) ; Philippas Tsigas (Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers))
Journal of Parallel and Distributed Computing Vol. 65 (2005), 5, p. 609-627.
[Artikel, refereegranskad vetenskaplig]

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.

Nyckelord: priority queue, skip list, non-blocking, lock-free, shared data structure, real-time, multi-thread, concurrent



Denna post skapades 2006-08-25.
CPL Pubid: 4463

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för data- och informationsteknik, Datavetenskap, Datakommunikation och distribuerade system (Chalmers) (2005-2007)

Ämnesområden

Information Technology

Chalmers infrastruktur