Real-time computer “garbage collector”

• US 6,341,293 B1
• Filed: 07/13/1994
• Issued: 01/22/2002
• Est. Priority Date: 07/13/1994
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Object Technology Licensing Corporation
• Inventors: Hennessey, Wade
• Primary Examiner(s): Black, Thomas
• Assistant Examiner(s): RONES, CHARLES
• Application Number:
  US08/274,923
• Time in Patent Office: 2,750 Days
• Field of Search: 395/600, 395/622, 707/206, 707/103
• US Class Current: 1/1
• 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

The present invention provides a novel method and apparatus for performing real-time computer garbage collection, in a manner that offers unprecedented low bounds on the worst-case frequency and duration of the collection task. The invention is used with a plurality of data objects and with one or more mutator programs. The mutators and a garbage collector run on one or more processors. The mutators each have a corresponding thread with a corresponding thread state. In the present invention, execution of all mutators is temporarily restricted at the start of each new garbage collection cycle. However, unrestricted execution of a mutator is quickly resumed, as soon as that mutator'"'"'s thread state is processed. The remainder of the garbage collection cycle may be performed concurrently with the mutators. In another feature of the present invention yielding important performance benefits, the mutators are executed subject to a protective write barrier, but the write barrier does not have to be applied to the modification of mutator thread states.

Claims

1. A method for performing real-time computer garbage collection, for use with a plurality of data objects and with one or more mutator programs, each one of said mutators having a corresponding thread and each one of said mutator threads having a corresponding thread state separate from said plurality of data objects, said method comprising the following steps:

commencing a new garbage collection cycle;

temporarily restricting execution of said mutators while processing the corresponding thread state for each one of said mutators;

permitting each one of said mutators to resume unrestricted execution, as soon as said mutator'"'"'s own corresponding thread state has been processed;

completing the garbage collection cycle by identifying each one of said objects that is currently accessible to at least one of said mutators.

2. The method of claim 1, wherein said step of commencing a garbage collection cycle further includes the step of flipping one or more of said objects, from a first label representative of accessible status to a second label representative of undetermined status.

3. The method of claim 1, wherein said step of commencing a garbage collection cycle further includes the step of saving a list of said mutator threads.

4. The method of claim 1, wherein said step of temporarily restricting the execution of said mutators includes a first step of restricting said mutators from creating any new data objects, and a second step of temporarily suspending execution of said mutators.

5. The method of claim 1, wherein said step of completing the garbage collection cycle further includes the step of tracing one or more pointers stored in each of said mutator thread states.

6. The method of claim 1, wherein said step of completing the garbage collection cycle further includes the step of tracing one or more pointers stored in said objects, for each one of said objects that is in turn pointed to by at least one pointer stored in at least one of said mutator thread states.

7. The method of claim 1, wherein said step of completing the garbage collection cycle is performed without copying any object in said plurality of data objects.

8. The method of claim 1, wherein said step of completing the garbage collection cycle further includes the step of executing said mutators subject to a write barrier which is invoked when said mutators modify pointers within said plurality of data objects but not when said mutators modify pointers within said thread states.

9. An apparatus for performing real-time computer garbage collection, for use with a plurality of data objects and with one or more mutator programs, each one of said mutators having a corresponding thread and each one of said mutator threads having a corresponding thread state separate from said plurality of data objects, said apparatus comprising:

a garbage collector for processing the corresponding thread states of said mutators at the beginning of a garbage collection cycle, and for identifying each one of said data objects that is accessible to at least one of said mutators during said cycle;

one or more processors for executing said garbage collector and said mutators; and

scheduling means coupled to said processors for scheduling execution of said garbage collector and said mutators on said processors, said scheduling means being operative to temporarily restrict execution of said mutators while the corresponding thread state is being processed for each one of said mutators, and to permit each one of said mutators to resume unrestricted execution as soon as said mutator'"'"'s own corresponding thread state has been processed.

10. The apparatus of claim 9, wherein said garbage collector further includes means for flipping said one or more objects from a first label representative of accessible status to a second label representative of undetermined status.

11. The apparatus of claim 9, wherein said garbage collector further includes means for saving a list of said mutator threads.

12. The apparatus of claim 9, wherein said garbage collector includes means for tracing one or more pointers stored in each of said mutator thread states.

13. The apparatus of claim 9, wherein said garbage collector includes means for tracing one or more pointers stored in said data objects, for each one of said objects that is in turn pointed to by at least one pointer stored in at least one of said mutator thread states.

14. The apparatus of claim 9, wherein said garbage collector does not copy said data objects.

15. The apparatus of claim 9, wherein said one or more processors are implemented with stock hardware.

16. The apparatus of claim 9, wherein said scheduling means is operative to temporarily restrict said mutators from creating any new data objects, and is further operative to suspend execution of said mutators.

17. The apparatus of claim 9, further including means for executing said mutators subject to a write barrier which is invoked when said mutators modify pointers within said plurality of data objects but not when said mutators modify pointers within said thread states.