Handling Deadlocks

Deadlocks Handling
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.
1. Deadlock Prevention
2. Deadlock avoidance
3. Deadlock detection
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.
It is important to prevent a deadlock before it can occur. So, the system checks each
transaction before it is executed to make sure it does not lead to deadlock. If there is even a
slight possibility that a transaction may lead to deadlock, it is never allowed to execute.
Some deadlock prevention schemes that use timestamps in order to make sure that a
deadlock does not occur are given as follows −
Wait - Die Scheme
 In the wait - die scheme, if a transaction T1 requests for a resource that is held by
transaction T2, one of the following two scenarios may occur −
o TS(T1) < TS(T2) - If T1 is older than T2 i.e T1 came in the system earlier than T2,
then it is allowed to wait for the resource which will be free when T2 has
completed its execution.
o TS(T1) > TS(T2) - If T1 is younger than T2 i.e T1 came in the system after T2,
then T1 is killed. It is restarted later with the same timestamp.
In short Wait-Die scheme there are two transactions, T1 and T2, where T1 tries to lock a data
item which is already locked by T2. If T1 is older than T2, T1 is allowed to wait. Otherwise,
if T1 is younger than T2, T1 is aborted and later restarted.
Wound - Wait Scheme

 In the wound - wait scheme, if a transaction T1 requests for a resource that is held by
transaction T2, one of the following two possibilities may occur −
o TS(T1) < TS(T2) - If T1 is older than T2 i.e T1 came in the system earlier than T2,
then it is allowed to roll back T2 or wound T2. Then T1 takes the resource and
completes its execution. T2 is later restarted with the same timestamp.
o TS(T1) > TS(T2) - If T1 is younger than T2 i.e T1 came in the system after T2,
then it is allowed to wait for the resource which will be free when T2 has
completed its execution.
In short Wound-Wait scheme − there are two transactions, T1 and T2, where T1 tries to lock
a data item which is already locked by T2. If T1 is older than T2, T2 is aborted and later
restarted. Otherwise, if T1 is younger than T2, T1 is allowed to wait.
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
It is better to avoid a deadlock rather than take measures after the deadlock has occurred. The
wait for graph can be used for deadlock avoidance. This is however only useful for smaller
databases as it can get quite complex in larger databases.
Wait for graph
The wait for graph shows the relationship between the resources and transactions. If a
transaction requests a resource or if it already holds a resource, it is visible as an edge on the
wait for graph. If the wait for graph contains a cycle, then there may be a deadlock in the
system, otherwise not.
Ostrich Algorithm
The ostrich algorithm means that the deadlock is simply ignored and it is assumed that it will
never occur. This is done because in some systems the cost of handling the deadlock is much
higher than simply ignoring it as it occurs very rarely. So, it is simply assumed that the
deadlock will never occur and the system is rebooted if it occurs by any chance.
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.
Deadlock can be detected by the resource scheduler as it keeps track of all the resources that
are allocated to different processes. After a deadlock is detected, it can be handed using the
given methods −
 All the processes that are involved in the deadlock are terminated. This approach is not
that useful as all the progress made by the processes is destroyed.
 Resources can be preempted from some processes and given to others until the deadlock
situation is resolved.

Handling Deadlocks

Uploaded by

Copyright:

Available Formats

Handling Deadlocks

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Handling Deadlocks

Uploaded by

Copyright:

Available Formats

Deadlocks Handling

Wound - Wait Scheme

2. Deadlock Avoidance : This approach allows the three necessary conditions of deadlock

Wait for graph

3. Deadlock Detection : Deadlock detection is used by employing an algorithm that tracks

You might also like