Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-06-17
2002-03-19
Mizrahi, Diane D. (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
06360233
ABSTRACT:
The present invention relates to a method and apparatus for handling stored data objects and particularly, but not exclusively, to the handling of system requests for allocation of memory occurring during garbage collection procedures executing in real time in real or virtual memory space of a data processing apparatus.
BACKGROUND OF THE INVENTION
Garbage collection is the automated reclamation of system memory space after its last use by a program. 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 programmes 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 programme runs, is essential.
A number of garbage collection techniques involve sweeping of the data objects on the memory heap in order to identify those objects which have become redundant. In such garbage collected systems, memory allocation requests operate concurrently with the sweeper process, which process moves dead (garbage collected) objects to a free structure. If the system memory management cannot service an allocation request immediately from the free structure, typically the allocation process is blocked until completion of the current sweep cycle. The allocation request may then be retried, and if it again fails, more extreme actions are taken. These could include heap expansion or compaction, or abortion of the process with an error. As will be recognised, the blocking of allocation requests can slow the system and generally reduces efficiency.
SUMMARY OF THE INVENTION
It is therefore an object of the present invention to provide an improved technique for handling of memory allocation requests, and an apparatus embodying the same.
In accordance with the present invention there is provided a method of memory management for use in data processing apparatuses, wherein a random-access memory contains a plurality of data objects, each said data object being at a respective known location within the memory and being accessed via respective pointers carried by memory stacks, the method comprising periodically sweeping the memory to determine those data objects having no extent pointers thereto from any source and transferring the blocks of memory space taken thereby to a free memory structure, with external requests for memory space being met by allocation from the free memory structure; characterised in that external requests for which there is insufficient memory available from the free memory structure are entered in a request list, with freed blocks of memory space being made available to the listed requests and only transferred to the free memory structure if not allocated to any listed request. By directing the freed blocks of memory to those program threads or system utilities that particularly require them (as evinced by their being in the unfulfilled requests list), the general efficiency of the system is improved, and the more drastic measures such as stopping to compact the heap are deferred, and in some instances avoided altogether.
The transfer of freed blocks to the free memory structure may suitably comprise establishing pointers thereto from an address table for freed blocks, and entries in the request list may be held in first-in-first-out order, with the freed blocks being made available to stored external requests in sequence of oldest to most recent request.
Although the present invention reduces the need for extreme measures to make memory space available, one or more additional memory reclamation techniques (such as compaction) may still be applied to the contents of the random access memory at the conclusion of a sweep with memory space recovered thereby being used to clear listed requests. In such circumstances, a record is suitably maintained, for each listed request, of the time since listing, with the application of the one or more additional memory reclamation techniques being triggered by one or more of the listed requests having been on the list for longer than a predetermined period. As an alterative to maintaining a real-time count, the time for which a request has been on the list may be given as the number of memory sweeps undertaken since listing.
Also in accordance with the present invention, there is provided data processing apparatus comprising a data processor coupled with a random access memory containing a plurality of data objects, each said data object being at a respective known location within the memory and being accessed via respective pointers carried by memory stacks, the processor being configured to periodically sweep the memory contents to identify those stored data objects having no extent pointers thereto and transfer the blocks of memory space taken thereby to a free memory structure, the processor being arranged to meet programme requests for memory space by allocation from the free memory structure; characterised by a further storage means coupled with the processor, the processor being arranged to enter in said further storage means those programme requests for which there is insufficient memory available from the free structure, and to allocate the freed blocks of memory to one or more of the stored programme requests in preference to placing thereof in the free memory structure.
The apparatus may comprise still further storage means holding the free memory structure in the form of an ordered list of pointers to the random-access memory locations of the freed memory objects, and the further storage means holding the stored programme requests suitably includes, for each entry, a respective field in which the processor maintains an ongoing count of the number of memory sweeps since that request was stored.
The invention will now be described by way of example only, with reference to the accompanying drawings, in which:
REFERENCES:
patent: 5560003 (1996-09-01), Nilsen et al.
patent: 5784699 (1998-07-01), McMahon et al.
patent: 6047295 (2000-04-01), Endicott et al.
patent: 6055612 (2000-04-01), Spertus et al.
Gupta et al. (IEEE publication, 1988) discloses reliable garbage collection in distributed object oriented systems, Computer Software and Applications Conference, COMPSAC 88, pp. 324-328.*
Srisa-An et al. (IEEE publication, 2000) discloses scalable hardware-algorithm for mark-sweep garbage collection; Euromicro Conference 200. Proc. pp. 274-281 (vol. 1).*
One pass real-time generational mark-sweep garbage collection by J. Armstrong et al., pp. 313-322.*
Mark during sweep rather than mark then sweep by C. Queinnect et al., pp. 1-12.*
Garbage collection with multiple processes an exercise in parallelism by L. Lamport, pp. 50-54.*
By R. Jones et al., “Garbage Collection: Algorithms for Automatic Dynamic Memory Management” Pub., John Wiley & Sons 1996, ISBN 0-471-94148-4, pp. 1-18.
Mizrahi Diane D.
U.S. Philips Corporation
LandOfFree
Dynamic memory space allocation does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Dynamic memory space allocation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic memory space allocation will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2860906