Resource Allocation Graph

In multiprogramming system, when a waiting process is never able to get resources to complete its execution because the resources it has requested are held by another waiting process. This situation is called deadlock. This process can not proceed because of cyclic waiting of resources.


Resource Allocation Graph (RAG):

Resource allocation graph (RAG) is used for recognize deadlock situation in the system. RAG is directed graph which consist of set of vertices that represents processes (P = {P1, P2, … , Pn}), also resources (R = {R1, R2, … , Rn}) and set of directed edges that represents resources requests (P1 → R1, P2 → R3) and allocations in the system (R2 → P1, R1 → P1, R3 → P4).

Each process utilizes a resource using request, use and release. Each resource type Ri has Wi instances.

When a process request a resource; it is made through a system call. If resource is not available or it held by another process, then process must have to wait for resource. A process releases the resources through system call. Process can use a resource if it is available to use.


Processes always represented with circles and resources represented with rectangles in RAG as following:




RAG when a process request a resource:




RAG when an instance of a resource allocated to a process: