Deadlock

• A situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
• This block situation is called Deadlock(DL)
• 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.

• Starvation is long wating
• Deadlock is infinite wating

How a process/thread utilize a resource(R)?

• 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

Deadlock Necessary Condition

• 4 Condition should hold simultaneously.

1. 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.
2. Hold & Wait
   • A process must be holding at least one resource & waiting to acquire additional resources that are currently being held by other processes.
3. No-preemption
   • Resource must be voluntarily released by the process after completion of execution. (No resource preemption)
4. Circular wait
   • A set {P0, P1, … ,Pn} of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by P2, and so on.

Methods for handling Deadlocks

• Deadlock ignorance*
  • Ignore the problem altogether and pretend that deadlocks never occur in system. (Ostrich algorithm) aka, Deadlock ignorance.
• Deadlock prevention
  • Ensuring that the system will never enter a deadlocked state.
  • By ensuring atleast one of the necessary conditions for deadlock fails.
• Deadlock avoidance
  • Check safe and unsafe state to avoid deadlocl.
• Deadlock detection and recovery*
  • Allow deadlock the system to enter a deadlocked state, detect it, and recover.

Deadlock Prevention

• Deadlock prevention can be done by ensuring at least one of the necessary conditions for deadlock fails

1. 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): Each process has to request and be allocated all its resources before its execution
  • Protocol (B): Allow a process to request resources only when it has none
• No preemption
  • If new resource 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).
  • 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

• 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.
• Schedule process and its resources allocation in such a way that the DL never occur.
• i.e Scheduling algorithm using which DL can be avoided by finding safe state. (Banker Algorithm)

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.

Deadlock Detection

• 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.
  • 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

Deadlock detection and recovery*

• Detection
  • In single-instance RAG –> detect cycle
  • In multi-instance –> Use safety algo
• Recovery
  • Process termination
    • Abort all DL processes
    • Abort one process at a time until DL cycle is eliminated.
  • Resource
    • Resource Preemption
    • Resource Rollback