|
We address the problem of integrating lockfree shared data structures with
standard dynamic allocation mechanisms (such as malloc and
free).
We have two main contributions. The first is the design and experimental
analysis of two dynamic-sized lockfree FIFO queue implementations, which
extend Michael and Scott's previous implementation by allowing unused
memory to be freed. We compare our dynamic-sized implementations to the
original on 16-processor and 64-processor multiprocessors. Our experimental
results indicate that the performance penalty for making the queue
dynamic-sized is modest, and is negligible when contention is not too high.
These results were achieved by applying a solution to the Repeat Offender
Problem (ROP), which we recently posed and solved.
Our second contribution is another application of ROP solutions.
Specifically, we show how to use any ROP solution to achieve a general
methodology for transforming lockfree data structures that rely on garbage
collection into ones that use explicit storage reclamation.
|
