Demand-based memory-block splitting

Details Demand-based memory-block splitting Demand-based memory-block splitting

2001-10-29

2004-10-05

Vital, Pierre M. (Department: 2186)

Electrical computers and digital processing systems: memory

Storage accessing and control

Memory configuring

C711S159000, C711S173000, C707S793000

Reexamination Certificate

active

06801990

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention concerns computer-memory allocators and in particular mechanisms that they employ for splitting memory blocks.
2. Background Information
Some of the instructions that a processor reads from its memory direct it to read data stored in other memory locations. The program as loaded often specifies the locations in which the data are to be stored: memory is allocated statically. But many programs generate large quantities of intermediate results that require only temporary storage. To use memory efficiently, memory should not be allocated to such results unless and until they are actually produced: it should be allocated dynamically. And, once the program no longer needs the data for which space was thus allocated, the program should be allowed to reuse that memory space.
For this reason, most large programs employ a “heap” of dynamically allocable memory. As the program proceeds, various previously free memory blocks within the heap contain needed data, while other memory blocks become free for reuse because they contain data that are no longer needed. To keep track, the computer system usually maintains an inventory of locations and sizes of “free” memory blocks, i.e., of memory blocks that can receive new results.
Now, computer programs typically deal with data as various-sized “objects,” each of which usually has all of its data stored in contiguous memory locations. So a block of (contiguous) memory locations must be found when the time comes to allocate memory dynamically to an object. An allocator is the system component that handles the task of keeping track of such free memory blocks and determining which of the free memory blocks are to be used to store new data.
Allocators occur at various levels in the software hierarchy. An operating system itself generates data for which it must dynamically allocate memory, so one of an operating system's tasks is to act as an allocator for that purpose. The operating system typically also serves as an allocator in response to various system calls made by applications programs. The C library function malloc( ), for instance, is a system call that an application uses to ask the system to allocate memory to the application. The free( ) library function conversely tells the system that the calling process no longer needs the data contained by the memory block that the call identifies.
Additionally, some applications that have called upon the operating system to allocate them memory will in turn act as allocators in “sub-allocating” that memory. An example of such an application is the Java Virtual Machine (“JVM”). (Java is a trademark or registered trademark of Sun Microsystems, Inc., in the United States and other countries.) Such an application calls upon the operating system to allocate it memory for its private heap, which it sub-allocates to objects created by the virtual-machine-language programs that it executes. The input to the JVM is one or more “class files,” which include virtual-machine programs, i.e., sequences of the virtual machine's instructions. Included in the virtual machine's instruction set are instructions for allocating new objects, and the virtual machine can so operate as to allocate object memory by removing blocks from the free-block inventory. The JVM not only executes the class file's explicit instructions but also performs automatic “garbage collection”: it identifies objects that the virtual-machine program will no longer use. The JVM may add such objects' memory space to the free-block inventory after they are thus identified.
Independently of the software-hierarchy level at which an allocator operates, one function that it must perform is “splitting.” When a program frees a memory block of a relatively large size, the allocator may initially place it in its free-block inventory as a single block. Or, when the program frees several contiguous small memory blocks, the allocator may “coalesce” those entries into a single large block. (Workers in this field treat coalesce as a transitive verb.) In either case, the allocator may subsequently split that block into smaller blocks if a program thereafter requests allocation of a smaller block and no block of the requested size is available.
Performing such splitting is desirable because it conserves memory resources; allocating a large block in response to a request for a small one wastes memory space. But it can also detract from program performance; in a program that frequently allocates memory dynamically, the cost of splitting can become significant.
SUMMARY OF THE INVENTION
We have developed an approach to splitting that can reduce splitting cost. In accordance with the invention, we derive a demand indicator for each of a plurality of memory-block size ranges. Preferably, this is done by monitoring at run time the allocations of memory blocks whose sizes fall within the respective ranges, although demand derivation can instead be performed by static (compile-time) analysis or by profiling a previous execution of the program. One way to use the demand indicators is to compare the demand signified by the demand indicator for a given block size with the supply of blocks of that size. Typically, if the supply of blocks of a given size exceeds a demand projected for blocks of that size, then blocks of that size will tend to be selected for splitting, whereas blocks whose sizes not in adequate supply will tend not to be selected. This tends to reduce the likelihood that splitting performed at one time will necessitate further splitting or coalescing at a later time.


REFERENCES:
patent: 5978893 (1999-11-01), Bakshi et al.
patent: 6490670 (2002-12-01), Collins et al.
Paul R. Wilson et al., Dynamic Storage Allocation: A Survey and Critical Review, Department of Computer Science, University of Texas at Austin, USA. pp. 1-78.
B. H. Margolin et al., Analysis of Free-Storage Algorithms, Free-Storage Algorithms, No. 4, pp. 283-304, 1971.
Dirk Grunwald et al., CustoMalloc: Efficient Synthesized Memory Allocators, Department of Computer Science, University of Colorado at Boulder, Technical Report CU-CS-602-92, pp. 1-22, 1992.

Affiliated with

Also associated with

Rating

Demand-based memory-block splitting does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Demand-based memory-block splitting, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Demand-based memory-block splitting will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3264819