Real time, concurrent garbage collection system and method

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.

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.

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.

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.