5
$\begingroup$

The situation is as follows

'm' process shares 'n' resources of same type. The maximum need of each process does not exceed 'n' and the sum all their maximum needs is always less than m+n. In this set up will deadlock ever occur

This is a question from Operating System Concepts by Silberschatz, Gagne and Galvin.

I tried to prove this using using Banker's Algorithm. Initially, I assumed that the Allocated Matrix for 'm' processes is a zero matrix. And Maximum Matrix of 'm' process is 'n'. Since Need matrix is difference of Allocated Matrix and Max Matrix therefore, Need Martix is equilavent of Maximum Matrix. And at last Available Matrix is equal to 'n'.

At this point I feel stuck and not able to find a way to proceed. Looking forward for help from you guys. Thanks in advance.

Improve this question
$\endgroup$
3
  • $\begingroup$ Hint: Petri nets! $\endgroup$ – Raphael♦ Jun 29 '15 at 14:34
  • $\begingroup$ @Raphael Is Petri Nets similar to resource allocation graph? Or they are two different concept. $\endgroup$ – Prateek Jun 29 '15 at 15:33
  • 1
    $\begingroup$ I can't answer that in a comment. Google "Petri net", it's a famous formalism. You'll find lots of material. $\endgroup$ – Raphael♦ Jun 29 '15 at 15:37
3
$\begingroup$

The question in the given situation is equivalent to the question: is it possible to create or to design a system such that m processes sharing n resources of the same type may enter a deadlock state subject to the following: each process needs less than or equal to n resources, and the total number of needed resources is less than or equal to m+n (“For a given certain situation”, 2015)?

Assumptions. Processes run on a single processor. The processor can execute a statement from one and only one process at a time. In other words every statement in a process is an atomic operation. After ending a statement and before executing the next statement of a process, the processor can switch to another process and execute the other process’ next statement.

Consider using a Petri Net for the system design. In terms of Petri Nets a deadlock is a situation when no transition is enabled. Figure 1 is an example of a system that may enter a deadlock state. In this example, m=2 and n=2. For the same number of processes and resource needs per process (m=2 and n=2), it is also possible to create a system that does not enter a deadlock state. Each of Figure 2 and Figure 3 is an example of two systems that will never reach a deadlock state.

Figure 1: A System with Deadlock A System with Deadlock

Figure 2: A System without Deadlock A System without Deadlock

Figure 3: Another System without Deadlock Another System without Deadlock

Notes

For Figure 1, the transitions related to Process 1 (Process 2) are:

  • T0 (T4) – get 1 resource unit.
  • T1 (T5) – get 1 resource unit.
  • T2 (T6) – process critical section.
  • T3 (T7) – return 2 resource units.

For Figure 2, the transitions related to Process 1 (Process 2) are:

  • T0 (T4) – get 1 resource unit.
  • T1 (T5) – get 1 resource unit.
  • T2 (T6) – process critical section.
  • T3 (T7) – return 2 resource units.
  • T8 (T9) – return 1 resource unit.

For Figure 3, the transitions related to Process 1 (Process 2) are:

  • T0 (T3) – get 2 resource units.
  • T1 (T4) – process critical section.
  • T2 (T5) – return 2 resource units.

For the PDF version of this reply, Figure 1, Figure 2 and Figure 3 are interactive, dynamic diagrams.

References

Chionglo, J. F (2015). "A Reply to "For a given certain situation how to prove that the system will never get into the state of deadlock" at Computer Science Stack Exchange". Available at http://www.aespen.ca/AEnswers/OnMWQ1449933168.pdf

“For a given certain situation how to prove that the system will never get into the state of Deadlock” (2015). Mathematics Stack Exchange. Retrieved on Dec. 2, 2015 at For a given certain situation how to prove that the system will never get into the state of Deadlock.

Improve this answer
$\endgroup$
0
$\begingroup$

The solution of a related problem helped me in the proof. Here I am first sharing that question along with one of the possible answer, and later propose my proof in a similar manner.

Consider a system which has $3$ processes and each process requires $2$ identical resources to complete their execution then what is the minimum number of resources required to ensure deadlock free execution.

The easy way to do this is, allocate exactly one less than the required number of instances of the resource to all the processes. Except for one of the processes, whose need is completely fulfilled.

If there are $3$ processes say $P_1,P_2,P_3$. We give exactly one instance of the resource to $P_2, P_3$ and two instances of resource to $P_1$. In total $4$ instances of the resource are required to ensure a deadlock free execution.

Let us now generalize this concept and see what we get.

There are $m$ processes say $P_1,P_2,P_3,..,P_m$ sharing $n$ resources. And let $S_i$ be the maximum requirement of a process $P_i$ to execute completely.

Now to ensure that system is deadlock-free, we allocate all the processes exactly one less than the required number of instances of the resource except for one of the processes whose requirement is completely fulfilled.

Mathematically,

$$\sum_{i=1}^{m}S_i-m+1 \leq n$$

or we can say

$$\sum_{i=1}^{m}S_i < m+n$$

This expression tells us that as long as the sum of maximum need of all the processes is less than $m+n$, the system will remain deadlock free.

HTH

Improve this answer
$\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.