Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-06-21
2002-05-21
Mizrahi, Diane D. (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06393439
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. While 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.
Finalization is a concept used in Sun Microsystems' Java ® and other current garbage-collected languages and programming environments, such as Modula-3 and Cedar. Stored data objects may have an associated finaliser which is to be executed after the object nominally becomes available for garbage collection but before the data is collected. 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 claimed by the object.
However, as a finalizer is just another of the class of object handling methods, with all the power of other methods, the finaliser procedure can access all data objects accessible from the object being finalized. Therefore, all objects reachable by a finaliser must be explicitly excluded from garbage collection. Furthermore, it is possible for the finalized method to resurrect any such objects reachable by a finalized including the object being finalised itself, by making the object reachable again. Consequently, a garbage collection procedure cannot delete any objects that are reachable from a finalized object until its finalized has executed and the reachability of the objects has been re-evaluated. In Java and other languages, the possibility of an object repeatedly resurrecting itself is typically removed by stating that the finalized for each instance is executed only once. This control on finalization will be assumed herein.
In PC's or workstations, the extra processing and memory load to support finalization 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 finalizer and reclaimed any memory used by them.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide an incremental garbage collection system which supports finalisable objects while minimizing the time-to-collection for these objects wherever possible.
In accordance with the present invention there is provided a garbage collection and marking method for traversing data structures formed of data objects linked by identifying pointers in a contiguous heap memory, with garbage collection of objects classed as deletable, the method comprising the steps of:
a) for a selected root object, traversing the pointers carried thereby to determine the objects linked to the root object; and
b) traversing pointers to determine further objects linked to those identified by the previous step;
wherein step b) is repeated until no further pointers remain to be traversed following which the objects identified therein are classed as marked, wherein some of the heap data objects carry finalizers and some further objects are identified as potentially reachable by those finalisers which objects are classed as pending, wherein a first count is maintained of heap objects carrying finalizers and, for each traversal, if the detected total of objects carrying finalizer is less than the maintained first count, a further sweep is undertaken to identify and mark root objects for the remaining finalizer reachable objects, whilst if the detected and maintained totals match, those objects classed as pending are immediately reclassed as deletable with no further sweep undertaken.
The present invention also provides a data processing apparatus comprising a data processor coupled with a random access memory containing a plurality of data objects linked in data structures by identifying pointers and within a heap in a contiguous area of the memory, the apparatus further comprising first additional storage means containing for each heap object an identifier for one of a predetermined set of marking classes, and the processor being configured to effect the following operations on the stored plurality of data objects:
a) for a selected root object, traversing the pointers carried thereby to determine the objects linked to the root object; and
b) traversing pointers therefrom to determine further objects linked to those identified;
wherein the processor repeats operation b) until no further pointers remain to be traversed following which the stored class identifiers for the objects identified therein are set as marked, wherein some of the heap data objects carry finalisers and some further objects are identified as potentially reachable by those finalisers which objects are classed as pending wherein the processor is coupled with means maintaining a first count of heap objects carrying finalizer and arranged to determine, for each traversal, if the detected total of objects carrying finalizer is less than the maintained first count, with the processor being configured to then undertake a further sweep to identify and mark root objects for the remaining finalizer reachable objects, whilst if the detected and maintained totals match, the processor is arranged to reclass as deletable all pending objects with no further sweep undertaken.
In operation, heap data objects carrying finalizer may suitably include a respective flag which, when set, prevents the object from being reclassed as deletable. In such an arrangement, the maintained first count may suitably be incremented on setting of the flag, and decremented on its removal. In order to cope with the occurrence, possible in incremental garbage collection, of the total number of heap objects carrying finalizer changing as the sweep progresses, a second count may be maintained of the ongoing number of marked finalisable objects detected during a sweep with this second count value being subtracted from the detected total of objects carrying finalisers at the end of the sweep and prior to comparison with the first count value.
Further features and advantages of the present invention will become apparent from reading of the following description of embodiments of the invention, and are recited in the attached claims to which reference should now be made.
REFERENCES:
patent: 5784699 (1998-07-01), McMahon et al.
patent: 6047295 (2000-04-01), Endicott et al.
patent: 6055612 (2000-04-01), Spertus et al.
Scalable hardware-algorithm for mark-sweep garbage collection Srisa-An, W.; Chia-Tien Dan Lo; Chang, J.M. Euromicro Conference, 2000. Proceedings of the 26th, vol.: 1, 2000 pp.: 274-281 vol. 1.*
Gupta, A.; Fuchs, W.K. Computer Software and Applications Conference, 1988. COMPSAC 88. Proceedings., Twelfth International, 1988 pp.: 324-328.*
“One Pass Real-Time Generational Mark-Sweep Garbage Collection”, by J. Armstrong et al, pp. 313-322.
“Uniprocessor Garbage Collection Techniques”, by P.R. Wilson, pp. 1-32.
“Garbage Collection: Algorithms for Automatic Dynamic Me
Houldsworth Richard J.
Morris Steven
Mizrahi Diane D.
U.S. Philips Corporation
LandOfFree
Stored data object marking for garbage collectors does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Stored data object marking for garbage collectors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Stored data object marking for garbage collectors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2855776