Real-time Concurrent Collection on Stock Multiprocessors

Abstract:

This paper presents the first garbage-collection algorithm that is efficient, real-time, concurrent, runs on stock commercial uniprocessors and multiprocessors, and requires no change to compilers. Our algorithm is related to Baker's algorithm, in which objects are copied from "from space" to "to space" while the mutator is running. We maintain the invariant that registers point only into to-space by arranging to get a page fault from the virtual memeory system if certain pages are fetched from. We have data structures
to allow us to scan the pages of to-space and the stack in arbitrary order. We have implemented the algorithm, and find that it performs efficiently in practice as well as in theory.