Patent ID: 7321908

Claim:
A method for collecting garbage in a computing environment, the method comprising: a) tracing a root object to any of its reachable objects in a population of objects; b) marking any of said objects referred to in step a); c) tracing any of said marked objects to an unmarked referent object of said marked object; d) marking said unmarked referent object; e) tracing said referent object marked in step d) to any of its reachable objects; f) marking any of said objects referred to in step e); g) tracing any unmarked root object referent to any of its reachable objects; h) marking any of said objects referred to in step g); i) performing any of steps c)-f); and j) designating any unmarked object in said population of objects as available for reallocation, wherein either of steps a) and e) are performed for a given object only if the card to which the object belongs is not marked, wherein any of steps a)-f) are performed upon said population of objects concurrently with the operation of a mutator upon said population of objects within said computing environment, and wherein any of steps g)-j) are performed upon said population of objects while no mutator operates upon said population of objects within said computing environment.