Introduction to Dead lock
A dead lock is situation in which two or more process
waiting on same event to happen which is never going to be happen then we say those
processes are in dead lock.
In order to analyze Dead lock in any system we make use of Resource allocation graph.
Resource allocation graph
Resource allocation
graph is a graph contain vertices and Edges which represent the Resource,
allocation and Request status for each and every process.
Resource allocation
graph = G (V, E) where V is Process or Resources and E is allocation or
Request.
In above resource
allocation graph P1 does not leave the resource R1 and cannot stop requesting
for R2 similarly P2 does not leave the resource R2 and cannot stop requesting
for R1 they are trying to execute thus there is dead lock.
In above case it is
seem like dead lock but actually it is not dead lock. Because process P3 and P4
require only one resources which is already allotted thus they execute and
release the resources.
Notation used to represent Resource allocation graph.
Process will be
represented by circle
Resources will be
represented by Rectangle
Single instance or Multiple instance
Here is example of
single instance
represented as following
 |
|
P1 is requesting for instance of R1 |
Allocation is
represented as following
 |
|
One instance of R1 is allocated to P1 |
Q1 Consider a system with n Process and 6 tape drive
and if each process requires two tap drive to complete their execution, then
what is maximum value of n which ensure dead lock?
The solution is quite easy, let first we check what is given in the question
We have n process and 6 tape drive
each process require two tapes
so we first allocate 1 instance of tape drive to each process
P1 – 1
P2 – 1
P3 – 1
P4 – 1
P5 – 1
P6 – 1
as we have only 6 instance of resources, we need one more resources to satisfies the need of each process thus we reduce one process from the above scenario. that’s mean we can able to execute 5 maximum process without any deadlock.
Q2: Consider a system with 3 process each require 2 unit of resources R to complete the execution then what is the minimum number of resources are required to ensure dead lock ?
Solution
This question is little tricky
here we are not going to assign one resources one by one instead of this we take 2 resources at a time like
P1 – 2
P2 – 2
P3 – 2
but this will not ensure deadlock free execution, as there one scenario in which there three process can execute without creating any deadlock like
P1 – 3
P2 – 2
P3 – 1
but as it is not fully ensuring dead lock so 3 is not a right answer
thus right answer is 2 processes, means 2 is the maximum number process which can executed in this scenario without creating deadlock.
Q4: Consider a system with P1, P2, P3 process each require 5, 9, 13 unit of resources R respectively to complete the execution then what is the minimum number of resources are required to ensure dead lock?
Solution:
In question there is need of little bit understanding that first we assign one recourse less then its need like
P1 – 4
P2 – 9
P3 – 12
now system needs one more instance of resource R to complete the need of any one process, than after executing any one processes we get plenty amount of resources to satisfy the need of other process.
here is list of related post
Dead Lock Prevention in Operating System click here