Tuesday, Jun 27th

Last update12:59:40 PM GMT

Deadlock Avoidance using Resource-Allocation Graph

Write e-mail

Avoid the Deadlock


A very good way of Deadlock avoidance is using directed graphs called a System Resource-Allocation Graph.

The R-A-G consists of a set of nodes:

P= {P1, P2, P3,...} denoting set of active processes in the system

R= {R1, R2, R3,..} denoting set of available resources in the system (resource instances)

  • The directed edge from Rj to Pi is called an assignment edge signifying process Pi is resource Rj is currently allocated to process Pi.
  • The directed edge from Pi to Rj is called an request edge signifying process Pi is waiting for resource Rj.

Here I will waste no time in saying as it can be deduced easily from the above R-A-G that if a R-A-G contains no cycles, then we can be sure no deadlock exists in the system for any of the active processes. However, if a cycle exists, then we can say that a deadlock will exist.

Please not here when we say Rj it means a resource instance and not set of resources instances.

If Rj comprises of a set of resource instances of type Rj, then presence of a cycle will indicate that a deadlock MAY be existing in the system.

Now coming back to our assumption of one resource instance of each type, we can extend the RAG to a variant graph that can be used for deadlock avoidance.

In the above RAG we further introduce a claim edge.

  • A claim edge Pi --> Rj indicates that Process Pi may be requesting the resource Rj sometime in future.
  • This edge is shown similar to request edge but is represented  by a dashed line.
  • When a resource is requested the claim edge gets converted to request edge.
  • When a resource is released by a process, the assignment edge gets reconverted to claim edge.
  • It is necessary to first claim a resource before requesting it.

We know presence of a cycle in system means that the system is in unsafe state. Hence we say, that a resource is not granted to a process if on allocation of resource to that process results in the formation of a cycle, that is, system entering into an unsafe state.

In the below figure:


Even though the resource R2 is free we still cannot allocate R2 to P2 as P1 might be requesting it as well in near future. Hence allocation of R2 to P2  at this stage will result in the formation of a cycle.











Share this post

Add comment

Please refrain from using slang or abusive language in the comments.
To avoid waiting for your comment to be published after being reviewed, please log in as a registered user.

Security code

Web Hosting