Operating Systems
Lecture 9 Deadlock
Deadlock Resource Deadlock
Copyright By PowCoder代写 加微信 powcoder
Deadlock Safety
Request Deadlock
characteristics allocation prevention avoidance
COMP 2432 2021/2022
What is Deadlock?
There is a narrow bridge or road.
Traffic can only go in one direction.
If a car is driving along the bridge, no car can drive in the other direction.
All cars behind the moving car can also drive through bridge.
When both cars meet in the middle, both cannot move
We call this a deadlock situation.
Each one is waiting for the other to yield.
No one can make any progress.
It can only be resolved if one car backs up.
COMP 2432 2021/2022
Compare deadlock with a case that looks similar. Two persons are moving towards each other and almost
Both seeing that they are going to run into each other, both try to avoid by turning to one side of the road to proceed.
Now, one turns left and the other turns right. What happen?
They both would collide again. So they both make another
In an unlucky case, when both are always making the wrong move, they end up spending time to try alternative route but unsuccessful.
We call this a livelock situation.
Each one tries to make a move to avoid forever waiting. No one can make any progress.
It can be resolved if people are more lucky.
Note that once a deadlock is there, it will be there but a livelock can be removed with a bit of luck. COMP 2432 2021/2022
move to avoid it.
Recall that OS is a resource manager.
The presence of a user in the OS could be represented by a
process, that will need to use resources.
A process will consume CPU time, use up memory to execute,
Consider two processes P1 and P2 communicating via pipes. P1: read(fd2to1[0], b1, 80); write(fd1to2[1], b1, strlen(b1));
P2: read(fd1to2[0], b2, 80); write(fd2to1[1], b2, strlen(b2));
Both processes will wait to read from the pipe before each goes ahead to write into the pipe.
The result is a deadlock! Another example
Both P1 and P2 want to print a file on disk to printer. P1 gets hold of printer and wants to get file on disk, but P2 has already got the file on disk and wants to get printer.
Deadlock! COMP 2432 2021/2022
read inputs from a file and send outputs to a printer. Example
Resource Model
Steps to use a resource:
Request for the resource (acquire or open).
Wait until the resource is allocated or granted.
Use the resource (read or write).
Release the resource (return or close).
A resource can only be used by a process after it issues a request to the resource manager and the manager approves its usage (grant the resource).
A process releases the resource when done to the manager so that the next process waiting in line could use it.
We assume that all processes follow this rule. COMP 2432 2021/2022
A resource is an object that is capable of being used.
A process uses a file by opening the file and gets the file pointer or
file descriptor.
A process gets a block of memory with malloc().
A process uses I/O device via a system call to the device driver.
CPU is consumed by processes as arranged by the scheduler.
Resource Model
Resources could be grouped into types.
There are m types of resources: R1, R2, . . ., Rm.
Each resource type Ri has Wi copies (or Wi instances).
For example, there may be 10 shared buffers, 80 physical memory frames, and 4 worker threads in the thread pool.
A process utilizes a resource through the request/use/release cycle.
A deadlock is a set of blocked processes, each holding a resource and waiting to acquire a resource held by another process in the set.
A process is blocked if it is waiting for a resource currently held by another process.
We call this resource deadlock and is the focus of this lecture.
Another type of deadlock is called communication deadlock.
A set of processes are waiting for a message to be sent from processes (e.g. data to be written into a pipe) within the set, or an event to be triggered by the set (e.g. go ahead signal).
COMP 2432 2021/2022
Deadlock Characterization
Deadlock can only occur if all four necessary conditions are true.
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.
No preemption
A resource can be released only voluntarily by the process holding it, after that process completes its task.
Circular wait
There is a chain of waiting processes {P1, P2, …, Pn, P1} such that P1 is waiting for a resource that is held by P2,
P2 is waiting for a resource that is held by P3, …, Pn-1 is waiting for a resource that is held by Pn, and Pn is
waiting for a resource that is held by P1. COMP 2432 2021/2022
Resource Allocation Graph
To study deadlock, we use resource allocation graph as a tool.
A resource allocation graph has a set of vertices V and a set of edges E.
There are two types of vertices V:
P = {P1, P2, …, Pn} is the set of all processes.
R = {R1, R2, …, Rm} is the set of all resource types.
There are two types of edges E:
Request edge is a directed edge from P to R.
Pi Rj means that Pi is requesting for resource Rj.
Assignment edge is a directed edge from R to P.
Rj Pi means that Rj is allocated/assigned to Pi, which holds
If a request can be fulfilled by the resource manager, a request edge will become an assignment edge and the direction of the edge is reversed. COMP 2432 2021/2022
the resource.
Resource Allocation Graph
Notations
A process
A resource type with 4 instances
Pi requests an instance of Rj Pi Rj
Pi is holding an instance of
COMP 2432 2021/2022
Resource Allocation Graph
Cycle and deadlock
Cycle and no deadlock
P4 can finish
Then P3 gets
COMP 2432 2021/2022
resourcPe . . . 4
P4 can finish Then P3 gets resource . . .
Resource Allocation Graph
The request to resource can be granted only if converting the request edge to an assignment edge does not result in a cycle
in the resource allocation graph. COMP 2432 2021/2022
Quick rules of thumb
If the graph contains no cycle, then there is definitely no
If the graph contains a cycle, is there a deadlock?
If there is only one instance per resource type, then a cycle means that there is a deadlock.
If there are several instances per resource type, then a cycle only means that there is a possibility of deadlock.
Thus, cycle is only a necessary condition of a deadlock, but it is not a sufficient condition for a deadlock.
Algorithm
Before a resource is allocated, OS checks whether the
allocation would result in a cycle.
Do not allocate the resource if a cycle is produced.
Deadlock in Databases
Recall that in resource allocation graph.
If the graph contains no cycle, then there is no deadlock.
If the graph contains a cycle, but if there is only one instance per resource type, then a cycle means that there is a deadlock.
So in a one-instance resource situation, a cycle is a necessary and sufficient condition for a deadlock.
In a database, the shared resource is the data item (or data record).
Locking a data item or record implies exclusive access to it without being interfered by other users / transactions.
There is just one copy per data item or record, unless a replicated database is used.
Database systems will execute the cycle detection algorithm periodically on the simplified resource allocation graph
(called wait-for graph) to detect deadlocks, and that is very common under Two-Phase Locking. COMP 2432 2021/2022
Deadlock Handling
Four types of methods to deal with a deadlock.
Ostrich approach
Ignore the deadlock problem and pretend that deadlocks never occur in the system.
Deadlock prevention
Ensure that the system will never enter a deadlock state.
Deadlock avoidance
Allocate the resources very carefully so that system will not enter a deadlock state.
Deadlock detection
Allow the system to enter a deadlock state, detect it and
then recover from it.
COMP 2432 2021/2022
Deadlock Prevention
There are four necessary conditions. Attack any one to ensure that it is not satisfied.
Mutual exclusion
For sharable resources, mutual exclusion is not true and there is no deadlock.
Problem: some resources are inherently not sharable. Hold and wait
Ensure that whenever a process requests a resource, it does not hold any other resources.
Example: you should return all your books before you can borrow a book from the library!
This means that process should request and be allocated all its resources before it begins execution, or allow a process to request resources only when it has none.
Problem: low resource utilization, starvation.
COMP 2432 2021/2022
Deadlock Prevention
No preemption
Allow resources to be preempted from a process.
If a process that is holding some resources requests another resource that cannot be allocated to it, then all resources currently being held are released (preempted).
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.
Problem: not all resources can be preempted, starvation is possible.
Circular wait
Order all resource types with possibly a number.
Each process can only request resources in an increasing order of resource number.
Then no one can wait in a cycle, because everyone can only wait for a higher number. COMP 2432 2021/2022
Prevention in Databases
Consider a database again.
To make use of deadlock prevention technique, look at those four conditions:
Mutual exclusion: data items cannot be shared for updating.
Hold and wait: you may request data transactions to lock all data items at the beginning, but they could be held for too long, and sometimes hard to predict future need.
Non-preemption: allow high priority transactions to take over data items. This is adopted in some database systems, in the wound-wait protocol.
Circular wait: do not allow transactions to wait in a cycle.
This is also adopted in some database systems to enforce
the waiting order, by ordering the data items, or in the wait- die protocol. COMP 2432 2021/2022
Deadlock Avoidance
Use additional information about how resources are requested.
Carefully control the allocation of resources.
The simplest and most useful model is to ask each process to declare the maximum number of resources of each type that it may need.
OS can check in advance when allocating resource to ensure that system remains in a safe state that will not enter a deadlock state.
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.
COMP 2432 2021/2022
Deadlock Avoidance
If a system is in a safe state, there is no deadlock.
If a system is in an unsafe state, there is a possibility of deadlock.
Deadlock occurs only if a bad sequence of events happen.
There may not be deadlock if there is some luck.
Deadlock avoidance
Ensure that a system will never enter an unsafe state, with care.
COMP 2432 2021/2022
Deadlock Avoidance
Safe state
A state is safe if the system can allocate the remaining
resources in a certain order so as to avoid a deadlock. That allocation order is indicated by a safe sequence.
A safe sequence
For each Pj, the resources that Pj can still request can be satisfied by currently available resources plus resources currently held by all preceding processes Pk with k < j.
Based on a safe sequence,
If the resources needed by Pj are not immediately available,
then Pj can wait until all Pk have finished.
When Pk finishes, Pj can obtain its needed resources, execute,
return its allocated resources, and terminate.
When Pj finishes, Pj+1 can obtain its needed resources, and so
on. COMP 2432 2021/2022
Deadlock Avoidance
COMP 2432 2021/2022
Safesequenceexample
Systemstate Pool=1
P1 holds 2 and needs 2 more. P2 holds 1 and needs 1 more. P3 holds 1 and needs 5 more. P4 holds 2 and needs 3 more.
Stepstocompletion
P2 gets 1 from pool (1), P1 gets 2 from pool (2), P4 gets 3 from pool (4), P3 gets 5 from pool (6),
now holds 1+1, now holds 2+2, now holds 2+3, now holds 1+5,
+ 1 (held by P2) + 1 (held by P2) + 1 (held by P2)
finishes, returns 2. finishes, returns 4. finishes, returns 5. finishes, returns 6.
+ 2 (held by P1)
+ 2 (held by P1) + 2 (held by P4)
The safe sequence 2143
P2: need = 1 1 (pool)
P1: need = 2 1 (pool)
P4: need = 3 1 (pool)
P3: need = 5 1 (pool)
Banker’s Algorithm
Banker’s Algorithm is an algorithm for multiple instances of resource types.
Assumptions:
Each process must declare its maximum use before hand.
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.
Try to find a safe sequence pretending that the request is satisfied.
If a safe sequence exists, the request can be granted.
If there is no safe sequence, granting the request will lead the system into an unsafe state. Put the request on hold
until some resources are returned. COMP 2432 2021/2022
Banker’s Algorithm
Notations
n: number of processes (P1 to Pn).
m: number of resources types (R1 to Rm). Available[m]: array of m.
Available[j] = number of instances of resource type Rj available.
Maxi[m]: array of m.
Max [j] = maximum number of instances of resource
Allocation [j] = number of instances of R currently
type Rj that process Pi may request.
Allocationi[m]: array of m.
ij allocated to Pi.
Needi[m]: array of m.
Need [j] = additional number of instances of R that P
Needi[j] = Maxi[j] – Allocationi[j]. COMP 2432 2021/2022
may need to complete its task.
Banker’s Algorithm
Safety algorithm
Define temporary arrays Work[m] and Finish[n]
Work Available
Finish false
while not done do
find an i such that Finish[i] = false and Needi ≤ Work if no such i exists, break from the loop
Work Work + Allocationi
Finish[i] true
if for all i, Finish[i] = true, then declare safe.
if for some i, Finish[i] = false, then declare unsafe.
COMP 2432 2021/2022
Banker’s Algorithm
Example:
5 processes, P0 to P4, 3 resource types A, B, C,
After some allocation exercises, there are only 3, 3 and 2 instances of A, B, C available. The current allocation state is shown. Now compute Need.
Allocation Max Need
ABC ABC ABC
P0 010 753 743
P1 200 322 122
P2 302 902 600
P3 211 222 011
P4 002 433 431
We can find a safe sequence
with 10, 5 and 7 instances.
Banker’s Algorithm
Finding the safe sequence for Available = (3 3 2): Allocation Max Need
ABC ABC ABC
P0 010 753 743
P1 200 322 122
P2 302 902 600
P3 211 222 011
P4 002 433 431
Work=(332).
Need1 ≤ Work, Work = (3 3 2) + (2 0 0) = (5 3 2), P1 done.
Need3 ≤ Work, Work = (5 3 2) + (2 1 1) = (7 4 3), P3 done.
Need0 ≤ Work, Work = (7 4 3) + (0 1 0) = (7 5 3), P0 done.
Need2 ≤ Work, Work = (7 5 3) + (3 0 2) = (10 5 5), P2 done.
Need4 ≤ Work, Work = (10 5 5) + (0 0 2) = (10 5 7), P4 done.
All finished,
COMP 2432 2021/2022
Banker’s Algorithm
Finding the safe sequence for Available = (3 3 2): Allocation Max Need
ABC ABC ABC
P0 010 753 743
P1 200 322 122
P2 302 902 600
P3 211 222 011
P4 002 433 431
Work=(332).
Need1 ≤ Work, Work = (3 3 2) + (2 0 0) = (5 3 2), P1 done.
Need3 ≤ Work, Work = (5 3 2) + (2 1 1) = (7 4 3), P3 done.
Need0 ≤ Work, Work = (7 4 3) + (0 1 0) = (7 5 3), P0 done.
Need4 ≤ Work, Work = (7 5 3) + (0 0 2) = (7 5 5), P4 done.
Need2 ≤ Work, Work = (7 5 5) + (3 0 2) = (10 5 7), P2 done.
All finished,
COMP 2432 2021/2022
Banker’s Algorithm
Finding the safe sequence for Available = (3 3 2): Allocation Max Need
ABC ABC ABC
P0 010 753 743
P1 200 322 122
P2 302 902 600
P3 211 222 011
P4 002 433 431
Work=(332).
Need1 ≤ Work, Work = (3 3 2) + (2 0 0) = (5 3 2), P1 done.
Need3 ≤ Work, Work = (5 3 2) + (2 1 1) = (7 4 3), P3 done.
Need4 ≤ Work, Work = (7 4 3) + (0 0 2) = (7 4 5), P4 done.
Need2 ≤ Work, Work = (7 4 5) + (3 0 2) = (10 4 7), P2 done.
Need0 ≤ Work, Work = (10 4 7) + (0 1 0) = (10 5 7), P0 done.
All finished,
Banker’s Algorithm
Request algorithm
Define Requesti[m] to be requests by process Pi.
If not (Requesti ≤ Needi) then raise error (Pi has exceeded its maximum claim) and stop.
If not (Requesti ≤ Available) then Pi must wait, since resources are not available.
[Else] pretend to allocate requested resources to Pi by modifying the allocation state:
allocation state is restored. COMP 2432 2021/2022
Available = Available – Request Allocation = Allocation + Request
If safe, then resources are allocated to P . i
Need = Need – Request
Run safety algorithm on this pretended state.
If unsafe, then P must wait and the old resource i
Banker’s Algorithm
Example: Available = (3 3 2)
Process P1 wants to request 1A and 2C.
P1 (3 0 2)
P3 (2 1 1)
P0 (0 1 0)
P2 (3 0 2)
(10 5 5) P4 (0 0 2)
(10 5 7) Lecture 9
Request1 = (1 0 2) ≤ Available, we can continue.
Pretend that Request1 is granted, then Available = (2 3 0). Change Allocation1 and Need1 as well.
Request of 1A and 2C can be granted to P1.
COMP 2432 2021/2022
Allocation Max
P0 010 753
P1 30 2 322
P2 302 902
P3 211 222
P4 002 433
Need ABC 743 02 0 600 011 431
Banker’s Algorithm
Example: Available = (3 3 2)
Process P1 wants to request 1A and 2C.
P1 (3 0 2)
P3 (2 1 1)
P0 (0 1 0)
P4 (0 0 2)
P2 (3 0 2)
(10 5 7) Lecture 9
Request1 = (1 0 2) ≤ Available, we can continue.
Pretend that Request1 is granted, then Available = (2 3 0). Change Allocation1 and Need1 as well.
Request of 1A and 2C can be granted to P1.
COMP 2432 2021/2022
Allocation Max
P0 010 753
P1 30 2 322
P2 302 902
P3 211 222
P4 002 433
Need ABC 743 02 0 600 011 431
Banker’s Algorithm
How to find out all possible safe sequences? 230
P0 743 P4 P2
P2 P4 P0 P4
P0 P2 P0 P2
10 5 5 7 5 5 10 5 5
7 5 5 10 4 7 10 5 7
7 5 5 10 4 7
COMP 2432 2021/2022
Banker’s Algorithm
Example: Available = (2 3 0)
Now process P0 wants to request only 2B.
Request0 = (0 2 0) ≤ Available, we can continue.
Pretend that Request0 is granted, then Available = (2 1 0). Change Allocation0 and Need0 as well.
Allocation Max Need
ABC ABC ABC
P0 0 3 0 753 7 2 3
P1 302 322 020
P2 302 902 600
P3 211 222 011
P4 002 433 431
We cannot find a safe sequence.
Request of 2B cannot be granted to P0.
COMP 2432 2021/2022
Deadlock Detection
Allow sys
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com