Deadlock

WHAT IS A DEADLOCK???
 WHAT IS DEADLOCK?
 A set of blocked processes each
holding a resource and waiting to
acquire a resource held by another
process in the set.
 Example
 System has 2 disk drives.
 P1 and P2 each hold one disk drive and
each needs another one.
 Example
 Four cars approaches each other at
crossing, all will come to stop and
neither shall start until other has gone.
3
Necessary Conditions
 NECESSARY CONDITIONS
 Deadlock can arise if four conditions
hold simultaneously.
 Mutual exclusion: only one process

at a time can use a resource.

 Hold and wait: a process holding at

least one resource is waiting to
acquire additional resources held by
other processes.

5
 NECESSARY CONDITIONS
 No preemption: a resource can be released
only voluntarily by the process holding it, after
that process has completed its task.

 Circular wait: there exists a set {P0, P1, …, P0}

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 .

6
Resource Allocation Graph
EXAMPLE OF RESOURCE-ALLOCATION GRAPH

Resource instances:
One instance of resource type R1
One instance of resource type R3
Two instances of resource type R2
Three instance of resource type R4

8
EXAMPLE OF RESOURCE-ALLOCATION GRAPH

Process States:
Process P1 is holding an instance
of resource type R2 and waiting for
an instance of resource type R1.
Process P2 is holding an instance
of resource type R1 and R2 and
waiting for an instance of resource
type R3.
Process P3 is holding an instance
of resource type R3. 9
RESOURCE-ALLOCATION GRAPH
 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.

10
RESOURCE-ALLOCATION GRAPH WITH A DEADLOCK

 P1 -> R1 -> P2 -> R3

-> P3 -> R2 -> P1
 P2 -> R3 -> P3 -> R2
-> P2
 Cycles are formed.
 Deadlock may exist.
 P1, P2, P3 are
deadlocked.

11
RESOURCE-ALLOCATION GRAPH WITH A DEADLOCK

Allocated Requested

R1 R2 R3 R4 R1 R2 R3 R4

P1 0 1 0 0 1 0 0 0

P2 1 1 0 0 0 0 1 0

P3 0 0 1 0 0 1 0 0

Available=(0, 0, 0, 3)

12
GRAPH WITH A CYCLE BUT NO DEADLOCK

Allocate Requested
d
R1 R2 R1 R2

P1 0 1 1 0

P2 1 0 0 0

P3 1 0 0 1

P4 0 1 0 0

Available= (0, 0)

13
GRAPH WITH A CYCLE BUT NO DEADLOCK
 P1 -> R1 -> P3 ->
R2 -> P1
 No deadlock
 P4 may release its
instance of
resource R2
 Then it can be
allocated to P3

14
Handling Deadlock
 METHODS FOR HANDLING
DEADLOCK
 We can deal with DL problem in 3-ways:
 Prevention/Avoidance

 Ensure that the system will never enter

a deadlock state.
 Detection/Correction

 Allow system to enter a deadlock state and

then recover.
 Ignorance

 Ignore problem and pretend that deadlocks

never occur.
 Used by most operating systems,
16
Deadlock Prevention
DEADLOCK PREVENTION
Restrain the ways request can be made.
 Mutual Exclusion – not required for

sharable resources; must hold for

non-sharable resources.
 A printer cannot simultaneously
shared by several process.
 Read-only file is a good example of

sharable resource.

19
 DEADLOCK PREVENTION
 Hold and Wait – must guarantee that whenever a
process requests a resource, it does not hold any
other resources.
 Require process to request and be allocated all

its resources before it begins execution

 E.g. disk, drive, printer
 Or…allow process to request resources only

when the process has none.

 E.g. disk, drive and disk, printer
 Cons:

 Lower resource utilization

 Starvation
20
 DEADLOCK PREVENTION
 No Preemption –
 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.
 If process is requesting another resource, if it is
available then it is given to requesting process
 If it is held by another process which is waiting for
another resource, we release it n give it to
21
 DEADLOCK PREVENTION
 Circular Wait –
 impose a total ordering of all
resource types, and require that each
process requests resources in an
increasing order of enumeration.
R1

P1 P2

R2
22
Deadlock Avoidance
 DEADLOCK AVOIDANCE
 Requires additional information about how
resources are to be requested.

 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. 24
 SAFE STATE
 Systems is in safe state if there exists a
safe sequence of all process

 A sequence <P1, P2, …, Pn> of ALL the

processes is the system such that 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.

25
 SAFE STATE
 That is:
 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.

26
SAFE, UNSAFE DEADLOCK STATE
 If system is in safe
state => No
deadlock.
 If system in not in
safe state =>
possibility of
deadlock.
 OS cannot prevent

processes from
requesting resources
in a sequence that
leads to deadlock
 Avoidance => ensures
that system will never 27
 SAFE STATE - EXAMPLE
Max Allocat Need
Need ed
P0 10 5 5
P1 4 2 2
P2 9 2 7
 Suppose processes P0, P1, and P2 share 12
magnetic tape drives
 Currently 9 drives are held among the
processes and 3 are available(Free
resources).
 Question: Is this system currently in a safe
state?
 Answer: Yes! 28
SAFE STATE - EXAMPLE
Start with P0=>
P0 requires 5 more resources.
Available=3 Can’t be fulfilled.

P1=> P1 requires 2 resources

Available = 3 can be fulfilled.
P1 completes execution and returns=>
New + old= 3+2 = 5 => Available

P0=> P0 requires 5 resources

Available = 5 can be fulfilled.
P0 completes and returns
New + old = 5+5 = 10 =>Available
SAFE STATE - EXAMPLE
 Start with P2=>
P2 requires 7 more resources.
Available=10 Can ne fulfilled.
P2 completes execution and returns
New + old= 10 + 2 = 12 =>Available
SYSTEM IN UNSAFE STATE

3
 Suppose process P2 requests and is allocated 1
more tape drive.
 Question: Is the resulting state still safe?
 Answer: No! Because there does not exist a safe
sequence anymore.
 Only P1 can be allocated its maximum needs.
 IF P0 and P2 request 5 more drives and 6 more
drives, respectively, then the resulting state will
be deadlocked.
SAFE STATE - DEADLOCK
AVOIDANCE
 Key Ideas:
 Initially the system is in a safe state.
 Whenever a process requests an available
resource, system will allocate resource
immediately only if the resulting state is
still safe!
 Otherwise, requesting process must wait.

32
DEADLOCK AVOIDANCE
ALGORITHM
 Single instance of a resource type.
 Use a resource-allocation graph.

 Cycles are sufficient for deadlock.

 Multiple instances of a resource type.

 Use the banker’s algorithm.

 Cycles are necessary, but not sufficient for

deadlock.

33
RESOURCE ALLOCATION GRAPH
ALGORITHM
 Claim edge Pi  Rj indicates that process Pj
may request resource Rj; represented by a
dashed line.
 Claim edge converts to request edge when a
process requests a resource.
 Request edge converted to an assignment
edge when the resource is allocated to the
process.
 When a resource is released by a process,
assignment edge reconverts to a claim edge.
 Resources must be claimed a priori in the
system. 34
RESOURCE ALLOCATION GRAPH ALGORITHM

 P2 requesting R1,
but R1 is already
allocated to P1.

 Both processes have

a claim on
resource R2

 What happens if P2
now requests
resource R2? 35
UNSAFE STATE IN RESOURCE ALLOCATION GRAPH
ALGORITHM

 Cannot allocate
resource R2 to
process P2

 Why? Because
resulting state is
unsafe
 P1 could request

R2, thereby
creating
deadlock!
36
 RESOURCE ALLOCATION GRAPH ALGORITHM
 Use only when there is a single instance of
