Buddy System Allocator in Operating System
Buddy System Allocator in Operating System
While dealing with Memory management, especially memory allocation to processes, we need to take care of fundamental issue such that the allocation done is most efficient and least probable to be insufficient.
As discussed before a fixed partitioning scheme bars the number of processes that can be accommodated in the memory space and also lead to inefficiency.
Why Buddy System Allocator?
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 solution is the buddy system.
Buddy System: How it works
In a buddy system, the entire memory space available for allocation is treated as a single block whose size is a power of 2.
Suppose that the size of memory is 2U and the requirement is of size S.
Allocation can happen if –
- If 2U-1<S<=2U: is satisfied else
- Recursively divide the block equally and test the condition at each time, when it satisfies, allocate the block and get out the loop.
Advantage
- Faster allocation of memory and even faster deallocation
- More useful.
Using the above method itself, if we assume that physical address space is of 128KB and we need the allocation for 18KB partition. Then it will fall into the 32KB partition. Check the image above to understand the same.
Linux also uses buddy system to allocate the memory.
Disadvantage
The disadvantage of this approach is that it wastes a lot of memory in internal fragmentation since all the blocks are rounded of to the size of two.
Only the above should be known if preparing for placements. More information is given below but, its not vital.
Detailed Analysis (Not Important)
When the first request is made, if its size is greater than half of the initial block then the entire block is allocated. Otherwise, the block is split in two equal companion buddies. If the size of the request is greater than half of one of the buddies, then allocate one to it.
Otherwise, one of the buddies is split in half again. This method continues until the smallest block greater than or equal to the size of the request is found and allocated to it.
In this method, when a process terminates the buddy block that was allocated to it is freed. Whenever possible, an unnallocated buddy is merged with a companion buddy in order to form a larger free block. Two blocks are said to be companion buddies if they resulted from the split of the same direct parent block.
The following figure illustrates the buddy system at work, considering a 1024k (1-megabyte) initial block and the process requests as shown at the left of the table.
Your task is to implement a buddy memory manager and simulate it at work. You will be given the upper and lower sizes admissible for blocks in the system and a list of requests. A request is made for a process and it may either be for a block of a certain size or just an indication of termination.
Requests should be attended in a firstcome firstserved basis. After serving all requests, your program should display the state of the buddy system at that point, indicating which processes are in memory and which blocks are free. Notice that, whenever there is a request that corresponds to a block of size s, your program should select the block of that size that was most recently declared free.
Furthermore, when a block is split in two, the left-one (lower addresses) should be selected before the right-one. You can assume that the list of requests is such that all requests can always be served.
In other words, you can make the following assumptions: no process will request more than the available memory; processes are uniquely identified while active; and no request for process termination is issued before its corresponding request for memory allocation
Input
The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.
The first line of input consists of two numbers, U and L, that determine the upper (2Uk) and lower (2Lk) block sizes admissable. You can assume U > L > 0. The following input lines are requests being made, one per line.
A request is defined by two values, P and S, where P is a capital letter that identifies the process associated with the request, and (S>= 0) is a number. If S > 0 then it is a memory block request; Otherwise (S = 0) it is a request indicating that process P has terminated.
Output
For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line. The output must list the state of the buddy immediatly after having served the last request. This corresponds to listing the processes still in memory, if any, and the free blocks (holes) available. Processes and holes must be listed in a left to right order as you traverse the buddy (i.e. from lower addresses towards upper memory addresses). The output format for processes is P : S, P is the process identifier and S its size, and for holes is Hole:S where S is the size of the free block
Sample Input
1 10 4 A 70 B 35 C 80 A 0 D 60 B 0
Sample Output
Hole:128 Hole:64 D:60 C:80 Hole:128 Hole:512
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment