Method and apparatus for generational garbage collection of a heap memory shared by multiple processors

• US 6,199,075 B1
• Filed: 05/30/1997
• Issued: 03/06/2001
• Est. Priority Date: 05/30/1997
• Status: Expired due to Term

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Wolczko, Mario I., Ungar, David M.
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/866,351
• Time in Patent Office: 1,376 Days
• Field of Search: 707/206, 707/10, 707/104
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0276 Generational garbage collection
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

Apparatus, methods, systems and computer program products are disclosed describing generational garbage collection on a card-marked heap memory shared by multiple processing units. When one of the processing units detects that the free space available for node creation is below a threshold, that processing unit pauses its heap mutation processes and signals the other processing units to also pause mutation. After the other processing units pause heap mutation, the processing units then proceed to execute generational garbage collection procedures on the shared heap. The generational garbage collection procedures for each processing unit are driven by pointers stored in each processing unit'"'"'s register, stack and static variables along with pointers within a specified partition of the shared card-marked heap. The processing units resume mutation of the heap once they all complete their garbage collection processes.

Claims

1. A computer controlled method for garbage collecting a shared heap memory subject to mutation by at least two processing units, said shared heap memory being divided into a plurality of partitions including a first partition and a second partition, said method comprising steps of:

(a) detecting an initiate garbage collection condition by one of said at least two processing units;

(b) pausing mutation of said shared heap memory by said at least two processing units;

(c) initiating a generational garbage collection process in said at least two processing units including a first processing unit and a second processing unit on said shared heap memory, wherein said first processing unit performs generational garbage collection on said first partition of said shared heap memory while said second processing unit performs generational garbage collection on said second partition;

wherein said generational garbage collection process includes, locating an object to be garbage collected by,

searching for a marked card within said one of said plurality of partitions, and

processing a pointer within said marked card to find said object to be garbage collected;

(d) detecting completion of said generational garbage collection process in said at least two processing units; and

(e) resuming mutation of said shared heap memory by said at least two processing units.

2. The computer controlled method of claim 1 wherein step (b) comprises steps of:

(b1) signaling said at least two processing units to pause mutation of said shared heap memory; and

(b2) waiting for said at least two processing units to pause mutation of said shared heap memory.

3. The computer controlled method of claim 1 wherein step (d) comprises steps of:

(d1) signaling, by said at least two processing units, that said generational garbage collection process has completed; and

(d2) waiting for said generational garbage collection process to complete in said at least two processing units.

4. The computer controlled method of claim 1 wherein said shared heap memory is a card-marked shared heap and said method further comprises steps of:

(f) partitioning said card-marked shared heap into a plurality of partitions; and

(g) assigning one of said at least two processing units to one of said plurality of partitions.

5. An apparatus having at least two processing units coupled to a shared heap memory, said shared heap memory accessible by said at least two processing units, said shared heap memory being divided into a plurality of partitions including a first partition and a second partition, wherein said apparatus comprises:

a first detection mechanism configured to detect an initiate garbage collection condition by one of said at least two processing units;

a mutation suspension mechanism, responsive to the first detection mechanism, configured to pause mutation of said shared heap memory by said at least two processing units;

an initiation mechanism configured to initiate a generational garbage collection process in said at least two processing units including a first processing unit and a second processing unit after said at least two processing units pause mutation of said shared heap memory in response to the mutation suspension mechanism, wherein said first processing unit performs generational garbage collection on said first partition of said shared heap memory while said second processing unit performs generational garbage collection on said second partition;

a garbage collection mechanism configured to locate an object to be garbage collected by,

searching for a marked card within said one of said plurality of partitions, and

processing a pointer within said marked card to find said object to be garbage collected;

a second detection mechanism configured to detect completion of said generational garbage collection process in said at least two processing units initiated by the initiation mechanism; and

a resumption mechanism, responsive to the second detection mechanism, configured to resume mutation of said shared heap memory by said at least two processing units.

6. The apparatus of claim 5 wherein the mutation suspension mechanism comprises:

a first signaling mechanism configured to cause said at least two processing units to pause mutation of said shared heap memory; and

a first delay mechanism configured to wait for said at least two processing units to pause mutation of said shared heap memory.

7. The apparatus of claim 6 wherein the second detection mechanism comprises:

a second signaling mechanism configured to cause said at least two processing units to signal that said generational garbage collection process has completed; and

a second delay mechanism configured to wait for said generational garbage collection process to complete in said at least two processing units.

8. The apparatus of claim 6 wherein said shared heap memory is a card-marked shared heap and said apparatus further comprises:

a partitioning mechanism configured to partition said card-marked shared heap into the plurality of partitions; and

an assignment mechanism configured to assign one of said at least two processing units to one of said plurality of partitions, including assigning the first processing unit to the first partition and assigning the second processing unit to the second partition.

