[Link] | [Link] | [Link]

me/jntuh

UNIT – III CS403PC: OPERATING SYSTEMS

UNIT - III
DEADLOCK
A process in operating system uses resources in the following way.
(i) Requests a resource
(ii) Use the resource
(iii) Releases the resource
A 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 the
same track and there is only one track, none of the trains can move once they are
in front of each other.
A similar situation occurs in operating
systems when there are two or more processes that
hold some resources and wait for resources held
by other(s). For example, in the below diagram,
Process1 is holding Resource1 and waiting for
Rsource2 which is acquired by Process2, and
Process2 is waiting for Resource1.

Examples of Deadlock
1. The system has 2 tape drives. P1 and P2 each hold one tape drive and each
needs another one.
2. Semaphores A and B, initialized to 1, P0, and P1 are
P0 P1
in deadlock as follows:
P0 executes wait(A) and preempts.
wait(A); wait(B)
P1 executes wait(B).
Now P0 and P1 enter in deadlock.
wait(B); wait(A)

3. Assume the space is available for allocation of 200K bytes, and the
following sequence of events occurs.
P0 P1

Request Request
80KB; 70KB;

Request Request
60KB; 80KB;

C. Dinesh, AP/CSE-AIML, MRCE Page 1

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

NECESSARY CONDITIONS FOR DEADLOCK

 Mutual Exclusion
Two or more resources 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 Pre-emption
A resource cannot be taken from a process unless the process
releases the resource.
 Circular Wait
A set of processes waiting for each other in circular form.

Resource Allocation Graph

The resource allocation graph is the pictorial representation of the state of a
system. As its name suggests, the resource allocation graph is the complete
information about all the processes which are holding some resources or waiting
for some resources.
It also contains the information about all the instances of all the resources
whether they are available or being used by the processes.
In Resource allocation graph, the process is represented by a Circle while
the Resource is represented by a rectangle.
Vertices are mainly of two types, Resource and Process. Each of them will
be represented by a different shape. Circle represents process while rectangle
represents resource. A resource can have more than one instance. Each instance
will be represented by a dot inside the rectangle.
Edges in RAG are also of two types,
one represents Assignment Edge and other
represents the wait of a process for a
resource [Link] Edge.
A resource is shown as assigned to a
process if the tail of the arrow is attached to
an instance to the resource and the head is
attached to a process.
A process is shown as waiting for a resource if the tail of an arrow is
attached to the process while the head is pointing towards the resource.

C. Dinesh, AP/CSE-AIML, MRCE Page 2

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Example
Consider 3 processes P1, P2 and P3 and two
types of resources R1 and R2. The resources are
having 1 instance each.
According to the graph, R1 is being used by
P1, P2 is holding R2 and waiting for R1, P3 is
waiting for R1 as well as R2.
The graph is deadlock free since no cycle is
being formed in the graph.

Using Resource Allocation Graph, it can be easily detected whether system

is in a Deadlock state or not. The rules are

Rule-01: In a Resource Allocation Graph where all the resources are single
instance,
 If a cycle is being formed, then system is in a deadlock state.
 If no cycle is being formed, then system is not in a deadlock state.

Rule-02: In a Resource Allocation Graph where all the resources are NOT single
instance,
 If a cycle is being formed, then system may be in a deadlock state.
 Banker’s Algorithm is applied to confirm whether system is in a deadlock
state or not.
 If no cycle is being formed, then system is not in a deadlock state.
 Presence of a cycle is a necessary but not a sufficient condition for the
occurrence of deadlock.

C. Dinesh, AP/CSE-AIML, MRCE Page 3

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

METHODS FOR HANDLING DEADLOCK

There are three ways to handle deadlock
1) Deadlock prevention or avoidance
PREVENTION
The idea is to not let the system into a deadlock state. This system will
make sure that above mentioned four conditions will not arise. These techniques
are very costly so we use this in cases where our priority is making a system
deadlock-free.
One can zoom into each category individually, Prevention is done by
negating one of the four necessary conditions for deadlock.

Eliminate 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.

Solve 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 a printer at a later time and we have
allocated a 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.

Allow pre-emption
Preempt resources from the process when resources are required by other
high-priority processes.

Circular wait Solution

Each resource will be assigned a numerical number. A process can request
the resources to increase/decrease. order of numbering. For Example, if the P1
process is allocated R5 resources, now next time if P1 asks for R4, R3 lesser than
R5 such a request will not be granted, only a request for resources more than R5
will be granted.

