DEADLOCK
➢Deadlock refers to the condition when 2 or more processes are
waiting for each other to release a resource indefinitely. A process in
nature requests a resource first and uses it and finally release it.
IN DEADLOCK SITUATION
✓Both the processes wait for the other process. Let’s look at one
example to understand it – Process P1 has resource R1, Process P2 has
resource R2. If Process P1 request resource R2 and Process P2
requests resource R1 at the same time, then deadlock occurs.
IN DEADLOCK SITUATION
CONDITIONS FOR DEADLOCK
Deadlock can occur if all the given 4 conditions are satisfied, that is if all are
true :
1. Mutual Exclusion : If at least 1 or more resources are in non sharable
mode, the resource should be in mutual exclusion. Non shareable means,
resource can not be used by more than 1 process at a time, unless the
resource gets released. (Only one process can use a resource at a time)
2. Hold and Wait : Processes which are already holding at least 1 resource
may request new resource
CONDITIONS FOR DEADLOCK
3. No Preemption : Resources can not be released by force, only the
process holding the resource can release it, which does so after the
process has finished its task
4. Circular wait : 2 or more processes form a circular chain where each
process waits and want to acquire the resource which the next
process in the chain holds
DEADLOCK DETECTION AND RECOVERY
Deadlock Detection is an important task of OS. As the OS does not take
many precautionary means to avoid it. The OS periodically checks if
there is any existing deadlock in the system and take measures to
remove the deadlocks
DETECTION
There are 2 different cases in case of
Deadlock detection –
1. If all resources have only a single
instance
• We make a Wait-For graph
2. If all resources have multiple
instances
• We make a different algorithm
(Deadlock Detection Algorithm)
➢ IF ALL RESOURCES HAVE ONLY A SINGLE INSTANCE
A wait-for graph is made. A wait-for graph vertex denotes process. The
edge implies process waiting for Process 2 to release resources. A
deadlock is detected if one wait-for graph contains a cycle.
IF ALL RESOURCES HAVE ONLY A SINGLE INSTANCE
The Wait-for graph is made by looking at the resource-allocation graph. An
edge between P1 to P2 exists if P1 needs some resources which P2 has
• In the Wait-for graph P1 is waiting for resources currently in use by P2
• And P2 is waiting for resources currently in use by P3 and so on …
• P5 is waiting for a resource currently in use by P1. Which creates a cycle thus
deadlock is confirmed
SINGLE INSTANCE OF EACH RESOURCE TYPE
IF ALL RESOURCES HAVE MULTIPLE INSTANCES
DEADLOCK RECOVERY
➢Deadlock can be recovered by
✓Kill the Process – One way is to kill all the processes in deadlock or the
second way kill the process one by one, and check after each if still
deadlock exists and do the same till the deadlock is removed
✓Preemption – the resources that are allocated to the processes involved
in deadlock are taken away (preempted) and are transferred to other
processes. In this way, system may recover from deadlock as we may
change system state.
DEADLOCK RECOVERY
➢Deadlock can be recovered by
✓Rollback – the OS maintains a database of all different state of system, a
state when the system is not in deadlock is called safe state. A rollback to
previous ‘n’ number of safe states in iterations can help in the recover.
DEADLOCK PREVENTION AND AVOIDANCE
DEADLOCK PREVENTION
For deadlock to occur, all of the following condition must be true :
1. Mutual exclusion
2. Hold and wait
3. No preemption
4. Circular wait
Hence, the way to prevent deadlock is to ensure that at least one of these conditions
do not hold :
• Mutual exclusion – If 1 resource is non-shareable, then mutual exclusion condition
must hold. We can’t prevent deadlock by denying this mutual exclusion condition,
as some resource are inherently non shareable and this can’t be changed.
• Hold and wait - For hold and wait condition to never occur, it should be made sure
that whenever a process request a resource, it does not hold any other resource.
There can be many protocols implemented –
✓One protocol could be Allocating all resources to a process before its execution
✓Other could be, a process can request resource only when it has no resource
• Both these suffer from
• Low resource utilization
• Starvation
• No preemption of resources – allow preemption of resources from
process when resources are acquired by high priority process
• Circular wait – to prevent this, impose a total ordering of all resources
types and every process should request resource in increasing order.
DEADLOCK AVOIDANCE
✓Deadlock prevention causes low device utilization and reduced system
throughput
✓To avoid deadlocks, one requires additional information about how
resources all to be requested
• For one instance of each resource type, Resource Allocation Graph Algorithm is used
• For avoidance of multiple instances of each resource type, Banker’s Algorithm is used
THE BANKER’S ALGORITHM
The Banker’s algorithm is a resource allocation and deadlock
avoidance algorithm developed by Edsger Dijkstra. It ensures that a
system remains in a safe state by simulating the allocation of
resources and checking for potential deadlocks before granting any
resource requests.
➢Key Concepts:
1. Resources: The algorithm tracks the maximum possible demand, current allocation, and available
resources.
2. Safe State: A state where the system can allocate resources to each process in some order and still
avoid deadlock.
3. Data Structures:
o Available: Vector indicating the number of available resources of each type.
o Max: Matrix defining the maximum demand of each process.
o Allocation: Matrix showing the number of resources currently allocated to each process.
o Need: Matrix indicating the remaining resource need of each process (calculated as Max -
Allocation).
THE BANKER’S ALGORITHM
SOLUTION
EXAMPLE 2 : BANKER’S ALGORITHM
Using Algorithm
Step 1 : P0 (7,4,3) & Available(3,3,2) => Finish = False
Step 2 : P1(1,2,2) & Available(3,3,2) => Finish = True,
Available-new = P1(2,0,0)Allocation + Available-old(3,3,2) = (5,3,2)
Step 3 : P2(6,0,0) & Available(5,3,2) => Finish = False
Step 4 : P3(0,1,1) & Available(5,3,2) => Finish = True => Available-new(5,4,3)
To check for Safe state, we have < P1 , P3 , P4 , P0 , P2 > is a safe state
EXAMPLE 3 : BANKER’S ALGORITHM
The system is not in a safe state. Why ?
< P0, P2, P3, P1 false ? >
