- requires longer searching for a free block
- allows faster searching for free block
- variations allows faster searching and/or insertion:
- segregated free lists (blocks grouped by size)
- sorted free list (by size, possibly a tree)
| COP 4610: Operating Systems & Concurrent Programming |
These notes deal with data structures and algorithms for memory management. They have a number of different applications. The one that is probably familiar to most people is the dynamic allocation of virtual memory within a process, as is done by malloc().
The two operations any memory manager must support are requests for allocation and deallocation (freeing) of storage.
When allocating:
When freeing:
There are a few basic questions that any implementation of these two operations must answer.
When allocating, we must have a way to identify the set of free blocks. Given we can find out which blocks are free, we need a way to choose which of them to allocate. Given we have chosen which one to allocate, if it is not an exact fit we need to decide what to with the left-over fragment.
When freeing a block, we are only given a pointer to the block. From this pointer, we must find out the size of the block. Once we have found the size of the block, we must find out whether it has any adjacent free blocks, and if there are such blocks we need to know their locations in order to coalesce (combine) them together into a single free block.
We need to know whether the two neighbor blocks are free, so that if they are free we can coalesce (combine) them into a single free block. If we do not coalesce adjacent free blocks, our storage will become fragmented into smaller and smaller blocks, and after a time will not be able to allocate any more large blocks.
The figure shows the four different cases we need to recognize and deal with. The pink-filled rectangles represent areas of storage that are allocated, and the white rectangles represent areas of storage that are free. The left part of the figure shows the four possible cases for the neighbors of a block X that is freed. The right part of the figure shows what should happen after the block X is freed and we have finished coalescing any adjacent pairs of free blocks.
The usual method:
This figure shows individual bytes (dashed lines) within words, for a 32-bit word architecture, and the size is shown in bytes. Later, in the figures below, we will simplify, showing only whole word boundaries are shown, and giving the sizes as counts of whole words.
The function free() takes only one parameter, which is a pointer, of type void *. Somehow, the implementation of free() must infer the size of the entity pointed to by this pointer, so that it knows how much memory to free.
You can keep the size (i.e., length) of an allocated entity in the word preceding it in memory. This extra word is called a header. This method takes extra memory, one word for each allocated entity.
The storage required for the header is sometimes called overhead. The remaining space, available to the user, is sometimes called the payload.
In these figures each box represents a whole word, capable of storing an integer or a pointer. The white boxes represent free words of memory, and the pink shaded boxes represent words that are not free.
We can see from the first figure that with the block sizes we do not need any pointers to traverse the list of blocks. We can start from the beginning of the managed memory region, and step from each block to the block by adding the block size. We call these block sizes implicit pointers because they are not full pointers, but they contain enough information to serve the same purpose.
Notice that with the implicit list representation the list contains all the blocks, both allocated and free. Some further data is needed to tell which blocks are free and which are allocated.
Observing that each free block contains some storage that is not otherwise in use, we can make use of that storage to speed the search of the free blocks. One way is put in a pointer to the next free block. Using this kind of explicit free list we can traverse the list of free blocks without having to go through all the allocated blocks. This saves time when we are looking for a free block of a given size. It also solves the problem of distinguishing free blocks from allocated blocks, since a block is free if-and-only-if (iff) it is in the list.
Once we accept the idea of storing pointers in the free blocks, we can imagine all sorts of linked data structures, which may enable us to speed up the search for a free block of a given size. For example, we could keep several lists of blocks, grouped by approximate size. This would save us time when we are looking for larger sized blocks, because we can skip over the lists of smaller sized blocks. If we want to go further, we can build a search tree, ordered by block size, and use binary search go to the size of block we want within O(log n) time.
Three of the most basic algorithms for selecting which of the free blocks to allocate for a request of a given size are listed here. These and other algorithms were studied extensively in the 1960's, before the days of virtual memory, when operating systems needed then to manage process storage and when applications programmers routinely had to manage their own storage within a program (because programming language implementations did not yet have built-in dynamic storage management like malloc() and free()). A number of simulation studies were performed, testing various placement algorithms.
The following summaries are not so scientific, but try to provide a little bit of intuitive rationale for differences between the algorithms.
First fit tends to allocate blocks preferentially in the lower end of storage (which it searches first). After repeated allocations, splits, deallocations, and coalescing, the lower end of storage tends to have a higher density of allocated blocks, smaller allocated blocks, and smaller-than-average free blocks. That most of the blocks in the lower end of memory are allocated already makes searching for a free block slow if you are using an implicit list. You have to search past all the allocated blocks first. Even with an explicit list, the high density in the lower end of storage of free blocks that are smaller than the average request size means you often have to search far down the free list to find and average-sized. This can be counteracted, though, by using a set of free lists segregated by block size, or a free-block search tree.
Next fit tends to allocated blocks uniformly across the memory. This means there is less chance of finding a really large block when you need one, but searching for a block to fit an average-case request does not take as long as with First Fit. You can preserve one large block at the end, by making it a special case (cycling over only the other blocks in normal searches), but you still have more problems with fragmentation than first fit or best fit.
Best fit is often criticised for creating tiny fragments, when a free block is chosen that is just a little bit larger than the request. If unchecked, this can lead to very bad fragmentation. However, there is a way to limit the problem. You just set a lower limit on the size of (external) fragment that is allowed. If splitting a block would create too small a fragment, you just leave the block entire, allocating a bit more than was requested. This keeps the fragment with the block (an internal fragment), so that when the block is freed the fragment will come with it. Best fit is also sometimes criticised for long search times. Certainly with an implicit free list (ordered by memory location), one may need to search the full length of the list to find the best fit (if no exact fit is found first). However, if we take advantage of explicit pointers to build a free list that is structured for fast searching, we can cut the search time down to O(log n) in the number of free blocks.
General rules:
Buddy System:
In general, if the block is too large, we need to split of the unused part and return it to the free list. However, if the unused part is very small, it may be better to just round up the size of the block, so that we don't chop up our free storage into excessively many small fragments.
The buddy system uses a special rule that is consistent with the above principles. It never splits off a fragment unless the fragment is at least as big as the block that is being allocated, rounded up to a power of two.
Subproblems:
The problem of coalescing breaks naturally into three parts. First, we must find (beginnings of) the neighbor blocks. Then, we must determine whether they are free or alread allocated. Finally, if they are free, we must update the free-list data structures to reflect the coalescing of the blocks.
With a free list ordered by memory address, we can find the nearest already-free blocks to the one we are about to free (say at address X) by traversing the list and comparing the block addresses against X. If the addresses go from less than X to greater than X, we know we have just passed block X. The problem with this is that it is slow, linear in the length of the free list.
The only real problem is finding the left-neighbor (the one toward the lower-address end of memory). We can find the right neighbor by adding the block size, just as when we traverse the implicit list. If we are willing to store the block length at both ends of each block, we can also traverse the implicit list in the other direction, and find the left neighbor. This adds to our storage overhead, of course, reducing our payload by one more word.
Traversing the free list, if we use an explicit free list can be used to find out whether the neighbor blocks are free, but it takes time linear in the number of free blocks.
A faster solution is to use one bit at each end of the block to tell whethe the block is free. This is called a boundary tag. If we already have the length storage at both ends of the block, we can just use the sign bit of that field to tell whether the block is free. For example, we could agree that if the size is negative it means the block is in use, as shown in the figure.
Again, the updating of the free list is simplest if we use boundary tags and the implicit list. All we need to do is update the sizes at the two ends of the coalesced new free block. With an explicit free list, we need to patch up pointers. The problem case is when only the right-neigbor is free, so the incoming pointer to the right neighbor needs to be shifted to point to the newly freed block. This means we must be able to locate the preceding free block in the list quickly. One way is to make the free list a doubly linked list.
When implementing a storage manager you need to compute and compare sizes of storage objects, and create pointers to chunks of storage. In this kind of programming you treat pointers as addresses (which is what they really are). You will need to type-cast between different pointer types, and do arithmetic on pointer values. Take care when you do pointer arithmetic that you are not trapped into making an error because of misunderstanding C pointer arithmetic. To avoid this, before doing arithmetic I generally cast all pointers to type char *, so that arithmetic is done in term of bytes. If you do not do this, the results of the arithmetic may not be what you want. For example, if p is a pointer variable of type int * and an int value occupies 4 bytes, p = p + 1; actually adds four (4) to the address that is stored in the pointer. That is correct for pointer arithmetic. The "1" in "p + 1" means "the size of one object of the type pointed to by p", which in this case is 4.
For example, consider the following program:
#include <ctype.h>
#include <stdio.h>
typedef struct mystruct {
char eightchars[8];
} * myptr;
struct mystruct x;
int main (int argc, const char *argv[]) {
myptr p1, p2;
char * a1, * a2;
fprintf (stderr, "sizeof (struct mystruct) = %d\n\n", sizeof (struct mystruct));
fprintf (stderr, "(int) &x = %d\n", (int) &x);
fprintf (stderr, "(int) (&x + 1) = %d\n", (int) (&x + 1));
fprintf (stderr, "(int) &x + 1 = %d\n", (int) &x + 1);
fprintf (stderr, "(int) ((char *)(&x) + 1) = %d\n\n", (int) ((char *)(&x) + 1));
p1 = &x;
p2 = p1 + 1;
fprintf (stderr, "(int)(p2 - p1) = %d\n", (int)(p2 - p1));
fprintf (stderr, "(int)(p2) - (int)(p1) = %d\n\n", (int)(p2) - (int)(p1));
a1 = (char *) p1;
a2 = a1 + 1;
fprintf (stderr, "(int)(a2 - a1) = %d\n", (int)(a2 - a1));
fprintf (stderr, "(int)(a2) - (int)(a1) = %d\n\n", (int)(a2) - (int)(a1));
return 0;
}
Because the size of an object of type struct mystruct is 8, "+1" on the address of object x or the pointer p1 means add 8 bytes.
The full output of the program is as follows:
sizeof (struct mystruct) = 8 (int) &x = 138140 (int) (&x + 1) = 138148 (int) &x + 1 = 138141 (int) ((char *)(&x) + 1) = 138141 (int)(p2 - p1) = 1 (int)(p2) - (int)(p1) = 8 (int)(a2 - a1) = 1 (int)(a2) - (int)(a1) = 1
The point of this example is that the effect of adding an integer to a pointer depends on the type of the pointer.
For individuals unaccustomed to writing low-level C code, the following bits of code illustrate how some of the operations described above can be coded in C:
#define ALIGN (sizeof (size_t)) #define round_up(size) ((size + ALIGN - 1) / ALIGN * ALIGN)
typedef struct pool_block_header {
size_t size;
} * pool_block_ptr;
/* The following macros help us remember to adjust the pointers
we give to and get from the user, so that the user's view
does not include the part of the block we use for housekeeping.
pointer
|
| add_offset (pointer)
+------+---------------------------------------------+
| size | |
+------+---------------------------------------------+
sub_offset (pointer)
|
| pointer
+------+---------------------------------------------+
| size | |
+------+---------------------------------------------+
*/
#define BLKOFF sizeof(struct pool_block_header)
#define add_offset(pointer) (((char *) pointer) + BLKOFF)
#define sub_offset(pointer) (((char *) pointer) - BLKOFF)
Note that the macros above are similar to macros in the Linux kernel header file list.h. The ones here are much simpler, because they are specific to one structure.
| © 2002, 2005 T. P. Baker & Florida State University. No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means without written permission. (Last updated by $Author: cop4610 $ on $Date: 2002/09/26 20:06:06 $.) |