Process Management | Deadlock Introduction

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.
Consider an example when two trains are coming toward each other on same track and there is only one track, none of the
trains can move once they are in front of each other. Similar situation occurs in operating systems when there are two or
more processes hold some resources and wait for resources held by other(s). 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.

Deadlock can arise if following four conditions hold simultaneously (Necessary Conditions)
Mutual Exclusion: One or more than one resource are non-sharable (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.
Circular Wait: A set of processes are waiting for each other in circular form.

Methods for handling deadlock

There are three ways to handle deadlock
1) Deadlock prevention or avoidance: The idea is to not let the system into deadlock state.
2) Deadlock detection and recovery: Let deadlock occur, then do preemption to handle it once occurred.
3) Ignore the problem all together: If deadlock is very rare, then let it happen and reboot the system. This is the approach
that both Windows and UNIX take.

Deadlock Detection And Recovery

In the previous post, we have discussed Deadlock Prevention and Avoidance. In this post, Deadlock Detection and
Recovery technique to handle deadlock is discussed.
Deadlock Detection

1
1. If resources have single instance:
In this case for Deadlock detection we can run an algorithm to check for cycle in the Resource Allocation Graph. Presence
of cycle in the graph is the sufficient condition for deadlock.

In the above diagram, resource 1 and resource 2 have single instances. There is a cycle R1–>P1–>R2–>P2. So Deadlock is
Confirmed.
2. If there are multiple instances of resources:
Detection of cycle is necessary but not sufficient condition for deadlock detection, in this case system may or may not be in
deadlock varies according to different situations.
Deadlock Recovery
Traditional operating system such as Windows doesn’t deal with deadlock recovery as it is time and space consuming
process. Real time operating systems use Deadlock recovery.
Recovery method
1. Killing the process.
killing all the process involved in deadlock.

Killing process one by one. After killing each

process check for deadlock again keep repeating
process till system recover from deadlock.
2. Resource Preemption
Resources are preempted from the processes involved in deadlock, preempted resources are allocated to other processes,
so that their is a possibility of recovering the system from deadlock. In this case system go into starvation.

2
Deadlock, Starvation, and Livelock
Livelock occurs when two or more processes continually repeat the same interaction in response to changes in the other
processes without doing any useful work. These processes are not in the waiting state, and they are running concurrently.
This is different from a deadlock because in a deadlock all processes are in the waiting state.

Example:
Imagine a pair of processes using two resources, as shown:
filter_none
brightness_4
void process_A(void)
{
enter_reg(& resource_1);
enter_reg(& resource_2);
use_both_resources();
leave_reg(& resource_2);
leave_reg(& resource_1);
}
void process_B(void)
{
enter_reg(& resource_1);
enter_reg(& resource_2);
use_both_resources();
leave_reg(& resource_2);
leave_reg(& resource_1);
}
Each of the two processes needs the two resources and they use the polling primitive enter_reg to try to acquire the locks
necessary for them. In case the attempt fails, the process just tries again.
If process A runs first and acquires resource 1 and then process B runs and acquires resource 2, no matter which one runs
next, it will make no further progress, but neither of the two processes blocks. What actually happens is that it uses up its
CPU quantum over and over again without any progress being made but also without any sort of blocking. Thus this
situation is not that of a deadlock( as no process is being blocked) but we have something functionally equivalent to
deadlock: LIVELOCK.
What leads to Livelocks?
Occurrence of livelocks can occur in the most surprising of ways. The total number of allowed processes in some systems,

3
is determined by the number of entries in the process table. Thus process table slots can be referred to as Finite Resources.
If a fork fails because of the table being full, waiting a random time and trying again would be a reasonable approach for the
program doing the fork.
Consider a UNIX system having 100 process slots. Ten programs are running, each of which having to create 12
(sub)processes. After each process has created 9 processes, the 10 original processes and the 90 new processes have
exhausted the table. Each of the 10 original processes now sits in an endless loop forking and failing – which is aptly the
situation of a deadlock. The probability of this happening is very little but it could happen.
Difference between Deadlock, Starvation, and Livelock:
A livelock is similar to a deadlock, except that the states of the processes involved in the livelock constantly change with
regard to one another, none progressing. Livelock is a special case of resource starvation; the general definition only states
that a specific process is not progressing.
Livelock:
var l1 = .... // lock object like semaphore or mutex etc
var l2 = .... // lock object like semaphore or mutex etc

