Methods for Handling Deadlocks

The problem of deadlock can deal with the following 3 ways.

• We can use a protocol to prevent or avoid deadlock ensuring that the system will never enter to a deadlock state.
•  We can allow the system to enter a deadlock state, detect it and recover.
• We can ignore the problem all together.

To ensure that deadlock never occur the system can use either a deadlock prevention or deadlock avoidance scheme.

Deadlock Prevention:
Deadlock prevention is a set of methods for ensuring that at least one of these necessary conditions cannot hold.

•  Mutual Exclusion: The mutual exclusion condition holds for non sharable. The example is a printer cannot be simultaneously shared by several processes. Sharable resources do not require mutual exclusive access and thus cannot be involved in a dead lock. The example is read only files which are in sharing condition. If several processes attempt to open the read only file at the same time they can be guaranteed simultaneous access.
•  Hold and wait:To ensure that the hold and wait condition never occurs in the system, we must guaranty that whenever a process requests a resource it does not hold any other resources. There are two protocols to handle these problems such as one protocol that can be used requires each process to request and be allocated all its resources before it begins execution. The other protocol allows a process to request resources only when the process has no resource. These protocols have two main disadvantages. First, resource utilization may be low, since many of the resources may be allocated but unused for a long period. Second, starvation is possible. A process that needs several popular resources may have to wait indefinitely, because at least one of the resources that it needs is always allocated to some other process.
• No Preemption: To ensure that this condition does not hold, a protocol is used. If a process is holding some resources and request another resource that cannot be immediately allocated to it. The preempted one added to a list of resources for which the process is waiting. The process will restart only when it can regain its old resources, as well as the new ones that it is requesting. Alternatively if a process requests some resources, we first check whether they are available. If they are, we allocate them. If they are not available, we check whether they are allocated to some other process that is waiting for additional resources. If so, we preempt the desired resources from the waiting process and allocate them to the requesting process. If the resources are not either available or held by a waiting process, the requesting process must wait.
•  Circular Wait:We can ensure that this condition never holds by ordering of all resource type and to require that each process requests resource in an increasing order of enumeration.
  Let R = {R1 , R2, …….Rn} be the set of resource types. We assign to each resource type a unique integer number, which allows us to compare two resources and to determine whether one precedes another in our ordering. Formally, we define a one to one function F: R → N, where N is the set of natural numbers. For example, if the set of resource types R includes tape drives, disk drives and printers, then the function F might be defined as follows:
  F (Tape Drive) = 1,
  F (Disk Drive) = 5,
  F (Printer) = 12.We can now consider the following protocol to prevent deadlocks: Each process can request resources only in an increasing order of enumeration. That is, a process can initially request any number of instances of a resource type, say Ri. After that, the process can request instances of  resource type Rj
  if and only if F (Rj) > F (Ri).
  If several instances of the same resource type are needed, defined previously, a process that wants to use the tape drive and printer at the same time must first request the tape drive and then request the printer.

Deadlock Avoidance
Requires additional information about how resources are to be used.Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need.The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition.Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.
Safe State
When a process requests an available resource, system must decide if immediate allocation leaves the system in a safe state.Systems are in safe state if there exists a safe sequence of all process. A sequence of ALL the processes is the system such that for each Pi , the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj , withj No deadlock
• If system in not in safe state => possibility of deadlock
• OS cannot prevent processes from requesting resources in a sequence that leads to deadlock
• Avoidance => ensue that system will never enter an unsafe state, prevent getting into deadlock