retagged by
12,089 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

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.

 

edited by
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
0 votes
0 votes
-> For 1000 elements, except last level in tree, sum of total number of elements for all levels will be 511.

reason for above statement: In binary tree for every next level elements gets doubled and sum of elements of all levels except the last level will be nearest 2's power - 1.

here, nearest 2's power from 1000 is 2^9 = 512. So total no of element in tree except last level = 512  - 1 = 511.

hence index of largest element will 511, here it will be 510.(because indexing starts from 0).

Now if draw a binary search tree with 2 , 3 or any level, and write down the inorder traversal, you will observe 2nd last node always stores the 3rd largest element.

Hence, in this case index of 3rd largest element(which stored at 2nd last node in tree) = 510 (last node index) -1 = 509.
Answer:

Related questions