DEADLOCK:

The concept of a deadlock can be illustrated by two vehicles crossing a

narrow bridge which permits passing of only one vehicle.
 Introduction of Deadlock in Operating System

A process in operating systems uses different resources and uses resources

in the following way.
1) Requests a resource
2) Use the resource
3) 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.
For example, in the below diagram, Process 1 is holding Resource
1 and waiting for resource 2 which is acquired by process 2, and
process 2 is waiting for resource 1.
 (Necessary Conditions for deadlock)

Deadlock can arise if the following four conditions hold simultaneously

(Necessary Conditions)
Mutual Exclusion: One or more than one resource are non-shareable (Only one
process can use at a time)
Hold and Wait: A process is holding at least one resource and waiting for
resources.
No Preemption: A resource cannot be taken from a process unless the process
releases the resource. The process which once scheduled will be executed till
the completion. No other process can be scheduled by the scheduler
meanwhile.
Circular Wait: A set of processes are waiting for each other in circular form.
Mutual Exclusion
• It means whatever resource we are using it must be used in a mutually
exclusive(non sharable) way. Where only one processes use one resource
at a time only.
• For example, the printing process is going on and all sudden another
process tries to interrupt the printing process. So here in mutual exclusion
situation, only after the printing task is completed then only the next task
is processed.
• Mutual exclusion can be eliminated by sharing resources simultaneously,
which is not possible practically.
No Pre-emption
Resources cannot be preempted; that is, a resource can be released
only voluntarily by the process holding it, after that process has
completed its task.
A situation explained as per the above example where a process
holds the resource as long as it gets executed, that is P1 can release
R1 only after executing, similarly P2 release R2 only after execution.
If there is no pre-emption the deadlock may occur.
Hold and Wait
A process is holding some resources and is waiting for additional
resources but those resources are acquired by some other
process. From the above example, P1 is holding R1 and waiting for
R2, where R2 is acquired by P2, and P2 is holding R2 and waiting
for R1, where R1 is acquired by P1 is a hold and wait situation
deadlock may occur in the system.
Circular Wait
A set of processes are said to be in deadlock if one process
is waiting for a resource that is allocated to another process
and that process is waiting for a resource, it is similar to the
above-explained example where it is in loop form. Where
P1 is waiting for R2 and R2 is allocated for P2 and P2 is
waiting for R1 and R1 allocated for P1 which is a circular
wait form if this condition satisfies deadlock occurs.
Methods for handling deadlock
There are mainly four methods for handling deadlock.
1. Deadlock ignorance
2. Deadlock prevention
3. Deadlock avoidance
4. Detection and recovery
1. Deadlock ignorance
It is the most popular method and it acts as if no deadlock and the user
will restart. As handling deadlock is expensive to be called of a lot of
codes need to be altered which will decrease the performance so for
less critical jobs deadlock are ignored. Used in windows, Linux etc.
• This strategy involves ignoring the concept of deadlock and
assuming as if it does not exist.
• This strategy helps to avoid the extra overhead of handling
deadlock.
• Windows and Linux use this strategy and it is the most widely used
method.
2.Detection and recovery
When the system is in deadlock then one method is to inform the
operator and then operator deal with deadlock manually and the
second method is system will automatically recover from
deadlock. There are two ways to recover from deadlock:
Process termination:
Deadlock can be eliminated by aborting a process. Abort all
deadlock process. Abort is processed at a time until the deadlock
cycle is eliminated. This can help to recover the system from file
deadlock.
Resources preemption:
To eliminate deadlock using resources preemption, we preempt
the same resources and give these resources to another process
until the deadlock cycle is broken.
Here a process is partially rollback until the last checkpoint or and
then detection algorithm is executed.
• This strategy involves waiting until a deadlock occurs.
• After deadlock occurs, the system state is recovered.
• The main challenge with this approach is detecting the
deadlock.
Deadlock Prevention-

This strategy involves designing a system that violates one of the four
necessary conditions required for the occurrence of deadlock.
This ensures that the system remains free from the deadlock.

The various conditions of deadlock occurrence may be violated as-

1. Mutual Exclusion-

To violate this condition, all the system resources must be such that they
can be used in a shareable mode.
In a system, there are always some resources which are mutually exclusive
by nature.
So, this condition can not be violated.
The mutual-exclusion condition must hold for non-sharable resources.
Sharable resources, do not require mutually exclusive access and thus cannot
be involved in a deadlock.
Read-only files are a good example of a sharable 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 sharable resource. In general, however, we
cannot prevent deadlocks by denying the mutual-exclusion condition, because
some resources are intrinsically non-sharable.
2. Hold and Wait-

This condition can be violated in the following ways-

Approach-01:

In this approach,
A process has to first request for all the resources it requires for execution.
Once it has acquired all the resources, only then it can start its execution.
This approach ensures that the process does not hold some resources and
wait for other resources.

Drawbacks-

The drawbacks of this approach are-

It is less efficient.
It is not implementable since it is not possible to predict in advance which
resources will be required during execution.
Approach-02:

In this approach,
•A process is allowed to acquire the resources it desires at the current moment.
•After acquiring the resources, it start its execution.
•Now before making any new request, it has to compulsorily release all the
resources that it holds currently.
•This approach is efficient and implementable.

Approach-03:

In this approach,
•A timer is set after the process acquires any resource.
•After the timer expires, a process has to compulsorily release the resource.
To ensure that the hold-and-wait condition never occurs in the system, we
must guarantee that, whenever a process requests a 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.
• An alternative protocol allows a process to request resources only when it
has none. A process may request some resources and use them. Before it
can request any additional resources, however it must release all the
resources that it is currently allocated.
• we consider a process that copies data from a DVD drive to a file on disk,
sorts the file, and then prints the results to a printer.
• If all resources must be requested at the beginning of the process, then the
process must initially request the DVD drive, disk file, and printer. It will
hold the printer for its entire execution, even though it needs the printer
only at the end.
• The second method allows the process to request initially only the DVD
drive and disk file. It copies from the DVD drive to the disk and then
releases both the DVD drive and the disk file. The process must then again
request the disk file and the printer. After copying the disk file to the printer,
it releases these two resources and terminates.
Both these protocols have two main disadvantages.
First, resource utilization may be allocated, since 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.
3. No preemption
We will see two approaches here. If a process request for a
resource which is held by another waiting resource, then the
resource may be preempted from the other waiting resource. In
the second approach, if a process request for a resource which are
not readily available, all other resources that it holds are
preempted.
The challenge here is that the resources can be preempted only if
we can save the current state can be saved and processes could be
restarted later from the saved state.
To ensure that no preemption 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 (that is, the process must wait), then all resources
currently being held are preempted.
The preempted 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 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, we check whether they are allocated to some other process that is
waiting for additional resources.
P2(waiting
P1(requesting process)
process for printer)
Holds Waiting for
Holds DVD printer disk file.

If so, we preempt the desired resources from the waiting process and allocate them
to the requesting process.
If the resources are neither available nor held by a waiting process, the
requesting process must wait. While it is waiting, some of its resources may
be preempted, but only if another process requests them.
A process can be restarted only when it is allocated the new resources it is
requesting and recovers any resources that were preempted while it was
waiting.
This protocol is often applied to resources whose state can be easily saved
and restored later, such as CPU registers and memory space. It cannot
generally be applied to such resources as printers and tape drives.
4. Circular Wait-

This condition can be violated by not allowing the processes to wait for
resources in a cyclic manner.
To violate this condition, the following approach is followed-

Approach-

A natural number is assigned to every resource.

Each process is allowed to request for the resources either in only increasing
or only decreasing order of the resource number.
In case increasing order is followed, if a process requires a lesser number
resource, then it must release all the resources having larger number and vice
versa.
This approach is the most practical approach and implementable.
However, this approach may cause starvation but will never lead to deadlock.
 Prevent the circular wait condition from coming true – Solution I: a
process can only hold 1 resource at a time
• disadvantage: in some cases, a process needs to hold multiple
resources to accomplish a task –
Solution II: impose a total ordering of all resource types and require
each process to request resources in increasing order • this prevents a
circular wait
Example of preventing circular waits using ordering: – Order all resources into a
list: R1, R2, ..., Rm, where R1 < R2 < ... < Rm
• tape drive = R1
• disk drive = R2
• printer = R10 –
Impose the rule that a process holding Ri can only request Rj if Rj > Ri –
If a process P holds some R k and requests Rj such that Rj < R k, then the process
must release all such R k, acquire Rj, then reacquire R k • can lead to poor
performance
The fourth and final condition for deadlocks 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 to require that each process requests resources in an
increasing order of enumeration.
To illustrate, we let R = {R1, R2, ..., Rm} 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
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, a single request for all
of them must be issued.
For example, using the function 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.
Alternatively, we can require that, whenever a process requests an instance of
resource type Rj, it has released any resources Ri such that F(Ri )> F(Rj).
If these two protocols are used, then the circular-wait condition cannot hold.
 Deadlock avoidance/deadlock avoidance in os

