Consider a system with four resource types as follows:

Resource Type Number of Instances

RT$16$

RT$29$

RT$312$

RT$45$

The following table presents the maximum resource needs for each process for each of the four resource types:

Process Max RT$1$ Need Max RT$2$ Need Max RT$3$ Need Max RT$4$ Need

P$15684$

P$23743$

P$34572$

In the following sequence of resource requests, let REQ$($A$,$ N$1,$ N$2,$ N$3,$ N$4)$ represent a request from process A for N$1$ resources of type RT$1,$ N$2$ resources of type RT$2,$ N$3$ resources of type RT$3$ and N$4$ resources of type RT$4$:

REQ$($P$1,0,1,3,0)$

REQ$($P$3,3,0,3,0)$

REQ$($P$1,0,1,0,1)$

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

REQ$($P$3,0,3,1,0)$

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

The above sequence of resource requests can be granted safely without any danger of leading the system into a deadlock situation. Determine the set of resources available after processing the above sequence of requests and the remaining resource needs of the processes. Verify that a safe sequence of resource allocation to the processes does exist in this situation.

Now, consider the following additional requests for resources. For each request, determine if it can be granted safely in a manner that avoids deadlocks. Identify the request that can be safely granted.

a$)$ REQ$($P$1,1,0,2,0)$

b$)$ REQ$($P$1,0,1,3,0)$

c$)$ REQ$($P$1,1,2,0,0)$

d$)$ REQ$($P$2,0,1,0,2)$

Consider a system with ten resources and four processes competing for them. Let process P$1$ have a maximum need of seven resources, process P$2$ have a maximum need of five resources, process P$3$ have a maximum need of eight resources and process P$4$ have a maximum need of six resources.

Let $[$a$1,$ a$2,$ a$3,$ a$4]$ represent the allocation vector with respect to the resources currently allocated to the processes P$1$ through P$4,$ in that order. The system is deemed to be in a safe state with respect to an allocation vector if there is a possibility of allocating the remaining resources in such a way as to satisfy the maximum needs of all the processes.

Examine each of the following allocation vectors and determine if it is safe or not. Identify the one that is NOT safe?

a$)[1,2,1,4]$

b$)[3,1,1,2]$

c$)[0,3,1,3]$

d$)[2,0,2,4]$

In order to prevent deadlocks, let a system adopt the policy of forcing processes to request resources in ascending order of request type rank. In particular, when a process is requesting a resource of a certain type, the process cannot be holding other higher ranked resources.

Consider four resource types with the following profile in this system:

Resource Type Rank Number of Instances

RT$142$

RT$274$

RT$383$

RT$4102$

Let the following sequence of resource requests be processed by the system $($note that REQ$($A$,$ B$,$ k$)$ represents the request of k resources of type B by process A and REL$($A$,$ B$,$ k$)$ represents process A releasing k resources of type B$)$:

REQ$($P$4,$ RT$2,3)$

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

REQ$($P$2,$ RT$4,1)$

REL$($P$4,$ RT$2,3)$

REQ$($P$4,$ RT$1,2)$

REL$($P$2,$ RT$4,1)$

REL$($P$3,$ RT$3,2)$

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

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

REQ$($P$1,$ RT$4,2)$

Note that all of the above request and release operations can be processed without any violation of the deadlock$-$prevention policy of the system.

For each of the following sequences of request$/$release operations, examine if it can or cannot be processed without violating the deadlock$-$prevention scheme above. Identify the sequence that is allowed by the scheme and consequently can be processed without leading to system deadlock?

a$)$ REL$($P$2,$ RT$3,2),$ REQ$($P$3,$ RT$4,2),$ REQ$($P$2,$ RT$1,2),$ REQ$($P$1,$ RT$2,2)$

b$)$ REQ$($P$4,$ RT$3,3),$ REL$($P$3,$ RT$2,3),$ REQ$($P$3,$ RT$3,3),$ REQ$($P$2,$ RT$1,2)$

c$)$ REL$($P$2,$ RT$3,2),$ REQ$($P$4,$ RT$4,2),$ REQ$($P$2,$ RT$4,2),$ REQ$($P$1,$ RT$1,2)$

d$)$ REQ$($P$2,$ RT$4,2),$ REL$($P$3,$ RT$2,3),$ REQ$($P$4,$ RT$2,2),$ REQ$($P$3,$ RT$1,2)$

Consider six process P$1,$ P$2,$ P$3,$ P$4,$ P$5$ and P$6$ operating on four resources W$,$ X$,$ Y and Z$.$ Let REQ$($A$,$ B$)$ denote that process A requests resource B and let REL$($A$,$ B$)$ denote that process A releases resource B$.$

Let the system state be such that process P$1$ is holding resource W$,$ process P$3$ is holding resource X$,$ process P$4$ is holding resource Y and process P$6$ is holding resource Z$.$ Construct a resource$-$allocation graph reflecting this state of the system. For each of the following sequences of REQ and REL operations, modify the resource$-$allocation graph appropriately and determine if the sequence causes a deadlock. Identify the sequence that is deadlock free.

a$)$ REQ$($P$2,$ X$),$ REQ$($P$2,$ Z$),$ REL$($P$3,$ X$),$ REQ$($P$6,$ X$)$

b$)$ REQ$($P$2,$ X$),$ REL$($P$3,$ X$),$ REQ$($P$4,$ X$),$ REQ$($P$2,$ Y$)$

c$)$ REQ$($P$1,$ X$),$ REL$($P$4,$ Y$),$ REQ$($P$3,$ W$),$ REL$($P$6,$ Z$)$

d$)$ REQ$($P$3,$ W$),$ REQ$($P$2,$ Z$),$ REL$($P$6,$ Z$),$ REQ$($P$4,$ X$)$