GATE CSE 2022 | Question: 16

Question

Which of the following statements is/are $\text{TRUE}$ with respect to deadlocks?

• A. Circular wait is a necessary condition for the formation of deadlock.
• B. In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
• C. If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.
• D. In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Comments

Snippet from galvin to show why option C is false

Answer 1

Option A, D

---

 

• A. Circular Wait is one of the four necessary conditions for deadlock to happen. True
   
• B. Not necessarily, if every resource had only a single instance then, a cycle would’ve been necessary and sufficient for a deadlock to occur. A Cycle in a multi-instance resource is necessary but isn’t sufficient and in this case, each resource is made up of more than one instance, a simple contradiction. False
   
• C. An Unsafe state is where no method of allocation of resources can prevent deadlock from happening. Whereas in a safe state, there exists a method of allocation in which all processes are complete. False
   
• D. Resource Allocation graph accommodates future resource requirements in the form of request edges. If there are no request edges, then resource requirements for all the processes are satisfied. True

 

Comments

The diagram shown in the link (https://gateoverflow.in/?qa=blob&qa_blobid=992651939091185654) is a resource allocation graph, not a wait for graph. In a wait for graph, only processes are represented as vertices. 

How to draw a wait for graph in the case of multiple instance resource? 
(P1 is actually not waiting for P2 to release a resource(because it is already available), so I think there would be no edge from P1 tto P2 in the wait for graph. 

 

---

@aditya_kumar

When there are multiple instances of a resource, a cycle in RAG / Wait-for graph may not be a sufficient condition for deadlock

Answer 2

Ans is : Option A, D.

---

 

• A. The four necessary conditions for deadlock to happen are: Mutual Exclusion, Hold and Wait, No Pre-emption, Circular Wait. Hence option A is True. 

 

• A. Here they have asked about the wait-for graph. A wait-for graph is a directed graph used for deadlock detection in operating systems and relational database systems (Wikipedia). We must note that “The wait-for graph scheme is not applicable to a resource-allocation system with multiple instances of each resource type.” (Galvin Pg:338 Article 8.7.2). This makes option B, False. 

 

An excerpt from Galvin (Pg: 337 Article 8.7.1) for more clarity on Wait-for Graph on Single Instance Resource: -

If all resources have only a single instance, then we can define a deadlock-detection algorithm that uses a variant of the resource-allocation graph, called a wait-for graph. We obtain this graph from the resource-allocation graph by removing the resource nodes and collapsing the appropriate edges. More precisely, an edge from Ti to Tj in a wait-for graph implies that thread Ti is waiting for thread Tj to release a resource that Ti needs. An edge Ti → Tj exists in a wait-for graph if and only if the corresponding resource-allocation graph contains two edges Ti → Rq and Rq → Tj for some resource Rq. In Figure 8.11, we present a resource-allocation graph and the corresponding wait-for graph.

 

Thus, every cycle in a multi-instance resource type (In a system where each resource has more than one instance) wait-for graph (which is not even possible) is not a deadlock. Hence option B is False.

But in the case of a single-instance resource type a cycle in its wait-for graph indicates the presence of a deadlock. 

100. Every unsafe state doesn’t necessarily mean that a deadlock would occur. Deadlock is a subset of an unsafe state. Hence option C is False.

• A. In Resource Allocation graph, if every edge is an assignment edge, it means there are no future resource requirements. So the resources requirements of all the processes are already satisfied. The necessary condition of Hold and Wait is not fulfilled, as system is not waiting for any resource. Hence deadlock cannot occur. Therefore, option D is True.

 

Comments

Best explanation!! :-)

---

covered everything 👌👍.