5
$\begingroup$

I was reading about deadlocks in Operating Systems. Where I came across two examples below.

Circles with label $P_x$ are processes. Squares with label $R_x$ are resources. Each dot in the square represents single instance of resource type $R_x$. An edge from $R_x$ to $P_x$ means an instance of resource $R_x$ is allocated to process $P_x$. An edge from $P_x$ to $R_x$ means the process $P_x$ is waiting for getting an instance of resource $R_x$ allocated.

Now consider below two resource allocation graphs

enter image description here

The example on left involves deadlock while the one on the right did not involved deadlock.

I can understand that in right-side figure, if $P_2$ releases its instance of $R_1$, it can be assigned to $P_1$, breaking the circular wait. Or if $P_4$ release its instance of $R_2$, it can be assigned to $P_3$, breaking the circular wait. However we cannot break circular wait in left-side figure.

While I can try out this on any given resource allocation graph and decide if there is deadlock or not, I want to know can we have a generalized rule for this which can tell what exactly it is which is contributing to the deadlock, especially in case of multiple instances of resources are there. I did not found any reference / book speaking of this clearly. So after a bit of thinking I came up with following fact:

If there are multiple instances of same resource, for deadlock to exist, for any combination of two processes, if both are allocated an instance of same resource, then both should be a part of at least one cycle.

In right-side figure above, there is no deadlock because

  • processes $P_2$ and $P_3$ are allocated instances of $R_1$, but they both are not part of any cycle
  • similarly processes $P_1$ and $P_4$ are allocated instances of $R_2$, but they both are not part of any cycle

In left-side figure above, there is a deadlock because

  • processes $P_1$ and $P_2$ are allocated instances of resource $R_3$ and are part of same cycle,$P_1-R_1-P_2-R_3-P_3-R_3-P_1$

So am I correct with the above realization of fact? Or there are more aspects/conditions to the above fact (of when deadlock is present and when not) that I am missing?

What I am asking is if there is any other condition which if met, instead of the above one, will still result in the deadlock (in the context of multiple instances of resources and apart from four classic conditions of deadlock: mutual exclusion, no preemption, hold and wait and circular wait)?

$\endgroup$
4
$\begingroup$

All 4 conditions must be satisfied at the same time.

  • Hold and Wait
  • Non-preemption of resources
  • Mutual Exclusion
  • Circular wait

In case of single instance of resources:

Cycle in resource allocation graph represents deadlock.

In case of multiple instance of resources:

Cycle in RAG doesn't mean deadlock. You must check in the same way as you did. Let me write clear steps.

  • We need to identify a process, in the cycle, which can execute without any dependency and execute that.
  • Release the resources held by process.
  • Next check the process which has all the resources to execute and execute completely and release the resources held by it.
  • Keep doing till all the processes are executed.
  • If you can't execute all the processes this way, then there is deadlock.

Hope that helps!

$\endgroup$
  • $\begingroup$ thanks for explicitly listing steps. But as you may realize, I am in search of properties which can lead me to conclusion whether deadlock is there or not, without requiring me to follow all these steps. For example, above, the characteristics of processes $P_2$ and $P_3$ is that they are allocated instances of $R_1$, but they both are not part of any cycle, finding this characteristic immediately lead to conclusion that a least these two states do not lead to deadlock without requiring to perform the steps. $\endgroup$ – anir123 Nov 26 '15 at 10:26
  • $\begingroup$ The difference between the following steps and finding above characteristic is that, steps start with finding process that can be completed without dependecy, while finding characteristic start with finding two processes assigned instances of same resource. May be I am thinking unnecessarily and thats it there, nothing more. $\endgroup$ – anir123 Nov 26 '15 at 10:29
  • $\begingroup$ Seems that we cannot have such initial characteristics indicating existence of deadlock. Just had another little bit more involved problem. I am able to discern three processes initially possessing above property. However one of them can be executed completely after completion of few other processes. This cannot be realized just by recognizing processes possessing certain initial properties. Only remaining two cannot be completed. So they form deadlock. So we have to follow these steps anyway to find out if deadlock exists or not. $\endgroup$ – anir123 Nov 27 '15 at 17:29
0
$\begingroup$

Your logic follows, and falls in line with the need for a circular wait in a deadlock.

$\endgroup$
  • 1
    $\begingroup$ It has to, as circular wait is essential requirement for deadlock unlike others (mutual exclusion, hold and wait and no preemption) which are possible reasons for circular wait, thus in turn for deadlock. (Ref. Stallings) $\endgroup$ – anir123 Nov 25 '15 at 18:52
  • 1
    $\begingroup$ @Mahesha999 Then I don't understand your question. Your question asks if there are any other conditions, apart from the four standard ones; your comment says that there cannot possibly be any other conditions, citing a reference. So what is your question? $\endgroup$ – David Richerby Nov 26 '15 at 9:04
0
$\begingroup$

A different type of diagram and model may help in answering the question “is there any other condition which if met […] will still result in the deadlock?” (“When do deadlocks occur?”, 2015).

Consider a Petri Net model of the process-resource system, based on the left resource allocation graph and the following assumptions:

  1. Process P_1 requires one unit of Resource R_1 and one unit of Resource R_3 to perform its task.
  2. P_2 requires one unit of R_1 and two units of R_3 to perform its task.
  3. P_3 requires two units of R_3 to perform its task.
  4. A process takes one unit of a resource at a time.
  5. A process returns every unit of every resource it has taken at a time.
  6. All processes run on a single processor. The processor can handle one and only one process at a time.

Figure 1: A Petri Net Model Based on the Left Resource Allocation Graph -- with Deadlock

A Petri Net Model Based on the Left Resource Allocation Graph -- with Deadlock

A deadlock occurs in a system if or when the system “keeps waiting” for one or more resources it needs but the resource or resources will never be available. There are two reasons why the resource or resources will never be available. First, the resource was taken but never returned. Second, there was never “enough resources” to begin with.

If the left allocation graph is in a state of deadlock, then Figure 1 is one possible model that can reach this state.

Assuming there is enough resources, one way to prevent a deadlock is for a process to release the resources it has taken if one or more of the other resources it needs are not available. Another way to prevent a deadlock would be for a process allocate the resources it needs only if all of the resources it needs are available; otherwise, the process should not allocate any of the resources. The Petri Net in Figure 2 was designed this way – resources are allocated at the same time to a process if and only if every resource needed by the process is available.

Figure 2: A Petri Net Model for Allocating Resources without Deadlock

A Petri Net Model for Allocating Resources without Deadlock

Notes

For the PDF version, Figure 1 and Figure 2 are interactive, dynamic diagrams. You can step through each process and see the state changes – including the occurrence of deadlock in Figure 1.

Figure 1 can be initialized in two ways: no resource is allocated to any process, and the resource allocation based on the left resource allocation graph.

References

When do deadlocks occur?” (2015). Computer Science Stack Exchange. Retrieved on Nov. 27, 2015.

Chionglo, J. F. (2015) "A Reply to 'When do deadlocks occur?' at Computer Science Stack Exchange.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.