US6065020A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Dynamic adjustment of garbage collection
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-05-27
•
Granted: 2000-05-16
•
Expires: 2018-05-27
Abstract
Abstract Storage space within a heap may be subject to different types of garbage collection. A first type of garbage collection may be employed when there is a large amount of garbage in the heap, and the second type of garbage collection may be employed when there is a small amount of garbage in the heap. The computer system on which the heap is maintained may include intelligence for automatically deciding which of the garbage collection techniques to employ. The computer system may also automatically control when garbage collection is triggered by setting trigger points according to the amount of garbage collected in the most recent garbage collection. The trigger point may be decreased when there is a high amount of garbage collected, and the trigger point may be increased when there is a low amount of garbage collected.
Inventors
- 👤 Patrick Dussud
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 12:59
CPC Classifications
G; G06; G06F; G06F12/00; G06F12/02; G06F12/0223; G06F12/023; G06F12/0253; Y; Y10; Y10S; Y10S707/00; Y10S707/99951; Y10S707/99956; Y10S707/99957
Claims Analysis
Total Claims: 56
Claim 1
Independent Claim
119 words
A method in a computer system for collecting garbage, the method comprising: determining an amount of memory that has been allocated since garbage was last collected; when the determined amount exceeds a trigger point, determining whether a mark-and-sweep garbage collection technique or a copying garbage collection technique is currently selected; when it is determined that the mark-and-sweep garbage collection technique is currently selected, performing mark-and-sweep garbage collection; when it is determined that the copying garbage collection technique is currently selected, performing copying garbage collection; calculating characteristics of the performed garbage collection; adjusting the trigger point based on the calculated characteristics; and selecting either the mark-and-sweep garbage collection technique or the copying garbage collection technique based on the calculated characteristics.
Claim 2
Independent Claim
119 words
A method in a computer system for collecting garbage, the method comprising: determining an amount of memory that has been allocated since garbage was last collected; when the determined amount exceeds a trigger point, determining whether a mark-and-sweep garbage collection technique or a copying garbage collection technique is currently selected; when it is determined that the mark-and-sweep garbage collection technique is currently selected, performing mark-and-sweep garbage collection; when it is determined that the copying garbage collection technique is currently selected, performing copying garbage collection; calculating characteristics of the performed garbage collection; adjusting the trigger point based on the calculated characteristics; and selecting either the mark-and-sweep garbage collection technique or the copying garbage collection technique based on the calculated characteristics.
Claim 3
Dependent Claim
16 words
The method of claim 1 wherein the garbage collection is performed by a Java virtual machine.
Claim 4
Dependent Claim
38 words
The method of claim 1 wherein the adjusting of the trigger point is based on a characteristic that is a ratio of the amount of collected garbage to the amount of allocated memory after garbage collection is performed.
Claim 5
Dependent Claim
23 words
The method of claim 1 wherein the adjusting of the trigger point is based on a characteristic of the amount of garbage collected.
Claim 6
Dependent Claim
32 words
The method of claim 1 wherein the selection of either the mark-and-sweep garbage collection technique or the copying garbage collection technique is based on a characteristic that is the adjusted trigger point.
Claim 7
Dependent Claim
33 words
The method of claim 1 wherein the selection of either the mark-and-sweep garbage collection technique or the copying garbage collection technique is based on a characteristic that is the amount of garbage collected.
Claim 8
Dependent Claim
29 words
The method of claim 1 wherein the mark-and-sweep garbage collection technique uses a free list and the copying garbage collection technique is modified to also use the free list.
Claim 9
Independent Claim
71 words
A method in a computer system for collecting garbage within a heap, the method comprising: determining a characteristic of the heap; based on the determined characteristic, selecting a first garbage collection technique or a second garbage collection technique; and performing the selected garbage collection technique on the heap wherein the first garbage collection technique is a mark-and sweep garbage collection and the second garbage collection technique is copying garbage collection technique.
Claim 10
Independent Claim
71 words
A method in a computer system for collecting garbage within a heap, the method comprising: determining a characteristic of the heap; based on the determined characteristic, selecting a first garbage collection technique or a second garbage collection technique; and performing the selected garbage collection technique on the heap wherein the first garbage collection technique is a mark-and sweep garbage collection and the second garbage collection technique is copying garbage collection technique.
Claim 11
Dependent Claim
52 words
The method of claim 8 wherein the determined characteristic of the heap is an amount of garbage collected when garbage was last collected and wherein the first garbage collection technique is suitable for a small amount of garbage and the second garbage collection technique is suitable for a large amount of garbage.
Claim 12
Dependent Claim
27 words
The method of claim 8 wherein the determined characteristic of the heap is a trigger point representing amount of memory to be allocated between performing garbage collection.
Claim 13
Dependent Claim
18 words
The method of claim 10 wherein the trigger point is adjusted based on amounts of garbage previously collected.
Claim 14
Dependent Claim
18 words
The method of claim 8 wherein the determined characteristic is based on an amount of garbage previously collected.
Claim 15
Dependent Claim
26 words
The method of claim 8 wherein the determined characteristic is based on both an amount of garbage previously collected and an amount of memory currently allocated.
Claim 16
Dependent Claim
28 words
The method of claim 8 wherein the determined characteristic is based on a ratio of an amount of garbage previously collected and an amount of memory currently allocated.
Claim 17
Dependent Claim
24 words
The method of claim 8 wherein the first and second garbage collection techniques are dynamically selected based on a current characteristic of the heap.
Claim 18
Dependent Claim
29 words
The method of claim 15 wherein the first garbage collection technique is a mark-and-sweep garbage collection technique and the second garbage collection technique is a copying garbage collection technique.
Claim 19
Dependent Claim
29 words
The method of claim 16 wherein the mark-and-sweep garbage collection technique uses a free list and wherein the copying garbage collection technique is modified to use the free list.
Claim 20
Independent Claim
57 words
A method in a computer system for determining when to perform garbage collection, the method comprising: determining whether an amount of memory allocated since garbage collection was last performed exceeds a trigger point; and when it is determined that the amount of memory allocated since garbage collection was last performed exceeds the trigger point, performing garbage collection.
Claim 21
Independent Claim
57 words
A method in a computer system for determining when to perform garbage collection, the method comprising: determining whether an amount of memory allocated since garbage collection was last performed exceeds a trigger point; and when it is determined that the amount of memory allocated since garbage collection was last performed exceeds the trigger point, performing garbage collection.
Claim 22
Dependent Claim
34 words
The method of claim 18 including after performing garbage collection, adjusting the trigger point based on an amount of garbage collected so that garbage collection is next performed based on the adjusted trigger point.
Claim 23
Dependent Claim
22 words
The method of claim 19 wherein the adjusted trigger point is limited by a floor trigger point and a ceiling trigger point.
Claim 24
Dependent Claim
19 words
The method of claim 18 including calculating trigger data and adjusting the trigger point based on the trigger data.
Claim 25
Dependent Claim
20 words
The method of claim 21 wherein the trigger data is based on amount of garbage collected during last garbage collection.
Claim 26
Dependent Claim
29 words
The method of claim 21 wherein the trigger data is based on both an amount of garbage collected during last garbage collection and an amount of memory currently allocated.
Claim 27
Dependent Claim
25 words
The method of claim 22 wherein the trigger point is adjusted when the trigger data is not within a low threshold and a high threshold.
Claim 28
Dependent Claim
26 words
The method of claim 24 wherein when the trigger data is below the low threshold, then the adjusting of the trigger point increases the trigger point.
Claim 29
Dependent Claim
26 words
The method of claim 24 wherein when the trigger data is above the high threshold, then the adjusting of the trigger point decreases the trigger point.
Claim 30
Dependent Claim
30 words
The method of claim 18 wherein the performing of the garbage collection includes selecting a first or a second garbage collection technique based on an amount of garbage previously collected.
Claim 31
Dependent Claim
29 words
The method of claim 27 wherein the first garbage collection technique is a mark-and-sweep garbage collection technique and the second garbage collection technique is a copying garbage collection technique.
Claim 32
Dependent Claim
42 words
The method of claim 27 wherein the first garbage collection technique is selected when a small amount of garbage has been previously collected and wherein the second garbage collection technique is selected when a large amount of garbage has been previously collected.
Claim 33
Independent Claim
75 words
A method in a computer system for collecting garbage, the method comprising: determining whether a small amount of garbage or a large amount of garbage has been generated; when it is determined that a small amount of garbage has been generated, performing garbage collection without copying blocks that are not garbage; and when it is determined that a large amount of garbage has been generated, performing garbage collection with copying blocks that are not garbage.
Claim 34
Independent Claim
75 words
A method in a computer system for collecting garbage, the method comprising: determining whether a small amount of garbage or a large amount of garbage has been generated; when it is determined that a small amount of garbage has been generated, performing garbage collection without copying blocks that are not garbage; and when it is determined that a large amount of garbage has been generated, performing garbage collection with copying blocks that are not garbage.
Claim 35
Dependent Claim
34 words
The method of claim 30 wherein when the performing of garbage collection without copying blocks that are not garbage includes marking blocks that are not garbage and then collecting blocks that are not marked.
Claim 36
Dependent Claim
15 words
The method of claim 31 wherein the collected blocks are added to a free list.
Claim 37
Dependent Claim
36 words
The method of claim 30 wherein when the performing of garbage collection with copying blocks that are not garbage includes adding the blocks that are garbage and the blocks that are copied to a free list.
Claim 38
Dependent Claim
70 words
A computer system for performing garbage collection, comprising: a heap including allocated blocks of memory that are accessible and allocated blocks of memory that are inaccessible; and a memory manager with dynamically adjusting garbage collection for allocating block of memory of the heap and for determining when to perform garbage collection on the heap based on the amount of memory that has been allocated since garbage collection was last performed.
Claim 39
Dependent Claim
70 words
A computer system for performing garbage collection, comprising: a heap including allocated blocks of memory that are accessible and allocated blocks of memory that are inaccessible; and a memory manager with dynamically adjusting garbage collection for allocating block of memory of the heap and for determining when to perform garbage collection on the heap based on the amount of memory that has been allocated since garbage collection was last performed.
Claim 40
Dependent Claim
34 words
The computer system of claim 34 wherein the memory manager with dynamically adjusting garbage collection uses a dynamically adjusted trigger point to indicated the amount of memory to be allocated before performing garbage collection.
Claim 41
Dependent Claim
25 words
The computer system of claim 35 wherein the trigger point is adjusted based on an amount of the allocated blocks of memory that are inaccessible.
Claim 42
Dependent Claim
70 words
A computer system for performing garbage collection, comprising: a heap including allocated blocks of memory that are accessible and allocated blocks of memory that are inaccessible; and a memory manager with dynamically adjusting garbage collection for allocating block of memory of the heap, for determining when to perform garbage collection on the heap, and for selecting a garbage collection technique based on the allocated blocks of memory that are inaccessible.
Claim 43
Dependent Claim
70 words
A computer system for performing garbage collection, comprising: a heap including allocated blocks of memory that are accessible and allocated blocks of memory that are inaccessible; and a memory manager with dynamically adjusting garbage collection for allocating block of memory of the heap, for determining when to perform garbage collection on the heap, and for selecting a garbage collection technique based on the allocated blocks of memory that are inaccessible.
Claim 44
Dependent Claim
43 words
The computer system of claim 37 wherein the memory manager with dynamically adjusting garbage collection selects a garbage collection technique that does not copy allocated blocks of memory that are accessible when a small amount of the allocated block of memory are inaccessible.
Claim 45
Dependent Claim
19 words
The computer system of claim 38 wherein the small amount is determined based on a previously performed garbage collection.
Claim 46
Dependent Claim
63 words
A computer-readable medium containing instructions for causing a computer system to determine when to perform garbage collection, by: determining whether an amount of memory allocated since garbage collection was last performed exceeds a dynamically adjusted trigger point; and when it is determined that the amount of memory allocated since garbage collection was last performed exceeds the dynamically adjusted trigger point, performing garbage collection.
Claim 47
Dependent Claim
63 words
A computer-readable medium containing instructions for causing a computer system to determine when to perform garbage collection, by: determining whether an amount of memory allocated since garbage collection was last performed exceeds a dynamically adjusted trigger point; and when it is determined that the amount of memory allocated since garbage collection was last performed exceeds the dynamically adjusted trigger point, performing garbage collection.
Claim 48
Dependent Claim
49 words
The computer-readable medium of claim 40 including after performing garbage collection, adjusting the dynamically adjusted trigger point based on an amount of garbage collected so that garbage collection is performed more frequently when large amounts of garbage are generated and less frequently when small amounts of garbage are generated.
Claim 49
Dependent Claim
24 words
The computer-readable medium of claim 40 wherein the dynamically adjusted trigger point is limited by a floor trigger point and a ceiling trigger point.
Claim 50
Dependent Claim
28 words
The computer-readable medium of claim 40 wherein the trigger point is adjusted when a measure of collected garbage is not within a low threshold and a high threshold.
Claim 51
Dependent Claim
26 words
The computer-readable medium of claim 43 wherein the measure of collected garbage is based on both an amount of garbage and an amount of memory allocated.
Claim 52
Dependent Claim
70 words
A computer-readable medium containing instructions for causing a computer system to collect garbage, by: determining a characteristic of a previous garbage collection; based on the determined characteristic, selecting a first garbage collection technique or a second garbage collection technique; and performing the selected garbage collection technique wherein the first garbage collection technique is a mark-and-sweep garbage collection technique and the second garbage collection technique is a copying garbage collection technique.
Claim 53
Dependent Claim
70 words
A computer-readable medium containing instructions for causing a computer system to collect garbage, by: determining a characteristic of a previous garbage collection; based on the determined characteristic, selecting a first garbage collection technique or a second garbage collection technique; and performing the selected garbage collection technique wherein the first garbage collection technique is a mark-and-sweep garbage collection technique and the second garbage collection technique is a copying garbage collection technique.
Claim 54
Dependent Claim
45 words
The computer-readable medium of claim 45 wherein the determined characteristic is an amount of garbage collected and wherein the first garbage collection technique is suitable for a small amount of garbage and the second garbage collection technique is suitable for a large amount of garbage.
Claim 55
Dependent Claim
22 words
The computer-readable medium of claim 46 wherein the first garbage collection technique does not copy blocks of memory that are not garbage.
Claim 56
Dependent Claim
18 words
The computer-readable medium of claim 46 wherein the first and second garbage collection techniques share a free list.
References Cited (Backward Citations)
US4989134A
Cited
US5758347A
Cited
US5991779A
Cited
US5960087A
Cited
US5920720A
Cited
US5903899A
Cited
US5842016A
Cited
US5857210A
Cited
US5873104A
Cited
US5873105A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-05-16 | 2003-11-15 | 2004-05-16 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-05-16 | 2007-11-15 | 2008-05-16 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-05-16 | 2011-11-15 | 2012-05-16 | $7700.00 | Window Closed / Lapsed |