THINK FIRST·CODE LATER

← All labs

VM placement: FF, BF, FFD and BFD with a power model

Problem

Input: policy (FF, BF, FFD, BFD), host capacity cpu mem, then VMs name cpu mem until the end of input. Hosts are identical and opened on demand.

  • FF: the first open host where the VM fits (CPU and memory); otherwise open a new host.
  • BF: among hosts where it fits, the one with the smallest remaining normalized space after placement: (remCpu − cpu)/capCpu + (remMem − mem)/capMem; ties → lowest index.
  • FFD / BFD: first sort VMs by their dominant demand max(cpu/capCpu, mem/capMem), largest first (stable for ties), then apply FF / BF.
  • A VM larger than a host prints X -> REJECTED (larger than a host) (it still counts in the lower bound).

Print A -> H1 per VM (in placement order), then for each host H1 [A, B, E] cpu 8/10 (80%), mem 14/32 (44%), then FF: 4 hosts (lower bound 3), power 850 W, where the lower bound is ⌈max(ΣCPU/capCpu, ΣMem/capMem)⌉ and each host draws 100 + 150 × CPU utilization watts.

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.

os12-1-data-1.txt

FF 10 32
A 2 4
B 5 8
C 4 4
D 7 8
E 1 2
F 3 4
G 8 4
What your program must print for os12-1-data-1.txt
A -> H1
B -> H1
C -> H2
D -> H3
E -> H1
F -> H2
G -> H4
H1 [A, B, E] cpu 8/10 (80%), mem 14/32 (44%)
H2 [C, F] cpu 7/10 (70%), mem 8/32 (25%)
H3 [D] cpu 7/10 (70%), mem 8/32 (25%)
H4 [G] cpu 8/10 (80%), mem 4/32 (13%)
FF: 4 hosts (lower bound 3), power 850 W

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

Windows PowerShell does not understand <:

Get-Content os12-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.