Consider a system employing a deadlock$-$avoidance scheme based on pre$-$declaration of resource needs for various processes. In particular, the resource needs of the processes are represented by claim arcs in the resource$-$allocation graph. Whenever a resource request by a process is issued, it is rejected by the system if the newly formed allocation arc $($from the resource vertex to the process vertex$)$ replacing the corresponding claim arc $($from the process vertex to the resource vertex$)$ closes a cycle in the resource$-$allocation graph. Otherwise, the system grants the request and converts the claim arc to the allocation arc in the resource$-$allocation graph.

Let P$1,$ P$2$ and P$3$ be three processes in the system. Let P$1$ declare that it may request resources W$,$ X and Y; P$2$ declare that it may request resources X$,$ Y and Z; P$3$ declare that it may request resources W$,$ Y and Z$.$ Construct the resource$-$allocation graph with the appropriate claim arcs.

Consider each of the following pairs of resource requests. Based on the resource$-$allocation graph constructed above, identify the pair of requests among the following that can be granted without a deadlock possibility?

a$)$ P$1$ requesting W and P$3$ requesting Y

b$)$ P$1$ requesting X and P$2$ requesting Z

c$)$ P$2$ requesting Z and P$3$ requesting Y

d$)$ P$2$ requesting Y and P$3$ requesting Z

Let a system allocate resources to processes as long as the system state remains safe with respect to deadlocks. Note that a system state is safe if there is a way to allocate the remaining resources in such a manner as to satisfy the maximum needs of all the processes.

With respect to a resource R$,$ let the system have $10$ instances of the resource and let there be five processes P$1,$ P$2,$ P$3,$ P$4$ and P$5$ that have maximum needs of $5,7,4,9$ and $8$ instances of the resource respectively.

Start with a safe state in which P$1$ is holding no instances, P$2,$ P$3$ and P$4$ are holding two instances each and P$5$ is holding one instance of R$.$ Now, consider each of the following requests. For each request, determine if it can be granted while keeping the system in a safe state. Identify the request that can be granted safely.

a$)$ P$5$ requesting two instances of R

b$)$ P$5$ requesting one instance of R

c$)$ P$4$ requesting two instances of R

d$)$ P$3$ requesting two instances of R

Consider a system in which processes post resource requests that are treated as follows. If the resource is free $($not currently held by any other process$),$ it is granted to the process. If the resource is currently held by some other process, the requesting process is thus notified. A process that could not obtain a requested resource can continue to post requests for more resources. However it cannot complete its work without obtaining all the resources it has requested. Whenever a process terminates it releases all the resources it had obtained.

In the following sequence of requests, let REQ$($A$,$ B$)$ denote process A requesting resource B:

REQ$($P$10,$ R$1)$

REQ$($P$1,$ R$8)$

REQ$($P$8,$ R$2)$

REQ$($P$5,$ R$4)$

REQ$($P$2,$ R$7)$

REQ$($P$6,$ R$3)$

REQ$($P$4,$ R$5)$

REQ$($P$3,$ R$6)$

REQ$($P$4,$ R$7)$

REQ$($P$7,$ R$5)$

REQ$($P$9,$ R$4)$

REQ$($P$3,$ R$7)$

REQ$($P$2,$ R$3)$

REQ$($P$5,$ R$8)$

REQ$($P$2,$ R$4)$

REQ$($P$8,$ R$1)$

REQ$($P$7,$ R$6)$

REQ$($P$5,$ R$2)$

REQ$($P$1,$ R$1)$

REQ$($P$10,$ R$7)$

REQ$($P$6,$ R$6)$

REQ$($P$5,$ R$1)$

Construct a wait$-$for graph for the above sequence of requests. A wait$-$for graph has the set of processes as its vertices. An arc Pi$->$Pj represents that process Pi is waiting for a resource that is held by process Pj$.$ Cycles in the wait$-$for graph correspond to deadlocks in the system. Based on the wait$-$for graph, identify the process, among those given below, that is NOT part of any deadlock.

a$)$ P$5$

b$)$ P$3$

c$)$ P$2$

d$)$ P$4$

Consider a system with eight resources currently allocated as follows:

Resource Allocated to Process

R$1$ P$4$

R$2$ P$1$

R$3$ P$5$

R$4$ P$7$

R$5$ P$2$

R$6$ P$8$

R$7$ P$3$

R$8$ P$6$

The following sequence of additional resource requests is then processed. $($Let REQ$($A$,$B$)$ denote process A$\text{'}$s request for resource B$.)$

REQ$($P$4,$ R$2)$

REQ$($P$3,$ R$6)$

REQ$($P$2,$ R$1)$

REQ$($P$7,$ R$7)$

REQ$($P$6,$ R$1)$

REQ$($P$5,$ R$7)$

The above sequence of requests do not cause a deadlock. Verify this fact by constructing a resource$-$allocation graph involving R$1$ through R$8$ and P$1$ through P$8.$

For each of the following resource requests, add an arc to the resource$-$allocation graph and examine if the resource request causes a deadlock in the system. Identify the request, among the following, that does NOT cause a deadlock.

a$)$ REQ$($P$3,$ R$3)$

b$)$ REQ$($P$8,$ R$3)$

c$)$ REQ$($P$8,$ R$8)$

d$)$ REQ$($P$3,$ R$4)$