Memory reclamation method

• US 6,571,260 B1
• Filed: 03/16/2000
• Issued: 05/27/2003
• Est. Priority Date: 03/31/1999
• Status: Expired due to Fees

• Current Assignee: Uniloc 2017 LLC (SoftBank Group Corp.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Morris, Steven
• Primary Examiner(s): Metjahic, Safet
• Assistant Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US09/527,198
• Time in Patent Office: 1,167 Days
• Field of Search: 707/206, 707/104.1, 707/205, 705/40, 712/34, 714/9, 717/109
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A method and apparatus for reclaiming memory space allocated to data structures comprising data objects linked by identifying pointers. A repetitious cycle is performed including the following steps of traversing the data structures to identify and mark active data objects, deleting data objects that were marked as garbage during the previous cycle, marking data objects not marked as active as garbage, and executing the finalizer of any data object marked as garbage having a finalizer.

Claims

1. A method of reclaiming memory space allocated to data structures comprising data objects linked by identifying pointers, comprising the repetitious cycle of the following steps:

traversing the data structures to identify and mark active data objects;

deleting data objects that were marked as garbage during the previous cycle;

marking data objects not marked as active as garbage; and

executing the finaliser of any data object marked as garbage having a finaliser.

2. A method as claimed in claim 1, wherein the step of executing the finaliser of any data object marked as garbage having a finaliser comprises the step of queuing each finaliser to be executed and executing each queued finaliser in turn, and wherein the step of traversing the data structures to identify and mark active data structures includes the step of traversing the data structure of each object having a finaliser queued to be executed and marking it and its descendants as active.

3. A method as claimed in claim 1, wherein a first mark and a second mark are used in alternate cycles to mark objects as garbage, wherein data objects having the alternate mark to that used in the current cycle are deleted.

4. A method as claimed in claim 1, wherein a total of data objects having unexecuted finalisers is compared to a total of data objects of active data structures having finalisers and, if the totals are equal all objects not marked as active are deleted.

5. A method as claimed in claim 2, wherein the data structure corresponding to a data object having a finaliser to be queued for execution is processed to find any other data object of the data structure also having a finaliser queued for execution and, if the other data object is higher in any hierarchy of the data structure, the finaliser is queued for execution after the finaliser for the other data object, otherwise, if the data object is higher in any hierarchy of the data structure than the other data object, the finaliser is queued for execution before the finaliser for the other object.

6. A method as claimed in claim 2, wherein a first mark and a second mark are used in alternate cycles to mark objects as garbage, wherein data objects having the alternate mark to that used in the current cycle are deleted.

7. A method as claimed in claim 6, wherein a total of data objects having unexecuted finalisers is compared to a total of data objects of active data structures having finalisers and, if the totals are equal all objects not marked as active are deleted.

13. A program storage device readable by a machine and encoding one or more programs of instructions for executing the method steps of claim 1.

8. A data processing apparatus comprising a data processor coupled with a random access memory containing a data structure comprising data objects linked by identifying pointers, the processor being configured to provide the following in a repetitious cycle for operating on the stored plurality of data objects:

means for traversing the data structures to identify and mark active data objects;

means for deleting data objects that were marked as garbage during the previous cycle;

means for marking data objects not marked as active as garbage; and

means for executing the finaliser of any data object marked as garbage having a finaliser.

9. A data processing apparatus as claimed in claim 8, wherein the means for executing the finaliser of any data object marked as garbage having a finaliser comprises means for queuing each finaliser to be executed and executing each queued finaliser in turn, and wherein the means for traversing the data structures to identify and mark active data structures includes means for traversing the data structure of each object having a finaliser queued to be executed and marking it and its descendants as active.

10. A data processing apparatus as claimed in claim 8, wherein a first mark and a second mark are used in alternate cycles to mark objects as garbage, wherein data objects having the alternate mark to that used in the current cycle are deleted.

11. A data processing apparatus as claimed in claim 8, including means for obtaining a total of data objects having unexecuted finalisers and means for comparing the total with a total of data objects of active data structures having finalisers and, if the totals are equal deleting all objects not marked as active.

12. A data processing apparatus as claimed in claim 9, including means for processing the data structure corresponding to a data object having a finaliser to be queued for execution to find any other data object of the data structure also having a finaliser queued for execution and, means for inserting the finaliser in the queue, wherein if the other data object is higher in any hierarchy of the data structure, the finaliser is inserted after the finaliser for the other data object, otherwise, if the data object is higher in any hierarchy of the data structure than the other data object, the finaliser is inserted before the finaliser for the other object.