AVOIDANCE
Avoidance is kind of futuristic. By using the strategy of “Avoidance”, we
have to make an assumption. We need to ensure that all information about
resources that the process will need is known to us before the execution of the
process.

C. Dinesh, AP/CSE-AIML, MRCE Page 4

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Resource Allocation Graph

The resource allocation graph (RAG) is used to visualize the system‟s
current state as a graph. The Graph includes all processes, the resources that are
assigned to them, as well as the resources that each Process requests. Sometimes,
if there are fewer processes, we can quickly spot a deadlock in the system by
looking at the graph rather than the tables we use in Banker‟s algorithm.
Banker’s Algorithm
Bankers‟s Algorithm is a resource allocation and deadlock avoidance
algorithm which test all the request made by processes for resources, it checks
for the safe state, and after granting a request system remains in the safe state it
allows the request, and if there is no safe state it doesn‟t allow the request made
by the process.

In prevention and avoidance, we get the correctness of data but

performance decreases.

2) Deadlock detection and recovery

If Deadlock prevention or avoidance is not applied to the software then we
can handle this by deadlock detection and recovery, which consist of two phases.
In the first phase, we examine the state of the process and check whether
there is a deadlock or not in the system.
If found deadlock in the first phase then we apply the algorithm for
recovery of the deadlock.

3) Deadlock ignorance:
If a deadlock is very rare, then let it happen and reboot the system. This is
the approach that both Windows and UNIX take. We use the ostrich algorithm
for deadlock ignorance.
In Deadlock, ignorance performance is better than the above two methods
but not the correctness of data.

SAFE STATE
A safe state can be defined as a state in which there is no deadlock. It is
achievable if:
 If a process needs an unavailable resource, it may wait until the same has
been released by a process to which it has already been allocated. if such a
sequence does not exist, it is an unsafe state.
 All the requested resources are allocated to the process.

C. Dinesh, AP/CSE-AIML, MRCE Page 5

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

BANKER'S ALGORITHM
It is a banker algorithm used to avoid deadlock and allocate
resources safely to each process in the computer system. The 'S-State' examines
all possible tests or activities before deciding whether the allocation should be
allowed to each process. It also helps the operating system to successfully share
the resources between all the processes.
The banker's algorithm is named because it checks whether a person should
be sanctioned a loan amount or not to help the bank system safely simulate
allocation resources.
Suppose the number of account holders in a particular bank is 'n', and the
total money in a bank is 'T'. If an account holder applies for a loan; first, the bank
subtracts the loan amount from full cash and then estimates the cash difference is
greater than T to approve the loan amount. These steps are taken because if
another person applies for a loan or withdraws some amount from the bank, it
helps the bank manage and operate all things without any restriction in the
functionality of the banking system.
Similarly, it works in an operating system. When a new process is created
in a computer system, the process must provide all types of information to
the operating system like upcoming processes, requests for their resources,
counting them, and delays.
Based on these criteria, the operating system decides which process
sequence should be executed or waited so that no deadlock occurs in a system.
Therefore, it is also known as deadlock avoidance algorithm or deadlock
detection in the operating system.

When working with a banker's algorithm, it requests to know about three

things:
1. How much each process can request for each resource in the system. It is
denoted by the [MAX] request.
2. How much each process is currently holding each resource in a system. It is
denoted by the [ALLOCATED] resource.
3. It represents the number of each resource currently available in the system.
It is denoted by the [AVAILABLE] resource.

C. Dinesh, AP/CSE-AIML, MRCE Page 6

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Following are the important data structures terms applied in the banker's
algorithm as follows:
Suppose n is the number of processes, and m is the number of each type of
resource used in a computer system.
1. Available: It is an array of length 'm' that defines each type of resource
available in the system. When Available[j] = K, means that 'K' instances of
Resources type R[j] are available in the system.
2. Max: It is a [n x m] matrix that indicates each process P[i] can store the
maximum number of resources R[j] (each type) in a system.
3. Allocation: It is a matrix of m x n orders that indicates the type of
resources currently allocated to each process in the system. When
Allocation [i, j] = K, it means that process P[i] is currently allocated K
instances of Resources type R[j] in the system.
4. Need: It is an M x N matrix sequence representing the number of
remaining resources for each process. When the Need[i] [j] = k, then
process P[i] may require K more instances of resources type Rj to complete
the assigned work.
Need[i][j] = Max[i][j] - Allocation[i][j].
5. Finish: It is the vector of the order m. It includes a Boolean value
(true/false) indicating whether the process has been allocated to the
requested resources, and all resources have been released after finishing its
task.

The Banker's Algorithm is the combination of the safety algorithm and the
resource request algorithm to control the processes and avoid deadlock.
Safety Algorithm
It is a safety algorithm used to check whether or not a system is in a safe
state or follows the safe sequence in a banker's algorithm:
Step1:
There are two vectors Wok and Finish of length m and n in a safety
algorithm.
Initialize: Work = Available
Finish[i] = false; for I = 0, 1, 2, 3, 4… n - 1.
Step2:
Check the availability status for each type of resources [i], such as:
Need[i] <= Work
Finish[i] == false
If the i does not exist, go to step 4.
C. Dinesh, AP/CSE-AIML, MRCE Page 7

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Step3:
Work = Work +Allocation(i) // to get new resource allocation
Finish[i] = true
Go to step2 to check the status of resource availability for the next process.
Step4:
If Finish[i] == true; it means that the system is safe for all processes.

Resource Request Algorithm

Let create a resource request array R[i] for each process P[i].
Step1:
When the number of requested resources of each type is less than
the Need resources, go to step2 and if the condition fails, which means that the
process P[i] exceeds its maximum claim for the resource. As the expression
suggests:
If Request(i) <= Need, then go to step2, Else raise an error message.
Step2:
And when the number of requested resources of each type is less than the
available resource for each process, go to step (3). As the expression suggests:
If Request(i) <= Available, then go to step3.
Else Process P[i] must wait for the resource.
Step3:
When the requested resource is allocated to the process by changing state:
Available = Available – Request
Allocation(i) = Allocation(i) + Request (i)
Needi = Needi - Requesti

When the resource allocation state is safe, its resources are allocated to the
process P(i). And if the new state is unsafe, the Process P (i) has to wait for each
type of Request R(i) and restore the old resource-allocation state.

C. Dinesh, AP/CSE-AIML, MRCE Page 8

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Example:
Consider a system that contains five processes P1, P2, P3, P4, P5 and the
three resource types A, B and C. Following are the resources types: A has 10, B
has 5 and the resource type C has 7 instances.

Process Allocation Max Available

A B C A B C A B C

P1 0 1 0 7 5 3 3 3 2

P2 2 0 0 3 2 2

P3 3 0 2 9 0 2

P4 2 1 1 2 2 2

P5 0 0 2 4 3 3
Answer the following questions using the banker's algorithm:
1. What is the reference of the need matrix?
2. Determine if the system is safe or not.
3. What will happen if the resource request (1, 0, 2) for process P1 can the
system accept this request immediately?
4. What will happen if the resource request (3, 3, 0) for process P5?
5. What will happen if the resource request (0, 2, 0) for process P1?

Ans.1:
Context of the need matrix is as Need [i] = Max [i] - Allocation [i]
Need for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3
Need for P2: (3, 2, 2) - (2, 0, 0) = 1, 2, 2 Process Need
Need for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0 A B C
Need for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1
Need for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1 P1 7 4 3

P2 1 2 2

P3 6 0 0

P4 0 1 1

P5 4 3 1

C. Dinesh, AP/CSE-AIML, MRCE Page 9

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Ans.2: Apply the Banker's Algorithm:

Available Resources of A, B and C are 3, 3, and 2.
Now we check if each type of resource request is available for each
process.
Step 1:
For Process P1:
Need <= Available
7, 4, 3 <= 3, 3, 2 condition is false.
So, we examine another process, P2.
Step 2:
For Process P2:
Need <= Available
1, 2, 2 <= 3, 3, 2 condition true
New available = available + Allocation
(3, 3, 2) + (2, 0, 0) => 5, 3, 2
Similarly, we examine another process P3.
Step 3:
For Process P3:
P3 Need <= Available
6, 0, 0 < = 5, 3, 2 condition is false.
Similarly, we examine another process, P4.
Step 4:
For Process P4:
P4 Need <= Available
0, 1, 1 <= 5, 3, 2 condition is true
New Available resource = Available + Allocation
5, 3, 2 + 2, 1, 1 => 7, 4, 3
Similarly, we examine another process P5.
Step 5:
For Process P5:
P5 Need <= Available
4, 3, 1 <= 7, 4, 3 condition is true
New available resource = Available + Allocation
7, 4, 3 + 0, 0, 2 => 7, 4, 5
Now, we again examine each type of resource request for
processes P1 and P3.

