snippetMinor
For a given certain situation how to prove that the system will never get into the state of Deadlock
Viewed 0 times
neverthedeadlockintosystemsituationprovewillthatfor
Problem
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.
'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.
Solution
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
Figure 2: A System without Deadlock
Figure 3: Another System without Deadlock
Notes
For Figure 1, the transitions related to Process 1 (Process 2) are:
For Figure 2, the transitions related to Process 1 (Process 2) are:
For Figure 3, the transitions related to Process 1 (Process 2) are:
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.
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
Figure 2: A System without Deadlock
Figure 3: 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.
Context
StackExchange Computer Science Q#44030, answer score: 3
Revisions (0)
No revisions yet.