Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2000-02-15
2003-11-04
Gossage, Glenn (Department: 2751)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C711S170000, C707S793000
Reexamination Certificate
active
06643754
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to computer storage methods and systems, and more particularly to methods and systems for robust dynamic storage allocation.
2. Description of the Related Art
Many computer systems need to allocate storage dynamically. Dynamic storage allocation is used by operating systems to allocate storage for executing programs. Other examples of dynamic storage allocation may include Web servers which store Web data. In many cases, sizes of memory being requested are unknown until the time of the request. The lifetime for a dynamically allocated block may also be unknown.
A considerable amount of work has been performed in developing efficient dynamic storage allocation algorithms for main memory. Considerably less work has been done in developing efficient dynamic storage allocation algorithms for disks.
Dynamic storage allocation on disk is important for a number of reasons. In many cases, it is essential to have data which persists over time, even after the system is shut down. Disk memory provides persistent storage. Disk memory also provides fault-tolerant storage; information stored on disk can often be preserved after a system crash in situations where the contents of main memory are lost. Another advantage of disk memory includes the possibility that more of disk memory can be made available at a more reasonable price than main memory. It can thus be used for storing information which cannot fit in main memory.
Referring to
FIG. 1
, a first fit system allocates (all or part of) the first memory block located which is large enough to satisfy a memory request. For a memory request of “7”, a first fit returns B
1
since this is the first block encountered which can satisfy the request. A best fit system allocates (all or part of) a smallest block which is large enough to satisfy a request. In
FIG. 1
, block B
3
would be returned since “7” fits best in B
3
(which has a capacity of 8).
Referring to
FIG. 2
, in a binary buddy system, block sizes are in powers of 2 (e.g., 4 and 4, 8 and 8, etc.). Many dynamic storage allocators (DSA's) maintain one or more lists of free blocks. Such lists are known as free lists, e.g., lists of free blocks. Separate free lists exist for blocks of different sizes. Buddy system allocating blocks of other sizes also exist as well. A good overview of prior art in dynamic storage allocation is described in a paper by Arun Iyengar titled “Scalability of Dynamic Storage Allocation Algorithms” published in Proceedings of IEEE Frontiers '96, October 1996, as well as the bibliographic references in this paper.
Dynamic storage allocators (DSAs) can use different methods for coalescing adjacent free blocks. One approach is to use immediate coalescing, in which a deallocated block is combined with neighboring free blocks at the time the block is deallocated as shown in FIG.
3
. In
FIG. 3
, the block sizes are indicated in each block. A positive size indicates a free block, while a negative size indicates an allocated block.
Referring to
FIG. 4
, another approach includes deferred coalescing. When deferred coalescing is used, adjacent free blocks are not automatically combined after a deallocation. Instead, at some point (such as when a large enough block to satisfy a request cannot be located), the DSA will scan through blocks in memory and combine adjacent ones as shown in FIG.
4
.
Fragmentation is memory wasted by a DSA. Internal fragmentation is memory lost by satisfying a request with a block larger than the request size (e.g., satisfying a request for a block of size
25
with a block of size
32
). External fragmentation occurs when free blocks become interspersed with allocated blocks. In these situations, an allocation request for b bytes may be unsatisfiable even if >b bytes are free because the largest contiguous block of free storage is smaller than b bytes.
Multiple free list fit I (MFLF I) as described in “Scalability of Dynamic Storage Allocation Algorithms” cited above uses multiple free lists, organized by size. Free lists for small blocks are known as quick lists. Free lists for large blocks are known as misc lists. When a single misc list is maintained, MFLF I degenerates into a storage allocation system known as quick fit.
Referring to
FIG. 5
, a quick fit technique is shown. In this system, quick lists exist for blocks up to size 16; the number of quick lists can be varied to optimize performance for different request distributions. In this example, allocations for a block of size s where 2≦s≦16 (2 is the minimum block size) is done by examining the quick list for size s. If this list is not empty, the first block on the list is used to satisfy the request. Note that it is possible to have quick lists for block sizes corresponding to multiples of grain sizes. For example, in
FIG. 2
, the grain size is
1
. If the grain size is
1000
, quick lists for blocks of size
1000
,
2000
,
3000
, . . . ,
16000
, (a total of 16 quick lists) may be used. MFLF I uses deferred coalescing. Memory is divided into working storage
12
and a tail
14
as shown in FIG.
5
. Working storage
12
includes allocated blocks and blocks on a free list. Tail
14
includes a contiguous block of unallocated storage at one end of the memory. Initially, before anything is allocated, tail
14
includes all allocatable memory, and free lists are empty. free lists include quick lists and misc lists, where misc lists are employed for larger memory blocks. Blocks
13
include a size (indicated by the numbers in blocks
13
). When a request cannot be satisfied by examining one or more free lists, the request is satisfied by allocating from tail
14
. A tail pointer (tail ptr.) indicates where tail
14
begins. Free lists are populated when allocated blocks are deallocated.
To satisfy a request for a block which is too large for a quick list, quick fit does a first fit search of the misc list. Searches for large blocks may require many instructions. To reduce this overhead, MFLF I can use multiple misc lists, as indicated in
FIG. 6
, instead of a single list as in quick fit. In
FIG. 6
, a misc list exists for blocks
13
of size
17
-
25
, another one exists for blocks
13
of size
26
-
40
, and yet another one exists for blocks of size
41
-
60
. Various strategies can be used for satisfying a request, including the one shown in
FIGS. 7A and 7B
to allocate “
84
” using MFLF I.
FIG. 7A
shows a “before” snapshot of memory while
FIG. 7B
shows an “after” snapshot when the request to allocate
84
is satisfied. In
FIGS. 7A and 7B
, the system allocates a first block on list L
2
to satisfy the request by splitting a block of size “
90
” and returning the excess of size “
6
” to a free list. The system examines L
2
instead of L
1
because a smallest block allowed on L
2
is of size
89
. Therefore, it is not necessary to search beyond the first block in L
2
to satisfy a request of size less than or equal to
89
.
Although the techniques described above are sufficient for many applications, straightforward adaptations of main-memory dynamic storage allocation algorithms to disk systems often result in poor performance because the latency for accessing and writing to disks is much higher than for main memory.
Therefore, a need exists for dynamic storage methods for disk memory which reduces a number of accesses and a number of writes to a disk. A further need exists for memory allocation and deallocation methods which provide for more efficient storage and faster access times.
SUMMARY OF THE INVENTION
A method for managing computer memory, in accordance with the present invention, includes maintaining multiple sets of free blocks of memory wherein a free block is added to a set based on its size. In response to a request for a block of a request size, a set of blocks is searched for a free block which is at least as large as the request size but smaller than the request size plus a threshold. If such a block is found, the block is allocated in its entirety. In o
Challenger James R. H.
Iyengar Arun K.
F.Chau & Associates, LLP
Gossage Glenn
LandOfFree
System and method for dynamically allocating computer memory does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for dynamically allocating computer memory, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for dynamically allocating computer memory will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3176258