C. Dinesh, AP/CSE-AIML, MRCE Page 10

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Step 6:
For Process P1:
P1 Need <= Available
7, 4, 3 <= 7, 4, 5 condition is true
New Available Resource = Available + Allocation
7, 4, 5 + 0, 1, 0 => 7, 5, 5
So, we examine another process P2.
Step 7:
For Process P3:
P3 Need <= Available
6, 0, 0 <= 7, 5, 5 condition is true
New Available Resource = Available + Allocation
7, 5, 5 + 3, 0, 2 => 10, 5, 7
Hence, we execute the banker's algorithm to find the safe state and the safe
sequence like P2, P4, P5, P1 and P3.

Ans. 3:
For granting the Request (1, 0, 2), first we have to check that
Request <= Available, that is (1, 0, 2) <= (3, 3, 2),
Since the condition is true, the process P2 may
get the request immediately.
Process Need
Allocation for P2 is (3,0,2) and new Available A B C
is (2, 3, 0)
Context of the need matrix is as follows: P1 7 4 3
Need [i] = Max [i] - Allocation [i]
Need for P1: (7, 5, 3) - (0, 1, 0) = 7, 4, 3 P2 0 2 0
Need for P2: (3, 2, 2) - (3, 0, 2) = 0, 2, 0 P3 6 0 0
Need for P3: (9, 0, 2) - (3, 0, 2) = 6, 0, 0
Need for P4: (2, 2, 2) - (2, 1, 1) = 0, 1, 1 P4 0 1 1
Need for P5: (4, 3, 3) - (0, 0, 2) = 4, 3, 1
P5 4 3 1

Apply the Banker's Algorithm:

Available Resources of A, B and C are 2, 3, and 0.
Now we check if each type of resource request is available for each
process.

C. Dinesh, AP/CSE-AIML, MRCE Page 11

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Step 1:
For Process P1:
Need <= Available
7, 4, 3 <= 2, 3, 0 condition is false.
So, we examine another process, P2.
Step 2:
For Process P2:
Need <= Available
1, 2, 2 <= 2, 3, 0 condition true
New available = available + Allocation
(2, 3, 0) + (3, 0, 2) => 5, 3, 2
Similarly, we examine another process P3.
Step 3:
For Process P3:
P3 Need <= Available
6, 0, 0 < = 5, 3, 2 condition is false.
Similarly, we examine another process, P4.
Step 4:
For Process P4:
P4 Need <= Available
0, 1, 1 <= 5, 3, 2 condition is true
New Available resource = Available + Allocation
5, 3, 2 + 2, 1, 1 => 7, 4, 3
Similarly, we examine another process P5.
Step 5:
For Process P5:
P5 Need <= Available
4, 3, 1 <= 7, 4, 3 condition is true
New available resource = Available + Allocation
7, 4, 3 + 0, 0, 2 => 7, 4, 5
Now, we again examine for processes P1 and P3.
Step 6:
For Process P1:
P1 Need <= Available
7, 4, 3 <= 7, 4, 5 condition is true
New Available Resource = Available + Allocation
7, 4, 5 + 0, 1, 0 => 7, 5, 5
So, we examine another process P2.
C. Dinesh, AP/CSE-AIML, MRCE Page 12

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

Step 7:
For Process P3:
P3 Need <= Available
6, 0, 0 <= 7, 5, 5 condition is true
New Available Resource = Available + Allocation
7, 5, 5 + 3, 0, 2 => 10, 5, 7
Hence, P2 granted immediately and the safe sequence like P2, P4, P5, P1
and P3.

Ans. 4:
For granting the Request (3, 3, 0) by P5, first we have to check that
Request <= Available, that is (3, 3, 0) <= (2, 3, 0),
Since the condition is false. So the request for (3, 3, 0) by process P5
cannot be granted.

Ans. 5:
For granting the Request (0, 2, 0) by P1, first we have to check that
Request <= Available, that is (0, 2, 0) <= (2, 3, 0),
Since the condition is true. So the request for (0, 2, 0) by process P1 may be
granted.
Allocation for P1 is (0, 3, 0) Process Need
Context of the need matrix is as follows: A B
Need [i] = Max [i] - Allocation [i] C
Need for P1: (7, 5, 3) - (0, 3, 0) = 7, 2, 3
P1 7 2 3

Apply the Banker's Algorithm: P2 0 2 0

