Document Open Access Logo

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

Authors Aras Atalar, Paul Renaud-Goud, Philippas Tsigas

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.23.pdf
  • Filesize: 0.58 MB
  • 17 pages

Document Identifiers

Author Details

Aras Atalar
Paul Renaud-Goud
Philippas Tsigas

Cite As Get BibTex

Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas. How Lock-free Data Structures Perform in Dynamic Environments: Models and Analyses. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.23

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.

Subject Classification

Keywords
  • Lock-free
  • Data Structures
  • Parallel Computing
  • Performance
  • Modeling
  • Analysis

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Yehuda Afek, Gideon Stupp, and Dan Touitou. Long lived adaptive splitter and applications. Distributed Computing, 15(2):67-86, 2002. URL: http://dx.doi.org/10.1007/s004460100060.
  2. Dan Alistarh, Keren Censor-Hillel, and Nir Shavit. Are lock-free concurrent algorithms practically wait-free? In STOC, pages 714-723. ACM, Jun 2014. Google Scholar
  3. Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas. Analyzing the performance of lock-free data structures: A conflict-based model. In DISC, pages 341-355, 2015. Google Scholar
  4. Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas. How lock-free data structures perform in dynamic environments: Models and analyses. Technical Report 2016:10, Chalmers University of Technology, Nov 2016. URL: http://arxiv.org/abs/1611.05793.
  5. Hagit Attiya and Arie Fouren. Algorithms adapting to point contention. JACM, 50(4):444-468, 2003. URL: http://dx.doi.org/10.1145/792538.792541.
  6. Hagit Attiya, Rachid Guerraoui, and Petr Kouznetsov. Computing with reads and writes in the absence of step contention. In DISC, pages 122-136, 2005. URL: http://dx.doi.org/10.1007/11561927_11.
  7. Tudor David, Rachid Guerraoui, and Vasileios Trigonakis. Everything you always wanted to know about synchronization but were afraid to ask. In SOSP, pages 33-48. ACM, Nov 2013. Google Scholar
  8. Dave Dice, Yossi Lev, and Mark Moir. Scalable statistics counters. In SPAA, pages 43-52. ACM, Jul 2013. Google Scholar
  9. Tanmay Gangwani, Adam Morrison, and Josep Torrellas. CASPAR: breaking serialization in lock-free multicore synchronization. In ASPLOS, pages 789-804, 2016. Google Scholar
  10. Danny Hendler, Nir Shavit, and Lena Yerushalmi. A scalable lock-free stack algorithm. J. Par. Distr. Computing, 70(1):1-12, 2010. Google Scholar
  11. Maurice Herlihy. Wait-free synchronization. TOPLAS, 13(1):124-149, 1991. Google Scholar
  12. Intel. Threading building blocks framework. Accessed: 2016-01-20. URL: https://www.threadingbuildingblocks.org/.
  13. Amos Israeli and Lihu Rappoport. Disjoint-access-parallel implementations of strong shared memory primitives. In PoDC, pages 151-160, 1994. Google Scholar
  14. John D. C. Little. A proof for the queuing formula: L= λ w. Operations research, 9(3):383-387, 1961. Google Scholar
  15. Maged M. Michael. Cas-based lock-free algorithm for shared deques. In Euro-Par, pages 651-660, 2003. URL: http://dx.doi.org/10.1007/978-3-540-45209-6_92.
  16. Maged M. Michael. Hazard pointers: Safe memory reclamation for lock-free objects. IEEE TPDS, 15(8), Aug 2004. Google Scholar
  17. Maged M. Michael and Michael L. Scott. Simple, fast, and practical non-blocking and blocking concurrent queue algorithms. In PoDC, pages 267-275. ACM, May 1996. Google Scholar
  18. Microsoft. NET Framework. Accessed: 2016-01-20. URL: http://www.microsoft.com/net.
  19. NYSE. Daily trades from 2015-08-05. Accessed: 2016-05-05. URL: http://www.nyxdata.com/Data-Products/Daily-TAQ#155.
  20. Oracle. Java concurrency package. Accessed: 2016-01-20. URL: https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/package-summary.html.
  21. R. Kent Treiber. Systems programming: Coping with parallelism. International Business Machines Incorporated, Thomas J. Watson Research Center, 1986. Google Scholar
  22. J. D. Valois. Implementing Lock-Free Queues. In ICPADS, pages 64-69, Dec 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact