L-4.2: Resource Allocation Graph in Deadlock | Single Instance with example | Operating System

Summary

The video explains how a Resource Allocation Graph (RAG) represents the resources processes hold and the resources they request. It focuses on systems where each resource type has a single instance and shows how to determine whether a deadlock exists.

RAG components and notation

• Process vertices are drawn as circles.
• Resource vertices are drawn as rectangles.
• Resources may have one or multiple instances; the video’s examples use single-instance resources.
• Edges show allocations or requests:
  • Allocation edge: resource → process. The process currently holds that resource.
  • Request edge: process → resource. The process is waiting for that resource.

Example 1: Deadlock

• P1 holds R1 and requests R2.
• P2 holds R2 and requests R1.
• Neither process can proceed until the other releases its resource. Since each is waiting, neither can release its resource.
• The graph contains a cycle: R1 → P1 → R2 → P2 → R1.
• This is a deadlock.

The video also demonstrates a table-based check:

1. Record each process’s allocated resources.
2. Record each process’s outstanding requests.
3. Record the currently available resources.
4. Check whether any process’s request can be met with the available resources.
5. If a process can finish, assume it terminates and returns its allocated resources to availability.
6. Repeat. If no remaining process can proceed, those processes are deadlocked.

In Example 1, no resources are available, and neither process’s request can be met, confirming the deadlock.

Example 2: No deadlock

• P1 holds R1 but has no outstanding request.
• P2 holds R2 but has no outstanding request.
• P3 requests one instance each of R1 and R2.
• P1 and P2 can finish and release their resources. The available resources can then satisfy P3’s request, allowing it to finish as well.
• Therefore, the graph does not represent a deadlock.

Key rule for single-instance resources

For a RAG in which every resource has exactly one instance:

A cycle exists if and only if a deadlock exists.

If there is no cycle, there is no deadlock. This rule applies specifically to the single-instance case; the video notes that multiple-instance resources are covered separately.

Terminology note

The lecture describes finite waiting as “starvation,” but this is not the standard definition. Starvation generally means a process may be postponed indefinitely while other processes continue to make progress. Deadlock involves processes that cannot proceed because they are waiting on one another.

The subtitles also contain a contradictory line suggesting that P1 and P2 in Example 2 wait indefinitely, even though the example’s reasoning shows they can finish and release their resources.

Speakers and sources

• Speaker: Varun (“Varun sir”), the lecturer identified in the video metadata.
• Source: Gate Smashers video on Resource Allocation Graphs and single-instance deadlock examples.