Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2000-03-16
2003-05-27
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06571260
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus for handling stored data objects and particularly, but not exclusively, to the handling of finalisation for objects in memory compaction and garbage collection procedures executing in real time in real or virtual memory space of a data processing apparatus.
Garbage collection is the automated reclamation of system memory space after its last use by a programme. A number of examples of garbage collecting techniques are discussed in “Garbage Collection: Algorithms for Automatic Dynamic Memory Management” by R. Jones et al, pub. John Wiley & Sons 1996, ISBN 0-471-94148-4, at pages 1 to 18. Whilst the storage requirements of many computer programs are simple and predictable, with memory allocation and recovery being handled by the programmer or a compiler, there is a trend toward functional languages having more complex patterns of execution such that the lifetimes of particular data structures can no longer be determined prior to run-time and hence automated reclamation of this storage, as the program runs, is essential.
Finalisation is a concept used in Sun Microsystems' Java 7 and other current garbage-collected languages (with Java being a trade mark of Sun Microsystems) and programming environments, such as Modula-3 and Cedar. Stored data objects created by a program process may no longer be needed at a point during the execution of the program process. Unneeded data objects are detected by the environment's garbage collector and marked as garbage so that the memory occupied by the data object can be reclaimed. A data object may have an associated finaliser which is to be executed after the object is detected as garbage but before the memory occupied by the data object is reclaimed. The purpose of this feature is to allow an object to clean up any other system resources the object has claimed before it is destroyed.
For example, the finaliser for a Java File object would close all the system file handles held by the object.
However, as a finaliser is just a special type of program procedure associated with a data object, with all the power of other program procedures, the finaliser procedure can access and manipulate all data objects accessible from the object being finalised. Therefore, all objects accessible by a finaliser, such as descendant objects accessible from referencing pointers held by the data object, must be explicitly excluded from garbage collection. Furthermore, it is possible for the finaliser method to resurrect any such objects accessible by a finaliser, including the object being finalised itself, by making the object accessible by the program process again. Consequently, a garbage collection procedure cannot delete any objects that are accessible by a finalisable object until its finaliser has executed and the accessibility of the objects has been reevaluated. In Java and other languages, the possibility of an object repeatedly resurrecting itself is typically removed by stating that the finaliser for each instance is executed only once. This control on finalisation will be assumed herein.
In PC's or workstations, the extra processing and memory load to support finalisation is not usually a problem due to the amount of memory typically available in a PC, although the support will, of course, affect the overall efficiency. In low-memory environments such as set-top boxes, however, support for finalisers can cause problems and even a concurrent or incremental garbage collector may have to halt the program until it has executed some or all of the outstanding finalisers and reclaimed any memory used by them.
In a conventional mark-sweep garbage collector a sweep phase is only executed after a mark phase has finished. Therefore only unmarked objects may be safely treated as garbage during the sweep since the mark phase has completely traversed all active data structures. Such collectors cannot immediately be run so the mark phase and sweep phase execute concurrently.
SUMMARY OF THE INVENTION
According to one aspect of the present invention, there is provided 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.
The method and apparatus of the present invention permit marking and sweeping to be executed concurrently by explicitly marking garbage objects. By marking objects as garbage on one sweep phase and reclaiming those objects on the next, the deletion of objects is separated completely from the marking phase. Thus memory is reclaimed concurrently with marking live objects, improving the efficiency of garbage collection.
The step of executing the finaliser of any data object marked as garbage having a finaliser may comprise the step of queuing each finaliser to be executed and executing each queued finaliser in turn, and the step of traversing the data structures to identify and mark active data structures may include 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.
A first mark and a second mark may be 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.
A total of data objects having unexecuted finalisers may be 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.
The method and apparatus of the present invention efficiently reclaim memory allocated to garbage and finalisable objects as quickly as possible.
The data structure corresponding to a data object having a finaliser to be queued for execution may be 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.
According to another aspect of the present invention, there is provided 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.
The means for executing the finaliser of any data object marked as garbage having a finaliser may comprise means for queuing each finaliser to be executed and executing each queued finaliser in turn, and the means for traversing the data structures to identify and mark active data structures may include means for traversing the data structure of each object having a finaliser queued to be executed and marking it and its descendants as active.
The data processing apparatus may include 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.
The data processing apparatus may include means for processing the data structure cor
Al-Hashemi Sana
Gross Russell
Koninklijke Philips Electronics , N.V.
Metjahic Safet
LandOfFree
Memory reclamation method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory reclamation method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory reclamation method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3030294