Transcript Deadlocks - pnu-cs-os

Princess Nora University
Faculty of Computer & Information Systems
Computer science Department
Operating Systems
(CS 340 D)
Dr. Abeer Mahmoud
(Chapter-7)
Deadlocks
Chapter 7: Deadlocks
1. The Deadlock Problem
2. Deadlock Characterization
3. Methods for Handling Deadlocks
3
OBJECTIVES:
 To develop a description of deadlocks, which prevent sets of
concurrent processes from completing their tasks
 To present methods for Handling Deadlocks
4
The Deadlock Problem
5
The Deadlock Problem

In a multiprogramming environment, several processes may
compete for a finite number of resources.

A process requests resources; if the resources are not
available at that time, the process enters a waiting state.

Sometimes, a waiting process is never again able to
change state, because the resources it has requested
are held by other waiting processes.
This situation is called a DEADLOCK.
6
The Deadlock Problem (cont..)

What is a deadlock problem??
o 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
o P1 and P2 each hold one disk drive and each need the other one
n Example
l semaphores A and B, initialized to 1
o

P0
P1
wait (A);
wait (B);
wait(B)
wait(A)
Note :– Most OSs do not prevent or deal with deadlocks
7
Bridge Crossing Example





8
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)
Several cars may have to be backed up if a deadlock occurs
Starvation is possible
System Model

The resources are partitioned into several types (R1, R2, . . ., Rm )
o E.g.: CPU cycles, memory space, I/O devices

Each resource type Ri has Wi instances.
o
E.g :
 If a system has (2) CPUs, then the resource type CPU has (2) instances.
 The
9
resource type printer may have (5) instances.

Each process utilizes a resource as follows:
1.
Request
>> If the request cannot be granted immediately ,then the
requesting process must wait until it can acquire the resource.
2.
3.
Use
Release
 A set of processes is in a deadlocked state when every
process in the set is waiting for an event that can be caused
only by another process in the set.
10
System Model (cont.)


Resource forms:
Physical resources
Logical resources
e.g. printers, DVD drives,
memory space, and CPU
cycles
e.g. files
Example:

11
consider a system with one printer and one DVD drive. Suppose that
process Pi is holding the DVD and process Pj is holding the printer. If Pi
requests the printer and Pj requests the DVD drive, a deadlock occurs.
The Deadlock
Characterization
12
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously:
1. Mutual exclusion: the resources are sharable or non sharable
 mutual exclusion happen when only one process at a
time can use a resource…(i.e. No resource sharing)
2. Hold and wait: a process holding at least one resource is
waiting to acquire additional resources held by other processes
13
Deadlock Characterization (cont..)
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 :
o P0 is waiting for a resource that is held by P1,
o P1 is waiting for a resource that is held by P2, …, Pn–1 is
waiting for a resource that is held by Pn,
o Pn is waiting for a resource that is held by P0.
P0
14
P1
P2
Pn
Resource-Allocation Graph
15
Resource-Allocation Graph

Deadlocks can be described in terms of a directed graph called a
system resource-allocation graph.

This graph consists of a set of vertices V and a set of edges E.
V is partitioned into two types:
E is partitioned into two types:
Request edge – directed edge
P = {P1, P2, …, Pn}, the set
Pi  Rj
consisting of all the processes
in the system
Assignment edge – directed edge
R = {R1, R2, …, Rm}, the set
R j  Pi
consisting of all resource types
in the system
16
Resource-Allocation Graph (Cont.)

Process

Resource Type with 4 instances

Pi requests instance of Rj
Pi
Rj

Pi is holding an instance of Rj
Pi
Rj
17
Example of a Resource Allocation Graph
 The sets P, R, and E:

P = {P1, P2, P3}

R = {R1, R2, R3, R4}
E = {P1 → R1, P2 → R3, R1 →
P2, R2 → P2, R2 → P1, R3 →
P3}

 Resource instances:

18
(1) instance of resource type R1
(2)
instances of resource type R2
(1)
instance of resource type R3
(3)
instances of resource type R4
Example of a Resource Allocation Graph
 Process states:
Process P1 is holding an instance of
resource type R2 and is waiting for an
instance of resource type R1.

Process P2 is holding an instance of R1
and an instance of R2 and is waiting for
an instance of R3.


19
Process P3 is holding an instance of R3.
Basic Facts

How we recognize deadlock by using a Resource Allocation
Graph??

If graph contains no cycles  no deadlock

If graph contains a cycle 
 If
