Module-3 Deadlocks.pptx BCS303 Operating system

Department of CSE- Data Science
Module-3
Deadlocks

Contents
 System model
 Deadlock characterization
 Methods for handling deadlocks
 Deadlock prevention
 Deadlock avoidance
 Deadlock detection and recovery from deadlock

Introduction
 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.

 Bridge Crossing Example
 Traffic only in one direction
 Each section of a bridge can be viewed as a resource
 If a deadlock occurs, it can be resolved if one car backs up (preempt resources and
rollback)

System Model
 System consists of Resource types R1, R2, . . ., Rm – CPU cycles, memory space, I/O
devices
 Each resource type Ri has Wi instances.
 Each process utilizes a resource as follows:
1. Request. The process requests the resource. If the request cannot be granted
immediately (for example, if the resource is being used by another process), then the
requesting process must wait until it can acquire the resource.
2. Use. The process can operate on the resource (for example, if the resource is a printer,
the process can print on the printer).
3. Release. The process releases the resource.

Deadlock Characterization
 Deadlock can arise if four conditions hold simultaneously
1. Mutual exclusion: only one process at a time can use a resource
2. Hold and wait: a process holding at least one resource is waiting to acquire
additional resources held by other processes
3. No preemption: a resource can be released only voluntarily by the process holding it,
after that process has completed its task
4. Circular wait: there exists a set {P0, P1, …, Pn} of waiting processes such that P0 is
waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2,
…, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource
that is held by P0.

Resource Allocation
 Graphical representation of the state of the system.
 It contains the information about all the instances of all the resources
 A set of vertices V and a set of edges E
 V is partitioned into two types:
– P = {P1, P2, …, Pn}, the set consisting of all the processes in the system
– R = {R1, R2, …, Rm}, the set consisting of all resource types in the system
 request edge – directed edge Pi  Rj
 assignment edge – directed edge Rj  Pi

Resource Allocation Graph Example
 One instance of R1
 Two instances of R2
 One instance of R3
 Three instance of R4
 P1 holds one instance of R2 and is waiting for
an instance of R1
 P2 holds one instance of R1, one instance of
R2, and is waiting for an instance of R3
 P3 is holds one instance of R3

Resource Allocation Graph with a Deadlock
 P1->R1->P2->R3->P3->R2->P1
 P2->R3->P3->R2->P2

Graph with a Cycle But no Deadlock
P1->R1->P3->R2->P1

Basic Facts
If graph contains no cycles -no deadlock
 If graph contains a cycle
– if only one instance per resource type, then deadlock
– if several instances per resource type, possibility of deadlock

Methods for Handling Deadlocks
 Ensure that the system will never enter a deadlock state
‣ To ensure that deadlocks never occur, the system can either use deadlock prevention or a
deadlock-avoidance scheme.
‣ Deadlock prevention provides a set of methods for ensuring that at least one of the
necessary conditions cannot hold.
• Deadlock-avoidance requires that the operating system be given in advance additional
information concerning which resources a process will request and use during its
lifetime. With this additional knowledge, it can decide for each request whether or not
the process should wait.
 Allow the system to enter a deadlock state and then recover
‣ The system can provide an algorithm that examines the state of the system to
determine whether a deadlock has occurred and an algorithm to recover from the
deadlock (if a deadlock has indeed occurred).
 Ignore the problem and pretend that deadlocks never occur in the system

Deadlock Prevention
 For a deadlock to occur, each of the four necessary conditions must hold.
 By ensuring that at least one of these conditions cannot hold, we can prevent the occurrence
of a deadlock.
1.Mutual Exclusion: not required for sharable resources; must hold for non sharable resources
 The mutual-exclusion condition must hold for non sharable resources.
 For example, a printer cannot be simultaneously shared by several processes.
 Sharable resources, in contrast, 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
 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.
 Example: 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.
 Two main disadvantages.
1. Resource utilization may be low, since resources may be allocated but unused for a long
period. In the example given, for instance, we can release the DVD drive and disk file, and
then again request the disk file and printer only if we can be sure that our data will remain
on the disk file. Otherwise, we must request all resources at the beginning for both protocols.
2. 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
 To ensure that this condition does not hold, we can use the following protocol.
‣ If a process that is holding some resources requests another resource that cannot be
immediately allocated to it, then all resources currently being held are released
‣ Preempted resources are added to the list of resources for which the process is waiting
‣ Process will be restarted only when it can regain its old resources, as well as the new
ones that it is requesting
4. Circular Wait
‣ 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.
‣ 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

‣ 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.
‣ Simply assign each resource (i.e., mutex locks) a unique number.
‣ Resources must be acquired in order.
If:
first_mutex = 1
second_mutex = 5

Deadlock Avoidance
 Requires that the system has some additional a priori information available
‣ Simplest and most useful model requires that each process declare the maximum
number of resources of each type that it may need
‣ The deadlock-avoidance algorithm dynamically examines the resource-allocation
state to ensure that there can never be a circular-wait condition
‣ Resource-allocation state is defined by the number of available and allocated
resources, and the maximum demands of the processes

Safe State
 When a process requests an available resource, system must decide if immediate
allocation leaves the system in a safe state.
 System is in safe state if there exists a safe sequence of all processes.
 Sequence <P1, P2, …, Pn> is safe if for each Pi, the resources that Pi can still request can
be satisfied by currently available resources + resources held by all the Pj, with j<i.
– If Pi resource needs are not immediately available, then Pi can wait until all Pj have
finished.
– When Pj is finished, Pi can obtain needed resources, execute, return allocated
resources, and terminate.
– When Pi terminates, Pi+1 can obtain its needed resources, and so on.

Basic Facts
 If a system is in safe state  no deadlocks
 If a system is in unsafe state  possibility of deadlock
 Avoidance  ensure that a system will never enter an unsafe state
Figure : Safe, unsafe, and deadlocked state spaces.

 To illustrate, we consider a system with twelve magnetic tape drives and three
processes: P0, P1, and P2.
 Process P0 requires ten tape drives, process P1 may need as many as four tape
drives, and process P2 may need up to nine tape drives.
 Suppose that, at time to, process P0 is holding five tape drives, process P1 is
holding two tape drives, and process P2 is holding two tape drives.
 Thus, there are three free tape drives.
Maximum Needs Current Needs
P0 10 5
P1 4 2
P2 9 2

 At time t0, the system is in a safe state. The sequence <P1, P0, P2> satisfies the safety
condition.
‣ Process P1 can immediately be allocated all its tape drives and then return them (the
system will then have five available tape drives);
‣ Then process P0 can get all its tape drives and return them (the system will then have
ten available tape drives)
‣ Finally process P2 can get all its tape drives and return them (the system will then
have all twelve tape drives available).
 A system can go from a safe state to an unsafe state.

Resource-Allocation Graph Algorithm
 Claim edge Pi  Rj indicated that process Pi may request resource Rj; represented
by a dashed line.
 Claim edge converts to request edge when a process requests a resource.
 When a resource is released by a process, assignment edge reconverts to a claim
edge.
 Resources must be claimed a priori in the system.

Resource-Allocation Graph For Deadlock Avoidance
Assignment
Edge
Request
Edge
Claim
Edge
Claim
Edge

Unsafe State In A Resource-Allocation Graph

Bankers Safety Algorithm
 The Banker's algorithm is a resource allocation and deadlock avoidance algorithm
developed by Edsger Dijkstra,
 Tests for safety by simulating the allocation of predetermined maximum possible amounts
of all resources, and then makes a "s-state" check to test for possible deadlock conditions
for all other pending activities, before deciding whether allocation should be allowed to
continue.
 The Banker's algorithm is run by the operating system whenever a process requests
resources
 The algorithm avoids deadlock by denying or postponing the request if it determines that
accepting the request could put the system in an unsafe state (one where deadlock could
occur).

 When a new process enters a system, it must declare the maximum number of instances
of each resource type that it may ever claim; clearly, that number may not exceed the
total number of resources in the system.
 Also, when a process gets all its requested resources it must return them in a finite
amount of time.
Data Structures for the Banker’s Algorithm
 Let n = number of processes, and m = number of resources types.
1. Available: Vector of length m. If available [j] = k, there are k instances of resource
type Rj available
2. Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k
instances of resource type Rj

3. Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k
instances of Rj
4. Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to
complete its task
Need [i,j] = Max[i,j] – Allocation [i,j]

Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively. Initialize:
Work = Available
Finish [i] = false for i = 0, 1, …, n- 1
2. Find an i such that both:
(a) Finish [i] = false
(b) Needi  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] == true for all i, then the system is in a safe state

Resource-Request Algorithm for Process Pi
Requesti = request vector for process Pi. If Requesti [j] = k then process Pi wants k
instances of resource type Rj.
1. If Requesti  Needi go to step 2. Otherwise, raise error condition, since process
has exceeded its maximum claim.
2. If Requesti  Available, go to step 3. Otherwise Pi must wait, since resources
are not available.
3. Pretend to allocate requested resources to Pi by modifying the state as follows:
Available := Available - Requesti;
Allocationi := Allocationi + Requesti;
Needi := Needi – Requesti;;
- If safe  the resources are allocated to Pi.
- If unsafe  Pi must wait, and the old resource-allocation state is restored

Example of Banker’s Algorithm
 5 processes P0 through P4; 3 resource types A (10 instances), B (5 instances), and C (7
instances).
 Snapshot at time T0:
Allocation Max Available
A B C A B C A B C
P0 0 1 0 7 5 3 3 3 2
P1 2 0 0 3 2 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2
P4 0 0 2 4 3 3

 The content of the matrix. Need is defined to be Max – Allocation.
Need
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1
 The system is in a safe state since the sequence < P1, P3, P4, P2, P0> satisfies safety
criteria.

 Check that Request  Available (that is, (1,0,2)  (3,3,2)  true.
Allocation Need Available
A B C A B C A B C
P0 0 1 0 7 4 3 2 3 0
P1 3 0 2 0 2 0
P2 3 0 1 6 0 0
P3 2 1 1 0 1 1
P4 0 0 2 4 3 1
 Executing safety algorithm shows that sequence <P1, P3, P4, P0, P2> satisfies safety
requirement.

Deadlock Detection
 If a system does not employ either a deadlock-prevention or a deadlock avoidance
algorithm, then a deadlock situation may occur.
 In this environment, the system may provide:
‣ An algorithm that examines the state of the system to determine whether a
deadlock has occurred
‣ An algorithm to recover from the deadlock

Single Instance of Each Resource Type
 If all resources have only a single instance, then we can define a deadlock detection
algorithm that uses a variant of the resource-allocation graph, called a wait-for graph.
 Resource Allocation Graph: Contains Processes and Resources.
 Wait-for-Graph: Contains only Processes after removing the Resources while conversion
from Resource Allocation Graph.
 If the Wait-for-Graph contains a cycle then we can say the system is in a Deadlock state
 To detect deadlocks, the system needs to maintain the wait-for graph and periodically
invoke an algorithm that searches for a cycle in the graph.
 An algorithm to detect a cycle in a graph requires an order of n2
operations, where n is the
number of vertices in the graph.

Deadlock Detection Steps
• Step 1: Take the first process (Pi) from the resource allocation graph and check the
path in which it is acquiring resource (Ri), and start a wait-for-graph with that
particular process.
• Step 2: Make a path for the Wait-for-Graph in which there will be no Resource
included from the current process (Pi) to next process (Pj), from that next process (Pj)
find a resource (Rj) that will be acquired by next Process (Pk) which is released from
Process (Pj).
• Step 3: Repeat Step 2 for all the processes.
• Step 4: After completion of all processes, if we find a closed-loop cycle then the
system is in a deadlock state, and deadlock is detected.

Step 1: First take Process P1 which is waiting for Resource R1, resource R1 is acquired by
Process P2, Start a Wait-for-Graph for the above Resource Allocation Graph.

Step 2: Now we can observe that there is a path from P1 to P2 as P1 is waiting for R1 which
is been acquired by P2. Now the Graph would be after removing resource R1 looks like.
Step 3: From P2 we can observe a path from P2 to P3 as P2 is waiting for R4 which is
acquired by P3. So make a path from P2 to P3 after removing resource R4 looks like.

Step 4: From P3 we find a path to P4 as it is waiting for P3 which is acquired by P4. After
removing R3 the graph looks like this.
Step 5: Here we can find Process P4 is waiting for R2 which is acquired by P1. So finally the
Wait-for-Graph is as follows:

Step 6: Finally In this Graph, we found a cycle as the Process P4 again came back to the
Process P1 which is the starting point (i.e., it’s a closed-loop). So, According to the Algorithm
if we found a closed loop, then the system is in a deadlock state. So here we can say the
system is in a deadlock state.

Solve this using Wait-for-Graph: Deadlock Exist or not

Solution
In this Graph, we don’t find a cycle as no
process came back to the starting point (i.e.,
there is no closed loop). So, According to the
Algorithm if we found a closed loop, then the
system is in a deadlock state in this case no
such closed loop; hence system is free from
deadlock and it is in safe state

Module-3 Deadlocks.pptx BCS303 Operating system

Several Instances of a Resource Type
 The wait-for graph scheme is not applicable to a resource-allocation system with multiple
instances of each resource type.
 Lets discuss the deadlock detection algorithm that is applicable to such a system.
 The algorithm employs data structures that are similar to those used in the banker's
algorithm
‣ Available: A vector of length m indicates the number of available resources of each
type.
‣ Allocation: An n x m matrix defines the number of resources of each type currently
allocated to each process.
‣ Request: An n x m matrix indicates the current request of each process. If Request
[i][j] = k, then process Pi is requesting k more instances of resource type.Rj.

Deadlock Detection Algorithm

Example
• Five processes P0 through P4;three resource types
A (7 instances), B (2 instances), and C (6 instances).
• Snapshot at time T0:
Allocation Request Available
A B C A B C A B C
P0 0 1 0 0 0 0 0 0 0
P1 2 0 0 2 0 2
P2 3 0 3 0 0 0
P3 2 1 1 1 0 0
P4 0 0 2 0 0 2
• Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true for all i.

Example (Cont.)
• P2 requests an additional instance of type C.
Request
A B C
P0 0 0 0
P1 2 0 1
P2 0 0 1
P3 1 0 0
P4 0 0 2
• State of system?
– Can reclaim resources held by process P0, but insufficient resources to fulfill other
processes; requests.
– Deadlock exists, consisting of processes P1, P2, P3, and P4.

Detection-Algorithm Usage
 When should the deadlock detection be done? Frequently, or infrequently?
 The answer may depend on how frequently deadlocks are expected to occur, as well as the
possible consequences of not catching them immediately
 There are two obvious approaches, each with trade-offs:
– Do deadlock detection after every resource allocation which cannot be immediately
granted. This has the advantage of detecting the deadlock right away, while the
minimum number of processes are involved in the deadlock
– Do deadlock detection only when there is some clue that a deadlock may have
occurred, such as when CPU utilization reduces to 40% or some other magic number.

Recovery from Deadlock
 When a detection algorithm determines that a deadlock exists, there are three basic
approaches to recovery from deadlock:
1. Inform the system operator, and allow him/her to take manual intervention
2. Terminate one or more processes involved in the deadlock
3. Preempt resources

Process Termination
 Two basic approaches, both of which recover resources allocated to terminated processes:
1. Abort all processes involved in the deadlock. This definitely solves the deadlock, but
at the expense of terminating more processes than would be absolutely necessary.
2. Abort process one by one until the deadlock is broken. This is more conservative, but
requires doing deadlock detection after each step.
 Aborting a process may not be easy.
‣ If the process was in the midst of updating a file, terminating it will leave that file in an
incorrect state.
‣ if the process was in the midst of printing data on a printer, the system must reset the
printer to a correct state before printing the next job.

 If the partial termination method is used, then we must determine which deadlocked process
(or processes) should be terminated. This determination is a policy decision, similar to CPU-
scheduling decisions.
 Many factors may affect which process is chosen, including:
1. What the priority of the process is
2. How long the process has computed and how much longer the process will compute
before completing its designated task
3. How many and what types of resources the process has used (for example, whether the
resources are simple to preempt)
4. How many more resources the process needs in order to complete
5. How many processes will need to be terminated
6. Whether the process is interactive or batch

Resource Preemption
• When preempting resources to relieve deadlock, there are three important issues to be addressed:
1. Selecting a victim - Deciding which resources to preempt from which processes involves
many of the same decision criteria outlined above.
2. Rollback - Ideally one would like to roll back a preempted process to a safe state prior to the
point at which that resource was originally allocated to the process. Unfortunately it can be
difficult or impossible to determine what such a safe state is, and so the only safe rollback is
to roll back all the way back to the beginning. ( I.e. abort the process and make it start over. )
3. Starvation - How do you guarantee that a process won't starve because its resources are
constantly being preempted? One option would be to use a priority system, and increase the
priority of a process every time its resources get preempted. Eventually it should get a high
enough priority that it won't get preempted any more.

Module-3 Deadlocks.pptx BCS303 Operating system

Recommended

More Related Content

Similar to Module-3 Deadlocks.pptx BCS303 Operating system (20)

More from ambikavenkatesh2 (19)

Recently uploaded (20)

Module-3 Deadlocks.pptx BCS303 Operating system