THINK FIRST·CODE LATER

← All labs

Contiguous allocation: first, best, worst and next fit

Problem

Simulate a contiguous memory allocator.

Input: the policy (first, best, worst or next), the memory size, then operations alloc NAME size and free NAME until the end of input. Initially memory is one hole [0, size).

  • Holes are kept sorted by address; a block is always placed at the start of the chosen hole. Ties: the lowest address.
  • Next fit starts searching at the first hole that ends after the end of the last allocated block, and wraps around.
  • On free, merge the freed block with adjacent holes.

Output: alloc A 200 -> [0, 200) or alloc F 180: FAILED (free 360, largest hole 150); free A -> holes [0, 200) [850, 1000). At the end: Final holes: … (or none), Free: X, largest hole: Y, failed requests: Z, and External fragmentation: P% where P = round(100 × (free − largest) / free) (0 if nothing is free).

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-1-data-1.txt — first 14 lines of 15

first 1000
alloc A 200
alloc B 50
alloc C 100
alloc D 50
alloc E 300
alloc F 50
free A
free C
free E
alloc G 90
alloc H 250
alloc I 200
alloc J 100
What your program must print for os9-1-data-1.txt
alloc G 90 -> [0, 90)
alloc H 250 -> [400, 650)
alloc I 200 -> [750, 950)
alloc J 100 -> [90, 190)
alloc K 200: FAILED (free 210, largest hole 100)
Final holes: [190, 200) [250, 350) [650, 700) [950, 1000)
Free: 210, largest hole: 100, failed requests: 1
External fragmentation: 52%

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-1-data-1.txt

Windows PowerShell does not understand <:

Get-Content os9-1-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.