only one instance per resource type, then there is a deadlock
 If several instances per resource type, possibility of deadlock .
20
Resource Allocation Graph With NO Deadlock
 Example (1):

21
The graph contains NO cycles  NO deadlock is occurred.
Resource Allocation Graph With a Deadlock
 Example (2):

The graph contains
(2)cycles  may be a
deadlock is occurred.

Cycle (1) : P1 → R1 → P2 → R3 → P3 → R2 → P1

Cycle (2) : P2 → R3 → P3 → R2 → P2

It ‘s a dead lock situation >>> Processes P1, P2, and P3
are deadlocked…….why??

22
There is no chance to break the cycle.
Graph With A Cycle But No Deadlock
 Example (3):

The graph contains (1)cycle
 may be a deadlock
Cycle : P1 → R1 → P3 → R2 → P1

NO dead lock situation .....WHY????

23
process P4 may release its instance of resource type
R2…… That resource can then be allocated to P3,
breaking the cycle.
To ensure that deadlocks never occur, the system can
use either
1. a deadlock prevention or
2. a deadlock-avoidance scheme

24
Deadlock prevention
Deadlock avoidance
provides a set of methods to ensure
that at least one of the necessary 4
conditions (explained before )
cannot hold.
• requires that the operating system be given
additional information in advance concerning
which resources a process will request and use
during its lifetime.
These methods prevent deadlocks
by constraining how requests for
resources can be made.
• With this additional knowledge, the operating
system can decide for each request whether or
not the process should wait.
25
1-Deadlock Prevention
26
Deadlock Prevention
Remove the possibility of deadlock occurring by
denying one of the four necessary conditions:
1- Mutual Exclusion – not required for sharable resources; must hold for nonsharable resources.
 That is, at least one resource must be nonsharable. Sharable resources, in contrast,
do not require mutually exclusive access and thus cannot be involved in a deadlock
2- Hold and Wait – must guarantee that whenever a process requests a
resource, it does not hold any other resources by using one of the following
protocols:
•The process must request all its
resources before execution.

27
•
0r allow process to request resources
only when the process has none
Problems-> Low resource utilization; starvation possible
Deadlock Prevention (Cont.)
3- 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
Process will be restarted only when it can regain its old resources, as
well as the new ones that it is requesting
It is applied to resources whose state easily saved and restored later,
such as CPU registers and memory space
The main Advantages is more better resource utilization
Problems


28
The cost of removing a process's resources
starvation possible
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.

let R = {R1, R2, ..., Rm} be the set of resource types. We assign
to each resource type a unique integer number, which allows us to
compare two resources and to determine whether one precedes
another in our ordering.

Formally, we define a one-to-one function F: R→N, where N is
the set of natural numbers.
29
Deadlock Prevention (Cont.)
4- Circular Wait – cont..





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
We can now consider the following protocol to prevent deadlocks:
Each process can request resources only in an increasing order of
enumeration.
That is, a process can initially request any number of instances of a resource
type —say, Ri . After that, the process can request instances of resource type Rj
if and only if F(Rj ) > F(Ri ).
30
Deadlock Prevention (Cont.)
4- Circular Wait – cont..

EX: 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.

Alternatively, we can require that a process requesting an instance
of resource type Rj must have released any resources Ri such that
F(Ri ) ≥ F(Rj ).

Problems
 Resources must be requested in ascending order of
resource number rather than as needed
31
2-Deadlock Avoidance
32
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
33
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 sequence <P1, P2, …, Pn>
of ALL the processes in the systems 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
o
o
o
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
34
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.
35
Safe, Unsafe , Deadlock State
36
Avoidance algorithms
 The avoidance algorithms ensure that the system will
always remain in a safe state.
37

Single instance of a resource type
 Use a resource-allocation graph

Multiple instances of a resource type
 Use the banker’s algorithm
Resource-Allocation Graph Scheme

Claim edge Pi → Rj indicated 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
38
Resource-Allocation Graph
39
Unsafe State In Resource-Allocation Graph
40
Resource-Allocation Graph Algorithm
 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 form of
a cycle in the resource allocation graph
41
Banker’s Algorithm
 Multiple instances
 Each process must a priori claim maximum use, When a
new process enters a system, it must declare the maximum
number of instances of each resource type that may not
exceed the total number of resources in the system
 When a process requests a resource it may have to wait
 When a process gets all its resources it must return them
in a finite amount of time
42
Banker’s Algorithm

