THINK FIRST·CODE LATER

← All labs

Wait-for graph: find cycles and choose victims

Problem

Resources have a single instance. Input lines (any order) until the end of input:

  • holds P R — process P holds resource R;
  • waits P R — process P waits for resource R;
  • cost P c — the cost of aborting P (default 0).
  1. Build the wait-for graph: for each waits P R (in input order) where R is held by another process Q, add the edge P → Q and print Edge P -> Q (R).
  2. Repeatedly find a cycle using DFS: start from the processes in alphabetical order, visit neighbours in alphabetical order, and report the first cycle found as Cycle: P1 -> P2 -> P3 -> P1 (starting from the node where the back edge points). Abort the process of the cycle with the smallest cost (ties: alphabetical) — print Abort P2 (cost 10) — and remove it with all its edges.
  3. When no cycle remains, print No deadlock if there was never a cycle, otherwise Deadlock resolved.

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.

os8-3-data-1.txt

cost P1 50
cost P2 10
cost P3 30
cost P4 5
holds P1 R1
holds P2 R2
holds P3 R3
holds P4 R4
waits P1 R2
waits P2 R3
waits P3 R1
waits P4 R1
What your program must print for os8-3-data-1.txt
Edge P1 -> P2 (R2)
Edge P2 -> P3 (R3)
Edge P3 -> P1 (R1)
Edge P4 -> P1 (R1)
Cycle: P1 -> P2 -> P3 -> P1
Abort P2 (cost 10)
Deadlock resolved

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

Windows PowerShell does not understand <:

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