Method and system for incremental stack scanning

• US 6,769,004 B2
• Filed: 04/27/2001
• Issued: 07/27/2004
• Est. Priority Date: 04/27/2000
• Status: Active Grant

• Current Assignee: Flir Detection, Inc. (Teledyne Technologies Incorporated)
• Original Assignee: iRobot Corporation
• Inventors: Barrett, Kim A.
• Primary Examiner(s): JUNG, DAVID YIUK
• Application Number:
  US09/844,358
• Publication Number:
  US 20030126352A1
• Time in Patent Office: 1,187 Days
• Field of Search: 707/1-10, 707/100-104, 707/200-206, 711/170-173
• 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/99953 Recoverability
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

An incremental garbage collector and method of incremental garbage collection useful for systems with real-time requirements, including a method for incrementally scanning multiple program stacks in units of individual stack locations. Methods and system allow the garbage collector to be preempted by the system and then return to garbage collection without rescanning any portion of a partially completed stack.

Claims

1. A method of automatic memory management, comprising the steps of (a) executing a stack scan phase by scanning each of a plurality of memory stacks, (b) replacing, when starting the scan of a call frame, the continuation for reactivating that frame with an unwind routine which will, if necessary, complete the scan of the call frame and only then reactivate the frame, and (c) performing the scan incrementally.

2. The method of claim 1 wherein the scanning of each of a plurality of memory stacks is in push order.

3. The method of claim 2 wherein once a stack has been completely scanned, by having a stack scanner reach the top of the stack, determining whether or not the stack needs to be rescanned during the current collection cycles.

4. The method of claim 2 wherein once a stack has been completely scanned, by the reactivation of a partially scanned frame causing the scan to be completed, determining whether or not the stack needs to be rescanned during the current collection cycles.

5. The method of claim 3, wherein the determining step comprises the step of (a) monitoring a mutator, and (b) if the mutator is using a “

snapshot at the beginning”

write barrier and stack scanning is performed as the first step of the scan phase of the collector, no rescanning is performed for the stack.