License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.23
URN: urn:nbn:de:0030-drops-70922
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7092/
Go to the corresponding LIPIcs Volume Portal

Atalar, Aras ; Renaud-Goud, Paul ; Tsigas, Philippas

How Lock-free Data Structures Perform in Dynamic Environments: Models and Analyses

pdf-format:
LIPIcs-OPODIS-2016-23.pdf (0.6 MB)

Abstract

In this paper we present two analytical frameworks for calculating the performance of lock-free data structures. Lock-free data structures are based on retry loops and are called by application-specific routines. In contrast to previous work, we consider in this paper lock-free data structures in dynamic environments. The size of each of the retry loops, and the size of the application routines invoked in between, are not constant but may change dynamically. The new frameworks follow two different approaches. The first framework, the simplest one, is based on queuing theory. It introduces an average-based approach that facilitates a more coarse-grained analysis, with the benefit of being ignorant of size distributions. Because of this independence from the distribution nature it covers a set of complicated designs. The second approach, instantiated with an exponential distribution for the size of the application routines, uses Markov chains, and is tighter because it constructs stochastically the execution, step by step.

Both frameworks provide a performance estimate which is close to what we observe in practice. We have validated our analysis on (i) several fundamental lock-free data structures such as stacks, queues, deques and counters, some of them employing helping mechanisms, and (ii) synthetic tests covering a wide range of possible lock-free designs. We show the applicability of our results by introducing new back-off mechanisms, tested in application contexts, and by designing an efficient memory management scheme that typical lock-free algorithms can utilize.

BibTeX - Entry

@InProceedings{atalar_et_al:LIPIcs:2017:7092,
  author =	{Aras Atalar and Paul Renaud-Goud and Philippas Tsigas},
  title =	{{How Lock-free Data Structures Perform in Dynamic Environments: Models and Analyses}},
  booktitle =	{20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-031-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{70},
  editor =	{Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7092},
  URN =		{urn:nbn:de:0030-drops-70922},
  doi =		{10.4230/LIPIcs.OPODIS.2016.23},
  annote =	{Keywords: Lock-free, Data Structures, Parallel Computing, Performance, Modeling, Analysis}
}

Keywords: Lock-free, Data Structures, Parallel Computing, Performance, Modeling, Analysis
Collection: 20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Issue Date: 2017
Date of publication: 06.04.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI