Dynamic adjustment of garbage collection

• US 6,065,020 A
• Filed: 05/27/1998
• Issued: 05/16/2000
• Est. Priority Date: 05/27/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dussud, Patrick
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/085,980
• Time in Patent Office: 720 Days
• Field of Search: 707/206, 707/103, 395/705, 713/16, 380/49, 364/200
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: Y10S 707/99957 Garbage collection

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.

Claims

1. 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.

2. The method of claim 1 wherein the garbage collection is performed by a Java virtual machine.

3. 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.

4. The method of claim 1 wherein the adjusting of the trigger point is based on a characteristic of the amount of garbage collected.

5. 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.

6. 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.

7. 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.

8. 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.

9. 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.

10. 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.

11. The method of claim 10 wherein the trigger point is adjusted based on amounts of garbage previously collected.

12. The method of claim 8 wherein the determined characteristic is based on an amount of garbage previously collected.

13. 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.

14. 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.

15. The method of claim 8 wherein the first and second garbage collection techniques are dynamically selected based on a current characteristic of the heap.

16. 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.

17. 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.

18. 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.

19. 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.

20. The method of claim 19 wherein the adjusted trigger point is limited by a floor trigger point and a ceiling trigger point.

21. The method of claim 18 including calculating trigger data and adjusting the trigger point based on the trigger data.

22. The method of claim 21 wherein the trigger data is based on amount of garbage collected during last garbage collection.

23. 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.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. 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.

32. The method of claim 31 wherein the collected blocks are added to a free list.

33. 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.

34. 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.

35. 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.

36. 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.

37. 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.

38. 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.

39. The computer system of claim 38 wherein the small amount is determined based on a previously performed garbage collection.

40. 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.

41. 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.

42. 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.

43. 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.

44. 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.

45. 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.

46. 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.

47. The computer-readable medium of claim 46 wherein the first garbage collection technique does not copy blocks of memory that are not garbage.

48. The computer-readable medium of claim 46 wherein the first and second garbage collection techniques share a free list.