CPSC 457: Assignment 4 5
Programming question (20 marks)
For this question you will write a program deadlock.c or deadlock.cpp or
deadlock.java that examines multiple system states and for each of them determines whether
the system is in a deadlock, and if it is, which processes are deadlocked.
Each system state will consist of some number of processes and resources. You will assume a
single instance per resource type. Hint: you should implement a cycle-detection algorithm.

Command line
Your program will take no command line arguments. Your program will read the standard input
to get state descriptions.

Input
Your program will read the descriptions of each system state from standard input. The input will
be line-based, with 3 types of lines: one represeting an assignment edge, one representing a
request edge and one representing an end of state description.
• a line N -> M represents a request edge, i.e. process N is requesting resource M;
• a line N <- M represents an assignment edge, i.e. process N holds resource M;
• a line that starts with # represents the end of state description.
• “N” and “M” above will be non-negative integers.

As an example, consider the following 4 system states:



CPSC 457: Assignment 4 6
The 4 system states above would be represented by the input below, and the output your program
should produce on this input is shown on the right.
Input: Output:
1 <- 1
3 -> 1
3 -> 7
2 -> 1
2 <- 7
# end of A
5 -> 1
5 <- 3
5 -> 2
7 <- 1
7 -> 3
12 <- 2
# end of B
12 <- 1
3 <- 1
3 -> 7
7 -> 1
7 <- 7
# end of C
12 -> 1
12 <- 1000
7 -> 1
7 -> 1000
3 -> 77
432 <- 77
432 -> 2
3 <- 2
Deadlocked processes: none
Deadlocked processes: 5 7
Deadlocked processes: 3 7
Deadlocked processes: 3 432

Notice there is no explicit end of state line # at the end of the input above, as it is implied by
the end-of-file. You may assume the following limits on input:
• process numbers will be in range [0 … 100000];
• resource numbers will be in range [0 … 100000];
• number of edges per state description will be in range [1 … 100000];
• number of states per input will be in range [1 … 20].
Your solution must be efficient enough to be able run on any input within the above limits in less
than 10 seconds.
Output
Your program will write the results to standard output. For each state it reads, it will print out
how the list of processes involved in the deadlock, sorted in ascending order. If there is no
deadlock, it should print out the word ‘None’. Your output should match the sample output above
exactly.