US 2003/0084264 A1 · Preemptive memory-block splitting

Abstract

A computer system (10) implements a memory allocator that employs a data structure (FIG. 3) to maintain an inventory of dynamically allocated memory available to receive new data. It receives from one or more programs requests that it allocate memory from a dynamically allocable memory “heap.” It responds to such requests by performing the requested allocation and removing the thus-allocated memory block from the inventory. Conversely, it adds to the inventory memory blocks that the supported program or programs request be freed. In the process, it monitors the frequencies with which memory blocks of various sizes are allocated, and it projects from those frequencies future-demand values for memory blocks of those sizes. It then splits larger blocks into smaller ones preemptively, i.e., before a request for the result of the splitting. To split a relatively large block preemptively in order to meet an expected request for a smaller block, it bases its selection of the larger block to be split on whether the supply of free blocks of that size is great enough to meet the expected demand for such blocks. It also splits blocks reactively, i.e., in response to a previously made request for a block that will result from the splitting operation.

Claims29

Dependent claims

For satisfying requests for dynamic allocation of blocks of a computer system's computer memory, a method that includes:

A) maintaining an inventory of memory blocks available for dynamic allocation;
B) in response to release requests that specify respective memory blocks, adding those memory blocks to the inventory;
C) performing splitting operations on memory blocks in the inventory and thereby producing split-result memory blocks;
and
D) satisfying some allocation requests by allocating such split-result memory blocks;
wherein at least some of the splitting operations, called preemptive splitting operations, are performed on memory blocks that have been identified by release requests performed before receipt of any allocation request satisfied by allocating a split-result memory block produced thereby.

3 more elements

A storage medium containing instructions readable, by a computer system that makes allocation requests, to configure the computer system to operate as an allocator that:

A) maintains an inventory of memory blocks available for dynamic allocation;
B) in response to release requests that specify respective memory blocks, adds those memory blocks to the inventory;
C) performs splitting operations on memory blocks in the inventory and thereby produces split-result memory blocks;
and
D) satisfies some said allocation requests by allocating such split-result memory blocks;
wherein at least some of the splitting operations, called preemptive splitting operations, are performed on memory blocks that have been identified by release requests performed before receipt of any allocation request satisfied by allocating a split-result memory block produced thereby.

3 more elements

A computer system that makes allocation requests, includes computer memory, and comprises:

A) memory locations, included in the computer memory, that contain instructions directing the computer system to maintain an inventory of memory blocks available for dynamic allocation;
B) memory locations, included in the computer memory, that contain instructions directing the computer system to respond to release requests specifying respective memory blocks by adding those memory blocks to the inventory;
C) memory locations, included in the computer memory, that contain instructions directing the computer system to perform splitting operations on memory blocks in the inventory and thereby produce split-result memory blocks;
and
D) memory locations, included in the computer memory, that contain instructions directing the computer system to satisfy some said allocation requests by allocating such split-result memory blocks;
wherein at least some of the splitting operations, called preemptive splitting operations, are performed on memory blocks that have been identified by release requests performed before receipt of any allocation request satisfied by allocating a split-result memory block produced thereby.

3 more elements

A computer signal representing sequences of instructions that, when executed by a computer system that makes allocation requests and includes computer memory, cause it to operate as an allocator that:

A) maintains an inventory of memory blocks available for dynamic allocation;
B) in response to release requests that specify respective memory blocks, adds those memory blocks to the inventory;
C) performs splitting operations on memory blocks in the inventory and thereby produces split-result memory blocks;
and
D) satisfies some said allocation requests by allocating such split-result memory blocks;
wherein at least some of the splitting operations, called preemptive splitting operations, are performed on memory blocks that have been identified by release requests performed before receipt of any allocation request satisfied by allocating a split-result memory block produced thereby.

3 more elements

Dependencies are inferred from the claim text.

Preemptive memory-block splitting

Life of this patent

Preemptive memory-block splitting

Life of this patent

Abstract

Claims29