each resource type
 Suppose that process Pi requests a
resource Rj
 The request can be granted only if
converting the request edge to an
assignment edge does not result in the
formation of a cycle in the resource
allocation graph.
 Here we check for safety by using cycle-
detection algorithm.
37
Banker’s Algorithm
 BANKER’S ALGORITHM
 RAL is not applicable for multiple
instance of resource
 Bankers’ algorithm - Multiple instances.
 Each process claims maximum resource
needs a priori.
 When a process requests a resource it may
have to wait.
 When a process gets all of its resources it
must return them in a finite amount of
time.
39
 BANKER’S ALGORITHM-DATA
STRUCTURE
Let,
 n = number of processes
 m = number of resources types
 Available: Vector of length m. If
Available[j] = k, there are k instances
of resource type Rj available.
 Max: n x m matrix. If Max [i,j] = k,
then process Pi may request at most k
instances of resource type Rj.
 Allocation: n x m matrix. If
Allocation[i,j] = k then Pi is currently
allocated k instances of Rj.
 Need: n x m matrix. If Need[i,j] = k, 40
 BANKER’S ALGORITHM-DATA
STRUCTURE
Available Resources = 9 Processes

Processes P1 P2 P3 P4

Max Resources
5 4 3 2
required

Allocated 2 3 2 1
resources

Need 3 1 1 1

Total Allocated Resources = 2+3+2+1=8

Free Resources = available – T allocated =9-8 = 1
BANKER’S ALGORITHM - 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.
[Link] and i such that both:
(a) Finish [i] = false
(b) Needi  Work
If no such i exists, go to step 4.
[Link] = Work + Allocationi
Finish[i] = true
go to step 2.
[Link] Finish [i] == true for all i, then the system
is in a safe state.
42
 BANKER’S ALGORITHM
- RESOURCE ALLOCATION ALGORITHM
 Request = 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 – Request;
Allocation = Allocation +
43
BANKER’S ALGORITHM - EXAMPLE
 5 processes P0 through P4;
 3 resource types:
 A (10 instances), B (5instances), and C (7
instances).
 Snapshot at time T0:
AllocationMax Available
ABC ABC ABC
P0 010 753 332
P1 2 0 0 322
P2 3 0 2 902
P3 2 1 1 222
P4 0 0 2 433
44
EXAMPLE
Available resources = A, B, C
A = 10, B=5, C=7
P Allocation Max
A B C A B C

P0 0 1 0 7 5 3

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
EXAMPLE
Available resources = A, B, C
A = 10, B=5, C=7
P Allocation Max
A B C A B C

P0 0 1 0 7 5 3

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
EXAMPLE
Available resources = A, B, C
A = 10, B=5, C=7
P Allocation Max
A B C A B C

P0 0 1 0 7 5 3

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
EXAMPLE
Available resources = A, B, C
A = 10, B=5, C=7
Allocated A= 0+2+3+2+0=7
P Allocation Max
A B C A B C
Allocated B= 1+0+0+1+0=2

P0 0 1 0 7 5 3 Allocated C= 0+0+2+1+2=5
P1 2 0 0 3 2 2 Available A= TA – Alloc
P2 3 0 2 9 0 2
= 10-7 = 3

P3 2 1 1 2 2 2 Available B= TA – Alloc
= 5-2 = 3
P4 0 0 2 4 3 3
Available C= TA – Alloc
= 7-5 = 2
EXAMPLE
Available resources = A, B, C
A = 10, B=5, C=7
P 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
EXAMPLE
P Allocation Max Available Need
A B C 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

Need = Max - Allocated

EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

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

Need = Max - Allocated

EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2

P3 2 1 1 2 2 2

P4 0 0 2 4 3 3

Need = Max - Allocated

EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2

P4 0 0 2 4 3 3

Need = Max - Allocated

EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3