// Thread1
Thread.Start( ()=> {

while (true) {

if (!l1.Lock(1000)) {
continue;
}

if (!l2.Lock(1000)) {
continue;
}

/// do some work

});

// Thread2
Thread.Start( ()=> {

while (true) {

if (!l2.Lock(1000)) {
continue;
}

if (!l1.Lock(1000)) {
continue;
}

// do some work
});
Deadlock:
var p = new object();
lock(p)
{
lock(p)
{
// deadlock. Since p is previously locked
// we will never reach here...
}

4
A deadlock is a state in which each member of a group of actions, is waiting for some other member to release a lock.
A livelock on the other hand is almost similar to a deadlock, except that the states of the processes involved in a livelock
constantly keep on changing with regard to one another, none progressing. Thus Livelock is a special case of resource
starvation, as stated from the general definition, the process is not progressing.
Starvation:
Starvation is a problem which is closely related to both, Livelock and Deadlock. In a dynamic system, requests for resources
keep on happening. Thereby, some policy is needed to make a decision about who gets the resource when. This process,
being reasonable, may lead to a some processes never getting serviced even though they are not deadlocked.
Queue q = .....

while (q.Count & gt; 0)

{
var c = q.Dequeue();
.........

// Some method in different thread accidentally

// puts c back in queue twice within same time frame
q.Enqueue(c);
q.Enqueue(c);

// leading to growth of queue twice then it

// can consume, thus starving of computing
}
Starvation happens when “greedy” threads make shared resources unavailable for long periods. For instance, suppose an
object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently,
other threads that also need frequent synchronized access to the same object will often be blocked.
Deadlock Prevention And Avoidance
Deadlock Characteristics
Deadlock has following characteristics.
Mutual Exclusion.
Hold and Wait.
No preemption.
Circular wait.

Deadlock Prevention
We can prevent Deadlock by eliminating any of the above four condition.
Eliminate Mutual Exclusion
It is not possible to dis-satisfy the mutual exclusion because some resources, such as the tap drive and printer, are
inherently non-shareable.

Eliminate Hold and wait

1. Allocate all required resources to the process before 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 remained blocked till it has completed its execution.
2. Process will make new request for resources after releasing the current set of resources. This solution may lead to
starvation.

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

Eliminate Circular Wait

Each resource will be assigned with a numerical number. A process can request for the resources only in increasing 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 check for safe state, if after granting request system remains in the safe state it allows the request and if
their is no safe state it don’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.
Request will only be granted under below condition.
1. If request made by process is less than equal to max need to that process.
2. If request made by process is less than equal to freely availbale resource in the system.
Example
Total resources in system:
A B C D
6 5 7 6
Available system resources are:
A B C D
3 1 1 2
Processes (currently allocated resources):
A B C D
P1 1 2 2 1
P2 1 0 3 3
P3 1 2 1 0
Processes (maximum resources):
A B C D
P1 3 3 2 2
P2 1 2 3 4

6
P3 1 3 5 0
Need = maximum resources - currently allocated resources.
Processes (need resources):
A B C D
P1 2 1 0 1
P2 0 2 0 1
P3 0 1 4 0

Banker’s Algorithm
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.
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
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.
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
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 ]

 Allocationi specifies the resources currently allocated to process P i and Needi specifies the additional resources
that process Pi may still request to complete its task.
 Banker’s algorithm consist of Safety algorithm and Resource request algorithm
 Safety Algorithm
 The algorithm for finding out whether or not a system is in a safe state can be described as follows:

 1) Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n

 2) Find an i such that both

a) Finish[i] = false
b) Needi <= Work
if no such i exists goto step (4)
 3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)

 4) if Finish [i] = true for all i

then the system is in a safe state
 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:
 1) If Requesti <= Needi
Goto step (2) ; otherwise, raise an error condition, since the process has exceeded its maximum claim.
 2) If Requesti <= Available
Goto step (3); otherwise, Pi must wait, since the resources are not available.
 3) Have the system pretend to have allocated the requested resources to process Pi by modifying the state as
follows:

7
Available = Available – Requesti
Allocationi = Allocationi + Requesti
Needi = Needi– Requesti
 Example:
 Considering a system with five processes P0 through P4 and three resources types 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 safe state? If Yes, then what is the safe sequence?
 Applying the Safety algorithm on the given system,

8

 Question3. What will happen if process P1 requests one additional instance of resource type A and two
instances of resource type C?


 We must determine whether this new system state is safe. To do so, we again execute Safety algorithm on the
above data structures.

9

Hence the new system state is safe, so we can immediately grant the request for process P1 .

Resource Allocation Graph (RAG)

