827 - Buddy Memory Allocator

[uzioriluzan]

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

[potato]

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]

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]

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]

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]

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 ?

[brianfry713]

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.