Unit – 5

Principles of Deadlock:

 A Deadlock is a situation where each of the computer process waits for a

resource which is being assigned to some another process. In this
situation, none of the process gets executed since the resource it needs,
is held by some other process which is also waiting for some other
resource to be released.
 Let us assume that there are three processes P1, P2 and P3. There are
three different resources R1, R2 and R3. R1 is assigned to P1, R2 is
assigned to P2 and R3 is assigned to P3.
 After some time, P1 demands for R1 which is being used by P2. P1 halts
its execution since it can't complete without R2. P2 also demands for R3
which is being used by P3. P2 also stops its execution because it can't
continue without R3. P3 also demands for R1 which is being used by P1
therefore P3 also stops its execution.

 In this scenario, a cycle is being formed among the three processes. None
of the process is progressing and they are all waiting. The computer
becomes unresponsive since all the processes got blocked.
Difference between Starvation and Deadlock:

Sr. Deadlock Starvation

1 All processes keep waiting for each other High priority processes keep executing
to complete and none get executed and low priority processes are blocked

2 Resources are blocked by the processes Resources are continuously utilized by

high priority processes

3 Also known as Circular wait Also know as lived lock

4 Necessary conditions Mutual Exclusion, Priorities are assigned to the processes
Hold and Wait, No preemption, Circular
Wait

5 It can be prevented by avoiding the It can be prevented by Aging.

necessary conditions for deadlock.

Starvation:

 Starvation is the problem that occurs when high priority processes keep
executing and low priority processes get blocked for indefinite time. In
heavily loaded computer system, a steady stream of higher-priority
processes can prevent a low-priority process from ever getting the
CPU. In starvation resources are continuously utilized by high priority
processes. Problem of starvation can be resolved using Aging. In Aging
priority of long waiting processes is gradually increased.

Deadlock Prevention:

 The possibility of deadlock is excluded before making requests, by

eliminating one of the necessary conditions for deadlock. Example:
Only allowing traffic from one direction, will exclude the possibility of
blocking the road.
Type of deadlock.

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

 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:

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.

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 is the mostly used by several types of operating

systems, but it is used mainly for end users. This concept is more comfortable
for single user system because they use their system for simply browsing as
well as other simple activities.

Deadlock avoidance technique (method) helps to avoid deadlock to

occur in the system. So, Wait for Graph technique is used for deadlock
avoidance.

 How does Deadlock Avoidance work?

In this method, the request for any resource will be granted only if the
resulting state of the system doesn't cause any deadlock in the system. This
method checks every step performed by the operating system. Any process
continues its execution until the system is in a safe state. Once the system
enters into an unsafe state, the operating system has to take a step back.

With the help of a deadlock-avoidance algorithm, you can dynamically assess

the resource-allocation state so that there can never be a circular-wait
situation.

According to the simplest and useful approach, any process should declare the
maximum number of resources of each type it will need. The algorithms of
deadlock avoidance mainly examine the resource allocations so that there can
never be an occurrence of circular wait conditions.

Deadlock avoidance can mainly be done with the help of Banker's Algorithm.

 Safe State and Unsafe State:

A state is safe if the system can allocate resources to each process( up to its
maximum requirement) in some order and still avoid a deadlock. Formally, a
system is in a safe state only, if there exists a safe sequence. So a safe state is
not a deadlocked state and conversely a deadlocked state is an unsafe state.

In an Unsafe state, the operating system cannot prevent processes from

requesting resources in such a way that any deadlock occurs. It is not
necessary that all unsafe states are deadlocks; an unsafe state may lead to a
deadlock.
Deadlock Detection:

In this approach, The OS doesn't apply any mechanism to avoid or prevent the
deadlocks. Therefore the system considers that the deadlock will definitely
occur. In order to get rid of deadlocks, The OS periodically checks the system for
any deadlock. In case, it finds any of the deadlock then the OS will recover the
system using some recovery techniques.

The main task of the OS is detecting the deadlocks. The OS can detect the
deadlocks with the help of Resource allocation graph.
In single instanced resource types, if a cycle is being formed in the system then
there will definitely be a deadlock. On the other hand, in multiple instanced
resource type graph, detecting a cycle is not just enough. We have to apply the
safety algorithm on the system by converting the resource allocation graph
into the allocation matrix and request matrix.

Deadlock Recovery:

For Resource

 Preempt the resource:

We can snatch one of the resources from the owner of the resource
(process) and give it to the other process with the expectation that it will
complete the execution and will release this resource sooner. Well,
choosing a resource which will be snatched is going to be a bit difficult.

 Rollback to a safe state:

System passes through various states to get into the deadlock state.
The operating system can rollback the system to the previous safe state.
For this purpose, OS needs to implement check pointing at every state.

The moment, we get into deadlock, we will rollback all the

allocations to get into the previous safe state.
For Process

 Kill a process:
Killing a process can solve our problem but the bigger concern is to
decide which process to kill. Generally, Operating system kills a process
which has done least amount of work until now.

 Kill all process:

This is not a suggestible approach but can be implemented if the
problem becomes very serious. Killing all process will lead to inefficiency
in the system because all the processes will execute again from starting.