Transcript deadlock - The University of Edinburgh

Operating Systems: Deadlock
Deadlock
• Examples: Traffic Jam :
• Dining Philosophers
• Device allocation
– process 1 requests tape drive 1 & gets it
– process 2 requests tape drive 2 & gets it
– process 1 requests tape drive 2 but is blocked
– process 2 requests tape drive 1 but is blocked
• Semaphores :
P(s)
P(t)
P(t)
P(s)
1
Operating Systems: Deadlock
• I/O spooling disc
– disc full of spooled input
– no room for subsequent output
• Over-allocation of pages in a virtual memory OS
– each process has a allocation of notional pages it must work within
– process acquires pages one by one
– normally does not use its full allocation
– kernel over-allocates total number of notional pages
» more efficient uses of memory
» like airlines overbooking seats
– deadlock may arise
» all processes by mischance approach use of their full allocation
» kernel cannot provide last pages it promised
» partial deadlock also - some processes blocked
– recovery ?
2
Operating Systems: Deadlock
• Resource:
– used by a single process at a single point in time
– any one of the same type can be allocated
• Pre-emptible:
– can be taken away from a process without ill effect
– no deadlocks with pre-emptible resources
• Non-Pre-emptible:
– cannot be taken away without problems
– most resources like this
– deadlock possible
3
Operating Systems: Deadlock
Definition : A set of processes is deadlocked if each process in the set is
waiting for an event that only another process in the set can cause
Necessary conditions for deadlock :
• Mutual Exclusion : each resource is either currently assigned to one
process or is available to be assigned
• Hold and wait : processes currently holding resources granted earlier can
request new resources
• Non-Pre-emption : resources previously granted cannot arbitrarily be
taken away from a process; they must be explicitly released by the process
• Circular wait : there must be a circular chain of two or more processes,
each of which is waiting for a resource held by the next member of the chain
4
Operating Systems: Deadlock
Resource Allocation Modelling using Graphs
Nodes :
resource
Arcs :
resource requested :
process
resource allocated :
5
Operating Systems: Deadlock
6
Operating Systems: Deadlock
7
Operating Systems: Deadlock
• For multiple resources of the same type :
• Deadlock :
• A cycle not sufficient to
imply a deadlock :
8
Operating Systems: Deadlock
Possible Strategies :
• Ignore - the Ostrich or Head-in-the-Sand algorithm
– try to reduce chance of deadlock as far as reasonable
– accept that deadlocks will occur occasionally
» example: kernel table sizes - max number of pages, open files etc.
– MTBF versus deadlock probability ?
– cost of any other strategy may be too high
» overheads and efficiency
9
Operating Systems: Deadlock
• Deadlock Prevention
– negate one of the necessary conditions
• negating Mutual Exclusion :
– example: shared use of a printer
» give exclusive use of the printer to each user in turn wanting to print?
» deadlock possibility if exclusive access to another resource also allowed
» better to have a spooler process to which print jobs are sent
- complete output file must be generated first
– example: file system actions
» give a process exclusive access rights to a file directory
» example: moving a file from one directory to another
- possible deadlock if allowed exclusive access to two directories simultaneously
- should write code so as only to need to access one directory at a time
– solution?
» make resources concurrently sharable wherever possible e.g. read-only access
» most resources inherently not sharable!
10
Operating Systems: Deadlock
Resource Trajectory Graph
11
Operating Systems: Deadlock
12
Operating Systems: Deadlock
• negating Hold and Wait
– process could request all the resources it will ever need at once
» inefficient - not all resources needed all the time
» processes probably will not know in advance what resources they will need
» may have to wait excessive time to get all resources at once - starvation
- high priority processes may cause starvation of low priority processes
13
Operating Systems: Deadlock
– process could release existing resources it holds if it fails to get a new
resource immediately
» try again later
» a form of two phase locking used in databases
– whenever a new resource is needed, the process always releases its
existing resources and asks for all of them at once
– example: a process which copies a file from tape to disc, sorts the file on
disc, and then prints the results on a printer
» could request all three resources at the start
- wasteful of printer first, then tape drive later
» could initially request tape and disc together, do the read and sort, then
release both and finally request disc and printer together to do the printing
- more efficient
- must ensure data stays intact on disc between phases
14
Operating Systems: Deadlock
• negating Non-Pre-emption
– difficult to achieve in practice
» cannot take a printer away from a process in the middle of printing
» cannot take a semaphore away from a process arbitrarily
- might be in the middle of updating a shared area
» cannot take open streams, pipes and sockets away
- process would need to be written very carefully, probably using signals
- very undesirable if possible at all
– occasionally possible :
» processes resident in main memory
» some deadlock occurs such as failure to allocate a page
» one or more processes can be swapped out to disc to release their pages
and allow remaining processes to continue
- as long as they release any other resources they also hold on the way out
» put back on the scheduling queues to be re-admitted to memory later
15
Operating Systems: Deadlock
• negating Circular Wait
– require that a process can only acquire one resource at a time
» example: moving a file from one directory to another
– require processes to acquire resources in a certain order
– example:
» 1: tape drive
» 2: disc drive
» 3: printer
» 4: plotter
» 5: typesetter
– example: semaphores
» semaphores identified by
number claimed in numerical order
16
Operating Systems: Deadlock
• Deadlock Avoidance
– deadlock possible but avoided by careful allocation of resources
– avoid entering unsafe states
– a state is safe if it is not deadlocked and there is a way to satisfy all requests
currently pending by running the processes in some order
– need to know all future requests of processes
17
Operating Systems: Deadlock
• Example: can processes run to completion in some order?
– with 10 units of resource to allocate :
– if A runs first and acquires a further unit :
18
Operating Systems: Deadlock
• avoidance using resource allocation graphs - for one instance resources
– add an extra type of arc - the claim arc to indicate future requests
– when the future request is actually made, convert this to an allocation arc
– then check for loops
19
Operating Systems: Deadlock
Banker’s Algorithm (Dijkstra)
• Single resource
– at each request, consider whether granting will lead to an unsafe state - if so,
deny
– is state after the notional grant still safe?
» are there enough resources to satisfy the demands of some process
» if so, process is notionally allowed to proceed
» in due course, it is assumed to finish and return all its resources
» process closest to its limit is the checked, and the steps repeated
» if all processes can eventually run to completion, state is safe
20
Operating Systems: Deadlock
• Multiple resources
– m types of resource, n processes
– vector comparison :
» A  B if Ai  Bi for 0  i  m
21
Operating Systems: Deadlock
C
R
» look for a row in R  A i.e. a process whose requests can be met
» if no such row exists, state is unsafe
» add this row of R into the same row of C and subtract it from A
i.e. notionally allocate the resources to the process
» add this row of C back into A and set the row of C to zero i.e. the process
notionally completes and returns its resources
» repeat these steps until all C is all zero i.e. all processes notionally finished
(initial state is safe) or until a suitable row in R cannot be found (unsafe)
22
Operating Systems: Deadlock
Drawbacks of Banker’s Algorithm
– processes rarely know in advance how many resources they will need
– the number of processes changes as time progresses
– resources once available can disappear
– the algorithm assumes processes will return their resources within a
reasonable time
– processes may only get their resources after an arbitrarily long delay
– practical use is therefore rare!
23
Operating Systems: Deadlock
• Detection and Recovery
– let deadlock occur, then detect and recover somehow
• Methods of Detection - single resources
– search for loops in resource allocation graph
24
Operating Systems: Deadlock
• Depth-first Graph search
– use a list of nodes L and progressively mark arcs
1.
For each node N in the graph, perform steps 2-6 with N as starting node
2.
Initialise L to empty and designate all arcs as unmarked
3.
Add current node to L
» check if node appears twice in L
» if so, graph contains a cycle - algorithm terminates
4.
From given node, if there are any unmarked outgoing arcs, goto 5
else goto 6
5.
Pick an unmarked outgoing arc and mark it
» follow it to new current node and goto 3
6.
Have reached a dead end
» go back to previous node and goto 4
» if this node is the initial node, graph does not contain cycles and
algorithm terminates
25
Operating Systems: Deadlock
26
Operating Systems: Deadlock
• Using an Adjacency Matrix
– adjacency matrix represents single hops
– two-hops :
node(i) -> node(j) :
or
or
or
node(i) -> node(1) and node(1) -> node(j)
node(i) -> node(2) and node(2) -> node(j)
node(i) -> node(3) and node(3) -> node(j)
.....
node(i) -> node(N) and node(N) -> node(j)
– binary (Boolean) matrix multiplication
» and replaces multiplication
» or replaces addition
27
Operating Systems: Deadlock
– 2 hops :
0
0
1
0
1
0
0
0
0
1
0
0
0
1
1
0
1
0
0
0
1
1
0
0
*
0
0
1
0
1
0
0
0
0
1
0
0
0
1
1
0
*
0
0
1
0
1
0
0
0
0
1
0
0
0
1
1
0
– 3 hops :
0
1
0
0
0
0
1
0
– 4 hops ?
> 4 hops ?
– identifying disjoint cycles ?
– Transitive Closure equivalent to the N matrix multiplications
28
Operating Systems: Deadlock
• Warshall’s Algorithm for computing Transitive Closure :
– if there is a way to get from node x to node y and a way to get from node y to node z, then
there is a way to get from node x to node z
– if there is a way to get from node x to node y using only nodes with indices less than x and a
way to get from node y to node z , then there is a way to get from from node x to node z using
only nodes with indices less than x+1
for (y=0; y<N; y++) {
for (x=1; x<N; x++) {
if ( A[x,y] ) {
for (z=1; z<N; z++) {
if ( A[y,z] ) A[x.z] = true;
}
}
}
}
29
Operating Systems: Deadlock
• Semaphore loop detection :
30
Operating Systems: Deadlock
• Multiple resources
– apply equivalent of Banker’s algorithm using current resource requests
– any processes unsatisfied are deadlocked
• When to check for deadlock?
– every time a resource request is made
– regularly at fixed time intervals
– when CPU utilisation drops below some threshold
31
Operating Systems: Deadlock
Recovery from Deadlock
• Pre-emption
– take resources from a process and give to others
– how to select a victim?
» order of precedence for pre-empting
» number of resources already held
» how many more will it need to complete?
» amount of CPU time already used
– swapping process out of memory may be sufficient
» but may still hold resources involved in deadlock
– may need to roll pre-empted process back
» back to some safe restart point or go back to beginning
» may need to checkpoint processes
» not convenient for user interaction!
– need to avoid starvation of a low priority process always being pre-empted
» include number of previous pre-emptions as a choice factor
32
Operating Systems: Deadlock
• Process Termination
– drastic ultimate solution
– abort all processes involved in the deadlock
» all resources returned for re-use
– abort processes one by one until deadlock resolved
» how to choose order of precedence?
» will the process need to be rerun?
– aborting a process may cause severe difficulties
» may be in the process of updating a file which will be left inconsistent
– a process gets into an infinite program loop while holding resources
» common situation in practice
33