Process requests a resource (R), if R is not available (taken by other process), process enters in a waiting state. Sometimes that waiting process is never able to change its state because the resource, it has requested is busy (forever)
Two or more processes are waiting on some resource’s availability, which will never be available as it is also busy with some other process. The Processes are said to be in Deadlock
DL is a bug present in the process/thread synchronization method, In DL, processes never finish executing, and the system resources are tied up, preventing other jobs from starting
Resources Examples
Memory Space
CPU cycles
Files
Locks
Sockets
I/O Devices
How a process/thread utilize a resource?
Request => Request the R, if R is free Lock it, else wait till it is available
Use
Release => Release resource instance and make it available for other processes
Necessary conditions for deadlock to happen
Mutual Exclusion
Only 1 process at a time can use the resource, if another process requests that resource, the requesting process must wait until the resource has been released
Hold & Wait
A process must be holding at least one resource & waiting to acquire additional resources that are currently being held by other processes
No-preemption
Resource must be voluntarily released by the process after completion of execution (No resource preemption)
Circular wait
Forming a Circle in diagram
Resource Allocation Graph (RAG)
Vertex
Process Vertex => In circle
Resource Vertex => Simple Instance, Multi Instance => In square
If RAG contains cycle then maybe deadlock but it does not have cycle then no deadlock
Methods for handling Deadlocks
Use a protocol to Prevent or Avoid deadlocks
Ensuring that the system will never enter a deadlocked state
Allow the system to enter a deadlocked state, Detect it, and Recover
Ostrich algorithm => Deadlock ignorance
Ignore the problem altogether and pretend that deadlocks never occur in system
Deadlock Prevention
Basic
By ensuring at least one of the necessary conditions cannot hold
Conditions
Mutual exclusion
Use locks (mutual exclusion) only for non-sharable resource
Sharable resources like Read-Only files can be accessed by multiple processes/threads
However, we can’t prevent DLs by denying the mutual-exclusion condition, because some resources are intrinsically non-sharable
Hold & Wait
To ensure H&W condition never occurs in the system, we must guarantee that, whenever a process requests a resource, it doesn’t hold any other resource
Protocol (A) can be, each process has to request and be allocated all its resources before its execution
Protocol (B) can be, allow a process to request resources only when it has none. It can request any additional resources after it must have released all the resources that it is currently allocated
No preemption
If a process is holding some resources and request another resource that cannot be immediately allocated to it, then all the resources the process is currently holding are preempted. The process will restart only when it can regain its old resources, as well as the new one that it is requesting
Live Lock may occur => Locks colliding with each other again and again, can be solved by adding delay between locks
If a process requests some resources, we first check whether they are available. If yes, we allocate them. If not, we check whether they are allocated to some other process that is waiting for additional resources. If so, preempt the desired resource from waiting process and allocate them to the requesting process
Circular wait
To ensure that this condition never holds is to impose a proper ordering of resource allocation
P1 and P2 both require R1 and R1, locking on these resources should be like, both try to lock R1 then R2. By this way which ever process first locks R1 will get R2
Deadlock Avoidance
Basic
Checks if the Deadlock will occur if process gets permission to execute
The kernel be given in advance info concerning which resources will use in its lifetime
By this, system can decide for each request whether the process should wait
The main key of the deadlock avoidance method is whenever the request is made for resources then the request must only be approved only in the case if the resulting state is a safe state
Schedule process and its resource allocation in such a way that DL never occurs
Safe state
A state is safe if the system can allocate resources to each process (up to its maximum) in some order and still avoid DL
A system is in safe state only if there exists a safe sequence
Unsafe state
The operating system cannot prevent processes from requesting resources in such a way that any deadlock occurs. It is not necessary that all unsafe states are deadlocks, an unsafe state may lead to a deadlock
If the system is unable to fulfill the request of all processes, then the state of the system is called unsafe
Banker Algorithm
When a process requests a set of resources, the system must determine whether allocating these resources will leave the system in a safe state. If yes, then the resources may be allocated to the process. If not, then the process must wait till other processes release enough resources
Current State => Given
Number of process
Maximum need of resource of each process
Currently allocated amount of resource to each process
Maximum amount of each resource
Format of Table
Process
Allocated
Max. Need
Available
Remaining Need
Deadlock Detection
Systems which haven’t implemented deadlock-prevention or deadlock avoidance technique, may use DL detection, if DL exists then recovery technique or else again DL detection after some time
Single Instance of Each resource type => wait-for graph method
A deadlock exists in the system if and only if there is a cycle in the wait-for graph
wait-for graph => Resources removed from RAG
In order to detect the deadlock, the system needs to maintain the wait-for graph and periodically system invokes an algorithm that searches for the cycle in the wait-for graph
Multiple Instances for each resource type
Banker Algorithm => Safe sequence available then no deadlock
Deadlock Recovery
Process Termination
Abort all DL processes
Abort one process at a time until DL cycle is eliminated
Resource Preemption
To eliminate DL, we successively preempt some resources from processes and give these resources to other processes until DL cycle is broken