Patent ID: 6393440
Filing Date: 2002-05-21
Classification: G06F,Y10S

Abstract:
A computer implemented method for performing garbage collection of unused memory objects in a memory heap by at least one collector thread; at least one mutator thread running on the computer simultaneously with said at least one collector thread, the method comprising the steps of:(a) providing a mark buffer data structure for each one of the mutator and collector threads; each mark buffer is associated with at least three operations, Insert, Extract, and isEmpty, wherein Insert inserts an element representative of a memory object, Extract chooses an arbitrary element representative of a memory object, removes it from the mark buffer, and isEmpty returns true if all the mark buffers include no remaining elements to extract, at the time the operation was initiated; (b) applying on-the-fly garbage collection in order to collect unused memory objects in the heap; said on the fly garbage collection step includes: i. the at least one mutator thread acquires a respective dedicated mark buffer and uses, said Insert, operation for inserting objects to said mark buffer; ii. the at least one collector thread uses, said Extract operation for extracting objects from a mark buffer; determining if there are remaining objects in the mark buffers utilizing said isEmpty operation; said isEmpty operation is substantially not synchronized with said Insert and Extract operations; whereby substantially no synchronization is required between the mutator threads themselves; and between said at least one collector threads and said mutator threads.