Available Resources of A, B and C are 2, 1,
P3 6 0 0
and 0.
P4 0 1 1
For Process P1: 7, 2, 3<= 2, 1, 0 condition is false.
For Process P2: 0, 2, 0<= 2, 1, 0 condition is false. P5 4 3 1
For Process P3: 6, 0, 0<= 2, 1, 0 condition is false.
For Process P4: 0, 1, 1 <= 2, 1, 0 condition is false.
For Process P5: 4, 3, 1 <= 2, 1, 0 condition is false.

Hence, the state is unsafe, P1 cannot be granted immediately.

C. Dinesh, AP/CSE-AIML, MRCE Page 13

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

DEADLOCK DETECTION
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 the system‟s state to determine whether
deadlock has occurred.
 Apply an algorithm to recover from the deadlock.

A deadlock detection algorithm is a technique used by an operating system to

identify deadlocks in the system. This algorithm checks the status of processes and
resources to determine whether any deadlock has occurred and takes appropriate
actions to recover from the deadlock.
The algorithm employs several times 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. The column represents resource and rows
represent a process.
Request – An n*m matrix indicates the current request of each process. If
request[i][j] equals k then process Pi is requesting k more instances of resource
type Rj.

The Bankers algorithm includes a Safety Algorithm / Deadlock Detection

Algorithm. The algorithm for finding out whether a system is in a safe state can
be described as follows:
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 Requesti = 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.

C. Dinesh, AP/CSE-AIML, MRCE Page 14

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

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.

C. Dinesh, AP/CSE-AIML, MRCE Page 15

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

There are several algorithms for detecting deadlocks in an operating system,

including:

1. Wait-For Graph:
A graphical representation of the system‟s processes and resources. A directed
edge is created from a process to a resource if the process is waiting for that
resource. A cycle in the graph indicates a deadlock.

2. Banker’s Algorithm:
A resource allocation algorithm that ensures that the system is always in a safe
state, where deadlocks cannot occur.

3. Resource Allocation Graph:

A graphical representation of processes and resources, where a directed edge
from a process to a resource means that the process is currently holding that
resource. Deadlocks can be detected by looking for cycles in the graph.

4. Detection by System Modeling:

A mathematical model of the system is created, and deadlocks can be detected
by finding a state in the model where no process can continue to make progress.

5. Timestamping:
Each process is assigned a timestamp, and the system checks to see if any
process is waiting for a resource that is held by a process with a lower timestamp.

These algorithms are used in different operating systems and systems with
different resource allocation and synchronization requirements. The choice of
algorithm depends on the specific requirements of the system and the trade-offs
between performance, complexity and accuracy.

C. Dinesh, AP/CSE-AIML, MRCE Page 16

[Link] | [Link] | [Link]

 [Link] | [Link] | [Link]

UNIT – III CS403PC: OPERATING SYSTEMS

RECOVERY FROM DEADLOCK

The OS will use various recovery techniques to restore the system if it
encounters any deadlocks. When a Deadlock Detection Algorithm determines that
a deadlock has occurred in the system, the system must recover from that
deadlock.

Approaches to Breaking a Deadlock

(a) Process Termination

To eliminate the deadlock, we can simply kill one or more processes. For this,
we use two methods:
1. Abort all the Deadlocked Processes:
Aborting all the processes will certainly break the deadlock but at a great
expense. The deadlocked processes may have been computed for a long time,
and the result of those partial computations must be discarded and there is a
probability of recalculating them later.
2. Abort one process at a time until the deadlock is eliminated:
Abort one deadlocked process at a time, until the deadlock cycle is
eliminated from the system. Due to this method, there may be considerable
overhead, because, after aborting each process, we have to run a deadlock
detection algorithm to check whether any processes are still deadlocked.

(b) Resource Preemption

To eliminate deadlocks using resource preemption, we preempt some resources
from processes and give those resources to other processes. This method will raise
three issues –
1. Selecting a victim:
We must determine which resources and which processes are to be
preempted and also in order to minimize the cost.
2. Rollback:
We must determine what should be done with the process from which
resources are preempted. One simple idea is total rollback. That means
aborting the process and restarting it.
3. Starvation:
In a system, it may happen that the same process is always picked as a
victim. As a result, that process will never complete its designated task. This
situation is called Starvation and must be avoided. One solution is that a
process must be picked as a victim only a finite number of times.

C. Dinesh, AP/CSE-AIML, MRCE Page 17

[Link] | [Link] | [Link]