Patent ID: 7716258

Claim:
A method of collecting garbage in a computer system having a shared memory and two or more processors that share the shared memory, the method comprising: logically dividing the memory into two or more heaps; dedicating each heap to one of the two or more processors for garbage collection, wherein each heap is sharable among the two or more processors for interfering processes and threads, and wherein a memory object in a heap dedicated to one of the two or more processors references an object in a heap dedicated to another of the two or more processors; initiating concurrently by each of the two or more processors one of a plurality of garbage collection phases, wherein each processor having a dedicated heap performs the one of the plurality of garbage collection phases on the heap dedicated to that processor substantially concurrently with another processor having a dedicated heap performing the one of the plurality of phases on the heap dedicated to that another processor, and wherein the plurality of garbage collection phases comprises: a marking phase that marks all reachable objects in the shared memory; a planning phase that maps a relocation of the reachable objects in each heap, the planning phase creating a directory indicating new address location information; a relocation phase that updates object reference information for each heap with a new address location based on information calculated by the planning phase; and a compaction phase that compacts the reachable objects in each heap; when a memory object in a heap dedicated to one of the two or more processors references an object in a heap dedicated to another of the two or more processors, allowing the one processor to perform the one of the plurality of garbage collection phases on the referenced object in the heap dedicated to the another processor at the same time the another processor is performing the one of the plurality of garbage collection phases on the referenced object in the heap dedicated to the another processor; and upon completion of the one of the plurality of garbage collection phases by each of the two or more processors, synchronizing the two or more processors prior to each processor beginning a next phase.