Abstract Lock-Free Garbage Collection for Multiprocessors

Garbage collection algorithms for shared-memory mul-tiprocessors typically rely on some form of global syn-chronization to preserve consistency. Such global syn-chronization may lead to problems on asynchronous architectures: if one process is halted or delayed, other, non-faulty processes will be unable to progress. By contrast, a storage management algorithm is loclc-j%ee if (in the absence of resource exhaustion) a process that is allocating or collecting memory can be delayed at any point without forcing other processes to block. This paper presents the first algorithm for lock-free garbage collection in a realistic model. The algorithm assumes that processes synchronize by applying read, write, and compare&swap operations to shared memory. This al-gorithm uses no locks, busy-waiting, or barrier synchronization, it does not assume that processes can observe or modify one another’s local variables or registers, and it does not use inter-process interrupts.