OS II-Lec7 Buddy Fragmentation

Buddy System
Both fixed and dynamic partitioning schemes have drawbacks. A fixed partitioning scheme limits the number of active processes and may use space inefficiently if there is a poor match between available partition sizes and process sizes. A dynamic partitioning scheme is more complex to maintain and includes the overhead of compaction. An interesting compromise is the buddy system.
In a buddy system, memory blocks are available of size 2K words, L K U, where 2L smallest size block that is allocated?2U largest size block that is allocated; generally 2U is the size of the entire memory available for allocation
To begin, the entire space available for allocation is treated as a single block of size 2U. If a request of size s such that 2U-1 < s 2U is made, then the entire block is allocated. Otherwise, the block is split into two equal buddies of size 2U-1. If 2U-2 < s 2U-1, then the request is allocated to one of the two buddies. Otherwise, one of the buddies is split in half again. This process continues until the smallest block greater than or equal to s is generated and allocated to the request. At any time, the buddy system maintains a list of holes (unallocated blocks) of each size 2i. A hole may be removed from the (i 1) list by splitting it in half to create two buddies of size 2i in the i list. Whenever a pair of buddies on the i list both become unallocated, they are removed from that list and coalesced into a single block on the (i 1) list. Presented with a request for an allocation of size k such that 2i-1 < k 2i, the following recursive algorithm (from [LIST93]) is used to find a hole of size 2i: