Parallel Garbage Collection Without Synchronization Overhead

Incremental garbage collection schemes incur substantial overhead which is directly translated as reduced execution efficiency for the user. Parallel garbage collection schemes implemented via time-slicing on a serial processor also incur this overhead, which might even be aggravated due to context switching. It is useful, therefore, to examine the possibility of implementing a parallel garbage collection algorithm using a separate processor operating asynchronously with the main list processor. The overhead in such a scheme arises from the synchronization necessary to manage the two processors, maintaining memory consistency. In this paper, we present an architecture and supporting parallel garbage collection algorithms designed for a virtual memory system with separate processors for list processing and for garbage collection. Each processor has its own primary memory; in addition, there is a small common memory which both processors may access. Individual memories swap off a common secondary memory, but no locking mechanism is required. In particular, a page may reside in both memories simultaneously, and indeed may be accessed and modified freely by each processor. A secondary memory controller ensures consistency without necessitating numerous lockouts on the pages.