Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Lock-Free Deques and Doubly Linked Lists
University of Borås, School of Business and IT.
2008 (English)In: Journal of Parallel and Distributed Computing, ISSN 0743-7315, E-ISSN 1096-0848, Vol. 68, no 7, 1008-1020 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
Academic Press , 2008. Vol. 68, no 7, 1008-1020 p.
Keyword [en]
lock-free, multi-thread, data structure, Computer Science / Datalogi
National Category
Computer Science
Identifiers
URN: urn:nbn:se:hb:diva-2418DOI: 10.1016/j.jpdc.2008.03.001Local ID: 2320/3594OAI: oai:DiVA.org:hb-2418DiVA: diva2:870512
Available from: 2015-11-13 Created: 2015-11-13 Last updated: 2017-01-21Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Sundell, Håkan
By organisation
School of Business and IT
In the same journal
Journal of Parallel and Distributed Computing
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 68 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf