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 • 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 3 -> 1 3 -> 7 2 -> 1 2 # end of A 5 -> 1 5 5 -> 2 7 7 -> 3 12 # end of B 12 3 3 -> 7 7 -> 1 7 # end of C 12 -> 1 12 7 -> 1 7 -> 1000 3 -> 77 432 432 -> 2 3 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.
