## 827 - Buddy Memory Allocator

Moderator: Board moderators

uzioriluzan
New poster
Posts: 27
Joined: Thu Feb 14, 2002 2:00 am

### 827 - Buddy Memory Allocator

Is there any trick with this problem? Does anyone have an interesting input?
Thanks a lot!

potato
New poster
Posts: 9
Joined: Tue Feb 25, 2003 8:13 am

### 827 Buddy Memory Allocator

I don't quite understand this statement in the problem:
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.
What does 'most recently declared free' mean??

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
For each possible size for a block (2^lowerBound, ..., 64, 128, 256, ..., 2^upperBound), you have a data structure of some sort which stores all the free blocks of that size.

When you need to allocate a block of size S and there is more than 1 free block of size S, there is a choice as to which one to allocate. You should choose to allocate the free block of size S which was added to the data structure of free blocks for size S the most recently. i.e. the last block of size S which was unallocated by a process/created from splitting a block of size 2 * S.

i.e. use a stack to implement the data structure for storing all free blocks of a given size.

Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States
Here are a few test cases:
7

10 4
A 70
B 35
C 80
A 0
D 60
B 0

10 4
A 70
B 35
C 80
A 0
D 60
B 0
C 0

10 4
A 70
B 35
C 80
A 0
D 60
B 0
D 0

10 4
A 70
B 35
C 80
A 0
D 60
B 0
C 0
D 0

10 4
A 70
B 35
C 80
A 0
D 60
B 0
D 0
C 0

10 4

10 4
A 70
A 0
and the expected output:
Hole:128
Hole:64
D:60
C:80
Hole:128
Hole:512

Hole:128
Hole:64
D:60
Hole:256
Hole:512

Hole:256
C:80
Hole:128
Hole:512

Hole:1024

Hole:1024

Hole:1024

Hole:1024
It would be useful to also try a few tests where there a choice between what block to allocate - The program should choose most recently freed block/block which was most recently created from splitting a larger block (with the lower address block given preference).

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
What is the correct output for the following input set?

Input:

Code: Select all

``````2

10 2
A 2
C 64
A 0
E 64
F 64

10 2
A 2
C 64
A 0
C 0
E 64
F 64``````

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

### Re: 827 - Buddy Memory Allocator

I think, that specification of problem is a bit misleading. Consider this two sentences:
1.
Whenever possible, an unnallocated buddy is merged with a companion buddy in order to form a larger free block.
2.
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.
First sentence leads to solution, in which we should, after termination of executed program, create as large free block as possible (I think binary tree is very good to do this). Second sentence suggest us that we can't create as large free block as possible, because we loose information about most recently declared free block of memory !!

Maybe correct solution (but problem statement says nothing about it - if I didn't miss anything) should combine free blocks only if larger amount of data is needed and no free block of requested size exists (this leads to unoptimal using of memory of course) ? But in this case what program should do if exists 2 companion buddies of size s and one of size 2s and we ask for block of size 2s ?

What should happen if situation looks like:
M: 1024k
request for 128k
M: 128k (used), 128k, 256k, 512k
request for 512k
M: 128k (used), 128k, 256k, 512k (used)
free 512k
M: 128k (used), 128k, 256k, 512k
free 128k
M: 128k, 128k, 256k, 512k
request for 256k <------- application should combine 2 128k blocks in one bigger and allocate it or get existing 256k block ?

Could anyone explain me which way we should use ?
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 827 - Buddy Memory Allocator

Input:

Code: Select all

``````4

10 2
A 2
C 64
A 0
E 64
F 64

10 2
A 2
C 64
A 0
C 0
E 64
F 64

10 2
A 128
B 512
B 0
A 0
C 256

10 2
A 64
B 64
C 64
D 64
B 0
C 0
E 64``````
AC output:

Code: Select all

``````E:64
C:64
F:64
Hole:64
Hole:256
Hole:512

E:64
F:64
Hole:128
Hole:256
Hole:512

C:256
Hole:256
Hole:512

A:64
Hole:64
E:64
D:64
Hole:256
Hole:512``````
When a process terminates, I create the largest free block possible by combining companion buddies. If all processes have terminated, the state is then the same as the beginning of that test case, one free memory block of size 1<<U. I keep a list of free blocks of each size, the location and size of each running process, and the current status of each block of memory. When modifying (splitting or merging) the size of a block, it then becomes the most recently declared free block of the new size. The list of free blocks of each size behaves as a stack, except possibly when merging companion buddies you may have to remove a block from inside the stack.
Check input and AC output for thousands of problems on uDebug!