Need = Max - Allocated

EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1

Need = Max - Allocated

EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1
EXAMPLE
1)Start with P0=>
Required resources for P0 = (7, 4, 3)=>(A, B, C)
Available resources = (3, 3, 2) =>(A, B, C)
Required > Available
=>requirement can’t be fulfilled.
Proceed with the next process.
EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1

Need = Max - Allocated

EXAMPLE
2) Check with P1=>
Required resources for P1 = (1, 2, 2) =>(A, B, C)
Available resources = (3, 3, 2) =>(A, B, C)
=>requirement can be fulfilled.
P1 completes its execution and returns =>
Newly allocated resources + old resources
=(3, 3, 2)+(2, 0, 0)=(5, 3, 2)
Available resources = (5, 3, 2)
EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1

Need = Max - Allocated

EXAMPLE
3) Check with P2=>
Required resources for P2 = (6, 0, 0) =>(A, B, C)
Available resources = (5, 3, 2) =>(A, B, C)
=>requirement can’t be fulfilled.
Proceed with the next process.
EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1

Need = Max - Allocated

EXAMPLE
4) Check with P3=>
Required resources for P3 = (0, 1, 1) =>(A, B, C)
Available resources = (5, 3, 2) =>(A, B, C)
=>requirement can be fulfilled.
P3 completes its execution and returns =>
Newly allocated resources + old resources
=(5, 3, 2)+(2, 1, 1)=(7, 4, 3)
Available resources = (7, 4, 3)
EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 3 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1

Need = Max - Allocated

EXAMPLE
5) Check with P4=>
Required resources for P3 = (4, 3, 1) =>(A, B, C)
Available resources = (7, 4, 3) =>(A, B, C)
=>requirement can be fulfilled.
P4 completes its execution and returns =>
Newly allocated resources + old resources
=(7, 4, 3)+(0, 0, 2)=(7, 4, 5)
Available resources = (7, 4, 5)
EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 2 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1

Need = Max - Allocated

EXAMPLE
6) Check with P0=>
Required resources for P0 = (7, 4, 3) =>(A, B, C)
Available resources = (7, 4, 5) =>(A, B, C)
=>requirement can be fulfilled.
P0 completes its execution and returns =>
Newly allocated resources + old resources
=(7, 4, 5)+(0, 1, 0)=(7, 5, 5)
Available resources = (7, 5, 5)
EXAMPLE
P Allocation Max Available Need
A B C A B C A B C A B C

P0 0 1 0 7 5 3 3 2 2 7 4 3

P1 2 0 0 3 2 2 1 2 2

P2 3 0 2 9 0 2 6 0 0

P3 2 1 1 2 2 2 0 1 1

P4 0 0 2 4 3 3 4 3 1

Need = Max - Allocated

EXAMPLE
7) Check with P2=>
Required resources for P2 = (6, 0, 0) =>(A, B, C)
Available resources = (7, 5, 5) =>(A, B, C)
=>requirement can be fulfilled.
P2 completes its execution and returns =>
Newly allocated resources + old resources
=(7, 5, 5)+(3, 0, 2)=(10, 5, 7)
Available resources = (10, 5, 7)
 EXAMPLE
 All processes are allocated with required number
of resources and all completed their execution.
 The system is in a safe state since the sequence

< P1, P3, P4, P0, P2> satisfies safety criteria.

Released Resources at the end

= (10, 5, 7) = Initially available resources.
EXAMPLE
 DEADLOCK DETECTION
 Allow system to enter deadlock state

 Detection algorithm

 Recovery scheme

72
RESOURCE-ALLOCATION GRAPH AND WAIT-
FOR GRAPH
 For single instance

 Pi -> Pj (Pi is waiting for Pj

to release a resource that Pi
needs)

 Pi -> Pj exist if and only if

RAG contains 2 edges Pi ->
Rq and Rq -> Pj for some
Resource-Allocation Corresponding resource Rq
Graph wait-for graph