As Banker’s algorithm using some kind of table like allocation, request, available all that thing to understand what is the state
of the system. Similarly, if you want to understand the state of the system instead of using those table, actually tables are
very easy to represent and understand it, but then still you could even represent the same information in the graph. That
graph is called Resource Allocation Graph (RAG).
So, resource allocation graph is explained to us what is the state of the system in terms of processes and resources. Like
how many resources are available, how many are allocated and what is the request of each process. Everything can be
represented in terms of the diagram. One of the advantages of having a diagram is, sometimes it is possible to see a
deadlock directly by using RAG, but then you might not be able to know that by looking at the table. But the tables are better
if the system contains lots of process and resource and Graph is better if the system contains less number of process and
resource.
We know that any graph contains vertices and edges. So RAG also contains vertices and edges. In RAG vertices are two
type –
1. Process vertex – Every process will be represented as a process vertex.Generally, the process will be represented with
a circle.
2. Resource vertex – Every resource will be represented as a resource vertex. It is also two type –
 Single instance type resource – It represents as a box, inside the box, there will be one dot.So the number of dots
indicate how many instances are present of each resource type.
 Multi-resource instance type resource – It also represents as a box, inside the box, there will be many dots present.

10
Now coming to the edges of RAG.There are two types of edges in RAG –
1.Assign Edge – If you already assign a resource to a process then it is called Assign edge.
2. Request Edge – It means in future the process might want some resource to complete the execution, that is called
request edge.

So, if a process is using a resource, an arrow is drawn from the resource node to the process node. If a process is
requesting a resource, an arrow is drawn from the process node to the resource node.
Example 1 (Single instances RAG) –

11
If there is a cycle in the Resource Allocation Graph and each resource in the cycle provides only one instance, then the
processes will be in deadlock. For example, if process P1 holds resource R1, process P2 holds resource R2 and process P1
is waiting for R2 and process P2 is waiting for R1, then process P1 and process P2 will be in deadlock.

Here’s another example, that shows Processes P1 and P2 acquiring resources R1 and R2 while process P3 is waiting to
acquire both resources. In this example, there is no deadlock because there is no circular dependency.
So cycle in single-instance resource type is the sufficient condition for deadlock.

12
Example 2 (Multi-instances RAG) –

From the above example, it is not possible to say the RAG is in a safe state or in an unsafe state.So to see the state of this
RAG, let’s construct the allocation matrix and request matrix.

 The total number of processes are three; P1, P2 & P3 and the total number of resources are two; R1 & R2.
Allocation matrix –
 For constructing the allocation matrix, just go to the resources and see to which process it is allocated.
 R1 is allocated to P1, therefore write 1 in allocation matrix and similarly, R2 is allocated to P2 as well as P3 and for the
remaining element just write 0.

13
Request matrix –
 In order to find out the request matrix, you have to go to the process and see the outgoing edges.
 P1 is requesting resource R2, so write 1 in the matrix and similarly, P2 requesting R1 and for the remaining element
write 0.
So now available resource is = (0, 0).
Checking deadlock (safe or not) –

So, there is no deadlock in this RAG.Even though there is a cycle, still there is no deadlock.Therefore in multi-instance
resource cycle is not sufficient condition for deadlock.
Therefore, every cycle in a multi-instance resource type graph is not a deadlock, if there has to be a deadlock, there has to
be a cycle.So, in case of RAG with multi-instance resource type, the cycle is a necessary condition for deadlock, but not
sufficient.
An example resource table may look like:

14
Above example is the same as the previous example except that, the process P3 requesting for resource R1.
So the table becomes as shown in below.

15
So,the Available resource is = (0, 0), but requirement are (0, 1), (1, 0) and (1, 0).So you can’t fulfill any one
requirement.Therefore, it is in deadlock.

Methods of resource allocation to processes by operating system

The Operating System allocates resources when a program need them. When the program terminates, the resources are
de-allocated, and allocated to other programs that need them. Now the question is, what strategy does the operating system
use to allocate these resources to user programs?
There are two Resource allocation techniques:
1. Resource partitioning approach –
In this approach, the operating system decides beforehand, that what resources should be allocated to which user
program. It divides the resources in the system to many resource partitions, where each partition may include various
resources – for example, 1 MB memory, disk blocks, and a printer.
Then, it allocates one resource partition to each user program before the program’s initiation. A resource table records the
resource partition and its current allocation status (Allocated or Free).
Advantages:
 Easy to Implement
 Less Overhead
Disadvantages:

16
 Lacks flexibility – if a resource partition contains more resources than what a particular process requires, the
additional resources are wasted.
 If a program needs more resources than a single resource partition, it cannot execute (Though free resources are
present in other partitions).
An example resource table may look like:

Pool based approach –

