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

Lock-Free and Practical Doubly Linked List-Based Deques using Single-Word Compare-And-Swap

Håkan Sundell (Institutionen för datavetenskap, Datakommunikation och Distribuerade System) ; Philippas Tsigas (Institutionen för datavetenskap, Datakommunikation och Distribuerade System)
Lecture Notes in Computer Science (0302-9743). Vol. 3544 (2004), p. 240-255.
[Artikel, refereegranskad vetenskaplig]

We present an efficient and practical lock-free implementation of a concurrent deque that supports parallelism for disjoint accesses and uses atomic primitives which are available in modern computer systems. Previously known lock-free algorithms of deques 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 is based on a general lock-free doubly linked list, and only requires single-word compare-and-swap atomic primitives. It also allows pointers with full precision, and thus supports dynamic deque sizes. We have performed an empirical study using full implementations of the most efficient known algorithms of lock-free deques. For 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. In addition, the proposed solution also implements a general doubly linked list, the first lock-free implementation that only needs the single-word compare-and-swap atomic primitive.

Nyckelord: deque, doubly linked list, lock-free, shared memory


Proceedings in: 8th International Conference on Principles of Distributed Systems (OPODIS 2004), Grenoble, FRANCE. DEC 15-17, 2004



Denna post skapades 2006-08-25. Senast ändrad 2013-06-19.
CPL Pubid: 2061

 

Läs direkt!


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


Institutioner (Chalmers)

Institutionen för datavetenskap, Datakommunikation och Distribuerade System (2002-2004)

Ämnesområden

Information Technology

Chalmers infrastruktur