Method and system for concurrent garbage collection

• US 7,310,655 B2
• Filed: 11/18/2002
• Issued: 12/18/2007
• Est. Priority Date: 07/31/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dussud, Patrick H.
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US10/299,489
• Publication Number:
  US 20030069905A1
• Time in Patent Office: 1,856 Days
• Field of Search: 707/206, 707/10, 709/1, 709/107, 709/315, 709/203, 714/9, 717/128, 717/162, 711/1, 711/165, 711/170
• US Class Current: 707/700
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and system for concurrent garbage collection wherein live memory objects, i.e., not garbage, can be marked while an application executes. Root information is gleaned by taking a snapshot program roots or by arranging the stack to be scanned during execution of the program. Next, a first marking act is performed using the root information while the program executes. Modifications in the memory structure that occur during the concurrent marking act are logged or accumulated by a write watch module. The application is then paused or stopped to perform a second marking act using information from the write watch module. Following the second marking act, the garbage collection may be completed using various techniques.

Claims

1. A computer-implemented method of marking memory objects for collecting garbage for an executing application in a computer system, which when executed by the computer system causes the computer system to execute said method comprising:

pausing the executing application;

cloning root information when the executing application is paused, the root information indicating live memory objects, wherein cloning root information includes locating program root objects in memory stacks and storing the program root objects, each live memory object being traceable back to one of the stored program root objects;

restarting the application after cloning the root information;

marking memory objects that are reachable from the stored program root objects using the cloned root information while the application is executing to indicate that the reachable memory objects are not to be collected, the reachable memory objects including memory objects that are live during marking and memory objects that become garbage after cloning the root information; and

after marking the reachable memory objects, collecting unmarked memory objects left unmarked during the act of marking.

2. A method as defined in claim 1 wherein an application thread modifies at least one of the memory objects following the act of cloning and wherein the method further comprises:

determining whether at least one memory object has been modified; and

marking the modified memory object.

3. A method as defined in claim 2 wherein the computer system further comprises a write watch module and the act of determining whether at least one memory object has been modified is performed by the write watch module.

4. A method as defined in claim 2 wherein the computer system further comprises at least one executing application and a stack of memory information, wherein the method further comprises:

following the act of marking the modified memory objects, pausing an executing application; and

marking at least one unvisited memory object from the stack.

5. A method as defined in claim 4 wherein prior to pausing the executing application, the marking act is repeated until the number of modified objects is below a predetermined threshold.

6. A method as defined in claim 5 wherein prior to the marking act, unvisited memory objects are indicated using a first color, visited objects are indicated using a second color, and modified visited objects are indicated using a third color, wherein the modified visited objects are objects that have been modified after being visited.

7. A method as defined in claim 1 wherein the act of collecting the unmarked memory objects operates on an ephemeral portion of memory of the computer system.

8. A method as defined in claim 7 further comprising:

upon completion of the ephemeral portion, marking the remaining portions.

9. A method as defined in claim 1, wherein collecting unmarked memory objects comprises collecting unmarked memory objects while the application is paused.

10. A computer-implemented method of marking memory objects for collecting garbage memory objects for an executing application in a computer system, which when executed by the computer system causes the computer system to execute said method comprising:

cloning root information when the executing application is paused, the root information indicating memory objects in use by the executing application, wherein cloning root information includes locating program root objects in memory stacks and storing the program root objects, each memory object in use by the executing application being reachable from one of the stored program root objects;

monitoring modifications made to memory objects to accumulate a list of modified memory objects, the modifications including at least one of requesting allocation of new memory objects, modifying existing memory objects, and creating new garbage memory objects;

marking memory objects that are reachable from the stored program root objects while the application is executing to indicate whether or not each memory object is to be collected, the reachable memory objects including memory objects that are not garbage memory objects during the act of marking and memory objects that became garbage memory objects after cloning the root information;

revisiting the modified memory objects on the list using the cloned root information, wherein revisiting includes determining whether the memory objects became garbage memory objects after cloning the root information; and

after revisiting the modified memory objects, collecting unmarked memory objects left unmarked during the act of marking.

11. A method as defined in claim 10, wherein collecting unmarked memory objects comprises collecting unmarked memory objects while the application is paused.