An indirect method of deadlock prevention is to prevent the occurrence of a circular wait.

Deadlock is a situation where a process or a set of processes is blocked, waiting for some other resource that is held by some other waiting process. It is an undesirable state of the system. The following are the four conditions that must hold simultaneously for a deadlock to occur.

1. Mutual Exclusion – A resource can be used by only one process at a time. If another process requests for that resource then the requesting process must be delayed until the resource has been released.
2. Hold and wait – Some processes must be holding some resources in non shareable mode and at the same time must be waiting to acquire some more resources, which are currently held by other processes in non-shareable mode.
3. No pre-emption – Resources granted to a process can be released back to the system only as a result of voluntary action of that process, after the process has completed its task.
4. Circular wait – Deadlocked processes are involved in a circular chain such that each process holds one or more resources being requested by the next process in the chain.

Methods of handling deadlocks : There are three approaches to deal with deadlocks.

These are explained as following below. 

1. Deadlock Prevention : The strategy of deadlock prevention is to design the system in such a way that the possibility of deadlock is excluded. Indirect method prevent the occurrence of one of three necessary condition of deadlock i.e., mutual exclusion, no pre-emption and hold and wait. Direct method prevent the occurrence of circular wait. Prevention techniques – Mutual exclusion – is supported by the OS. Hold and Wait – condition can be prevented by requiring that a process requests all its required resources at one time and blocking the process until all of its requests can be granted at a same time simultaneously. But this prevention does not yield good result because :

• long waiting time required
• in efficient use of allocated resource
• A process may not know all the required resources in advance

No pre-emption – techniques for ‘no pre-emption are’

• If a process that is holding some resource, requests another resource that can not be immediately allocated to it, the all resource currently being held are released and if necessary, request them again together with the additional resource.
• If a process requests a resource that is currently held by another process, the OS may pre-empt the second process and require it to release its resources. This works only if both the processes do not have same priority.

Circular wait One way to ensure that this condition never hold is to impose a total ordering of all resource types and to require that each process requests resource in an increasing order of enumeration, i.e., if a process has been allocated resources of type R, then it may subsequently request only those resources of types following R in ordering. 

2. Deadlock Avoidance : This approach allows the three necessary conditions of deadlock but makes judicious choices to assure that deadlock point is never reached. It allows more concurrency than avoidance detection A decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to deadlock. It requires the knowledge of future process requests. Two techniques to avoid deadlock :

1. Process initiation denial
2. Resource allocation denial

Advantages of deadlock avoidance techniques :

• Not necessary to pre-empt and rollback processes
• Less restrictive than deadlock prevention

Disadvantages :

• Future resource requirements must be known in advance
• Processes can be blocked for long periods
• Exists fixed number of resources for allocation

3. Deadlock Detection : Deadlock detection is used by employing an algorithm that tracks the circular waiting and killing one or more processes so that deadlock is removed. The system state is examined periodically to determine if a set of processes is deadlocked. A deadlock is resolved by aborting and restarting a process, relinquishing all the resources that the process held.

• This technique does not limit resources access or restrict process action.
• Requested resources are granted to processes whenever possible.
• It never delays the process initiation and facilitates online handling.
• The disadvantage is the inherent pre-emption losses.

Article Tags :

Practice Tags :

Deadlock Characteristics As discussed in the previous post, deadlock has following characteristics. 

1. Mutual Exclusion
2. Hold and Wait
3. No preemption
4. Circular wait

Deadlock Prevention We can prevent Deadlock by eliminating any of the above four conditions. 

Eliminate Mutual Exclusion 
It is not possible to dis-satisfy the mutual exclusion because some resources, such as the tape drive and printer, are inherently non-shareable. 

Eliminate Hold and wait 

1. Allocate all required resources to the process before the start of its execution, this way hold and wait condition is eliminated but it will lead to low device utilization. for example, if a process requires printer at a later time and we have allocated printer before the start of its execution printer will remain blocked till it has completed its execution. 
    
2. The process will make a new request for resources after releasing the current set of resources. This solution may lead to starvation.

Eliminate No Preemption 
Preempt resources from the process when resources required by other high priority processes. 

 Eliminate Circular Wait Each resource will be assigned with a numerical number. A process can request the resources increasing/decreasing. order of numbering. 

For Example, if P1 process is allocated R5 resources, now next time if P1 ask for R4, R3 lesser than R5 such request will not be granted, only request for resources more than R5 will be granted. 

 Deadlock Avoidance 
Deadlock avoidance can be done with Banker’s Algorithm. 

Banker’s Algorithm 
Bankers’s Algorithm is resource allocation and deadlock avoidance algorithm which test all the request made by processes for resources, it checks for the safe state, if after granting request system remains in the safe state it allows the request and if there is no safe state it doesn’t allow the request made by the process. 

Inputs to Banker’s Algorithm: 
 

1. Max need of resources by each process. 
2. Currently, allocated resources by each process. 
3. Max free available resources in the system.

The request will only be granted under the below condition: 

1. If the request made by the process is less than equal to max need to that process. 
2. If the request made by the process is less than equal to the freely available resource in the system.

Example: 

Note: Deadlock prevention is more strict than Deadlock Avoidance. 

Article Tags :

Practice Tags :