Digital Equipment Corporation

Andrew Appel

Kai Yi Li

John R Ellis

A real-time, concurrent garbage collection system and method uses the virtual-memory page protection mechanisms of a standard computer system to collect used storage space in a heap. The heap is divided into old-space and new-space portions, each of which is further divided into a multiplicity of pages. At least one mutator thread modifies and adds objects to new-space. Two garbage collection process threads are used: a fault processing thread, and a concurrent scanning thread, both of which help to collect the accessible objects in old-space. The garbage collector initially copies only the root objects, or a portion of the root objects, to new-space. In addition, all pages of new-space which contain copies of old-space objects are initially marked as being protected. Whenever the mutator tries to access an object in a protected page, a page-access trap is generated. The fault processing thread of the garbage collector responds to the trap by scanning the objects in the referenced page, copying old-space object and forwarding pointers as necessary. Then it unprotects the page and resumes the mutator at the faulting instruction. The concurrent scanning thread of the garbage collector executes concurrently with the mutator, scanning the protected pages in new-space and unprotecting them as each is scanned. The two collection threads together provide an efficient, medium-grained synchronization between the collector and the mutator.

Growing community of inventors

Princeton, NJ, United States of America

Andrew Appel