Safe state: A state is safe if the system can allocate all resources requested by
all processes without entering a deadlock state.
A state is safe if the system can allocate resources to each process (up
to its maximum) in some order and still avoid a deadlock.
a system is in a safe state only if there exists a safe sequence.
A sequence of processes < P1,P2,P3…Pn> is a safe sequence for the
current allocation state it for each Pi the resource requests can be
satisfied by the currently available resources plus the resources held
by all Pj, with j<i.
In this situation, if the resources that Pi needs are not immediately
available, then Pi can wait until all Pj have finished. When they have
finished, Pi can obtain all of its needed resources, complete its
designated task, return its allocated resources, and terminate.
When Pi terminates, Pi +1 can obtain its needed resources, and so on.
If no such sequence exists, then the system state is said to be unsafe.
An unsafe state may lead to a deadlock. As long as the state is safe,
the operating system can avoid unsafe (and deadlocked) states.
 The behavior of the processes controls unsafe states. To illustrate, we
consider a system with 12 magnetic tape drives and three processes:
Po, P1, and P2 . Process Po requires 10 tape drives, process P1 may
need as many as 4 tape drives, and process P2 may need up to 9 tape
drives. Suppose that, at time to, process Po is holding 5 tape drives,
process P1 is holding 2 tape drives, and process P2 is holding 2 tape
drives. (Thus, there are 3 free tape drives.)

At time to, the system is in a safe state. The sequence < P1, Po, P2 > satisfies the safety
condition. Process P1 can immediately be allocated all its tape drives and then return them
(the system will then have 5 available tape drives); then process Po can get all its tape
drives and return them (the system will then have 10 available tape drives); and finally
process P2 can get all its tape drives and return them (the system will then have all 12 tape
drives available).
A system can go from a safe state to an unsafe state. Suppose that, at
time t1, process P2 requests and is allocated one more tape drive. The
system is no longer in a safe state. At this point, only process P1can be
allocated all its tape drives. When it returns them, the system will have
only 4 available tape drives. Since process Po is allocated 5 tape drives
but has a maximum of 10, it may request 5 more tape drives. Since they
are unavailable, process Po must wait. Similarly, process P2 may request
an additional 6 tape drives and have to wait, resulting in a deadlock.
Our mistake was in granting the request from process P2 for one more
tape drive. If we had made P2 wait until either of the other processes
had finished and released its resources, then we could have avoided the
deadlock.

<p2(1+2=3), p1>
 Banker’s Algorithm in Operating System

The banker’s algorithm is a resource allocation and deadlock

avoidance algorithm that tests for safety by simulating the
allocation for predetermined maximum possible amounts of
all resources, then makes an “s-state” check to test for
possible activities, before deciding whether allocation should
be allowed to continue.
Following Data structures are used to implement the Banker’s
Algorithm:
Let ‘n’ be the number of processes in the system and ‘m’ be
the number of resources types. n=5(p0, p1,p2,p3,p4) i=0,1…4
m=3(printer, tape drive, file) j=2, j=5, j=8
Available :
It is a 1-d array of size ‘m’ indicating the number of available
resources of each type.
Available[ j ] = k means there are ‘k’ instances of resource
type Rj Available[2]=2
Max :
It is a 2-d array of size ‘n*m’ that defines the maximum
demand of each process in a system.
Max[ i, j ] = k means process Pi may request at
most ‘k’ instances of resource type Rj.
Max[p0,2]=2
Allocation :
It is a 2-d array of size ‘n*m’ that defines the number of
resources of each type currently allocated to each process.
Allocation[ i, j ] = k means process Pi is currently
allocated ‘k’ instances of resource type Rj
Allocation[p0,2]=1
Need :
It is a 2-d array of size ‘n*m’ that indicates the remaining
resource need of each process.
Need [ i, j ] = k means process Pi currently need ‘k’ instances of
resource type Rj
for its execution.
Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]
1 =2 the- resources
Allocationi specifies 1 currently allocated to process Pi and
Needi specifies the additional resources that process Pi may still request to
complete its task.
Banker’s algorithm consists of Safety algorithm and Resource
request algorithm

Resource-Request Algorithm
Let Requesti be the request array for process Pi. Requesti [j] =
k means process Pi wants k instances of resource type Rj.
When a request for resources is made by process Pi, the
following actions are taken:
 R0<=N0 3<5

R0<=A 3<=4

p Max Current Need Request Available

i Needs Allocation
p 15 10 5 3 4
0
10+3=13 5-3=2 4-3=1
 Safety Algorithm
The algorithm for finding out whether or not a system is in a
safe state can be described as follows:
Example:
Considering a system with five processes P0 through P4 and
three resources of type A, B, C. Resource type A has 10
instances, B has 5 instances and type C has 7 instances.
Suppose at time t0 following snapshot of the system has been
taken:
Question1. What will be the content of the Need matrix?
Need [i, j] = Max [i, j] – Allocation [i, j]
So, the content of Need Matrix is:
Question2. Is the system in a safe state? If Yes, then what is
the safe sequence?
Applying the Safety algorithm on the given system,