73
 Corresponding
Resource-Allocation
wait-for graph
Graph
RESOURCE-ALLOCATION GRAPH AND WAIT-
FOR GRAPH
 Deadlock exists in the system if and only if wait-for
graph contains a cycle.

 System needs to maintain the wait-for graph and

periodically invoke an algorithm. That searches for a
cycle in the graph.

75
SEVERAL INSTANCES OF A RESOURCE TYPE
 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 [ij] = k, then process Pi is requesting
k more instances of resource type. Rj.

76
 DETECTION ALGORITHM
1. Let Work and Finish be vectors of length m and n,
respectively Initialize:
(a) Work = Available
(b) For i = 1,2, …, n, if Allocationi  0, then
Finish[i] = false;otherwise, Finish[i] = true.

2. Find an index i such that both:

(a) Finish[i] == false
(b) Requesti  Work
If no such i exists, go to step 4.
DETECTION ALGORITHM
Work = Work + Allocationi
Finish[i] = true
go to step 2.

4. If Finish[i] == false, for some i, 1  i  n, then the

system is in deadlock state. Moreover, if Finish[i] ==
false, then Pi is deadlocked.

78
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202
P2 303 000
P3 211 100
P4 002 002
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
79
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202
P2 303 000
P3 211 100
P4 002 002
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
80
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202 010
P2 303 000
P3 211 100
P4 002 002
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
81
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202 010
P2 303 000
P3 211 100
P4 002 002
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
82
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202 010
P2 303 000 313
P3 211 100
P4 002 002
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
83
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202 010
P2 303 000 313
P3 211 100 524
P4 002 002
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
84
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202 010
P2 303 000 313
P3 211 100 524
P4 002 002
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
85
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202 010
P2 303 000 313
P3 211 100 524
P4 002 002 724
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
86
EXAMPLE OF DETECTION
ALGORITHM
 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
ABC ABC ABC
P0 010 000 000
P1 200 202 010
P2 303 000 313
P3 211 100 524
P4 002 002 7 2 4 => 7 2 6
 Sequence <P0, P2, P3, P1, P4> will result in Finish[i] = true
87
EXAMPLE OF DETECTION
ALGORITHM
 P2 requests an additional instance of type C.
Request
ABC
P0 000
P1 201
P2 001
P3 100
P4 002
 State of system?
 Can reclaim resources held by process P , but insufficient
0
resources to fulfill other processes; requests.
 Deadlock exists, consisting of processes P , P , P , and P . 88
1 2 3 4
DETECTION-ALGORITHM USAGE
 When should we invoke the detection algorithm depends on:
 How often a deadlock is likely to occur?

 How many processes will be affected by deadlock when it

happens?

 If detection algorithm is invoked arbitrarily, there may be

many cycles in the resource graph and so we would not be
able to tell which of the many deadlocked processes “caused”
the deadlock.

89
RECOVERY FROM DEADLOCK:
PROCESS TERMINATION
 Abort all deadlocked processes.
 Abort one process at a time until the deadlock cycle is
eliminated.
 In which order should we choose to abort?
 Priority of the process.
 How long process has computed, and how much longer to

completion.
 Resources the process has used.
 Resources process needs to complete.
 How many processes will need to be terminated.
 Is process interactive or batch?

90
 RECOVERY FROM DEADLOCK:
RESOURCE PREEMPTION
 Selecting a victim – minimize cost.
 Rollback – return to some safe state, restart process for
that state.
 Starvation – same process may always be picked as
victim, include number of rollback in cost factor.

91
DINING PHILOSOPHERS PROBLEM

• No two philosophers
can use the same
fork at the same time
(mutual exclusion)

• No philosopher must
starve to death
(avoid deadlock and
starvation)
USING SEMAPHORES

Cont.
A Second Solution . . .
THANK YOU

95