Transcript class slides

Concurrency:
Principles of Deadlock
Operating Systems
Fall 2002
OS Fall’02
Processes and resources
 Processes need resources to run
CPU, memory, disk, etc…
A process waiting for a resource cannot
complete its execution until the resource
becomes available
 There is only a finite amount of resources
E.g., 1 CPU, 1 GB memory, 2 disks
OS Fall’02
Concurrency and deadlocks
 In a multiprogramming system the total
resource demand by all concurrently
active processes exceeds by far the total
amount of available resources
 Processes compete for resources
A process can grab the last instance of a
resource A and wait for the resource B
Another process may hold B and wait for A
No one can proceed: Deadlock
OS Fall’02
Deadlock
 Permanent blocking of a set of processes
that either compete for system resources
or communicate with each other
 Involves conflicting needs for resources
by two or more processes
 There is no satisfactory solution in the
general case
OS Fall’02
Deadlock in the everyday life
3
2
4
1
OS Fall’02
Deadlock in the everyday life
OS Fall’02
Deadlock when contending for the
critical section
Process Pi :
Shared : boolean flag[2]
do {
flag[i ]  true;
while ( flag[1  i ]);
critical section
flag[i ]  false;
remainder section
} while(1)
OS Fall’02
Example of Deadlock
Progress
of Q
2
1
Release
A
A
Required
P and Q
want A
Release
B
Get A
deadlock
3 inevitable
B
Required
Get B
P and Q
want B
5
4
6
Get A
Get B
Release A Release B
A
Required
B Required
OS Fall’02
Progress
of P
Example of No Deadlock
Progress
of Q
1
2
3
Release
A
A
Required
Release
B
4
P and Q
want A
P and Q
want B
Get A
B
Required
5
Get B
6
Get A
Release A
A
Required
OS Fall’02
Get B
Release B
B Required
Progress
of P
Resource categories
 Reusable: Used by one process at a time
and not depleted by that use
 can be reused by other processes,may exist
several instances
Processors, memory, disks, tapes, etc.
 Consumable: Created (produced) and
destroyed (consumed) by a process
 Interrupts, signals, messages, and information in
I/O buffers
OS Fall’02
Reusable resources and Deadlock
 Deadlock might occur if each process
holds one resource and requests the
other
 E.g., Space is available for allocation of
200K
P1
P2
...
Request 80K bytes;
...
...
Request 70K bytes;
...
Request 60K bytes;
Request 80K bytes;
OS Fall’02
Consumable resources and Deadlock
 Example: Deadlock occurs if receive is
blocking
P1
P2
...
...
Receive(P2);
...
Receive(P1);
...
Send(P2);
Send(P1);
OS Fall’02
Conditions for Deadlock
 Policy conditions
Mutual exclusion
Hold-and-wait
No preemption
 Circular wait
Resource
A
Process
P1
Process
P2
Resource
B
OS Fall’02
Conditions for Deadlock
•Mutual exclusion
•Hold-and-wait
•No preemption
DEADLOCK
OS Fall’02
Circular wait
Circular Wait
P1
R1
R2
P2
P3
R3
OS Fall’02
No circular wait
P1
R1
R2
P2
P3
R3
OS Fall’02
Coping with Deadlocks
 Deadlock prevention
Deadlock possibility is excluded a priori by
the system design
 Deadlock avoidance
Deadlocks are possible in principle but
avoided
 Deadlock detection
Deadlocks can occur: detect and solve the
problem
OS Fall’02
Deadlock prevention
 Design system so that it violates one of
the four necessary conditions
Prevent hold and wait:
 request all the resources at the outset
 wait until all the resources are available
Prevent circular wait by defining linear
ordering of the resource types
 A process holding some resources can request
only resource types with higher numbers
OS Fall’02
Preventing circular wait
R1
P1
R2
P2
P3
R3
OS Fall’02
Deadlock prevention: Cons
 Degraded performance
Delayed execution
Low parallelism
 Hold and wait prevention is wasteful
Hold resources more than they are needed
When might this be reasonable?
OS Fall’02
Deadlock avoidance
 Allocate resources in a way that assures
that the deadlock point is never reached
 The allocation decision is made
dynamically based on
total amount of resources available
currently available
processes’ resource claim
processes’ current resources allocation
OS Fall’02
Banker’s algorithm (Dijkstra 65’)
 Do not grant an incremental resource
request to a process is this allocation
might lead to deadlock
 The system state: is the current
allocation of resources to processes
 Safe state: is a state in which there is at
least one sequence in which all processes
can be run to completion
 Unsafe state = NOT safe state
OS Fall’02
Determination of the safe state
 We have 3 resources types with amount:
R(1) = 9, R(2) = 3, R(3) = 6
 Is the state S0 below safe?
P1
P2
P3
P4
Claim
R1 R2
3 2
6 1
3 1
4 2
R3
2
3
4
2
Allocated
R1 R2 R3
1 0 0
6 1 2
2 1 1
0 0 2
OS Fall’02
Total
R1 R2 R3
9 3 6
Available
0 1 1
Determination of the safe state
P1
P2
P3
P4
Claim
R1 R2
3 2
0 0
3 1
4 2
P1
P2
P3
P4
Claim
R1 R2
0 0
0 0
3 1
4 2
R3
2
0
4
2
Allocated
R1 R2 R3
1 0 0
0 0 0
2 1 1
0 0 2
Total
R1 R2 R3
9 3 6
R3
0
0
4
2
Allocated
R1 R2 R3
0 0 0
0 0 0
2 1 1
0 0 2
Total
R1 R2 R3
9 3 6
OS Fall’02
Available
6 2 3
Available
7 2 3
Determination of the safe state
P1
P2
P3
P4
Claim
R1 R2
0 0
0 0
0 0
4 2
P1
P2
P3
P4
Claim
R1 R2
0 0
0 0
0 0
0 0
R3
0
0
0
2
Allocated
R1 R2 R3
0 0 0
0 0 0
0 0 0
0 0 2
Total
R1 R2 R3
9 3 6
R3
0
0
0
0
Allocated
R1 R2 R3
0 0 0
0 0 0
0 0 0
0 0 0
Total
R1 R2 R3
9 3 6
Available
9 3 4
Available
9 3 6
S0 is safe: P2->P1->P3->P4
OS Fall’02
Banker’s algorithm
 When a process request resources:
Assume the request is granted
Update the system state accordingly
Determine whether the resulting state is safe
If yes: grant the resources
Otherwise, block the process until it is safe to
grant the resources
OS Fall’02
Banker’s algorithm
P1
P2
P3
P4
Claim
R1 R2
3 2
6 1
3 1
4 2
R3
2
3
4
2
Allocated
R1 R2 R3
1 0 0
5 1 1
2 1 1
0 0 2
Total
R1 R2 R3
9 3 6
Available
1 1 2
P2 requests (1, 0, 1): Grant or not?
P1 requests (1, 0, 1): Grant or not?
OS Fall’02
Deadlock detection
 Banker’s algorithm is
Pessimistic: always assume that a process will
not release the resources until it got’m all
 decreased parallelism
Involves complicated checks for each resource
allocation request (O(n^2))
 Optimistic approach: don’t do any checks
When deadlock occurs - detect and recover
Detection: look for circular waits
OS Fall’02
Practice
 Most operating systems employ an
“ostrich” algorithm
 Break hold-and-wait
Cannot acquire a resource - fail back to the
user:
 e.g., too many processes, too many open files
 Quotas
 Programming discipline:
acquire locks (semaphores) in a specific
order
OS Fall’02
Dining philosophers problem
OS Fall’02
Dining philosophers problem
 An abstract problem demonstrating some
fundamental limitations of the deadlockfree synchronization
 There is no symmetric solution
 Solutions
execute different code for odd/even
give’m another fork
allow at most 4 philosophers at the table
Randomized (Lehmann-Rabin)
OS Fall’02
Concurrency: summary
 Critical section is an abstract problem for
studying concurrency and synchronization
software solutions
hardware primitives
higher level primitives: semaphores,
monitors
 Deadlocks are inherent to concurrency
4 conditions
3 ways to cope with
OS Fall’02
Next: Memory management
OS Fall’02