====== Deadlock =====
Conditions for Deadlock
1. deadlock prevention
2. deadlock avoidance
Prevention
- made some one of the conditions necessary for deadlock don't hold
Avoidance
- OS gets info about what resources a process may require during its lifetime anbased on
this makes decisions about whether immediately grant request or to make a process wait.
Prevention
----------
1. Mutual Exclution
- some resources sharable e.g. reading files.
- some resources intringsically not sharable.
* CAN NOT prevent deadlock by preventing the mutual exclusive condition.
2. Hold and wait
- make process request all the resources it needs at the start.
- cons:
- resource utilization.
- let a process request a resources only if it holds none.
- cons: starvation
3. No Preemption (of already allocated resoruces)
- protocal 1
P holds R1.....Rn, requests Rm;
Rm not available
resources held (R1...Rn) are implicitely released.
P now waiting for R1...Rn,Rm, resumes when they are available
- protocal 2
P requests R1,...Rn
if available,
P gets them
else if they are allocated to another process P2 that is waiting for other resources,
then they are taken from P2 and gien to P
else not availabe & not allocated to processes waiting on something
P waits.
while P waits some of its resources may be preempted.
4. Circular Wait
- Define a total order > on the resource types
F:R -> N
- Protocal 1
Process request resources in increasing order
- request instances of Ri (all needed instances at once)
- later request Rj only if F(Rj) > F(Ri)
- Protocal 2
Before Rj requested process must release all instances of Ri s.t. F(Ri) >= F(Rj)
NEVER holding resources numbered higher than the ones ???? requesting
then no circular wait.
Deadlock Avoidance
-------------------
- use information about a process's possible future resource use.
- OS gets info about max # of (instances of each) resource-type that a process needs.
Algorithm looks at resource allocation stat to avoid circular conditions.
- resource allocation state = f(# of availabe resources,
# of allocated resources,
max possible demands of the processes)
Safe State
-----------
- if the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock,
i.e. if there exists a safe sequence (of processes)
sequence <P1,P2,Pi,..Pn> is a safe sequence for the currenct allocation state,
if for each Pi the resources that Pi can still request
can be satisfied by
- currently available resources and
- resources held by all Pj, j<i
(P1 can request all availabe resources because no resources is held.
P2 can request all avilable resources + resources held by P1.
etc......)
Example.(P.257)
12 units of resources
Processes P0, P1, P2
Process Max Needs Cuurent Allocated
====== ========= =================
P0 10 5
P1 4 2
P2 9 2
--------
3 available
System IS in a safe state
safe sequence: <P1, P0,P2>
P1, : needs 2 more resources (that can be get from available resources)
P0: needs 5, = 3 free + 2 held by P1
P2: needs 7, = 3 free + 2 from P1 + 5 from P0
Go from safe to unsafe:
P2 request and is allocated 1 more unit
Process Max Needs Cuurent Allocated
====== ========= =================
P0 10 5
P1 4 2
P2 9 3
--------
2 available
any sequence must start with : P1 needs 2 more resources
<P1, P0
P1: needs 2 = 2 free
P0: needs 5 > 2 free + 2 from P1
OR <P1, P2
P1: needs 2 = 2 free
P2: needs 6 > 2 free + 2 from P1
So system won't immediately grant P2's request
Resource Allocation from Graph algorithm (See notes on paper)
- for 1 instance per resource
- resource use (max) known in advance
- reqeust edge
Banker's Algorithm
------------------
extension of safe state idea
- n processes in resources
- data structure used
available
0 m-1
-------------------------------------
| | | | | | | | | | # of units of each resource still unallocated.
-------------------------------------
max
------------------------------------
i |___________________________________|
|___________________________________|
n |___________________________________|
max(i,j) max # of units of resource j needed by process i
alloc
m
------------------------------------
|___________________________________|
|___________________________________|
n |___________________________________|
alloc(i,j) process i currently holding this many units of resource j
Need : "could still need"
m
------------------------------------
|___________________________________|
|___________________________________|
n |___________________________________|
need(i,j): # of units of resources j that may still be needed by process i
need = max - alloc
ResourceTotal
0 m-1
-------------------------------------
| | | | | | | | | | # of units of each resource still unallocated.
-------------------------------------
avail[j] = resourceTotal[j] - Sum(alloc[ij])
Safety Algorithm
----------------
See if there is an order of processes(safe sequence) Pi0, Pi1.... where we can do the following:
1. satifsy the outstanding need of process Pi0 with unused resources which is available only.
2. consider Pi0 finished and rturn its resources.
3. repeat for Pi1, Pi2, ... etc.
Notes: if there is more than one candidate for Pi0, it does NOT matter which one you choose.
Example:
4 resources R0,R1,R2,R3
5 processes: P0,P1,P2,P3,P4
resourceTotal
R0 R1 R2 R3
---------------------------------
| 8 | 5 | 9 | 1 |
---------------------------------
Max:
-------------------------------------
| R0 | R1 | R2 | R3 |
-------------------------------------
P0 | 3 | 2 | 1 | 4 |
-------------------------------------
P1 | 0 | 2 | 5 | 2 |
-------------------------------------
P2 | 5 | 1 | 0 | 5 |
-------------------------------------
P3 | 1 | 5 | 3 | 0 |
-------------------------------------
P4 | 3 | 0 | 3 | 3 |
-------------------------------------
Alloc
-------------------------------------
| R0 | R1 | R2 | R3 |
-------------------------------------
P0 | 2 | 0 | 1 | 1 |
-------------------------------------
P1 | 0 | 1 | 2 | 1 |
-------------------------------------
P2 | 4 | 0 | 0 | 3 |
-------------------------------------
P3 | 0 | 2 | 1 | 0 |
-------------------------------------
P4 | 1 | 0 | 3 | 0 |
-------------------------------------
Total| 7 | 3 | 7 | 5 |
-------------------------------------
NEED:
-------------------------------------
| R0 | R1 | R2 | R3 |
-------------------------------------
P0 | 1 | 2 | 0 | 3 |
-------------------------------------
P1 | 0 | 1 | 3 | 1 |
-------------------------------------
P2 | 1 | 1 | 0 | 2 |
-------------------------------------
P3 | 1 | 3 | 2 | 0 |
-------------------------------------
P4 | 2 | 0 | 0 | 3 |
-------------------------------------
NEED = MAX - ALLOC
---------------------------------
| R0 | R1 | R2 | R3 |
---------------------------------
ResourceTotal | 8 | 5 | 9 | 7 |
---------------------------------
TotalAlloc | 7 | 3 | 7 | 5 |
---------------------------------
Avail | 1 | 2 | 2 | 2 |
---------------------------------
1. Find need[i] such that avail >= need[i]
- only P2
2. consider P2 done return its resources
change Avail: = Avial + alloc
(alloc, NOT need)
---------------------------------
Avail | 5 | 2 | 2 | 5 |
---------------------------------
P2 DONE.
3. back to 1. Find another satisfiable Process
- P0 or P4
4. consider P0 (arbitrarily) done + its resources returnd.
- change avail
---------------------------------
Avail | 7 | 2 | 3 | 6 |
---------------------------------
P0 done
5. find next satisfiable process.
- P1 or P4
6. Consider P1 done, return its resources
---------------------------------
Avail | 7 | 3 | 5 | 7 |
---------------------------------
7. remaining processes P3, P4 satisfiable.
State IS SAFE.
State safe. Now comes a request from P3 for 1 unit of R0.
i.e. P3 requests <1,0,0,0>
Consider request by temprorily changing the allocation to reflect granting request.
Alloc
-------------------------------------
| R0 | R1 | R2 | R3 |
-------------------------------------
P0 | 2 | 0 | 1 | 1 |
-------------------------------------
P1 | 0 | 1 | 2 | 1 |
-------------------------------------
P2 | 4 | 0 | 0 | 3 |
-------------------------------------
P3 | 1 | 2 | 1 | 0 |
-------------------------------------
P4 | 1 | 0 | 3 | 0 |
-------------------------------------
Total| 8 | 3 | 7 | 5 |
-------------------------------------
NEED:
-------------------------------------
| R0 | R1 | R2 | R3 |
-------------------------------------
P0 | 1 | 2 | 0 | 3 |
-------------------------------------
P1 | 0 | 1 | 3 | 1 |
-------------------------------------
P2 | 1 | 1 | 0 | 2 |
-------------------------------------
P3 | 0 | 3 | 2 | 0 |
-------------------------------------
P4 | 2 | 0 | 0 | 3 |
-------------------------------------
---------------------------------
| R0 | R1 | R2 | R3 |
---------------------------------
ResourceTotal | 8 | 5 | 9 | 7 |
---------------------------------
TotalAlloc | 8 | 3 | 7 | 5 |
---------------------------------
Avail | 0 | 2 | 2 | 2 |
---------------------------------
So avail is 0, 2 ,2 ,2
What can be first process in safe sequence??
- NO process
- So NO Safe Sequence
------------------------------
This means granting P3's request would put the system into an unsafe state,
Must wait to satisfy request.
------------------------------
Aside. A request by P3 for 2 units of R0 would exceeds system resources.
No comments:
Post a Comment