Patent ID: 6317756
Filing Date: 2001-11-13
Classification: G06F,Y10S

Abstract:
A method for performing garbage collection of memory objects in a memory heap; a plurality of program threads each running in successive collection cycles; each collection cycle is constituted by a collection idle and collection active cycles; and an on-the-fly garbage collection running in said collection active cycle; said memory objects are associated, each, with an identifier value selected from a group of values that includes:a first identifier value indicating that said memory object is subject to reclaiming or has not yet been subject to trace,a second identifier value indicating that said object is referenced, constituting alive memory object, and descendant memory objects of said object have been subject to a trace for assigning to said descendant memory objects a value,and a third value indicating that said object is referenced, constituting alive memory object, and descendant memory objects of said object have not been subject to said trace; the method comprising the steps of:(a) partitioning said heap or portion thereof into at least two generations; and(b) applying substantiality on-the-fly garbage collection to memory objects in at least one from among said generations, whilst running at least one program thread said step (b) includes:(i) upon starting said collection active cycle, the program thread assigning the third value to any memory object a reference to which is subject to a reference modification;(ii) the program assigning a first inter-generational value, during said collection cycle, to an inter-generational value associated with a memory object that is subject to a reference modification;(iii) the on-the-fly garbage collection performing, for any memory object associated with said second value and having an inter-generational value indicative of candidate inter-generational reference, the following steps that include:(1) associating said third value to any memory object being descendant of said memory object, stipulated in (ii), and which descendant object being associated with said first value;(2) in response of assigning said third value to all descendant objects of said memory object, stipulated in (ii), altering said inter-generational value.