Resource-Allocation Graph

A set of vertices V and a set of edges E.

• V is partitioned into two types:
  =>FP = {P1, P2, …, Pn}, the set consisting of all the processes in the system.
  =>FR = {R1, R2, …, Rm}, the set consisting of all resource types in the system.
• request edge – directed edge P1 ® Rj.
• assignment edge – directed edge Rj ® Pi
  

Resource-Allocation Graph Algorithm

• Claim edge Pi ® Rj indicated that process Pj may request resource Rj; represented by a dashed line.
• Claim edge converts to request edge when a process requests a resource.
• When a resource is released by a process, assignment edge reconverts to a claim edge.
• Resources must be claimed a priori in the system.
  

Resource-Allocation Graph and Wait-for Graph

Resource-Allocation Graph Corresponding wait-for graph

How did you know if there is a deadlock based on a resource allocation graph?

• In a multiprogramming system, processes request resourceused by other processes then the process enters a processes are also in a waiting state, we have deadlock.

Example of a Resource Allocation Graph


Resource allocation graphs are drawn in order to see the allocatioand resources easily. In these graphs, processes are represented are represented by boxes. Resource boxes have some number available number of that resource, that is number of instances.

• If the resource allocation graph contains no cycles then there is no deadlock in the system at that instance.
• If the resource allocation graph contains a cycle then a deadlock may exist.
• If there is a cycle, and the cycle involves only resources which have a single instance, then a deadlock has occurred.






Resource Allocation Graph With A Deadlock


*In addition to the request and assignment edges, a claim edge is also introduced.
*Claim edge Pi ® Rj indicated that process Pj may request resource Rj in future; represented by a dashed line.
*Claim edge converts to request edge when a process requests a resource.
*When a resource is released by a process, assignment edge reconverts to a claim edge.
*Resources must be claimed a priori in the system. That is, before a process starts executing, all of its claim edges must already appear in the resource-allocation graph.
*Suppose that process Pi requests resource Rj. The request can be granted only if converting the request edge if converting the request edge Pi®Rj to an assignment edge does not result in a cycle in the resource-allocation graph. That is we use a cycle detection algorithm is used. If no cycle exits, the process Pi will have to wait.

Resource Allocation Graph With A Cycle But No Deadlock

*2 resources "R1, R2"
*4 processes "P1, P2, P3, P4"
*P1 and P3 is requesting a process to R1 and R2 respectively.
*P2 and P3 holds an instance of R1
*P1 and P4 holds an instance of R2
*There is no DeadLock













Resource-Allocation Graph For Deadlock Avoidance


The Resource Allocation Graph (RAG) is composed of 2 processes and 2 resources.
· P1 holds an instance of R1
· P2 requests an instance of R1
· P1 and P2 may request an instance of R2

Unsafe State In Resource-Allocation Graph


*the graph shows that R1 is holding the instances of P1, then P1 is requesting for a resource in R2, then R2 is holding the instances of P2 and P2 is requesting instance of R1.

Methods for Handling

Deadlock

• Prevent
– write code such that the necessary conditions can
never hold simultaneously
• Avoid
– dynamically ensure that a deadlock state is not
reachable.
• Detect and recover
– allow deadlock but provide mechanisms to detect
it and recover (e.g., kill a process)
• Ignore (ostrich approach)
pretend they cannot occur and reboot if they do.

Deadlock Prevention

• Disallow one of the four necessary conditions for deadlock
• Preventing deadlocks by constraining how requests for resources can be made in the system and how they are handled (system design).
• The goal is to ensure that at least one of the necessary conditions for deadlock can never hold.

Deadlock Detection

• Always grant resource request when possible. Periodically check for deadlocks. If a deadlock exists, recover from it.

Deadlock Recovery

• Abort all deadlock processes and release resource - too drastic - will lead to loss of work.
• Abort one process at a time - releasing resources until no deadlockHow do we determine which process to abort first ? - priority ordering, process which has done least work.
• Selectively restart processes from a previous checkpoint i.e. before it claimed any resources difficult to achieve - sometimes impossible.
• Successively withdraw resources from a process and give to another process until deadlock is broken. How to choose which processes and which resources ?

1. Complex decisions due to the large number of processes present within a system.
2. Difficult to automate.
3. Use Operator to resolve conflicts - BUT this requires the operator to have skill and understanding of what processes are actually doing.

Deadlock Characterization

Necessary conditions:

1) Mutual exclusion:
• at least one shared resource is held
2) Hold and wait:
• a process must be holding at least one resource and
waiting for another
3) No preemption:
• cannot steal a resource away from a process
4) Circular wait:
• E.g., A is waiting for B who is waiting for C who is
waiting for A.