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

Lock-Free Deques and Doubly Linked Lists

Håkan Sundell ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system, Datakommunikation och distribuerade system (Chalmers))
Journal of Parallel and Distributed Computing (0743-7315). Vol. 68 (2008), 7, p. 1008-1020.
[Artikel, refereegranskad vetenskaplig]

We present a practical lock-free shared data structure that efficiently implements the operations of a concurrent deque as well as a general doubly linked list. The implementation supports parallelism for disjoint accesses and uses atomic primitives which are available in modern computer systems. Previously known lock-free algorithms of doubly linked lists are either based on non-available atomic synchronization primitives, only implement a subset of the functionality, or are not designed for disjoint accesses. Our algorithm only requires single-word compare-and-swap atomic primitives, supports fully dynamic list sizes, and allows traversal also through deleted nodes and thus avoids unnecessary operation retries. We have performed an empirical study of our new algorithm on two different multiprocessor platforms. Results of the experiments performed under high contention show that the performance of our implementation scales linearly with increasing number of processors. Considering deque implementations and systems with low concurrency, the algorithm by Michael shows the best performance. However, as our algorithm is designed for disjoint accesses, it performs significantly better on systems with high concurrency and non-uniform memory architecture.

Nyckelord: Lock-free deque, Lock-free doubly linked list, lock-free programming, Concurrent data structures, Synchronization, multicore



Denna post skapades 2008-06-07. Senast ändrad 2008-06-08.
CPL Pubid: 71464

 

Läs direkt!


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