Multiple stage garbage collector

• US 10,572,181 B2
• Filed: 02/01/2017
• Issued: 02/25/2020
• Est. Priority Date: 02/01/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Stephens, Maoni Zhang, Dussud, Patrick H.
• Primary Examiner(s): Faal, Baboucarr
• Application Number:
  US15/422,131
• Publication Number:
  US 20180217779A1
• Time in Patent Office: 1,119 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• 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 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

A method for use with a garbage collector to provide different garbage collections is disclosed. The garbage collections are concurrent garbage collection provided in a dedicated thread concurrently running in a computing device with a mutator thread. A heap size stage, from multiple heap size stages including a heap size growth stage and a heap size stable stage, is determined from a free space amount subsequent a garbage collection. A heap stable garbage collection is applied in response to the heap size stage being the heap size stable stage. A heap growth garbage collection is applied in response to the heap size stage being the heap size growth stage.

Claims

1. A method of garbage collection in a computing device, comprising:

determining a heap size stage from a plurality of heap size stages including a heap size growth stage and a heap size stable stage, the determining of the heap size stage from an amount of free space in a previous garbage collection;

applying a heap stable garbage collection in response to the heap size stage determined to be the heap size stable stage; and

applying a heap growth garbage collection in response to the heap size stage determined to be the heap size growth stage, the heap stable garbage collection and heap growth garbage collection triggered based on a dynamically tunable parameter related to the amount of free space from a previous garbage collection in a closed feedback loop, an amount of free space at the heap stable garbage collection trigger includes a preselected goal amount of memory space and an error amount of memory space.

2. The method of claim 1 wherein applying the heap stable and heap growth garbage collections include providing a concurrent garbage collection in a dedicated thread concurrently running in the computing device with a mutator thread.

3. The method of claim 2 wherein the heap stable garbage collection is triggered based on a dynamically tunable parameter from previous heap growth garbage collections.

4. The method of claim 3 wherein the tunable parameter includes an amount of free space at a garbage collection trigger of the garbage collection.

5. The method of claim 4 wherein a trigger of a goal that determines which stage the garbage collection is in.

6. The method of claim 3 wherein the amount of free space at the heap stable garbage collection trigger includes a preselected goal amount of memory space and an error amount of memory space.

7. The method of claim 6 wherein the goal amount and the error amount are ratios.

8. The method of claim 3 wherein the heap stable garbage collection is triggered based on the amount of free space at the garbage collection trigger of the previous garbage multiplied by a constant.

9. The method of claim 1 wherein the heap size stage is determined based on an amount of free space at the completion of a previous garbage collection.

10. The method of claim 9 wherein the heap size stage is determined to be the heap size stable stage if the amount of free space at the completion of the previous garbage collection is greater than a selected upper threshold.

11. The method of claim 10 wherein a goal of the heap growth garbage collection includes a free space amount greater than the upper threshold.

12. The method of claim 10 wherein the heap size stage is determined to be the heap size growth stage if the amount of free space at the completion of the previous garbage collection is less than a selected lower threshold.

13. The method of claim 12 wherein a goal of the heap stable garbage collection includes a free space amount less than the lower threshold.

14. The method of claim 12 wherein the lower threshold is less than the upper threshold.

15. A system to reclaim memory, comprising:

a memory device to store a set of instructions; and

a processor to execute the set of instructions to;

determine a heap size stage from a plurality of heap size stages including a heap size growth stage and a heap size stable stage, the heap size stage is determined from a free space of a previous garbage collection;

apply a heap stable garbage collection in response to the heap size stage determined to be the heap size stable stage; and

apply a heap growth garbage collection in response to the heap size stage determined to be the heap size growth stage, the heap stable garbage collection and heap growth garbage collection triggered based on a dynamically tunable parameter related to a memory space goal from a previous garbage collection in a closed feedback loop, a free space amount at the heap stable garbage collection trigger includes a preselected goal amount of memory space and an error amount of memory space.

16. The system of claim 15 wherein the heap stable garbage collection includes a first goal of reclaiming a first amount of free space and the heap growth garbage collection includes a second goal of reclaiming a second amount of free space.

17. The system of claim 16 wherein the heap size stage is determined to be the heap size stable stage if the amount of free space at the completion of the previous garbage collection is greater than a selected upper threshold and the heap size stage is determined to be the heap size growth stage if the amount of free space at the completion of the previous garbage collection is less than a selected lower threshold.

18. The system of claim 17 wherein the first goal includes a free space amount less than the lower threshold and the second goal includes a free space amount greater than the upper threshold.

19. A computer readable medium to store computer readable instructions to control a processor to reclaim memory, the instructions comprising:

provide one of a plurality of concurrent garbage collections in a dedicated thread concurrently running in the computing device with a mutator thread;

determine a heap size stage from a plurality of heap size stages including a heap size growth stage and a heap size stable stage, the heap size stage determined from a previous one of the plurality of concurrent garbage collections;

apply a heap stable garbage collection having a first goal of free memory space in response to the heap size stage determined to be the heap size stable stage; and

apply a heap growth garbage collection having a second goal of free memory space in response to the heap size stage determined to be the heap size growth stage, the heap stable garbage collection and heap growth garbage collection triggered based on a dynamically tunable parameter related to an amount of free memory space from a previous garbage collection in a closed feedback loop, the amount of free memory space at the heap stable garbage collection trigger includes a preselected goal amount of memory space and an error amount of memory space.

20. The computer readable medium of claim 19 wherein the first goal of free space memory is less than the second goal of free space memory.