In a multiprocessing operating system, various processes execute simultaneously. However, the number of resources is limited. So the processes have to compete with each other to acquire these resources. The resources could be anything from a memory space to a file or even an I/O device (printer, disk driver etc.). If a resource is not available to a process, the process has to wait. This situation can be easily extended in real life as well.
Fig.1
In Fig.1, think of Bob and Jack as processes and the ball as the resource. If we assume that only one can play with the ball at a time, Bob has to wait for Jack to finish playing. This is a normal situation where both Bob and Jack (processes) get to play with ball (utilize the resource).
Deadlock occurs when a set of processes are waiting for resources which are held by other processes in the same set. Thus, each of the processes in the set is blocked since it cannot proceed further without resources.
Fig.2
Consider another classic example of a deadlock. In Fig.2, neither of the cars can proceed further since the resource (the road) needed by each of them is occupied by the other. The deadlock can be resolved only when one car backs up. Thus there has to be some kind of understanding between the processes to ensure that each one of them can use the resources without getting blocked.
Resource Allocation Graph
Fig. 3 Resource Allocation Graph
Fig. 3 shows an example of a resource allocation graph (RAG). RAG is a graphical representation depicting the resources held by or requested by processes. It helps us to decide whether a given situation might result in a deadlock or not.
The following is a set of vertices in a RAG:
- P = {P1, P2, ….Pn} is a set of all active processes (circle).
- R = {R1, R….Rm} is a set of all resource types (rectangle).
Notice that R is a set of resource types and not resources since there can be many instances of one resource type (like multiple printers etc.). The instances are represented by a dot(or an asterix) in the rectangles.
The following is a set of edges in a RAG:
- Request Edge (Pi—–>Rj) : A directed edge signifying that process Pi is waiting for an instance of resource Rj.
- Assignment Edge (Rj—–>Pi) : A directed edge signifying that an instance of resource Rj has been allocated to process Pi.
When a process requesting a resource is granted that resource, the request edge transforms into an assignment edge, consistent with the definition of RAG.
In the above example, P1, P2, P3 are processes and R1, R2, R3, R4 are available resource types having 1, 2, 1 and 3 instances respectively. P1 is holding R2 and waiting for R1, and so on with the other resources.
Rule:
If the RAG contains no cycles, then no processes are in deadlock.
If each resource type has exactly one instance, then a cycle implies deadlock.
If a resource has more than one instance, then a cycle may imply deadlock.
Fig. 4 Cycles in a RAG
In Fig.4a, there is a cycle R1->P2->R2->P1->R1. Each process holds one resource and waits for another. Here P1, P2 are in a deadlock, since neither of the processes will release a resource until it acquires the resource held by the other process.
In contrast, in Fig.4b, R2 has 2 instances and R1->P3->R2->P1->R1 form a cycle. However, when process P4 releases an instance of R2, it becomes available to P1. The request edge is reversed as it becomes an assignment edge and the graph does not contain a cycle anymore. This is an example where a cycle does not result into a deadlock when a resource has more than one instance.
Handling Deadlock
A deadlock is handled by the operating system in 3 ways:
- Preventing or avoiding the deadlock: The OS ensures that none of the processes ever enter a deadlock state.
- Detecting the deadlock: The system is allowed to enter a deadlock state. The deadlock is detected and recovered.
- Ignoring the deadlock: Pretend that deadlock never happens!
Various algorithms have been formulated to prevent or detect a deadlock in a system. However the operations are expensive, and hence most operating systems adopt the third approach of ignoring a deadlock.
Exercise: Examine whether the system is in deadlock.
You can post your answers in the form of comments.
