Repeat Offender Problem: A Mechanism for Supporting Dynamic-sized Lock-free Data Structures, The

Repeat Offender Problem: A Mechanism for Supporting Dynamic-sized Lock-free Data Structures, The

Maurice Herlihy, Victor Luchangco, Mark Moir

01 July 2002

We define the Repeat Offender Problem (ROP). Elsewhere, we have presented the first dynamic-sized lock-free data structures that can free memory to any standard memory allocator -- even after thread failures -- without requiring special support from the operating system, the memory allocator, or the hardware. These results depend on a solution to the ROP problem. Here we present the first solution to the ROP problem and its correctness proof. Our solution is implementable in most modern shared memory multiprocessors.


Venue : N/A