Patent ID: 8200718

Claim:
A method for garbage collection in which resources used by data objects in a multi-threaded computer program that are not accessed in the future are reclaimed, the method comprising the following steps: Providing a tracing garbage collector which is both parallelized and incremental; Integrating the garbage collector with a mutator in a computer program, the mutator being the portion of the program that produces data objects in memory to be scanned by the collector for resources that are not accessed in the future and are therefore reclaimable; Using two or more threads within a memory space that is shared with the mutator to simultaneously scan for and collect unused resources, the mutator being integrated with the collector so that they exist on the same thread, thus guaranteeing that collector processing is interleaved with mutator processing; Sharing one or more threads used by the mutator with the collector for the purpose of scanning and collecting unused resources; Dividing the collector's state between two or more threads that scan for and collect unused resources; Interleaving the collector portion's scanning and collection with unrelated processing by the computer program such that a thread of mutator processing is interrupted frequently for small periods of time instead of being interrupted by the collector relatively infrequently for potentially long periods of time; Using two or more colors in the representation of a potentially collectible resource's state to facilitate scanning for and collecting unused resources; Initiating and maintaining a counter of outstanding unprocessed messages during a given phase such that when the counter reaches zero, the collector sends the message that starts a next phase, this counter shared between threads and synchronized; Each actor maintaining a subset of handles that have been introduced into the collector, wherein within this subset, the actor maintains several subsets that categorize the collection state of the handle, such that a handle cannot belong to multiple sets, and being individually bound to a specific actor, a handle moves from set to set passively as related messages are processed and the handle's associated collection state changes; and Serializing access to the collector's state in such a manner that preserves the integrity of the collector's state without requiring all mutator threads to be stopped simultaneously for any portion of a collection cycle.