Tracking minimum mutator utilization (MMU) constraints in a garbage-collection system
View Patent ↗A garbage collector keeps a log of recent system usage. From that usage thus recorded, it determines whether a time slice whose duration a maximum-mutator-utilization (“MMU”) specification prescribes and whose end time is the same as a prospective future collection pause will contain more than the maximum imposed by the MMU specification on the time slice's garbage collector time. The collector uses that determination to arrive at a compliant length for a pause that is to start at a predetermined time or to find a time at which a pause of a predetermined length can start without violating the MMU specification.
1. For performing garbage collection for a mutator executing on a computer system, a method comprising:
A) providing a minimum mutator utilization (MMU) specification that dictates an MMU-specification time-slice duration and a maximum collection duration;
B) maintaining a utilization log by recording, in response to computer-system usage, information from which amounts of system usage by the mutator and a garbage collector can be determined;
C) employing the utilization log to make an assessment of a candidate garbage-collection interval's compliance with the MMU specification, wherein making the assessment of the candidate garbage-collection interval's compliance comprises:
defining a test time slice, associated with that candidate garbage-collection interval, that lasts for the MMU-specification time-slice duration and ends with the end of the candidate garbage-collection interval; and
determining, by combining the candidate garbage-collection interval's duration with the durations that the utilization log indicates for garbage-collection operations that have occurred during the test time slice and comparing the result with the maximum collection duration, whether the durations of garbage-collection operations that fall within the test time slice exceed the maximum collection duration;
D) scheduling garbage-collection operations in accordance with that assessment; and
E) reclaiming memory of the computer system for reuse by executing scheduled garbage-collection operations.
2. A method as defined in claim 1 wherein
A) the candidate garbage-collection interval has a predetermined duration; and
B) if the result of the assessment is a determination that the candidate garbage-collection interval would violate the MMU specification, the method additionally includes, in at least some circumstances, making an assessment of a further candidate garbage-collection interval, which starts later than the previous candidate garbage-collection interval and has the predetermined duration.
3. A method as defined in claim 2 wherein the time at which the further candidate garbage-collection interval starts is later than the previous candidate garbage-collection interval by the amount by which the durations of garbage-collection operations that fall within the test time slice associated with the previous candidate garbage-collection interval exceed the maximum collection duration.
4. A method as defined in claim 1 wherein
A) the candidate garbage-collection interval begins at a predetermined start time; and
B) if the result of the assessment is that the candidate garbage-collection interval would violate the MMU specification, the method additionally includes, in at least some circumstances, additionally making an assessment of a further candidate garbage-collection interval, which starts at the predetermined start time and has a duration less than that of the previous candidate garbage-collection interval.
5. A method as defined in claim 4 wherein the duration of the further candidate garbage-collection interval is less than that of the previous candidate garbage-collection interval by at least the difference between the maximum collection duration and the durations of the garbage-collection operations that fall within the test time slice associated with the previous candidate garbage-collection interval.
6. A computer system configured by machine-readable instructions to execute a mutator and a garbage-collector therefore and to operate the garbage collector using steps comprising:
A) providing a minimum mutator utilization (MMU) specification that dictates an MMU-specification time-slice duration and a maximum collection duration;
B) maintaining a utilization log by recording, in response to computer-system usage, information from which amounts of system usage by the mutator and the garbage collector can be determined;
C) employing the utilization log to make an assessment of a candidate garbage-collection interval's compliance with the MMU specification, wherein making the assessment of the candidate garbage-collection interval's compliance comprises:
defining a test time slice, associated with that candidate garbage-collection interval, that lasts for the MMU-specification time-slice duration and ends with the end of the candidate garbage-collection interval; and
determining, by combining the candidate garbage-collection interval's duration with the durations that the utilization log indicates for garbage-collection operations that have occurred during the test time slice and comparing the result with the maximum collection duration, whether the durations of garbage-collection operations that fall within the test time slice exceed the maximum collection duration;
D) scheduling garbage-collection operations in accordance with that assessment and
E) reclaiming memory of the computer system for reuse by executing scheduled garbage-collection operations.
7. A computer system as defied in claim 6 wherein
A) the candidate garbage-collection interval has a predetermined duration; and
B) if the result of the assessment is a determination that the candidate garbage-collection interval would violate the MMU specification, the machine-readable instructions additionally configure the computer system to, in at least some circumstances, make an assessment of a further candidate garbage-collection interval, which starts later than the previous candidate garbage-collection interval and has the predetermined duration.
8. A computer system as defined in claim 7 wherein the time at which the further candidate garbage-collection interval starts is later than the previous candidate garbage-collection interval by the amount by which the durations of garbage-collection operations that fall within the test time slice associated with the previous candidate garbage-collection interval exceed the maximum collection duration.
9. A computer system as defined in claim 6 wherein
A) the candidate garbage-collection interval begins at a predetermined start time; and
B) if the result of the assessment is that the candidate garbage-collection interval would violate the MMU specification, the machine-readable instructions additionally configure the computer system to, in at least some circumstances, make an assessment of a further candidate garbage-collection interval, which starts at the predetermined start time and has a duration less than that of the previous candidate garbage-collection interval.
10. A computer system as defined in claim 9 wherein the duration of the further candidate garbage-collection interval is less than that of the previous candidate garbage-collection interval by at least the difference between the maximum collection duration and the durations of the garbage-collection operations that fall within the test time slice associated with the previous candidate garbage-collection interval.
11. A storage medium containing instructions readable by a computer system to configure the computer system to execute a mutator and a garbage collector therefore and to operate the garbage collector using steps comprising:
A) providing a minimum mutator utilization (MMU) specification that dictates an MMU-specification timeslice duration and a maximum collection duration;
B) maintaining a utilization log by recording, in response to computer-system usage, information from which amounts of system usage by the mutator and the garbage collector can be determined;
C) employing the utilization log to make an assessment of a candidate garbage-collection interval's compliance with the MMU specification, wherein making the assessment of the candidate garbage-collection interval's compliance comprises:
defining a test time slice, associated with that candidate garbage-collection interval, that lasts for the MMU-specification time-slice duration and ends with the end of the candidate garbage-collection interval; and
determining, by combining the candidate garbage-collection interval's duration with the durations that the utilization log indicates for garbage-collection operations that have occurred during the test time slice and comparing the result with the maximum collection duration, whether the durations of garbage-collection operations that fall within the test time slice exceed the maximum collection duration;
D) scheduling garbage-collection operations in accordance with that assessment and
E) reclaiming memory of the computer system for reuse by executing scheduled garbage-collection operations.
12. A storage medium as defined in claim 11 wherein
A) the candidate garbage-collection interval has a predetermined duration; and
B) if the result of the assessment is a determination that the candidate garbage-collection interval would violate the MMU specification, the machine-readable instructions additionally configure the computer system to, in at least some circumstances, make an assessment of a further candidate garbage-collection interval, which starts later than the previous candidate garbage-collection interval and has the predetermined duration.
13. A storage medium as defined in claim 12 wherein the time at which the further candidate garbage-collection interval starts is later than the previous candidate garbage-collection interval by the amount by which the durations of garbage-collection operations that fall within the test time slice associated with the previous candidate garbage-collection interval exceed the maximum collection duration.
14. A storage medium as defined in claim 11 wherein
A) the candidate garbage-collection interval begins at a predetermined start time; and
B) if the result of the assessment is that the candidate garbage-collection interval would violate the MMU specification, the machine-readable instructions additionally configure the computer system to, in at least some circumstances, make an assessment of a further candidate garbage-collection interval, which starts at the predetermined start time and has a duration less than that of the previous candidate garbage-collection interval.
15. A storage medium as defined in claim 14 wherein the duration of the further candidate garbage-collection interval is less than that of the previous candidate garbage-collection interval by at least the difference between the maximum collection duration and the durations of the garbage-collection operations that fall within the test time slice associated with the previous candidate garbage-collection interval.
16. For performing garbage collection for a mutator executing on a computer system, a method comprising:
A) means for providing a minimum mutator utilization (MMU) specification that dictates an MMU specification time-slice duration and a maximum collection duration;
B) means for maintaining a utilization log by recording, in response to computer-system usage, information from which amounts of system usage by the mutator and a garbage collector can be determined;
C) means for employing the utilization log to make an assessment of a candidate garbage-collection interval's compliance with the MMU specification, wherein making the assessment of the candidate garbage-collection interval's compliance comprises:
defining a test time slice, associated with that candidate garbage-collection interval, that lasts for the MMU-specification time-slice duration and ends with the end of the candidate garbage-collection interval; and
determining, by combining the candidate garbage-collection interval's duration with the durations that the utilization log indicates for garbage-collection operations that have occurred during the test time slice and comparing the result with the maximum collection duration, whether the durations of garbage-collection operations that fall within the test time slice exceed the maximum collection duration;
D) means for scheduling garbage-collection operations in accordance with that assessment and
E) means for reclaiming memory of the computer system for reuse by executing scheduled garbage-collection operations.