THINK FIRST·CODE LATER

← All labs

Multicore load balancer with affinity

Problem

Balance tasks across cores, respecting pinned tasks (hard affinity).

Input: first line: number of cores k. Then k lines, one per core (core 0 first), each listing its tasks as name:load or name:load:pin separated by spaces, or - for an empty core.

Algorithm (push migration): repeat —

  1. Find the busiest core (highest total load) and the least loaded core (lowest total); on ties take the lower core number.
  2. Among the busiest core's unpinned tasks whose load is strictly smaller than the gap (busiest load − least load), choose the one with the largest load (on ties, the one listed first).
  3. If there is none, stop. Otherwise move it to the end of the least-loaded core and print move NAME (L) from core A to core B.

Print Before: core0=… core1=… at the start, After: … at the end, then Moves: m, imbalance (max - min): d.

Input:

4
A:30 B:20 C:10 D:20
E:10
F:20:pin G:10
-

Output:

Before: core0=80 core1=10 core2=30 core3=0
move A (30) from core 0 to core 3
move B (20) from core 0 to core 1
After: core0=30 core1=30 core2=30 core3=30
Moves: 2, imbalance (max - min): 0

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.

os5-3-data-1.txt

4
A:30 B:20 C:10 D:20
E:10
F:20:pin G:10
-
What your program must print for os5-3-data-1.txt
Before: core0=80 core1=10 core2=30 core3=0
move A (30) from core 0 to core 3
move B (20) from core 0 to core 1
After: core0=30 core1=30 core2=30 core3=30
Moves: 2, imbalance (max - min): 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 < os5-3-data-1.txt

Windows PowerShell does not understand <:

Get-Content os5-3-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.