DEADLOCKS AND

INFORMATION
MANAGEMENT

UNIT III 15 MARKS

DEADLOCKS

CONCEPT
• A process in operating systems uses different resources and uses resources in following
way.
1) Requests a resource
2) Use the resource
2) Releases the resource
• Deadlock is a situation where a set of processes are blocked because each process is
holding a resource and waiting for another resource acquired by some other process.
• Some I/O media, such as disks are easily sharable for example multiple processes could be
using the same disk drive for reading or writing.
• But we cannot do the same for certain I/O media such as a tape drive or a printer.
• For example, it is not very easily imaginable to have a printer allocated to two processes,
and most importantly, belonging to two different users.
• In such a case, a printed report may contain some lines of pay slips along with with the
lines of sales analysis or production figures.
• Therefore, some I/O media can be allocated to only one process at a time.
• Because of its non-sharable nature, the user process must request for the entire device
and the Operating System has to allocate those I/O devices accordingly.
• Only when the user process gives up a device, can the Operating System take it back and
add it to the free pool.
• Some problems arise when an I/O medium is allocated to a process in an exclusive
manner.
•Let us imagine two processes, PA and PB running simultaneously.
•Halfway through, PA requests the Operating System for a file on the tape drive, and PB
requests the Operating System for the printer.
•Let us assume that both the requests are granted.
•After a while, PA requests for the printer without giving up the tape drive.
•Similarly, PB requests for the tape drive without giving up the control of the printer.
•Assuming that the system has only one tape drive and one printer, what will happen?
• It is clear that both the processes cannot proceed.
• PA will wait until PB releases the printer. But that can happen only if PB can proceed further and
finish off its processing with the printer.
• And this can happen only if PB gets the tape drive that PA is holding.
• PB can get the tape drive only if PA can proceed further and completes its work with
the tape drive.
• That cannot happen too unless PA gets the printer which PB is holding.
• This situation is called a deadlock.
• It is not necessary that a deadlock can take place only in the context of the I/O media.
• It can happen for any shared resource, such as the internal tables maintained by the
Operating System.
Graphical representation of a Deadlock

• Figure shows square boxes as resources named RI

and R2.

• Similarly, processes shown as hexagons are named

PI and P2.

• The arrows show the relationship.

• For example, in part (a) of the figure, resource RI is

allocated to process PI, or in other words, PI holds RI.

• In part (b) of the figure, process P2 wants resource R2, but it has not yet got it.
• It is waiting for it. (The moment it gets the resource, the direction of the arrow will
change.)
•These graphs are called Directed Resource Allocation Graphs (DRAG).
•They help us in understanding the process of detection of a deadlock.
•Now let us imagine a typical scenario for the deadlock.
• PI holds RI but demands R2.
• P2holdsR2butdemands RI.
•A DRAG for this situation would look like this .
• We can see in the figure that a close loop has occurred. Therefore this situation is called
circular wait condition.
• Do not get confused with the shape of the DRAG.
• For example the same DRAG can be shown as
• Whenever you start from any node you must return to the original node .
• This is what it makes a circular wait or deadlock situation.
• The shape of the DRAG is not relevant.
• This principle is used by the Operating System to detect deadlocks.
• However, this is a simple picture.
• In actual, the DRAGS can get very complicated, and therefore, the detection of a
deadlock is very difficult.
• At any moment, when the Operating System realizes that the existing processes are not
finishing for a long time, it can find out whether there is a deadlock situation or not.
• All resource allocations are made by the Operating System.
• When any process waits for a resource, it is again the Operating System which keeps
track of this situation of waiting.
• Therefore, the Operating System knows which processes are holding which resources
and which resources these processes are waiting for.
• In order to detect a deadlock, the Operating System can give some imaginary
coordinates to the nodes, R and P.
• Depending upon the relationships between resources and processes (i.e. directions of
the arrows), it can keep traversing, each time checking if it has returned to a node it has
already travelled by, to detect the incidence of a deadlock.
What will the Operating System do if it finds a deadlock?

•The only way out is to kill one of the processes so that the cycle is broken.
•Many large mainframe computers use this strategy.
•Some systems do not go through the overhead of constructing a DRAG.
•They monitor the performance of all the processes.
•If none finishes for a very long time, the Operating System kills one of the processes.
Deadlock prerequisite (Deadlock condition)
What causes a deadlock?
There are four conditions which must be satisfied for a deadlock to occur. These
conditions are as follows:-
(i) Mutual Exclusion Condition
• Resources must be allocated to processes at any time in an exclusive manner and not on a shared
basis for a deadlock to be possible.
• For instance, a disk drive can be shared by two processes simultaneously. This will not cause a
deadlock.
• But printers, tape drives. plotters, etc. have to be allocated to a process in an exclusive manner
until the process completely finishes its work with it (which normally happens when
the process ends).
• This is the cause of the trouble.
(ii) Wait for Condition
•Even if a process holds certain resources at any moment, it should be possible for it to request for
new ones.
•It should not have to give up the already held resources to be able to request for new ones.
•If this is not true, a deadlock can never take place.
(iii) No Preemption Condition
•If a process holds certain resources, no other process should be able to take them away from it
forcibly.
•Only the process holding them should be able to release them explicitly.
(iv) Circular Wait Condition
• Processes (PI , P2) and Resources (R I , R2) should form a circular list as expressed in the form of a
graph (DRAG).
• In short, there must be a circular (logically, and not in terms of the shape) chain of multiple
resources and multiple processes forming a closed loop.
• It is necessary to understand that all these four conditions have to be satisfied
simultaneously for the existence of a deadlock.
• If any one of them does not exist, a deadlock can be avoided.
Deadlock Strategies

