For this assignment you'll investigate deadlock detection. The approach to deadlock detection that we discussed in class, is to model resource allocations and requests with a Resource Allocation Graph (RAG). Deadlock detection is then accomplished by finding a cycle in the graph.
Your task is to construct the RAG and detect any cycles that arise. Your program will track resource requests, allocations and releases. The ordering of resource requests and releases will be provided as input to your program in the format given below. When a request is made for a resource, it will be allocated if it is available. Otherwise the requesting process will be blocked until the resource is released by the process that holds it.
Your program should check for the presence of deadlock (a cycle) after every resource request or allocation. In a real system, this check would only be done periodically because it is too expensive to check after every request or allocation. However, your program is required to indicate the deadlock as soon as it occurs. Note that it is not necessary to check for deadlock after a resource release, because if deadlock didnt exist before the release then it wont exist afterward.
When your program detects a deadlock, it will report the deadlock along with the resources and processes involved in the cycle and then it will terminate. In a real system employing deadlock detection, some attempt would be made to resolve the deadlock. In this case, however, we are only interested in detecting it. If your program performs all of the resource allocations and releases without encountering a deadlock, then it will report that no deadlock was encountered and terminate.
Input to your program will consist of lines like the following, read from a file:
1 N 1
2 N 2
3 N 6
2 N 6
4 N 3
5 N 1
1 R 1
3 N 3
5 R 1
4 N 2
1 N 4
1 N 5
1 R 4
Each line of input contains an integer followed by N or R and then another integer. The first integer identifies the process, the second integer identifies the resource, and N indicates needs or R indicates releases. So the first line indicates that process 1 wants resource 1. The last line indicates that process 1 releases resource 4. All process and resource identifiers are unique, so the process 1 that is referred to five times in the input is the same process. Also, each resource has only one instance. Hence the resource can be allocated to only one process at a time. If a process wants a resource that is already allocated then it will have to wait until the resource is released by whichever process is holding it. When a resource is released, it should be allocated to the process that has been waiting for it the longest. If there are no processes waiting for it then the resource is now free. Note that all input will be consistent. That is, I will never specify an input file that process 7 Releases resource 3 if process 7 didnt hold resource 3.
Your program will write information to a file called output.txt that tracks the requests, allocations, and releases. The following format is required:
Process 1 needs resource 1 – Resource 1 is allocated to process 1.
Process 2 needs resource 2 – Resource 2 is allocated to process 2.
Process 3 needs resource 6 – Resource 6 is allocated to process 3.
Process 2 needs resource 6 – Process 2 must wait.
Process 4 needs resource 3 – Resource 3 is allocated to process 4.
Process 5 needs resource 1 – Process 5 must wait.
Process 1 releases resource 1 – Resource 1 is allocated to process 5.
Process 3 needs resource 3 – Process 3 must wait.
Process 5 releases resource 1 – Resource 1 is now free.
Process 4 needs resource 2 – Process 4 must wait.
DEADLOCK DETECTED: Processes 2, 3, 4, and Resources 2, 3, 6, are found in a cycle.
If your program processes all of the input and finds no deadlock then it should display the line: EXECUTION COMPLETED: No deadlock encountered. as the last line of the output. Remember: You should not assume any bound on the number of processes or resources. The integer identifier can range freely and you should expect larger numbers to test your program. That is, dont read the identifier as if its a character, read it in as an integer (or a string if you want to be more general and allow names for your processes and resources) so your program handles multiple digit identifiers.