  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.
