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

How lock-free data structures perform in dynamic environments: Models and analyses

Aras Atalar (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) ) ; P. Renaud-Goud ; Philippas Tsigas (Institutionen för data- och informationsteknik, Nätverk och system (Chalmers) )
Leibniz International Proceedings in Informatics, LIPIcs (1868-8969). Vol. 70 (2017), p. 23.1-23.17.
[Konferensbidrag, refereegranskat]

© Aras Atalar, Paul Renaud-Goud, and Philippas Tsigas.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.

Nyckelord: Analysis, Data structures, Lock-free, Modeling, Parallel computing, Performance

Denna post skapades 2017-05-18.
CPL Pubid: 249417


Läs direkt!

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