Buddy System Memory Manager ~ Fall 2012
The Buddy System Memory Manager was a project for Operating Systems at Boise State University. The goal of the project was to self-handle all of the memory that we were using. This allowed us to bypass the normal malloc/alloc routines for our own versions.
Ultimately this memory manager was incorporated into my version of the Bash shell (the dash Shell), and proved completely effective. The idea of the algorithm is as follows: Buddy systems are a subclass of strict segregated fit allocation mechanisms which make splitting and coalescing fast by pairing each block with a unique adjacent buddy block. There is an array of free lists, one for each allowable block size. Allocation rounds up the requested size to an allowable size and allocates from the corresponding free list. If the free list is empty, a larger block is selected and split. A block may only be split into a pair of buddies. A block may only be coalesced with its buddy, and this is only possible if the buddy has not been split into smaller blocks. The advantage of buddy systems is that the buddy of a block being freed can be quickly found by a simple address computation. The disadvantage of buddy systems is that the restricted set of block sizes leads to high internal fragmentation, as does the limited ability to coalesce. Performance of Buddy compared to malloc: [james@fedoraOne buddySystem]$ time ./buddy-test 20000000 1234 s real 0m2.872s user 0m2.851s sys 0m0.008s [james@fedoraOne buddySystem]$ time ./malloc-test 20000000 1234 s real 0m4.015s user 0m3.991s sys 0m0.001s From this timing we know that buddy does outperform malloc in pure speed. |
Program Files
| ||