• Various strategies have been followed by different Operating System to deal with deadlocks.
• These are as follows:-
❑ Ignorance
❑ Detection
❑ Recovery
❑ Prevention
❑ Avoidance
Ignore a deadlock (Ignorance)
•There are many approaches one can take to deal with deadlocks.
•One of them, the simplest, is to ignore them.
• Pretend as if you are totally unaware of them. (This is the reason why it is called, as Ostrich
algorithm.)
•There are valid reasons to ignore a deadlock.
• Firstly, the deadlock detection, recovery and prevention algorithms are complex to write, test and
debug.
•Secondly, they slow down the system considerably.
•System admin can simply kill deadlock process or reboot if the system is not responding.
Detect a deadlock (Detection)
• It is the process of actually determining whether a deadlock exists and identifying the process and the
resources involved in the deadlock.
• The graph (DRAG) can provide help in doing this.
• However a realistic DRAG is not as simple as a DRAG between two processes and two resources.
• Large number of processes can make DRAG very complex with deadlock detection turning into time
consuming task.
• The system needs an algorithm that determines whether a deadlock has occurred within a system or
not.
The two algorithms for detection of deadlocks are :-
1. One instance for resource type
2. Multiple instances for resource type
Recover from a deadlock (Recovery)
• When a system detects a deadlock it needs to recover from it.
• There are two approaches to detect a deadlock. These are:-
1. Suspend / Resume a process
2. Kill a process
1. Suspend / Resume a process
• In this method a process is selected based on a variety of criteria (like priority, scheduling etc.) and
it is suspended for a long time.
• The resources that were held by that process are reclaimed(taken) from it and then allocated to
other processes that are waiting for them.
• When one of the waiting processes gets over, the original suspended process is resumed.
• This scheme looks simple, but there are several problems in its implementation.
Disadvantages
• Not all Operating Systems support hold and resume operations.
• This strategy cannot be used in real time systems because response times of processes
becomes unpredictable.
• Suspend or resume is not easy to manage, because deciding which process to be
suspended is a tricky task.
2. Kill a process
• In this scheme The Operating System decides to kill one or more processes and reclaim all their
resources after ensuring that such action will solve the deadlock.
• The Operating System can use the DRAG and deadlock detection algorithms to ensure that after
killing a specific process, there will not be a deadlock.
• This solution is simple, but involves loss of at least one process.
• There are two methods to implement this approach.
• First method is to kill all the deadlocked processes.
• The method looks very simple and effective, but the operation of killing a number of
processes and starting them all over again is very costly.
•Second method involves the following steps:
I. Kill one process
2. Check the state of the system
3. If the deadlock is resolved, exit. Otherwise go back to step I
• Again this solution is not too satisfactory, as the deadlock detection procedure needs to be
executed repeatedly for second step.

• Choosing a process to be killed, depends on the scheduling policy and the process priority.
• It is safest to kill a lowest priority process which has just begun, so that the loss is not very
heavy.
Prevent a deadlock ( Prevention)
• This technique aims at creating circumstances that can prevent a deadlock.
• If any of the following conditions are not met then there will not be any deadlock:-
1. Mutual exclusion
2. Wait for condition
3. No pre-emption
4. Circular wait
1. Mutual exclusion
• If every resource in the system were sharable by multiple processes, deadlocks would never occur.
• However, such sharing is not practicable. For instance, a tape drive, a plotter or a printer cannot be
shared amongst several processes.
2.Wait for condition
• A process should not be allowed to request for more resources while it is already
holding certain resources.
• This can be achieved by demanding that at very beginning every process declares all the
resources that it is expected to use.
• A process must declare all the resources it is expected to use in its execution.
• The operating system should find out if these resources are available and allow the
process to execute only if all of them are available.
3. No pre-emption
• If a process is holding some resources and is demanding more resources but is unable to
get additional resources then it should release all the other resources held by it.
• If a process wants a resource which is held by another process which is aGain waiting for
some other process then the process should be able to take it forcibly.
4. Circular wait
• A process should be forced to hold only one resource at a time.
• If it wants another resource it should give up the one that is held by it.
Avoid a Deadlock (Avoidance)
• Maximum requirement of each resource must be stated in advance by each process.
• There are two approaches for avoiding a deadlock:
1. Do not start a process if its maximum requirement might lead to a deadlock.
2. Do not grant additional resources if the allocation leads to a deadlock.
 • Two algorithms
1. One instance for resource type – Resource allocation graph algorithm
2. Multiple instances per resource type – Bankers algorithm
• Resource allocation state is defined by number of available and allocated resources and
maximum demand of the processes.
• Deadlock avoidance algorithm examines the resource allocation state to ensure that
there can never be a circular wait condition.
• Limitation of this algorithm is that it requires specification of future needs.