Register

GATE CSE 2022 | Question: 16

• retagged by
13,038 views
12 votes
12 votes

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

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

3 Answers

Best answer
11 votes
11 votes

Option A, D

 

  1. Circular Wait is one of the four necessary conditions for deadlock to happen. So, option #A is True.
     
  2. 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. So, option #B is False.
     
  3. 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. Hence, option #C is False.
     
  4. 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. So, option #D is True.

 

• selected by
User Avatar
28 votes
28 votes

Ans is : Option A, D.

 

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

 

  1. 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. 

  1. 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.

  1. 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.

 

• edited by
User Avatar
2 votes
2 votes

A. Circular wait is one of the necessary conditions for a deadlock to occur.

B. A Cycle in a multi-instance resource may or may not cause Deadlock. (However, A Cycle in a single-instance resource will cause Deadlock)

C. In an unsafe state, the OS can't prevent threads from requesting resources in such a way that a deadlock occurs. It is not necessary unsafe state will always lead to deadlock because processes may not request their total possible resources, and may release some resources before acquiring othes.
Ref: sp13mtv6 (berkeley.edu) Check Q1)->b)->ii)

D. In the resource-allocation graph of a system, if every edge is an assignment edge, then one of the four necessary conditions, "hold and wait" is violated. That's why there is NO DEADLOCK. The absence of at least one of the four necessary conditions implies NO DEADLOCK.

Correct Option: A, D

User Avatar
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

16.2k
views
2 answers
6 votes
Arjun asked Feb 15, 2022
16,178 views
GATE CSE 2022 | Question: 13
Which of the following statements is/are $\text{TRUE}?$Every subset of a recursively enumerable language is recursive.If a language $\textit{L}$ and its complement $\over...
User Avatar
8.0k
views
1 answers
21 votes
Arjun asked Feb 15, 2022
8,025 views
GATE CSE 2022 | Question: 14
Let $\text{WB}$ and $\text{WT}$ be two set associative cache organizations that use $\text{LRU}$ algorithm for cache block replacement. $\text{WB}$ is a write back cache ...
User Avatar
8.8k
views
2 answers
15 votes
Arjun asked Feb 15, 2022
8,787 views
GATE CSE 2022 | Question: 15
Consider the following three relations in a relational database.$\text{Employee} (\underline{\text{eId}},\text{Name}), \; \text{Brand}(\underline{\text{bId}},\text{bName}...
User Avatar
7.8k
views
2 answers
14 votes
Arjun asked Feb 15, 2022
7,843 views
GATE CSE 2022 | Question: 17
Which of the following statements is/are $\text{TRUE}$ for a group $\textit{G}?$If for all $x,y \in \textit{G}, \; (xy)^{2} = x^{2} y^{2},$ then $\textit{G}$ is commutati...
User Avatar
Link Copied!