Patent ID: 7512745

Claim:
A method, in a multiprocessor data processing system, for performing a garbage collection operation on a shared memory, comprising: loading, in a processor of the multiprocessor data processing system, a portion of a global mark queue corresponding to a portion of the shared memory, wherein loading the portion of the global mark queue corresponding to the portion of the shared memory comprises: initially populating a local mark stack based on references to memory objects in the portion of the global mark queue; and loading, in a local store of the processor, the portion of the shared memory corresponding to the portion of the global mark queue, wherein each processor in the plurality of processors of the multi-processor data processing system loads different portions of the global mark queue and corresponding different portions of the shared memory and performs a marking operation on the different portions of the shared memory based on memory object references in the different portions of the global mark queue; performing a marking operation on the portion of the shared memory based on references to memory objects in the portion of the global mark queue assigned to the processor, to thereby identify reachable memory objects whose associated memory cannot be reclaimed as part of the garbage collection operation; and identifying, during the marking operation, references to memory objects that are not in the portion of the shared memory assigned to the processor, for further processing as part of the garbage collection operation, wherein performing the marking operation on the portion of the shared memory based on references to memory objects comprises: tracing memory object references in the portion of the global mark queue and references to dependent memory objects until a reference to a memory object that is not within the portion of the shared memory is identified; storing references to memory objects that are within the portion of the shared memory in the local mark stack; storing references to memory objects that are not within the portion of the shared memory in a non-local mark stack; merging a local mark descriptor data structure associated with the local mark stack with a global mark descriptor data structure; and merging the non-local mark stack with a â€œto be tracedâ€ portion of the global mark queue, wherein the â€œto be tracedâ€ portion of the global mark queue contains memory object references that are to be processed by performing the marking operation, and wherein the local mark descriptor data structure contains reachability information for memory objects whose references are in the local mark stack, wherein the global mark descriptor data structure comprises all references to memory objects that were identified as being within the portion of the shared memory, in local mark stacks of processors of the multiprocessor data processing system.