Dynamic-sized Lockfree Data Structures

Dynamic-sized Lockfree Data Structures

Victor Luchangco, Paul Martin, Mark Moir, Maurice Herlihy

01 June 2002

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.

Venue : N/A