Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-10-13
2001-11-06
Shah, Sanjiv (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06314436
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method and apparatus for handling interconnected stored data objects and particularly, but not exclusively, to tracing references through object structures in memory compaction and garbage collection procedures executing in real time in real or virtual memory space of a data processing apparatus.
BACKGROUND ART
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, and “Uniprocessor Garbage Collection Techniques” by P. R. Wilson, Proceedings of the 1992 International Workshop on Memory Management, St. Malo, France, September 1992. 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.
A common feature of a number of garbage collection reclamation techniques, as described in the above-mentioned Wilson reference, is incrementally traversing the data structure formed by referencing pointers carried by separately stored data objects. The technique involves first marking all stored objects that are still reachable by other stored objects or from external locations by tracing a path or paths through the pointers linking data objects. This may be followed by sweeping or compacting the memory—that is to say examining every object stored in the memory to determine the unmarked objects whose space may then be reclaimed.
In many cases, garbage collection is a system-wide task which operates on a single global heap, that is to say a single memory area where data structures or objects are stored in no specific order—only with regard to whether a particular space is large enough to hold a particular object. All tracing garbage collection systems include a mechanism for traversing the data structure within the heap. A mark stack or queue is used to store references to the objects pending traversal. However, in the worst case situation, the size of the marking data structure can be comparable with the size of the heap. As the purpose of the garbage collector is to reclaim memory, it is unacceptable for the marking process to require more memory than a small static amount. The Wilson reference identifies a number of conventional solutions, including dedicating a field in each allocated object for a pointer to the next in the marking list. This guarantees a static overhead by allowing for the worst-case situation, where all objects are on the marking list, and is therefore wasteful in memory. Another technique allocates a fixed-size marking structure, and uses the marking structure until is becomes full, following which the marking list is processed without placing new items back on it. Memory then needs to be scanned to find the overflow items. This compromise solution has a poor worst-case performance because large areas of memory may need to be repeatedly scanned for overflowed data. A third technique uses pointer reversal to store pointers back up the marking tree from the current node. Although no extra space is required, because the heap objects are in a non-usable state whilst the algorithm is running, this algorithm cannot be used incrementally. Of the three techniques, the second is preferred as it is not as wasteful of memory as the first and, unlike the third, it does not require the program execution to halt for extended periods which the complete garbage collection procedure is implemented.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide improved efficiency in a tracing/marking technique suitable for use as part of an incremental garbage collection procedure, and in data processing apparatuses employing the same, where a fixed and finite-sized marking structure is used.
In accordance with the present invention there is provided a marking method for traversing data structures formed of data objects linked by identifying pointers in a contiguous memory, preparatory to garbage collection of unmarked data objects, 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;
b) entering references to each object newly determined by the preceding step to a fixed size marking structure; and
c) traversing pointers to determine further objects linked to those identified by the previous step;
wherein steps b) and c) are repeated until the marking structure is full, following which the objects identified therein are marked, then the memory is scanned to locate any further objects linked to those already marked, characterised in that the contiguous memory is divided into a plurality of discrete pages, steps b) and c) are restricted to those objects within the same page as the root object, and for any linked objects outside of that page, an identifier for that page is instead stored at step b).
By limiting the area initially processed to a page, and then logging the pages where “overflow” objects occur, the efficiency is improved and the amount of subsequent scanning is reduced. The marking structure is preferably of a size to accommodate respective references for the largest number of objects capable of being contained in a page, such that the marking structure may be considered full when all objects within a page have been considered. In operation, the above-recited steps a), b), and c) are suitably performed for each page in sequence, with the subsequent iterations of steps b) and c) being repeated in a cycle through the pages until no unmarked linked objects remain within the contiguous memory: at this point, any remaining unmarked objects may be assumed to be unreachable, and hence garbage which may be deleted.
Also in accordance with the present invention there is provided 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 contiguous area of the memory, the apparatus further comprising first additional storage means containing a fixed sized marking data structure, 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;
b) entering references to each object newly determined by the preceding step in the structure of the first additional storage means; and
c) traversing pointers to determine further objects linked to those identified in the first additional storage means;
wherein the processor repeats operations b) and c) until the marking structure is full, marks the objects identified therein, and scans the contiguous area of random access memory to locate any further objects linked to those already marked; characterised in that the contiguous memory is divided into a plurality of discrete pages, operations b) and c) are restricted to those objects within the same page as the root object, for any linked objects outside of that page, an identifier for that page is stored in a second additional storage means, and the scanning to locate any further objects linked to those already marked is performed only for those pages identified in the second additional storage means. The first and second additional storage means may be provided as separate discrete devices, or they may comprises stacks or queues held within the same random access memory, although separate from the contiguous scanned section.
A third additional storage means may b
Shah Sanjiv
U.S. Philips Corporation
Verdonk Peter
LandOfFree
Space-limited marking structure for tracing 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 Space-limited marking structure for tracing garbage collectors, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Space-limited marking structure for tracing garbage collectors will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2595646