Operating Systems
Chapter 3: Deadlocks
Instr: Yusuf Altunel IKU Department of Computer Engineering (212) 498 42 10 [email protected]
1
Content
3.1.Sharing Resources
3.2. Introduction to deadlocks 3.3. The ostrich algorithm
3.4. Deadlock detection and recovery
3.5. Deadlock avoidance 3.6. Deadlock prevention 3.7. Other issues
Sharing Resources
Computer systems have resources
shared between processes can only be used by one process at a time
printers, tape drives, slots in the systems internal tables
Two processes simultaneously writing to the printer:
leads to gibberish.
two processes using the same file system table slot:
lead to a corrupted file system.
operating systems have the ability
to temporarily grant a process exclusive access to certain resources.
3
Deadlock
Two processes each want to record
a scanned document on a CD.
Process A requests permission
to use the scanner and is granted it.
Process requests the CD recorder first
and is also granted it.
Now A asks for the CD recorder,
but the request is denied until B releases it.
Instead of releasing the CD recorder
B asks for the scanner.
Both processes are blocked and will remain so forever. This situation is called a deadlock.
4
Resources
a resource is
anything that can be used
by only a single process at any instant of time
Types of resources:
hardware device
e.g., a tape drive, printers
piece of information
e.g., a record in a database
A computer has many different resources some resources have several identical instances
such as three tape drives. any one of them can be used
to satisfy requests for the resource.
Resources
Preemptable Resources
can be taken away from the process owning it
with no ill effects.
Example: Memory of a printer
Nonpreemptable Resources
cannot be taken away from its current owner
without causing the computation to fail
deadlocks involve nonpreemptable resources Example: CD Writer
If a process has begun to burn a CD-ROM,
suddenly taking the CD recorder away from it and giving it to another process will result in a garbled CD
6
Using a Resource
Sequence of events required to use a resource:
request the resource use the resource release the resource
Must wait if request is denied
requesting process may be blocked or fail with some error code
7
Introduction to Deadlocks
Formal 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 release of a currently held resource
Usually the event is
None of the processes can
run release resources be awakened
8
Conditions for Deadlock
1. All of four conditions must hold to be a deadlock: Mutual exclusion condition.
Each resource is either
currently assigned to exactly one process or is available.
2.
Hold and wait condition.
Processes currently holding resources granted earlier
can request new resources.
3.
No preemption condition.
Resources previously granted
cannot be forcibly taken away from a process. They must be explicitly released by the process holding them.
4.
Circular wait condition.
There must be a circular chain of two or more processes, each is waiting for a resource
held by the next member of the chain. 9
Deadlock Modeling
Using directed graphs
(a) Holding a resource by a process (b) Requesting a resource (c) Deadlock (C-T-D-U-C)
An arc from a resource to a process The resource is held by that process
An arc from a process to a resource The process is currently blocked waiting the resource to be available
A cycle in the graph means a deadlock
10
How deadlock occurs
11
How Deadlock Avoided
12
Strategies for dealing with Deadlocks
1.
2. 3.
just ignore the problem altogether detection and recovery dynamic avoidance
careful resource allocation
4.
prevention
negating one of the four necessary conditions
13
The Ostrich Algorithm
Stick your head in the sand
and pretend there is no problem
Reasonable if
deadlocks occur very rarely cost of prevention is high
UNIX and Windows takes this approach It is a trade-off between
convenience correctness
14
Deadlock Detection and Recovery
system does not attempt
to prevent deadlocks from occurring
Instead
lets them occur tries to detect when this happens and then takes some action to recover
15
Detection with One Resource of Each Type
Condition:
There is only one resource from each type
Example:
1. 2. 3. 4. 5. 6. 7. Process Process Process Process Process Process Process A holds R and wants S. B holds nothing but wants T. C holds nothing but wants S. D holds U and wants S and T. E holds T and wants V. F holds W and wants S. C holds V and wants U.
16
Example
Note the resource ownership and requests A cycle can be found within the graph, denoting deadlock
17
Algorithm
1. For each node, N in the graph,
perform the following 5 steps
with N as the starting node.
2. Initialize L to the empty list,
and designate all the arcs as unmarked.
3. Add the current node to the end of L
and check to see
if the node now appears in L two times.
If it does, the graph contains a cycle (listed in L) and the algorithm terminates.
4. From the given node,
see if there are any unmarked outgoing arcs. If so, go to step 5; if not, go to step 6
18
Algorithm
5. Pick an unmarked outgoing arc at random and mark it
Then follow it to the new current node and go to step 3.
6. We have now reached a dead end.
Remove it and go back to the previous node, make the previous one as the current node, and go to step 3. If this node is the initial node,
the graph does not contain any cycles and the algorithm terminates.
19
Detection with Multiple Resource of Each Type
Processes: P1 through Pn Resources: (1..m)
E1 resources of class 1,
(E1 = 2 means the system has two tape drives )
available resource vector: Ai current allocation matrix: C the request matrix : P
E2 resources of class 2, Ei resources of class i (1 i m)
Resources assigned to no processes Ai : available number of instances for resource i
20
Matrix for Deadlock Detection
The i-th row of C : Request matrix: Rij
tells how many instances of each resource class Pi currently holds, Cij :the number of instances of resource j that are held by process i. is the number of instances of resource j that Pi wants
21
R1
R2
R3
R4
R1
R2
R3
R4
P1 P2 P3
R1 R2 R3 R4
R1 R2 R3 R4
22
Invariants
Every resource is either allocated or available If we add up all allocated resources j (Example: Printer)
To the available resources The result is the number of instances for the resource class
C
i 1
ij
Aj Ej
23
Deadlock Detection Algorithm
Each process is initially said to be unmarked.
As the algorithm progresses processes will be marked, indicating that they are able to complete and are thus not deadlocked. When the algorithm terminates,
any unmarked processes are known to be deadlocked.
The deadlock detection algorithm:
1. Look for an unmarked process, Pi for which the ith row of R is less than or equal to A. 2. If such a process is found, add the ith row of C to A, mark the process, and go back to step 3. If no such process exists, the algorithm terminates.
When the algorithm finishes,
all the unmarked processes, if any, are deadlocked.
24
Deadlock Detection Algorithm
step 1 is looking for a process that can be run to completion Such a process is characterized
as having resource demands can be met by the currently available resources
The selected process is then run until it finishes,
it returns the resources it is holding to the pool of available resources.
It is then marked as completed. If all the processes are ultimately able to run
none of them are deadlocked
If some of them can never run, they are deadlocked. the algorithm is nondeterministic
because it may run the processes in any feasible order,
the result is always the same.
25
DDA Example (1)
we have three processes four resource classes,
Labeled as tape drives (4), plotters (2), scanner (2), and CD-ROM (1) drive. E=(4, 2, 2,1) A=(4, 2 , 1, 1)
Process 1 has one scanner (2-1=1).
Process 2 has two tape drives (4-2=2) and a CD-ROM drive (1-1=0). Process 3 has a plotter (2-1=1) and two scanners (1-1=0).
A=(2, 1 , 0, 0)
A=(2, 2 , 1, 0)
26
DDA Example (2)
Each process needs additional resources
P1: 2 Tape drives, 1 CD Rom P2: 1 Tape drive, 1 Scanner P3: 2 Tape drive, 1 Plotter
Execution of deadlock detection algorithm.
we look for a process whose resource request can be satisfied.
The first one cannot be satisfied
because there is no CD-ROM drive available.
The second cannot be satisfied either, because there is no scanner free. the third one can be satisfied, so process 3 runs: A=(0, 0 , 0, 0) After execution eventually returns all its resources
A = (2 2 2 0)
At this point process 2 can run
A = (1 2 1 0)
After execution returns its resources, giving
A= (4 2 2 1)
Now the remaining process can run. There is no deadlock in the system.
27
DDA Structures
P1
P2 P3
28
When to Detect the Deadlock?
One possibility is
to check every time a resource request is made. This is certain to detect them as early as possible,
but it is potentially expensive in terms of CPU time.
An alternative strategy is
to check every k minutes,
or perhaps only when the CPU utilization has dropped below some threshold.
The reason for considering the CPU utilization is
if enough processes are deadlocked, there will be few runnable processes,
and the CPU will often be idle.
29
Recovery from Deadlock
Recovery through Preemption
temporarily take a resource away from its current owner and give it to another process. manual intervention may be required,
in batch processing mainframe operating systems
Recovery through Rollback
arrange to have processes checkpointed periodically write process state to a file
so that it can be restarted later
When a deadlock occurs:
roll back the process to a point an earlier check-point
30
Recovery from Deadlock
Recovery through Killing Processes
The crudest, but simplest way kill one or more processes. Either kill a process in the cycle.
the other processes will be able to continue. If this does not help it can be repeated
until the cycle is broken
or kill a process not in the cycle
to release its resources. the process to be killed is carefully chosen because it is holding resources
that some process in the cycle needs
31
Deadlock Avoidance
The system must be able
to decide whether
granting a resource is safe or not only make the allocation when it is safe.
Question:
Is there an algorithm
can always avoid deadlock by making the right choice all the time?
The answer is:
Yes: we can avoid deadlocks,
but only if certain information is available in advance
32
Deadlock Avoidance Methods
Safe and unsafe states
Safe state: A state which
is not deadlocked and there is some scheduling order
Unsafe state:
Guarantee to run to completion Even if the process request its maximum number of resources immediately
The Bankers Algorithm
the completion is not guaranteed Although it may not result in a deadlock
Extension of deadlock detection algorithm Based on small-town banker
If so grant the request Else reject it
Dealing with a group of customers Check to see if granting credit request is a safe state
33
Safe and Unsafe States-1
Only 10 units are (b) Select B and apply reserved! (c) B completes and frees the States of processes: resources A,B,C (a) A has 3 instances of (d) Select C and apply the resources
B has 2 but need 4 C has 2 but need 7
May need as much as 9
(e) free the resources As a result this is a safe state
34
Safe and Unsafe States-2
States of processes: A,B,C (a) A has 3 instances of the resources
May need as much as 9
B has 2 but need 4 C has 2 but need 7
(b) A request and gets another resource (c) Select B and apply (d) B completes and frees the resources Only 4 free resources and both processes wants 5
35
The Bankers Algorithm
Considers each request as it occurs See if granting resource leads to a safe state.
If it does, the request is granted; otherwise, it is postponed until later.
To see if a state is safe,
the banker checks to see
if he has enough resources to satisfy some customer. If so, those loans are assumed to be repaid. and the customer now closest to the limit is checked
If all loans can eventually be repaid,
the state is safe and the initial request can be granted.
36
The Bankers Algorithm
Four customers A,B,C,& D Total reserved amount is 10 units (a) the reserved amounts for individual customers (b) after using some credits (safe condition) (c) B granted 1 more units of credits (unsafe condition)
37
Deadlock Prevention
1.
Attack the conditions stated for deadlock
Mutual exclusion condition.
Each resource is either
currently assigned to exactly one process or is available.
2. 3.
Hold and wait condition.
Processes currently holding resources granted earlier
can request new resources.
No preemption condition.
Resources previously granted
cannot be forcibly taken away from a process. They must be explicitly released by the process holding them.
4.
Circular wait condition.
There must be a circular chain of two or more processes, each is waiting for a resource held by the next member of the chain.
38
Mutual Exclusion Condition
if no resource were ever assigned exclusively to a single process
we would never have deadlocks.
However, allowing two processes
to write on the printer at the same time will lead to chaos. By spooling printer output,
several processes can generate output at the same time
Not all devices can be spooled
the process table does not lend itself well to being spooled. Furthermore, disk space competition for spooling
an itself lead to deadlock
Principle:
avoid assigning resource when not absolutely necessary as few processes as possible actually claim the resource
39
Hold and Wait Condition
Require processes to request resources before starting
a process never has to wait for what it needs
If everything is available,
the process will be allocated whatever it needs and can run to completion.
If one or more resources are busy,
nothing will be allocated and the process would just wait
Problems
may not know required resources at start of run also ties up resources other processes could be using
Variation:
process must give up all resources then request all immediately needed
40
No Preemption Condition
Attacking the third condition (no preemption)
is even less promising than attacking the second one.
If a process has been assigned the printer
and is in the middle of printing its output, forcibly taking away the printer
because a needed plotter is not available
is tricky at best and impossible at worst.
41
Circular Wait Condition - 1
The circular wait can be eliminated in several ways. One way is simply to have a rule
a process is entitled only
to a single resource at any moment.
If it needs a second one,
it must release the first one.
For a process needs
to copy a huge file from a tape to a printer, this restriction is unacceptable.
42
Circular Wait Condition - 2
provide a global numbering of all the resources The rule is :
processes can request resources
whenever they want to,
A process may request
but all requests must be made in numerical order. first a printer and then a tape drive, but it may not request first a plotter and then a printer. it may be impossible to find an ordering satisfies everyone.
Although numerically ordering the resources eliminates the problem of deadlocks,
43
Circular Wait Condition Summary
Summary of approaches to deadlock prevention
44
Two-Phase Locking
Useful in updating
large number of records in a table
Phase One
process tries to lock all records it needs, one at a time if needed record was locked, start over (no real work done in phase one)
If phase one succeeds, it starts second phase,
performing updates releasing locks
Note: similarity to requesting all resources at once Algorithm works where programmer can arrange
To start program stop and restart later
45
End of Chapter 3
Deadllocks
46
