This course is run at the The University of Nottingham within the School of Computer Science & IT. The course is run by Graham Kendall (EMAIL : gxk@cs.nott.ac.uk)
If we keep a list of holes sorted by their size, we can make allocation to
processes very fast as we only need to search down the list until we find a
hole that is big enough.
The problem is that when a process ends the maintenance of the lists is complicated. In particular, merging adjacent holes is difficult as the entire list has to be searched in order to find its neighbours.
The Buddy System (Knuth, 1973; Knowlton, 1965) is a memory allocation technique that works on the basis of using binary numbers as these are fast for computers to manipulate.
This is how the buddy system works.
Lists are maintained which store lists of free memory blocks of sizes 1, 2,
4, 8,…, n, where n is the size of the memory (in bytes). This means that
for a one megabyte memory we require 21 lists.
If we assume we have one megabyte of memory and it is all unused then there
will be one entry in the 1M list; and all other lists will be empty.
|
Now assume that a 112K process (process A) needs to be swapped into memory.
As lists are only held as powers of two we have to allocate the next highest
memory that is a power of two; in this case 128K.
The 128K list is currently empty. In fact, every list is empty except for the 1M list.
Therefore, we split the 1M block into two 512K blocks. One of the 512K blocks
is then split into 256K blocks and one of the 256K blocks is split into two
128K blocks; one of which is allocated to the process.
This situation is shown in the diagram above. At this stage we have three lists with one entry (128K, 256K and 512K) and the 1M list is empty (as are all the other lists).
The reason the scheme is known as the buddy system is because each time a block
is split it is called a buddy.
Next, a process (process B) requiring 35K might be swapped in. This will require
a 64K block. There are no entries in the 64K list so the next size list is considered
(128K). This has an entry so two buddies are created and the process is allocated
to one of those blocks.
If we now request an 80K process (process C), this will have to occupy a 128K block, which will come from the 256K list.
What happens if process A ends and releases its memory? In fact, the block of memory will simply be added to the 128K list.
If another process now requests 60K of memory it will find an entry in the 64K list, so can be allocated there.
Now process B terminates and releases its memory. This will simply place its
block in the 64K list.
If process D terminates we can start merging blocks. This is a fast process
as we only have to check adjacent lists and check for adjoining addresses.
Finally, process C terminates and we can merge all the way back to a single list entry in the 1M list.
The reason the buddy system is fast is because when a block size of 2k bytes is returned only the 2k list has to be searched to see if a merge is possible.
The problem with the buddy system is that it is inefficient in terms of memory
usage. All memory requests have to be rounded up to a power of two. We saw above
how an 80K process has to be allocated to a 128K memory block. The extra 40K
is wasted.
This type of wastage is known as internal fragmentation. As the wasted memory is internal to the allocated segments. This is the opposite to external fragmentation where the wasted memory appears between allocated segments.
For the interested student (Peterson, 1977) and (Kaufman, 1984) have modified
the buddy system to get around some of these problems.
| Last Page | Back to Main Index | Next Page |
Last Updated : 23/01/2002