Memory management, specially memory allocation to processes, is a fundamental issue in operating systems. 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, the entire memory space available for allocation is initially treated as a single
block whose size is a power of 2. 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 first-come first-served 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 (2U k) 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
solve in c++. use vector to stor binary tree. also for every vertex store the time it was created. use this rule 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. store using multiset what sizes of blocks are currently created to find lower bound and if it is not the smallest go for that tree level find with last time created and divide it