Real time, concurrent garbage collection system and method
First Claim
1. In a computer system havinga 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;
- anda 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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
7 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.
- and
-
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.
- and
-
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.
- and
-
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; andpage 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.
- and
-
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. - View Dependent Claims (6, 7)
-
Specification