GATE Overflow Test Series | Operating Systems | Test 1 | Question: 8

Question

Which of the following is/are correct? (Mark all the appropriate choices)

• A. If each resource type has exactly one instance, then a cycle in resource allocation graph is a necessary condition for the existence of deadlock
• B. If each resource type has exactly one instance, then a cycle in the resource allocation graph is a sufficient condition for the existence of deadlock
• C. If each resource type has several instances, then a cycle in the resource allocation graph is a sufficient condition for the existence of deadlock
• D. If each resource type has several instances, then a cycle in the resource allocation graph is a necessary condition for the existence of deadlock

Answer 1

If each resource type has exactly one instance, then a cycle in resource allocation graph is both a necessary and a sufficient condition for the existence of deadlock.

If each resource type has several instances, then a cycle in the resource allocation graph is a necessary condition for the existence of deadlock but not sufficient. That is, even if there is a cycle, a deadlock may not be present.

Comments

Even though this doesn’t require so much discussion, but still just for the sake of completion.

I get it what you guys are saying. Our statement a bi-implication statement, because

Deadlock in single instance resources $\rightarrow$ cycle

cycle in single instance resource $\rightarrow$ Deadlock

Now deadlock not possible, even then “Deadlock in single instance resources $\rightarrow$ cycle” holds true. Right?

---

yes.

---

logic - What is the difference between "necessary" and "sufficient"? - Philosophy Stack Exchange

Necessary: if p is necessary for q, q → p

Sufficient: if p is sufficient for q, p → q

 

Answer 2

If the graph contains no cycles $\implies$ no deadlock.

If the graph contains a cycle $\implies$

•  if only one instance per resource type, then deadlock.
•  if several instances per resource type, possibility of deadlock.

So, the correct answer is $A; B; D.$ 

Ref:https://www.cs.odu.edu/~cs471w/spring10/lectures/Deadlocks.htm

Comments

Sir, if we allow preemption of resources then B is not true, it’s not sufficient condition.

isn’t it?