Real time, concurrent garbage collection system and method

• US 5,088,036 A
• Filed: 01/17/1989
• Issued: 02/11/1992
• Est. Priority Date: 01/17/1989
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Appel, Andrew, Li, Kai, Ellis, John R.
• Primary Examiner(s): Lee, Thomas C.
• Assistant Examiner(s): Geckil, Mehmet
• Application Number:
  US07/297,845
• Time in Patent Office: 1,120 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

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.

Claims

1. In a computer system having

a heap of dynamically allocated storage which is divided into old-space and new-space, each of which is further divided into a multiplicity of pages,

a mutator task executed by the computer system which accesses objects stored in said heap;

and

a garbage collection process for recovering unused storage in the heap;

a computer implemented method of garbage collection performed by said garbage collection process, the steps of the method comprising;

copying at least one object from old-space into new-space and protecting those pages of said new-space which contain objects copied from old-space; and

trapping each memory access by said mutator task to a protected page in a new-space, scanning objects in the protected page for pointers to objects in old-space which have not been previously copied into new-space, copying each such object in old-space into new-space and protecting those pages in said new-space which contain said copied objects, and then unprotecting said page to which memory access was trapped;

whereby accessible objects in old-space are collected and copied into new-space a portion at a time.

2. In a computer system having

a heap of dynamically allocated storage which is divided into old-space and new-space, each of which is further divided into a multiplicity of pages,

a mutator task executed by the computer system which accesses objects stored in said heap;

and

a garbage collection process for recovering unused storage in the heap;

a computer implemented method of garbage collection performed by said garbage collection process, the steps of the method comprising;

copying at least a predefined root set of objects from old-space into new-space and protecting those pages of said new-space which contain said copied objects;

trapping each memory access by said mutator task to a protected page in new-space, scanning objects in the protected page for pointers to objects in old-space which have not been previously copied into new-space, copying each such object in old-space into new-space and protecting those pages of said new-space which contain said copied objects, and then unprotecting said page to which memory access was trapped; and

concurrently with said step of executing said mutator task, successively scanning each of said protected pages in new-space until there are no remaining protected pages in new-space;

each protected page being scanned by scanning objects in the protected page for pointers to objects in old-space which have not been previously copied into new-space, copying each such object in old-space into new-space and protecting those pages of said new-space which contain said copied objects, and then unprotecting said scanned page;

whereby accessible objects in old-space are collected and copied into new-space a portion at a time.

3. In a computer system having

a heap of dynamically allocated storage which is divided into old-space and new-space, each of which is further divided into a multiplicity of pages,

a mutator task executed by the computer system which accesses objects stored in said heap;

and

a garbage collection process for recovering unused storage in the heap;

a computer implemented method of garbage collection performed by said garbage collection process, the steps of the method comprising;

copying at least a portion of said root set of objects into new-space and protecting those pages of said new-space which contain said copied objects;

trapping each memory access by said mutator task to a protected page in new-space, scanning objects in teh protected page for pointers to objects in old-space which have not been previously copied into new-space, copying each such object in old-space into new-space and protecting those pages of said new-space which contain said copied objects, and then unprotecting said page to which memory access was trapped; and

concurrently with said step of executing said mutator task, successively scanning each of said protected pages in new-space until there are no remaining protected pages in new-space;

each protected page being scanned by scanning objects in the protected page for pointers to objects in old-space which have not been previously copied into new-space, copying each such object in old-space into new-space and protecting those pages of said new-space which contain said copied objects, and then unprotecting said scanned page;

whereby accessible objects in old-space are collected and copied into new-space a portion at a time.

4. In a multitasking computer having

at least one mutator task;

and

a heap of storage space in which objects generated by said at least one mutator task are stored, said heap being divided into old-space and new-space, said new-space being divided into a multiplicity of pages;

a memory management system, comprising;

flip means, coupled to said heap, for interchanging old-space and new-space, and then copying at least one object from old-space into new-space and protecting those pages of said new-space which contain objects copied from old-space;

memory allocation means, coupled to said heap and called by said at least one mutator task, for allocating portions of new-space for storing objects;

said memory allocation means invoking said flip means when predefined conditions are met; and

page trapping means, coupled to said heap, for trapping each memory access by said at least one mutator task to a protected page in new-space, scanning objects in the protected page for pointers to objects in old-space which have not been previously copied into new-space, copying each such object in old-space into new-space and protecting those pages of said new-space which contain said copied objects, and then unprotecting said page to which memory access was trapped;

wherein accessible objects in old-space are collected and copied into new-space a portion at a time.

5. In a multitasking computer having

at least one mutator task;

a heap of storage space in which objects generated by each mutator task are stored, said heap being divided into old-space and new-space, said new-space being furtehr divided into a multiplicity of pages; and

root means, associated with each said mutator task, for identifying a root set of pointers which point to a root set of objects stored in said heap;

a memory management system, comprising;

flip means, coupled to said root means and said heap, for interchanging said old-space and new-space, copying at least a portion of said root set of objects from old-space into new-space, and protecting those pages of said new-space which contain said copied objects;

memory allocation means, coupled to said heap and called by said at least one mutator task, for allocating portions of new-space for storing objects;

said memory allocation means invoking said flip means when predefined conditions are met;

page scanning means, coupled to said heap, for scanning objects stored in a specified protected page for pointers to objects in old-space which have not been previously copied into new-space, including means for copying each such object in old-space into new-space, protecting those pages of said new-space which contain said copied objects, and then unprotecting said specified page;

trap handling means, coupled to said page scanning means, for trapping each memory access by said at least one mutator task to a protected page in new-space and then calling said page scanning means to scan and unprotect said page; and

concurrent scanning means, operating concurrently with each said mutator task and coupled to said page scanning means, for calling said page scanning means to scan and unprotect each of said protected pages in the new-space of the corresponding heap until there are no remaining protected pages in new-space.

6. A computer memory management system as set forth in claim 5, said multitasking computer including:

virtual memory protection means, coupled to said flp means, page scanning means and said trap handling means, including means for protecting specified pages from access by user level tasks but not from kernel level tasks; and

means for designating said mutator tasks as user level tasks, for designating said trap handling means as a kernel level task, and for designating said page scanning means and concurrent scanning means as kernel level tasks.

7. A computer memory management system as set forth in claim 5,

said page scanning means including means for storign a forwarding pointer in each copied old-space object, wherein said forwarding pointer points to a copy in new-space of said copied old-space object;

said page scanning means further including means for replacing each pointer in said protected page which points to an object in old-space that contains a forwarding pointer with said forwarding pointer.