Methods for Handling Deadlocks: Deadlock Prevention

 

Methods for Handling Deadlocks:

 

 We can deal with the deadlock problem in one of three ways:

 

1.    We can use a protocol to prevent or avoid deadlocks ensuring that the system will never enter a deadlock state.

2.    We can allow other system to enter a deadlock state, detect it and recover.

3.    We can ignore the problem altogether and pretend that deadlocks never occur in the system. This solution is used by most operating systems including UNIX.

 

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

 

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

 

Deadlock avoidance on the other hand require that the operating system be given in advance additional information concerning which resources a process will request use during its lifetime.  With this additional knowledge we can decide for each request whether or not the process should wait.

 

Deadlock Prevention:

 

For a deadlock to occur each of the four necessary conditions must hold. By ensuring that at least one of these conditions cannot hold we can prevent the occurrence of a deadlock.

 

 

 

1.    Mutual exclusion:

 

The mutual exclusion condition must hold for non-sharable resources.  For example a printer cannot be simultaneously shared by several processes.

 

Shareable resources on the other hand do not require mutually exclusive access and thus cannot be involved in a deadlock.

 

Read only files are a good example of shareable resource.  If several processes attempt to open a read-only file at the same time they can be granted simultaneous access to the file. A process never needs to wait for a shareable resource.

 

 

2.    Hold and wait:

 

To ensure that the hold and wait condition never occurs in the system we must guarantee that whenever a process requested resource it does not hold any other resources.

 

One protocol that can be used requires each process to request and be allocated all its resources before it begins execution.  We can implement this by requiring that system calls requesting resources for a process precede all other system calls.

 

An alternative protocol allows a process to request resources only when the process has none.  A process requests some resources and uses them.  Before it can request any additional resources however it must release all the resources that it is currently allocated.

 

These protocols have two main disadvantages.  First, resource utilisation may be low since many of the resources may be allocated button used for a long period. Second, starvation is possible. A process that needs several resources may have to wait indefinitely because at least one of the resources that it needs is always allocated to some other process.

 

 

3.    No pre-emption:

 

The third necessary condition is that there be no pre-emption of resources that have already been allocated.

 

To ensure that this condition does not hold, we can use the following protocol. If a process is holding some resources and requests another resource that cannot be immediately allocated to it i.e. the process must wait until all resources currently being held are pre-empted.

The pre-empted resources are added to the list of resources for which the process is waiting. The process will be restarted only when it can regain its all 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.

 

 

4.    Circular wait:

 

The fourth and final condition for deadlock is the circular wait condition.

 

One way to ensure that this condition never holds is to impose a total ordering of all resource types, and you require that each process requests resources in an increasing order of enumeration.

 

Let R={R₁,R₂,...,R_m} be the set of resources types be assigned 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. 

 

We define a one to one function F: R->N, where ‘N’ is the set of natural numbers. For example, if the set of resources types ‘R’ includes tape drives, disk drives and printers then the function ‘F’ might be defined as follows:

 

F (tape drive) =1,

F (disc 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 resource type say R_i.

 

After that the process can request instances of resource type R_j if and only if F (R_j)>F(R_i).

 

If several instances of the same resource type are needed, a single request for all of them must be issued.

 

Alternatively, we can require that whenever a process request an instance of resource type Rj, it has released any resources R_i such that (R_i)>=F (R_j). If these two protocols are used, then the circular wait condition cannot hold.