Deadlock:

• The computer system uses may types of resource which are then used by various processes to carry out their individual functions.
• But problem is that the amount of resources available is limited and many process needs to use it.
• A set of process is said to be in a deadlocked state when every process in the set is waiting for an event that can be caused only by another process in the set. The event can be resource acquisition, resource release etc. The resource can be physical (printers, memory space) or logical (semaphores, files)

The necessary and sufficient conditions for deadlock to occur are:

• Mutual Exclusion

  • A resource at a time can only be used by one process.
  • If another process is requesting for the same resource, then it must be delayed until that resource is released.

• Hold and Wait

  • A process is holding a resource and waiting to acquire additional resources that are currently being held by other processes.

• No Pre-emption:

  • Resources cannot be pre-empted
  • Resource can be released only by the process currently holding it based on its voluntary decision after completing the task

• Circular wait

  • A set of processes { P0,P1,….,Pn-1,Pn } such that the process P0 is waiting for resource held by P1,P1 is waiting for P2 ,and Pn is waiting for P0 to release its resources.
  • Every process holds a resource needed by the next process.

All the four above mentioned conditions should occur for a deadlock to occur.

The three major approaches for handling deadlocks are as follows:

a) It ensures Deadlock Prevention:

• That the system never enters a deadlock state.
• It provides a set of methods to make sure that at least one of the four necessary conditions for a deadlock is never satisfied.
• Mutual Exclusion  this condition is needed to be checked for non-sharable resources (e.g. Printer)
• Hold and Wait  It requires a process to request a resource and get allocated before execution or allow process to request resources when the process has none.
• No preemption  If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
• Circular Waitwe can impose a total ordering of all resource types, and ask that each process requests resources in an increasing order of enumeration.
• Disadvantage is that it can lead to low device utilization and reduced system throughput.

b) Deadlock Avoidance:

• It is the simplest and most friendly method.
• It requires that each process declare the maximum number of resources of each type that it will need.
• The deadlock-avoidance algorithm dynamically checks the resource-allocation state to ensure the system can never be in a circular-wait condition.
• When a process requests a resource, the system must make sure that the allocation would leave the system in a safe state.
• It the system is in a safe state, then there would be no deadlock. However, if it is in an unsafe state, that there is a possibility (not certainty) of a deadlock.
• The avoidance approach requires that knowledge of all processes, all the resources available, the resources allocated presently and the future requests by the processes.
• For a single instance of a resource type we use the resource allocation graph.
• For multiple instance of a resource type, we use the banker’s algorithm.
• A major drawback of this method is that it is difficult to know at the beginning itself of the maximum resource required.

c) Deadlock detection and recovery:

• Here we allow the system to enter into a deadlock state and then try to recover the system back from it
• This method has two parts:

i. Detection: an algorithm to check the system state whether in deadlock

ii. Recovery: initiated when deadlock detected, to recover from that deadlock.

• This method doesn’t require the maximum need MAX or the Need matrix. It works using the Available, Allocation and Request data structures
• For single instance of a resource type we use the wait-for graphs and search for cycles in the graph.
• For multiple instances of each resource type, we use the Deadlock-detection algorithm.
• To recover we have two options

i. Abort one or more processes

ii. Pre-empt one or more resources from one or more deadlocked process