Method and apparatus for tracking activity of a garbage collector with a plurality of threads that operate concurrently with an application program

• US 20070162526A1
• Filed: 12/19/2005
• Published: 07/12/2007
• Est. Priority Date: 12/19/2005
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Printezis, Antonios, Detlefs, David
• Granted Patent: US 7,672,983 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

The time cost of collecting a region in a Garbage-First garbage collector is adjusted to account for concurrent thread activity. The overhead of a concurrent thread is tracked by dividing elapsed time into relatively short time “windows” and monitoring the system during those windows to determine how long that thread is scheduled to run during those windows. Using measurements of this type for each concurrent thread, the percentage of each elapsed time window dedicated to each concurrent thread is determined. Finally, by summing the percentages of elapsed time dedicated to concurrent thread activity, the cost of collecting a region can be increased by adding the overhead attributable to concurrent activity.

Claims

1. A method for tracking activity of a garbage collector with a plurality of threads that operate concurrently with the operation of an application program during a time window on a computer system having a number of processors, the method comprising:

(a) for each of the plurality of threads, computing the percentage of a small elapsed time window during which that thread is scheduled for operation;

(b) summing the percentages computed in step (a) over all of the plurality of threads; and

(c) multiplying the percentage computed in step (b) by the duration of the time window in order to determine the garbage collection time attributable to concurrent threads during the time window.

2. The method of claim 1 wherein step (a) comprises using each of the plurality of threads to track the elapsed time during which that thread is scheduled for operation and to store the result in a local data structure.

3. The method of claim 1 wherein step (b) comprises adjusting the sum of the percentages by the number of processors.

4. The method of claim 1 wherein step (b) comprises dividing each percentage computed in step (a) by the number of processors before summing the resulting quotients.

5. The method of claim 1 wherein step (b) comprises dividing the sum of the percentages by the number of processors.

6. The method of claim 1 further comprising:

(d) adding the garbage collection time attributable to concurrent threads during the time window as determined in step (c) to garbage collection time attributable to any stop-the-world garbage collection pauses in order to determine the time attributable to garbage collection activities during the time window.

7. The method of claim 1 wherein a total garbage collection time limit is specified by a user and wherein the method further comprises:

(d) reducing the total garbage collection time limit by the garbage collection time attributable to concurrent threads during the time window as determined in step (c).

8. Apparatus for tracking activity of a garbage collector with a plurality of threads that operate concurrently with the operation of an application program during a time window on a computer system having a number of processors, the apparatus comprising:

a local overhead calculator in each of the plurality of threads that computes the percentage of a small elapsed time window during which that thread is scheduled for operation;

a mechanism, including a summer that sums the percentages computed by the local overhead calculators over all of the plurality of threads; and

a multiplier that multiplies the percentage computed by the summer by the duration of the time window in order to determine the garbage collection time attributable to concurrent threads during the time window.

9. The apparatus of claim 8 wherein each local overhead calculator comprises an elapsed time calculator to track the elapsed time during the time window, a virtual time calculator that tracks the virtual time in the time window during which that thread is scheduled for operation, a divider that computes the quotient of the virtual time divided by the elapsed time and a mechanism that stores the quotient in a local data structure.

10. The apparatus of claim 8 further comprising adjusting the sum of the percentages computed by the local overhead calculators by the number of processors.

11. The apparatus of claim 8 wherein the mechanism comprises a divider that divides each percentage computed by a local overhead calculator by the number of processors.

12. The apparatus of claim 8 wherein the mechanism comprises a divider that divides the sum of the percentages computed by the local overhead calculators by the number of processors.

13. The apparatus of claim 8 further comprising an adder that adds the garbage collection time attributable to concurrent threads during the time window to garbage collection time attributable to any stop-the-world garbage collection pauses in order to determine the time attributable to garbage collection activities during the time window.

14. The apparatus of claim 8 wherein a total garbage collection time limit is specified by a user and wherein the apparatus further comprises a mechanism that reduces the total garbage collection time limit by the garbage collection time attributable to concurrent threads during the time window.

15. Apparatus for tracking activity of a garbage collector with a plurality of threads that operate concurrently with the operation of an application program during a time window on a computer system having a number of processors, the apparatus comprising:

means, operable for each of the plurality of threads, for computing a percentage of a small elapsed time window during which that thread is scheduled for operation;

means for summing the percentages computed by the means for computing a percentage over all of the plurality of threads; and

means for multiplying the sum generated by the means for summing by the duration of the time window in order to determine the garbage collection time attributable to concurrent threads during the time window.

16. The apparatus of claim 15 wherein the means for computing a percentage comprises means for using each of the plurality of threads to track the elapsed time during which that thread is scheduled for operation and to store the result in a local data structure.

17. The apparatus of claim 15 wherein the means for summing comprises means for adjusting the sum of the percentages by the number of processors.

18. The apparatus of claim 15 further comprising means for adding the garbage collection time attributable to concurrent threads during the time window to garbage collection time attributable to any stop-the-world garbage collection pauses in order to determine the time attributable to garbage collection activities during the time window.

19. The apparatus of claim 15 wherein a total garbage collection time limit is specified by a user and wherein the apparatus further comprises means for reducing the total garbage collection time limit by the garbage collection time attributable to concurrent threads during the time window.