Method and apparatus for performing generational garbage collection using remembered set counter
First Claim
1. In a computer system comprising a heap that stores a plurality of objects that are logically partitioned into at least a first set of objects that have each survived at least a predetermined number N of reclamation operations and a second set of objects distinct from said first set of objects, wherein the computer system further includes a remembered set identifying objects in the first set, and wherein the computer system performs a plurality of reclamation operations that use the remembered set to reclaim space in the heap, a method for maintaining the remembered set comprising the steps of:
- identifying objects that include an object reference that has been modified since the last reclamation operation;
updating the remembered set to include an entry for said identified objects, wherein each entry in said remembered set has an associated counter, C, indicating said reclamation operation when said entry was created; and
storing the updated remembered set for the next reclamation operation.
1 Assignment
0 Petitions
Accused Products
Abstract
A method and apparatus are provided for the efficient management of remembered sets in a generational garbage collection scheme. In order to manage the remembered set, the present invention provides a first mechanism for detecting when an old object has a pointer to a young object, and needs to be added to the remembered set, and a second mechanism for detecting when an object already in the remembered set no longer contains a pointer to a young object, so that the object can be removed from the remembered set. Entries in the remembered set have an associated counter, C, identifying the garbage collection cycle during which the object was placed in the remembered set. Objects inserted into the remembered set are assumed to point to the youngest possible object. Entries automatically expire from the remembered set when the garbage collection counter reaches C+N, since the objects pointed to by the object in the remembered set must now themselves be old objects. If an old object (one that has survived at least N garbage collections) is identified during a minor garbage collection, the old object is scanned normally, and is placed into the remembered set, with a counter C identifying the garbage collection cycle during which the old object was placed in the remembered set. The counter identifies the age of the youngest possible object pointed to by this object. When the garbage collection count reaches C+N, this entry can be discarded from the remembered set, since the associated object cannot point to any objects that are not old unless another more recent entry in the remembered set or write buffer exists for that object.
-
Citations
27 Claims
-
1. In a computer system comprising a heap that stores a plurality of objects that are logically partitioned into at least a first set of objects that have each survived at least a predetermined number N of reclamation operations and a second set of objects distinct from said first set of objects, wherein the computer system further includes a remembered set identifying objects in the first set, and wherein the computer system performs a plurality of reclamation operations that use the remembered set to reclaim space in the heap, a method for maintaining the remembered set comprising the steps of:
-
identifying objects that include an object reference that has been modified since the last reclamation operation;
updating the remembered set to include an entry for said identified objects, wherein each entry in said remembered set has an associated counter, C, indicating said reclamation operation when said entry was created; and
storing the updated remembered set for the next reclamation operation. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A method for managing a remembered set in a generational garbage collection system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said method employing a plurality of reclamation operations that use a remembered set identifying objects in the first set to reclaim space in the heap, said method comprising the steps of:
-
identifying objects that include an object reference that has been modified since the last reclamation operation;
creating an entry in said remembered set during one of said reclamation operations for said identified objects;
associating a counter, C, with said remembered set entry indicating said reclamation operation when said entry was created; and
discarding said entry when said counter has a predefined value. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23)
-
-
24. A generational garbage collection manager for a remembered set in a system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said generational garbage collection manager employing a plurality of reclamation operations that use a remembered set identifying objects in the first set to reclaim space in the heap, said generational garbage collection manager comprising:
-
a memory that stores computer-readable code; and
a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to;
identify objects that include an object reference that has been modified since the last reclamation operation;
update the remembered set to include an entry for said identified objects, wherein each entry in said remembered set has an associated counter, C, indicating said reclamation operation when said entry was created; and
store the updated remembered set for the next reclamation operation.
-
-
25. A generational garbage collection manager for a remembered set in a system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said generational garbage collection manager employing a plurality of reclamation operations that use a remembered set identifying objects in the first set that contain an object reference to objects in the second set to reclaim space in the heap, said generational garbage collection manager comprising:
-
a memory that stores computer-readable code; and
a processor operatively coupled to said memory, said processor configured to implement said computer-readable code, said computer-readable code configured to;
identify objects that include an object reference that has been modified since the last reclamation operation;
create an entry in said remembered set during one of said reclamation operations for said identified objects;
associate a counter, C, with said remembered set entry indicating said reclamation operation when said entry was created; and
discard said entry when said counter has a predefined value.
-
-
26. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a generational garbage collection system for a remembered set in a system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said generational garbage collection manager employing a plurality of reclamation operations that use a remembered set identifying objects in the first set that contain an object reference to objects in the second set to reclaim space in the heap, said method steps comprising:
-
identifying objects that include an object reference that has been modified since the last reclamation operation;
updating the remembered set to include an entry for said identified objects, wherein each entry in said remembered set has an associated counter, C, indicating said reclamation operation when said entry was created; and
storing the updated remembered set for the next reclamation operation.
-
-
27. A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for managing a generational garbage collection system for a remembered set in a system that stores a plurality of objects that are logically partitioned into at least a first set of objects and a second set of objects distinct from said first set of objects, said generational garbage collection manager employing a plurality of reclamation operations that use a remembered set identifying objects in the first set that contain an object reference to objects in the second set to reclaim space in the heap, said method steps comprising:
-
identifying objects that include an object reference that has been modified since the last reclamation operation;
creating an entry in said remembered set during one of said reclamation operations for said identified objects;
associating a counter, C, with said remembered set entry indicating said reclamation operation when said entry was created; and
discarding said entry when said counter has a predefined value.
-
Specification