Incremental class unloading in a train-algorithm-based garbage collector
First Claim
1. A method of garbage collection in which a train-algorithm-managed generation of a garbage-collected heap contains objects located in car sections and is collected in accordance with the train algorithm, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set that are referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the method further includes:
- A) associating proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and
B) evacuating from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation.
3 Assignments
0 Petitions
Accused Products
Abstract
A garbage collector collects a train-managed heap in accordance with the train algorithm. In doing so, it concentrates into a respective train the heap-located objects that belong to garbage cycles even if those cycles additionally include certain types of objects that are outside the train-managed heap. It does so by using objects within the heap as proxies for those extra-heap objects, and it evacuates into a proxy object'"'"'s train any collection-set objects referred to by the extra-heap objects for which the proxy object is a proxy. The objects in those garbage cycles containing the extra-heap objects can thereby be collected incrementally despite the extra-heap references to them.
-
Citations
73 Claims
-
1. A method of garbage collection in which a train-algorithm-managed generation of a garbage-collected heap contains objects located in car sections and is collected in accordance with the train algorithm, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set that are referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the method further includes:
-
A) associating proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and
B) evacuating from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
A) maintaining for each class represented by an external structure associated with a proxy object in the train-algorithm-managed generation a youngest-train identifier of the youngest train containing an instance of that class; and
B) evacuating proxy objects from the collection sets in accordance with youngest-train identifier maintained for the classes represented by the external structures with which those proxy objects are associated.
-
-
12. A method as defined in claim 11 wherein the method includes maintaining, for each car section that contains a proxy object associated with an external object that represents a class of which a younger train contains an instance, a remembered set containing the youngest-train identifier for each such class.
-
13. A method as defined in claim 12 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
14. A method as defined in claim 12 wherein:
-
A) the method includes maintaining for each car section a regular remembered set containing entries corresponding to references into the car section from younger car sections; and
B) objects are evacuated from car sections in accordance with the contents of those car sections'"'"' regular remembered sets.
-
-
15. A method as defined in claim 1 wherein:
-
A) the external objects contain information on which objects in the train-managed generation depend; and
B) the method further includes evacuating from the collection set those of its proxy objects that are associated with the external objects that contain information on which depend objects outside the collection set.
-
-
16. A method as defined in claim 15 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
17. A method as defined in claim 15 wherein the train into which is evacuated a proxy object from the collection set if that proxy object is associated with an external object containing information on which an object in a train within the garbage-collected generation depends is least as young as the youngest train that contains an object that depends on that external object.
-
18. A method as defined in claim 17 that further includes reclaiming the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
19. A garbage collector that employs the train algorithm to collect a train-algorithm-managed generation of a garbage-collected heap, which train-algorithm-managed generation contains objects located in car sections, the garbage collector collecting the train-algorithm-managed generation, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set that are referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the garbage collector:
-
A) associates proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and
B) evacuates from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation. - View Dependent Claims (20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
A) maintains for each class represented by an external structure associated with a proxy object in the train-algorithm-managed generation a youngest-train identifier of the youngest train containing an instance of that class; and
B) evacuates proxy objects from the collection sets in accordance with youngest-train identifier maintained for the classes represented by the external structures with which those proxy objects are associated.
-
-
30. A garbage collector as defined in claim 29 wherein the garbage collector maintains, for each car section that contains a proxy object associated with an external object that represents a class of which a younger train contains an instance, a remembered set containing the youngest-train identifier for each such class.
-
31. A garbage collector as defined in claim 30 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
32. A garbage collector as defined in claim 30 wherein:
-
A) the garbage collector maintains for each car section a regular remembered set containing entries corresponding to references into the car section from younger car sections; and
B) objects are evacuated from car sections in accordance with the contents of those car sections'"'"' regular remembered sets.
-
-
33. A garbage collector as defined in claim 19 wherein:
-
A) the external objects contain information on which objects in the train-managed generation depend; and
B) the garbage collector additionally evacuates from the collection set those of its proxy objects that are associated with the external objects that contain information on which depend objects outside the collection set.
-
-
34. A garbage collector as defined in claim 33 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
35. A garbage collector as defined in claim 33 wherein the train into which is evacuated a proxy object from the collection set if that proxy object is associated with an external object containing information on which an object in a train within the garbage-collected generation depends is least as young as the youngest train that contains an object that depends on that external object.
-
36. A garbage collector as defined in claim 35 that additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
37. A storage medium containing instructions readable by a computer configure the computer to operate as a garbage collector that employs the train algorithm to collect a train-algorithm-managed generation of a garbage-collected heap, which train-algorithm-managed generation contains objects located in car sections, the garbage collector collecting the train-algorithm-managed generation, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the garbage collector:
-
A) associates proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and
B) evacuates from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation. - View Dependent Claims (38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54)
A) maintains for each class represented by an external structure associated with a proxy object in the train-algorithm-managed generation a youngest-train identifier of the youngest train containing an instance of that class; and
B) evacuates proxy objects from the collection sets in accordance with youngest-train identifier maintained for the classes represented by the external structures with which those proxy objects are associated.
-
-
48. A storage medium as defined in claim 47 wherein the garbage collector maintains, for each car section that contains a proxy object associated with an external object that represents a class of which a younger train contains an instance, a remembered set containing the youngest-train identifier for each such class.
-
49. A storage medium as defined in claim 48 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
50. A storage medium as defined in claim 48 wherein:
-
A) the garbage collector maintains for each car section a regular remembered set containing entries corresponding to references into the car section from younger car sections; and
B) objects are evacuated from car sections in accordance with the contents of those car sections'"'"' regular remembered sets.
-
-
51. A storage medium as defined in claim 37 wherein:
-
A) the external objects contain information on which objects in the train-managed generation depend; and
B) the garbage collector additionally evacuates from the collection set those of its proxy objects that are associated with the external objects that contain information on which depend objects outside the collection set.
-
-
52. A storage medium as defined in claim 51 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
53. A storage medium as defined in claim 51 wherein the train into which is evacuated a proxy object from the collection set if that proxy object is associated with an external object containing information on which an object in a train within the garbage-collected generation depends is least as young as the youngest train that contains an object that depends on that external object.
-
54. A storage medium as defined in claim 53 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
55. A computer signal representing sequences of instructions that, when executed by a processor, cause it to operate as a garbage collector that employs the train algorithm to collect a train-algorithm-managed generation of a garbage-collected heap, which train-algorithm-managed generation contains objects located in car sections, the garbage collector collecting the train-algorithm-managed generation, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set referred to from outside the collection set, placing objects thus evacuated into the youngest trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the garbage collector:
-
A) associates proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and
B) evacuates from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation. - View Dependent Claims (56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72)
A) maintains for each class represented by an external structure associated with a proxy object in the train-algorithm-managed generation a youngest-train identifier of the youngest train containing an instance of that class; and
B) evacuates proxy objects from the collection sets in accordance with youngest-train identifier maintained for the classes represented by the external structures with which those proxy objects are associated.
-
-
66. A computer signal as defined in claim 65 wherein the garbage collector maintains, for each car section that contains a proxy object associated with an external object that represents a class of which a younger train contains an instance, a remembered set containing the youngest-train identifier for each such class.
-
67. A computer signal as defined in claim 66 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
68. A computer signal as defined in claim 66 wherein:
-
A) the garbage collector maintains for each car section a regular remembered set containing entries corresponding to references into the car section from younger car sections; and
B) objects are evacuated from car sections in accordance with the contents of those car sections'"'"' regular remembered sets.
-
-
69. A computer signal as defined in claim 55 wherein:
-
A) the external objects contain information on which objects in the train-managed generation depend; and
B) the garbage collector additionally evacuates from the collection set those of its proxy objects that are associated with the external objects that contain information on which depend objects outside the collection set.
-
-
70. A computer signal as defined in claim 69 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
71. A computer signal as defined in claim 69 wherein the train into which is evacuated a proxy object from the collection set if that proxy object is associated with an external object containing information on which an object in a train within the garbage-collected generation depends is least as young as the youngest train that contains an object that depends on that external object.
-
72. A computer signal as defined in claim 71 wherein the garbage collector additionally reclaims the external objects with which are associated proxy objects that remain in the collection set after evacuation.
-
73. A garbage collector that employs the train algorithm to collect a train-algorithm-managed generation of a garbage-collected heap, which train-algorithm-managed generation contains objects located in car sections, the garbage collector collecting the train-algorithm-managed generation, in collection cycles for which respective collection sets of the car sections are established, by repeatedly establishing new trains, evacuating from the collection set the objects in the collection set referred to from outside the collection set, placing objects thus evacuated into trains containing objects that refer to them, and reclaiming the car sections that remain in the collection set, wherein the garbage collector includes:
-
A) means for associating proxy objects in the garbage-collected heap with respective external objects outside the garbage-collected heap; and
B) means for evacuating from the collection set those of its objects that are referred to by external objects associated with proxy objects not in the collection set, the trains into which the objects thus evacuated are placed when the respective proxy objects are in the train-managed generation being the trains to which the respective proxy objects belong or to which the respective proxy objects are currently destined for evacuation.
-
Specification