THINK FIRST·CODE LATER

← All labs

The Linux buddy allocator

Problem

Simulate a buddy allocator.

Input: total memory (a power of two) and the minimum block size (a power of two), then alloc NAME size / free NAME operations.

  • alloc: round the size up to a power of two (at least the minimum). Take the smallest free block that is large enough (lowest address among equal sizes); split it in halves repeatedly, keeping the lower half and putting the upper half on the free list, until it has the right size. Print alloc A 70 -> block 128 at 0 (splits 3, internal waste 58) or alloc X 900: FAILED (needs a 1024 block).
  • free: repeatedly merge the block with its buddy (address XOR size) if the buddy is free with the same size. Print free D -> free block 256 at 0 (merges 2).

At the end print Free blocks: 64@192 … sorted by size then address (or none) and Allocated: B in blocks for R requested, internal fragmentation F (P%) — omit the percentage when nothing is allocated.

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

os9-4-data-1.txt

1024 64
alloc A 70
alloc B 35
alloc C 80
free A
alloc D 60
free B
free D
free C
What your program must print for os9-4-data-1.txt
alloc A 70 -> block 128 at 0 (splits 3, internal waste 58)
alloc B 35 -> block 64 at 128 (splits 1, internal waste 29)
alloc C 80 -> block 128 at 256 (splits 1, internal waste 48)
free A -> free block 128 at 0 (merges 0)
alloc D 60 -> block 64 at 192 (splits 0, internal waste 4)
free B -> free block 64 at 128 (merges 0)
free D -> free block 256 at 0 (merges 2)
free C -> free block 1024 at 0 (merges 3)
Free blocks: 1024@0
Allocated: 0 in blocks for 0 requested, internal fragmentation 0

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < os9-4-data-1.txt

Windows PowerShell does not understand <:

Get-Content os9-4-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.