In this approach, there is a common pool of resources. The operating System checks the allocation status in the resource
table whenever a program makes a request for a resource. If the resource is free, it allocates the resource to the program.
Advantages:
 Allocated resources are not wasted.
 Any resource requirement can be fulfilled if the resource is free (unlike Partitioning approach)
Disadvantages:
 Overhead of allocating and de-allocating the resources on every request and release.

Operating System | Banker’s Algorithm : Print all the safe state (or safe
sequences)
Prerequisite – Resource Allocation Graph (RAG), Banker’s Algorithm, Program for Banker’s Algorithm
Banker’s Algorithm is a resource allocation and deadlock avoidance algorithm. This algorithm test for safety 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.
In simple terms, it checks if allocation of any resource will lead to deadlock or not, OR is it safe to allocate a resource to a
process and if not then resource is not allocated to that process. Determining a safe sequence(even if there is only 1) will
assure that system will not go into deadlock.
Banker’s algorithm is generally used to find if a safe sequence exist or not. But here we will determine the total number of
safe sequences and print all safe sequences.
The data structure used are:

 Available vector
 Max Matrix
 Allocation Matrix
 Need Matrix
Example:

17
Explanation –
Total resources are R1 = 10, R2 = 5, R3 = 7 and allocated resources are R1 = (0+2+3+2 =) 7, R2 = (1+0+0+1 =) 2, R3 =
(0+0+2+1 =) 3. Therefore, remaining resources are R1 = (10 – 7 =) 3, R2 = (5 – 2 =) 3, R3 = (7 – 3 =) 4.
Remaining available = Total resources – allocated resources
and
Remaining need = max – allocated

So, we can start from either P2 or P4. We can not satisfy remaining need from available resources of either P1 or P3 in first
or second attempt step of Banker’s algorithm. There are only four possible safe sequences. These are :
P2–> P4–> P1–> P3
P2–> P4–> P3–> P1
P4–> P2–> P1–> P3
P4–> P2–> P3–> P1

18
Deadlock detection algorithm
If a system does not employ either a deadlock prevention or deadlock avoidance algorithm then a deadlock situation may
occur. In this case-
 Apply an algorithm to examine state of system to determine whether deadlock has has occurred or not.
 Apply an algorithm to recover from the deadlock. For more refer- Deadlock Recovery
Deadlock Detection Algorithm:
The algorithm employs several time varying data structures:
 Available- A vector of length m indicates the number of available resources of each type.
 Allocation- An n*m matrix defines the number of resources of each type currently allocated to a process. Column
represents resource and resource represent process.
 Request- An n*m matrix indicates the current request of each process. If request[i][j] equals k then process P i is
requesting k more instances of resource type Rj.
We treat rows in the matrices Allocation and Request as vectors, we refer them as Allocationi and Requesti.
Steps of Algorithm:
1. Let Work and Finish be vectors of length m and n respectively. Initialize Work= Available. For i=0, 1, …., n-1,
if Allocationi = 0, then Finish[i] = true; otherwise, Finish[i]= false.
2. Find an index i such that both
a) Finish[i] == false
b) Requesti <= Work
If no such i exists go to step 4.
3. Work= Work+ Allocationi
Finish[i]= true
Go to Step 2.
4. If Finish[i]== false for some i, 0<=i<n, then the system is in a deadlocked state. Moreover, if Finish[i]==false the process
Pi is deadlocked.
For example,

1. In this, Work = [0, 0, 0] &

Finish = [false, false, false, false, false]
2. i=0 is selected as both Finish[0] = false and [0, 0, 0]<=[0, 0, 0].
3. Work =[0, 0, 0]+[0, 1, 0] =>[0, 1, 0] &
Finish = [true, false, false, false, false].
4. i=2 is selected as both Finish[2] = false and [0, 0, 0]<=[0, 1, 0].
5. Work =[0, 1, 0]+[3, 0, 3] =>[3, 1, 3] &
Finish = [true, false, true, false, false].
6. i=1 is selected as both Finish[1] = false and [2, 0, 2]<=[3, 1, 3].
7. Work =[3, 1, 3]+[2, 0, 0] =>[5, 1, 3] &
Finish = [true, true, true, false, false].
8. i=3 is selected as both Finish[3] = false and [1, 0, 0]<=[5, 1, 3].
9. Work =[5, 1, 3]+[2, 1, 1] =>[7, 2, 4] &
Finish = [true, true, true, true, false].
10. i=4 is selected as both Finish[4] = false and [0, 0, 2]<=[7, 2, 4].
11. Work =[7, 2, 4]+[0, 0, 2] =>[7, 2, 6] &
Finish = [true, true, true, true, true].
12. Since Finish is a vector of all true it means there is no deadlock in this example.

19