When a user requests a set of resources, the system must
determine whether the allocation of these resources will leave
the system in a safe state.
o
o
43
If it will, the resources are allocated;
otherwise, the process must wait until some other process releases
enough resources.
Data Structures for the Banker’s Algorithm
Let n = number of processes, and 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, then Pi may need k
more instances of Rj to complete its task

Need [i][j] = Max [i][j] – Allocation [i][j]
44
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 index 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
45
Example of Banker’s Algorithm
 5 processes P0 through P4;
3 resource types:
A (10 instances), B (7 instances), and C (5 instances)
Snapshot at time T0:
Allocation
ABC
P0
010
P1
200
P2
302
P3
211
P4
002
46
Max Available
ABC ABC
753 332
322
902
222
433
Example of Banker’s Algorithm
 The matrix Need is defined to be Max – Allocation
Snapshot at time T0:
Allocation
ABC
P0
010
P1
200
P2
302
P3
211
P4
002
Max Available
ABC ABC
753 332
322
902
222
433
Need
ABC
743
122
600
011
431
 The system is in a safe state since the sequence < P1, P3, P4,
P2, P0> satisfies safety criteria
47
Example of Banker’s Algorithm

Suppose now that process P1 requests one additional
instance of resource type A and two instances of resource
type C, so Request1 = (1,0,2). To decide whether this
request can be immediately granted,
48
Example: P1 Request (1,0,2)
1- Check that Request ≤ Need (that is, (1,0,2) ≤ (1,2,2) ⇒ true
2- Check that Request ≤ Available (that is, (1,0,2) ≤ (3,3,2) ⇒ true
3- Available = Available – Request => (3,3,2) - (1,0,2) = (2,3,0)
Allocation = Allocation + Request => (2,0,0) - (1,0,2) = (3,0,2)
Need = Need – Request => (1,2,2) - (1,0,2) = (0,2,0)
P0
P1
P2
P3
P4
49
Allocation
ABC
010
302
302
211
002
Need
ABC
743
020
600
011
431
Available
ABC
230
Example: P1 Request (1,0,2) cont.
 Executing safety algorithm shows that sequence < P1, P3,
P4, P0, P2> satisfies safety requirement
o
P1 acquires 2 B more resources, achieving its maximum
o
o
P1 terminates, returning 3 A, 3 B, 2 C resources to the system
o
o
The system now still has 5 A, 2 B, and 1 C resource available
P3 terminates, returning 2 A, 2 B, 2 C resources to the system
o
50
The system now has 5 A, 3 B, and 2 C resources available
P3 acquires 1B and 1C more resources, achieving its maximum
o
o
The system now still has 2 A, 1 B, and no C resource available
The system now has 7 A, 4 B, and 3 C resources available
Example: P1 Request (1,0,2) cont.
 Executing safety algorithm shows that sequence < P1, P3, P4, P0, P2>
satisfies safety requirement
o
o
o
o
51
P4 acquires 4 A, 3 B AND 1 C more resources, achieving its
maximum
o The system now still has 3 A, 1 B, and 2 C resource available
P4 terminates, returning 4 A, 3 B, 3 C resources to the system
o The system now has 7 A, 4 B, and 5 C resources available
P0 acquires 7 A, 4 B AND 3 C more resources, achieving its
maximum
o The system now still has no A, no B, and 2 C resource
available
P0 terminates, returning 7 A, 5 B, 3 C resources to the system
o The system now has 7 A, 5 B, and 5 C resources available
Example: P1 Request (1,0,2) cont.
n Executing safety algorithm shows that sequence < P1, P3,
P4, P0, P2> satisfies safety requirement (cont.)
o
o
o
P2 acquires 6 A more resources, achieving its maximum
o The system now still has 1 A, 5 B, and 5 C resource available
P2 terminates, returning 9 A, and 2 C resources to the system
o The system now has 10 A, 5 B, and 7 C resources available
Because all processes were able to terminate, this state is safe
 Can request for (3,3,0) by P4 be granted?
 Can request for (0,2,0) by P0 be granted?
52
Methods for Handling Deadlocks
53
Methods for Handling Deadlocks

OS can deal with the deadlock problem in one of three ways
1-prevent or avoid
deadlocks
ensuring that the
system will never enter
a deadlocked state.
54
2-Allow
3-Ignore
Allow the system to Ignore the problem
enter a deadlocked
state, detect it, and
 Used by most operating
recover.
systems, including Unix &
windows
 This method is cheaper than 1
or 2 .
 Solution: The system must be
restarted manually
Thank you
End of
Chapter 7
55
Dr. Abeer Mahmoud