Suppose a system handles deadlocks by detecting them periodically and resolving them. In such a system, when a process requests a resource, it is granted to the process if the resource is free. Otherwise, an entry for the requesting proc ess is added to the end of the wait queue for the resource A process whose request could not be granted is allowed to request other resources and proceed. However it cannot finish all its work until it obtains all the resources it needs/requests. When a process terminates (either after finishing all its work or aborting prematurely), it releases all its resources When a resource is released by a process, the resource is granted to the first process in the wait queue. The wait-queue is maintained on a First Come First Served (FCFS) basis
On a periodic check for deadlocks, the system identifies all the that are currently deadlocked and selects a subset of them to abort (ie., terminate prematurely) in order to resolve all the existing deadlocks processes
Now, consider the following sequence of resource requests in the system (note that REQ(A, B) indicates a request by process A for resource B) .
REQ(P3, R7) .
REQ(P5, R5) .
REQ(P4,R6) .
REQ(P7, R3)
REQ(P2, R8)
REQ(P8, R2) .
REQ(P1,R9) .
REQ(P6, R4) .
REQ(P9,R1) .
REQ(P5, R6) .
REQ(P4, R8)
REQ(P2, R2) .
REQ(P6, R9)
REQ(P1, R8) .
REQ(P3,R3) .
REQ(P4, R1) .
REQ(P7, R6) .
REQ(P9, R3)
REQ(P3, R5) .
REQ(P2, R4) .
REQ(P8, R9)
At the end of processing the above sequence of requests, some of the processes in the system are deadlocked. Construct a wait-for graph for the sequence of requests above and identify the processes that are deadlocked Based on the wait-for graph, determine which of the following pairs of processes can be aborted in order to resolve all the existing deadlocks in the system?
a) P6 and P7
b) P7 and P2
c) P8 and P4
d) P2 and P4