Question

Consider a system with eight resources currently allocated as follows:

Resource	Allocated to Process
R1	P4
R2	P1
R3	P5
R4	P7
R5	P2
R6	P8
R7	P3
R8	P6

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

• REQ(P4, R2)
• REQ(P3, R6)
• REQ(P2, R1)
• REQ(P7, R7)
• REQ(P6, R1)
• REQ(P5, R7)

The above sequence of requests do not cause a deadlock. Verify this fact by constructing a resource-allocation graph involving R1 through R8 and P1 through P8.

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(P1, R3)
• B. REQ(P1, R8)
• C. REQ(P1, R1)
• D. REQ(P1, R5)

Answer 1

The following is the pic for the Resource allocation graph for the already allocated resources to the process and also the requests.

R1,R2....R8 are the resources and P1,P2......P8 are the processes.

The already allocated resources to their respective processes are shown in red arrows. (the arrows are drawn from the allocated resource to the process)

The requests for resources by the processes are shown in black arrows( the arrow is drawn from the process to the resource) These are those requests

• REQ(P4, R2)
• REQ(P3, R6)
• REQ(P2, R1)
• REQ(P7, R7)
• REQ(P6, R1)
• REQ(P5, R7)

from the above Resource allocation graph, you can observe that P2 is waiting for P4 to release R1, P4 is waiting for P1 to release R2 and so on. we can represent these dependencies between the resources in the form of a graph.

The below picture is the dependencies between the processes of the above c.

If you observe, this dependencies graph does not have any cycles. It indicates there is no deadlocks.

coming to the 2nd part of the question. We first represent these requests in the resource allocation graph.

• A. REQ(P1, R3)
• B. REQ(P1, R8)
• C. REQ(P1, R1)
• D. REQ(P1, R5)

These requests are represented with pencil

A. REQ(P1, R3) ---> P1->P5 (NO cycle so No deadlock)

B.REQ(P1, R8) --> P1->P6->P4->P1 ( cycle is present, so deadloack is possible)

C. REQ(P1, R1) --> P1->P4->P1 ( cycle is present, so deadloack is possible)

D. REQ(P1, R5) --> P1->P2->P4->P1 ( cycle is present, so deadloack is possible)

So, only option A doesn't cause any deadlock