PMOS Revitalised

Abstract

Traditional garbage collection techniques designed for language systems operating over transient data do not readily migrate to a persistent context. The size, complexity, and permanence characteristics of a persistent object store mean that an automatic storage reclamation system, in addition to ensuring that all unreachable and only unreachable data is reclaimed, must also maintain store consistency while limiting I/O overhead when collecting secondary-memory data. PMOS is an incremental garbage collection algorithm specifically designed for reclaiming persistent object storage. The collector extends the Mature Object Space algorithm (sometimes know as the train algorithm) to ensure incrementality in a persistent context, to achieve recoverability, and to impose minimum constraints on the order of collection of areas of the persistent address space. The goal of the PMOS algorithm is to break the collection of garbage into small enough units so that disruption can be minimised. PMOS is able to collect the small units in arbitrary orders whilst eliminating cyclic garbage, guaranteeing progress and minimising the impact on the I/O. Our initial implementation of the PMOS collector demonstrated the efficacy of the algorithm but highlighted some architectural assumptions and performance drawbacks. We have designed a new implementation incorporating numerous lessons learned. Here we report on the architecture of the second implementation and our plans for a range of experiments on collector policies.