Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
1998-08-24
2001-05-22
Kim, Matthew (Department: 2186)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C707S793000
Reexamination Certificate
active
06237072
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus for handling stored data and particularly, but not exclusively, to memory compaction during garbage collection in a 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-941484, at pages 1 to 18, and “Uniprocessor Garbage Collection Techniques” by P.R. Wilson, Proceedings of the 1992 International Wyrkshop on Memory Management, St. Malo, France, September 1992. 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 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.
One particular class of garbage collection/memory reclamation techniques, as described in the above-mentioned Wilson reference, is mark-compact collection. In common with many garbage collection techniques, it is a two-stage procedure and, as its name suggests, it involves first marking all stored objects that are still reachable by tracing a path or paths through the pointers linking data objects. Thereafter, the memory is compacted, moving the marked objects stored in the memory to a contiguous area of memory to leave a space containing only redundant objects, which space may then be reclaimed.
Fragmentaton of system memory is a problem which is particularly acute with garbage collected memory systems. Methods for compaction of memory, such as mark-compact collection, where all memory blocks are moveable are well known. However, the situation where there is a variety of fixed and moveable data, interleaved in an arbitrary fashion, causes problems.
Applying conventional defragmentation techniques in circumstances where there are unmoveable blocks may still leave memory in a partially fragmented state, that is to say composed of collected groups of filled memory blocks interspersed with more than one area of free memory. The consequence of this is that the allocator (the system function allotting storage locations to memory blocks) needs to be designed to work with partially fragmented memory. Also, an overall monitoring and control function must be applied to ensure that defragmentation actually results in a more useful memory organization than before compaction. As memory allocation patterns are arbitrary and unpredictable, the suitability of memory organizations for a particular size of allocation cannot be known before the allocation actually occurs.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide a method for dynamic allocation of storage locations in a random-access memory that can accommodate the limitations imposed by having some stored memory blocks unmovable from a respective storage location.
It is a further object to provide a data processing apparatus embodying such a method in the handling of data storage.
In accordance with the present invention, there is provided a method for management of stored data in the form of data blocks interspersed with free blocks in a fixed size memory. A compaction procedure is periodically applied during which the data blocks are moved together such as to increase the extent of free block contiguity within the memory. Some of the data blocks are fixed in memory location and not moved by the compaction procedure and the remainder are tested in sequence to determine whether a free block location is available for that block such as to improve the overall distribution. A data block is moved to a free block if the free block is greater than or equal to the data block size and less than or equal to the size of the data block when added to the size of any free block abutting the original data block position.
This motion condition enables a relatively rapid determination of a suitable location for moving a data block. This method may improve the efficiency of compaction without adding undue burden to the search procedure for identifying suitable free blocks.
To prevent unnecessary movement of blocks in an existing “best fit” location, any data block not abutted by at least one free block is suitably treated as fixed in memory location. The method described above may further comprise the step of determining, following movement of a data block, whether the block preceding the new data block location is a free block and, if so, moving the data block down to the preceding free block location. This use of sliding compaction can reduce small spaces appearing although preferably, as will be described, a data block is not moved down to a preceding free block location if said preceding free block is smaller than said data block.
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 interspersed with free blocks. Each data object and free block is at a respective known location within the memory. The apparatus is configured to periodically apply a compaction procedure during which at least some of the data blocks are repositioned within the memory such as to increase the extent of free block contiguity. Some of the data blocks are fixed in memory location with the apparatus comprising means operable to identify fixed blocks and exclude them from the compaction procedure. Search means are configured to determine, for each of the remaining data blocks, whether a free block location is available for that block to improve the overall distribution. The search means moves a data block to a free block if the free block is greater than or equal to the data block size and less than or equal to the size of the data block when added to the size of any free block abutting the original data block position.
A free block memory may be provided coupled with the search means and holding, for each size of free block in the random-access memory, the random-access memory address for the, or at least one of the, free blocks. In such a case, the addresses for all free blocks of a common size may be stored as a linked list in the free block memory, with entries in the linked list suitably being stored in order of lowest to highest random-access memory address, with the lowest forming the list header. With this latter arrangement, the list headers may be referenced in free block memory as nodes of a binary tree structure, with the search means configured to traverse the structure to identify free blocks of a selected size. In order to reduce the extent of required tree-traversal, the free block memory may comprise a plurality of binary tree structures, each referencing a different range of free block sizes, with a header array identifying the location in the free block memory of the header node of each binary tree. Further features and advantages of the present invention are recited in the attached claims or will become apparent from reading of the following description of example embodiments.
REFERENCES:
patent: 5479656 (1995-12-01), Rawlings, III
patent: 5652865 (1997-07-01), Rawlings, III
patent: 5784699 (1998-07-01), McMahon et al.
patent: 5848423 (1998-12-01), Ebrahim et al.
“Uniprocessor Garbage Collection Techniques”, Paul R. Wilson, Proc. of the 1992 International Workshop on Memory Management, St. Malo, France, Sep. 1992.
“Garbage Collection: Algorithms for Automatic Dynamic Memory Management” by R. Jones et al, Pub. John Wiley & Sons, 1996, ISBM 0-471-94148-4, pp. 1-18.
Anderson Matthew D.
Kim Matthew
U.S. Philips Corporation
LandOfFree
Memory management with compaction of data blocks 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 management with compaction of data blocks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory management with compaction of data blocks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2554572