Numbering sequences of cars with the same number in a generation managed by the train algorithm

• US 20040172428A1
• Filed: 02/27/2003
• Published: 09/02/2004
• Est. Priority Date: 02/27/2003
• Status: Abandoned Application

• Current Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Garthwaite, Alexander T.
• Application Number:
  US10/375,414
• Publication Number:
  US 20040172428A1
• Time in Patent Office: Days
• US Class Current: 707/206
• CPC Class Codes: G06F 12/0276 Generational garbage collection

Abstract

In the Train algorithm, popular and small oversized objects are defined and placed into separate special cars within the trains. The train and car numbers are arranged to fit into one computer word for simplicity and time efficiency of fetching and comparing. A maximum number of cars numbers allowed in any one train is determined from the counter or register (word) length holding the train/car numbers, and the train and car numbers encompass the entire generation being collected. A threshold of less than the maximum number of cars in one train is determined, and when reached, contiguous special cars are arranged to share a common number, and all the cars in the train are renumbered sequentially. However, cars sharing one car numbers remain as separate data structures, including separate remembered sets. A mechanism for shuffling non-contiguous special cars, so that they are contiguous, is disclosed. Moreover, if needed normal sized cars may be re-numbered and included with other cars in a collection set.

Claims

1. In a garbage collection method that divides a generation into car sections that belong to trains, wherein the trains are numbered in order from the oldest and the cars are numbered within trains in order from the oldest, and where the maximum number of cars in any train is defined, an improvement comprising the steps of:

adding a car to a train wherein the number of the car in that train exceeds the maximum number;

discovering contiguous car sections suitable for combining,

giving at least two of the discovered contiguous cars the same car number, and

renumbering sequentially all the cars in the train whereby the youngest car number is less than the maximum number.

2. The method as defined in claim 1 further comprising the steps of:

defining special cars with one object each,

discovering contiguously numbered special cars in the train, and

giving at least two of the special contiguously numbered special cars the same car number.

3. The method as defined in claim 2 further comprising the steps of:

discovering non-contiguously numbered special cars with normal cars between them in a train;

designating younger non-contiguously numbered special cars suitable for shuffling over in-between normal cars,

scanning each normal car between the special cars for first objects that reference objects in the designated younger special cars; and

updating the remembered sets in those younger special cars with those first objects, and then re-number those younger special cars with the older special car number, thereby shuffling the designated younger special cars over the in between normal cars.

4. The method as defined in claim 1 further comprising the steps of:

selecting a threshold number, less than N the maximum number, for cars in a train, wherein when a car is assigned the threshold number, the discovering and grouping of car numbers in a train is initiated.

5. The method as defined in claim 1 wherein for each car in a train, the train number and the car number are contain in a single processor word.

6. In a garbage collection method that divides a generation into car sections that belong to trains, wherein the trains are numbered in order from the oldest and the cars are numbered within trains in order from the oldest, and where the maximum number of cars in any train is defined, an improvement comprising:

means for adding a car to a train wherein the number of the car in that train exceeds the maximum number;

means for discovering contiguous car sections suitable for combining,

means for giving at least two of the discovered contiguous cars the same car number, and

means for renumbering sequentially all the cars in the train whereby the youngest car number is less than the maximum number.

7. The garbage collector as defined in claim 6 further comprising:

means for defining special cars with one object each,

means for discovering contiguously numbered special cars in the train, and

means for giving at least two of the special contiguously numbered special cars the same car number.

8. The garbage collector as defined in claim 7 further comprising:

means for discovering non-contiguously numbered special cars with normal cars between them in a train;

means for designating younger non-contiguously numbered special cars suitable for shuffling over in-between normal cars,

means for scanning each normal car between the special cars for first objects that reference objects in the designated younger special cars; and

means for updating the remembered sets in those younger special cars with those first objects, and then re-number those younger special cars with the older special car number, thereby shuffling the designated younger special cars over the in between normal cars.

9. The garbage collector as defined in claim 6 further comprising:

means for selecting a threshold number, less than N the maximum number, for cars in a train, wherein when a car is assigned the threshold number, the discovering and grouping of car numbers in a train is initiated.

10. The garbage collector as defined in claim 6 wherein for each car in a train, the train number and the car number are contain in a single processor word.

11. A computer readable media comprising the computer readable media containing instructions for execution on a processor for the practice of a garbage collection method that divides a generation into car sections that belong to trains, wherein the trains are numbered in order from the oldest and the cars are numbered within trains in order from the oldest, and where the maximum number of cars in any train is defined, an improvement comprising the steps of:

adding a car to a train wherein the number of the car in that train exceeds the maximum number;

discovering contiguous car sections suitable for combining,

giving at least two of the discovered contiguous cars the same car number, and

renumbering sequentially all the cars in the train whereby the youngest car number is less than the maximum number.

12. The computer readable media of claim 11 further containing instructions for practice of the steps of:

defining special cars with one object each,

discovering contiguously numbered special cars in the train, and

giving at least two of the special contiguously numbered special cars the same car number.

13. The computer readable media of claim 12 further containing instructions for practice of the steps of:

discovering non-contiguously numbered special cars with normal cars between them in a train;

designating younger non-contiguously numbered special cars suitable for shuffling over in-between normal cars,

scanning each normal car between the special cars for first objects that reference objects in the designated younger special cars; and

updating the remembered sets in those younger special cars with those first objects, and then re-number those younger special cars with the older special car number, thereby shuffling the designated younger special cars over the in between normal cars.

14. The computer readable media of claim 11 further containing instructions for practice of the steps of:

selecting a threshold number, less than N the maximum number, for cars in a train, wherein when a car is assigned the threshold number, the discovering and grouping of car numbers in a train is initiated.

15. The computer readable media of claim 11 wherein for each car in a train, the train number and the car number are contain in a single processor word.

16. Electromagnetic signals propagating on a computer network comprising the electromagnetic signals carrying instructions for execution on a processor for the practice of a garbage collection method that divides a generation into car sections that belong to trains, wherein the trains are numbered in order from the oldest and the cars are numbered within trains in order from the oldest, and where the maximum number of cars in any train is defined, an improvement comprising the steps of:

adding a car to a train wherein the number of the car in that train exceeds the maximum number;

discovering contiguous car sections suitable for combining,

giving at least two of the discovered contiguous cars the same car number, and

renumbering sequentially all the cars in the train whereby the youngest car number is less than the maximum number.

17. The electromagnetic signals propagating on a computer network of claim 16, the electromagnetic signals further containing instructions for practice of the steps of:

defining special cars with one object each,

discovering contiguously numbered special cars in the train, and

giving at least two of the special contiguously numbered special cars the same car number.

18. The electromagnetic signals propagating on a computer network of claim 17, the electromagnetic signals further containing instructions for practice of the steps of:

discovering non-contiguously numbered special cars with normal cars between them in a train;

designating younger non-contiguously numbered special cars suitable for shuffling over in-between normal cars,

scanning each normal car between the special cars for first objects that reference objects in the designated younger special cars; and

updating the remembered sets in those younger special cars with those first objects, and then re-number those younger special cars with the older special car number, thereby shuffling the designated younger special cars over the in between normal cars.

19. The electromagnetic signals propagating on a computer network of claim 16, the electromagnetic signals further containing instructions for practice of the steps of:

selecting a threshold number, less than N the maximum number, for cars in a train, wherein when a car is assigned the threshold number, the discovering and grouping of car numbers in a train is initiated.

20. The electromagnetic signals propagating on a computer network of claim 16 wherein for each car in a train, the train number and the car number are contain in a single processor word.