827 - Buddy Memory Allocator

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

827 - Buddy Memory Allocator

Post by uzioriluzan » Mon Nov 04, 2002 1:12 am

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

Post by potato » Thu Apr 24, 2003 5:13 am

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?? :(

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Wed Jun 25, 2003 7:40 am

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.

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by rjhadley » Wed Jun 25, 2003 7:47 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Mar 11, 2008 9:43 pm

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
Thanks in advance.

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

Re: 827 - Buddy Memory Allocator

Post by Dominik Michniewski » Thu Apr 14, 2011 7:27 am

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

Post by brianfry713 » Tue Jan 15, 2013 12:49 am

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!

Post Reply

Return to “Volume 8 (800-899)”