Memory-block coalescing based on run-time demand monitoring
First Claim
1. 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) for each of a plurality of size ranges, deriving a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
C) in response to each of at least one release request that specifies a respective memory block, adding the memory block thereby specified to the inventory, whereby a memory-block run occurs if the release requests specify memory blocks adjacent to memory blocks already in the inventory, and, if such a run occurs;
i) for each of at least one group of memory blocks within that memory-block run, making a coalescing decision that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated; and
ii) coalescing that group of memory blocks into a composite memory block only upon a positive outcome of the coalescing decision made for that group; and
D) in response to each of at least one allocation request, allocating such a composite memory block.
3 Assignments
0 Petitions
Accused Products
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 different sizes are allocated, and it projects from those frequencies future demand for different-sized memory blocks. When it needs to coalesce multiple smaller blocks to fulfil an actual or expected request for a larger block, it bases its selection of which constituent blocks to coalesce on whether enough free blocks of a constituent block'"'"'s size exist to meet the projected demand for them.
-
Citations
49 Claims
-
1. 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) for each of a plurality of size ranges, deriving a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
C) in response to each of at least one release request that specifies a respective memory block, adding the memory block thereby specified to the inventory, whereby a memory-block run occurs if the release requests specify memory blocks adjacent to memory blocks already in the inventory, and, if such a run occurs;
i) for each of at least one group of memory blocks within that memory-block run, making a coalescing decision that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated; and
ii) coalescing that group of memory blocks into a composite memory block only upon a positive outcome of the coalescing decision made for that group; and
D) in response to each of at least one allocation request, allocating such a composite memory block. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. 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) for each of a plurality of size ranges, derives a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
C) in response to each of at least one release request that specifies a respective memory block, adds the memory block thereby specified to the inventory, whereby a memory-block run occurs if the release requests specify memory blocks adjacent to memory blocks already in the inventory, and, if such a run occurs;
i) for each of at least one group of memory blocks within that memory-block run, makes a coalescing decision that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated; and
ii) coalesces that group of memory blocks into a composite memory block only upon a positive outcome of the coalescing decision made that group; and
D) in response to each of at least one allocation request, allocates such a composite memory block. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. 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 instruction directing the computer system to derived for each of a pluralitity of size range a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
C) memory locations, included in the computer memory, that contain instructions directing the computer system to response respond to each of at least one release request that specifies a respective memory block by adding the memory block thereby specified to the inventory, whereby a memory-block run occurs if the release requests specify memory blocks adjacent to memory blocks already in the inventory, and, if such a run occurs;
i) making a coalescing decision, for each of at least one group of memory blocks within that memory-block run, that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated; and
ii) coalescing that group of memory blocks into a composite memory block only upon a positive outcome of the coalescing decision made for that group; and
D) memory locations, included in the computer memory, that contain instructions directing the computer system to respond to each of at east one allocation request, by allocating such composite memory block. - View Dependent Claims (26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36)
-
-
37. A computer signal representing sequences of instructions that, when executed by a computer system, cause it to operate as an allocator that:
-
A) maintains an inventory of memory blocks available for dynamic allocation;
B) for each of a plurality of size ranges, derives a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
C) in response to each of at least one release request that specifies a respective memory block, adds the memory block thereby specified to the inventory, whereby a memory-block run occurs if the release requests specify memory blocks adjacent to memory blocks already in the inventory, and, if such a run occurs;
i) for each of at least one group of memory blocks within that memory-block run, makes a coalescing decision that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated; and
ii) coalesces that group of memory blocks into a composite memory block only upon a positive outcome of the coalescing decision made for that ground; and
D) in response to each of at least one allocation request, allocates such a composite memory block. - View Dependent Claims (38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48)
-
-
49. A computer system that makes allocation requests, includes computer memory, and includes:
-
A) means for maintaining an inventory of memory blocks available for dynamic allocation;
B) means for deriving, for each of a plurality of size ranges, a demand indicator by monitoring run-time allocations of memory blocks whose sizes belong to that range;
C) means for responding to each of at least one release request that specifies a respective memory block by adding the memory block thereby specified to the inventory, whereby a memory-block run occur if the release requests specify memory blocks adjacent to memory blocks already in the inventory, and, if such a run occurs;
ii) for each of at least one group of memory blocks within that memory-block run, making a coalescing decision that depends on the value of at least one said demand indicator and the number of inventory memory blocks that are in the size range with which the demand indicator is associated; and
ii) coalescing that group of memory blocks into a composite memory block only upon a positive outcome of the coalescing decision made for that group; and
D) means for allocating such a composite memory block in response to each of at least one allocation request.
-
Specification