9. A computer controlled system having a computer that includes at least two processing units coupled to a shared heap memory, said shared heap memory accessible by said at least two processing units, said shared heap memory being divided into a plurality of partitions including a first partition and a second partition, wherein said system comprises:

a first detection mechanism configured to detect an initiate garbage collection condition by one of said at least two processing units;

a mutation suspension mechanism, responsive to the first detection mechanism, configured to pause mutation of said shared heap memory by said at least two processing units;

an initiation mechanism configured to initiate a generational garbage collection process in said at least two processing units including a first processing unit and a second processing unit after said at least two processing units pause mutation of said shared heap memory in response to the mutation suspension mechanism, wherein said first processing unit performs generational garbage collection on said first partition of said shared heap memory while said second processing unit performs generational garbage collection on said second partition;

a garbage collection mechanism configured to locate an object to be garbage collected by,

searching for a marked card within said one of said plurality of partitions, and

processing a pointer within said marked card to find said object to be garbage collected;

a second detection mechanism configured to detect completion of said generational garbage collection process in said at least two processing units initiated by the initiation mechanism; and

a resumption mechanism, responsive to the second detection mechanism, configured to resume mutation of said shared heap memory by said at least two processing units.

10. The computer controlled system of claim 9 wherein the mutation suspension mechanism comprises:

a first signaling mechanism configured to cause said at least two processing units to pause mutation of said shared heap memory; and

a first delay mechanism configured to wait for said at least two processing units to pause mutation of said shared heap memory.

11. The computer controlled system of claim 9 wherein the second detection mechanism comprises:

a second signaling mechanism configured to cause said at least two processing units to signal that said generational garbage collection process has completed; and

a second delay mechanism configured to wait for said generational garbage collection process to complete in said at least two processing units.

12. The computer controlled system of claim 11, wherein said shared heap memory is a card-marked shared heap and said system fuirther comprises:

a partitioning mechanism configured to partition said card-marked shared heap into the plurality of partitions; and

an assignment mechanism configured to assign one of said at least two processing units to one of said plurality of partitions, including assigning the first processing unit to the first partition and assigning the second processing unit to the second partition.

13. A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer, having at least two processing units coupled to a shared heap memory, to mutate and garbage collect the shared heap memory, said shared hear memory being divided into a plurality of partitions including a first partition and a second partition, wherein said computer readable code comprises;

computer readable program code devices configured to cause said computer to effect a first detection mechanism configured to detect an initiate garbage collection condition by one of said at least two processing units;

computer readable program code devices configured to cause said computer to effect a mutation suspension mechanism, responsive to the first detection mechanism, configured to pause mutation of said shared heap memory by said at least two processing units;

computer readable program code devices configured to cause said computer to effect an initiation mechanism configured to initiate a generational garbage collection process in said at least two processing units including a first processing unit and a second processing unit after said at least two processing units pause mutation of said shared heap memory in response to the mutation suspension mechanism, wherein said first processing unit performs generational garbage collection on said first partition of said shared heap memory while said second processing unit performs generational garbage collection on said second partition;

computer readable program code devices configured to caues said computer to effect a garbage collection mechanism configured to locate an object to be garbage collected by,

searching for a marked card within said one of said plurality of partitions, and

processing a pointer within said marked card to find said object to be garbage collected;

computer readable program code devices configured to cause said computer to effect a second detection mechanism configured to detect completion of said generational garbage collection process in said at least two processing units initiated by the initiation mechanism; and

computer readable program code devices configured to cause said computer to effect a resumption mechanism, responsive to the second detection mechanism, configured to resume mutation of said shared heap memory by said at least two processing units.

14. The computer program product of claim 16 wherein the mutation suspension mechanism comprises:

computer readable program code devices configured to cause said computer to effect a first signaling mechanism configured to cause said at least two processing units to pause mutation of said shared heap memory; and

computer readable program code devices configured to cause said computer to effect a first delay mechanism configured to wait for said at least two processing units to pause mutation of said shared heap memory.

15. The computer program product of claim 16 wherein the second detection mechanism comprises:

computer readable program code devices configured to cause said computer to effect a second signaling mechanism configured to cause said at least two processing units to signal that said generational garbage collection process has completed; and

computer readable program code devices configured to cause said computer to effect a second delay mechanism configured to wait for said generational garbage collection process to complete in said at least two processing units.

16. The computer program product of claim 13 wherein said shared heap memory is a card-marked shared heap and said product further comprises:

computer readable program code devices configured to cause said computer to effect a partitioning mechanism configured to partition said card-marked shared heap into the plurality of partitions; and

computer readable program code devices configured to cause said computer to effect an assignment mechanism configured to assign one of said at least two processing units to one of said plurality of partitions, including assigning the first processing unit to the first partition and assigning the second processing unit to the second partition.