<aside> 💡

Summary of Section 6.1: A System Model for Deadlocks

</aside>

Resource Allocation Graphs

• A system consists of hardware and software resources used by processes.
• Resources are categorized as:
  • Reusable resources: Can be requested, acquired, and released (e.g., processors, memory, files).
  • Consumable resources: Created and consumed (e.g., messages, signals).
• Resource Allocation Graphs (RAGs):
  • Processes are represented as circles.
  • Resources are represented as rectangles, with units shown as small circles.
  • Edges:
    • Allocation edges: From a resource to a process (indicating ownership).
    • Request edges: From a process to a resource (indicating demand).
  • A process blocks on a resource when it requests it but there are insufficient free units.

Modeling Deadlocks

• A resource contains one or more units that processes use non-shared.
• Deadlock occurs when at least two processes hold one resource each while requesting another resource, leading to an indefinite wait.
• Example of deadlock:
  • Process p1 acquires r1.
  • Process p2 acquires r2.
  • Process p1 requests r2, and p2 requests r1, causing a cycle.

Conditions for Deadlock

• Deadlock can only occur when:
  • There are two or more processes and two or more resources.
  • The order of requests leads to circular waiting.

State Transitions in Resource Allocation Graphs

• Request Operation (req r, m): Process requests m units of resource r.
• Acquire Operation (acq r, m): If enough units are available, request edges are reversed into allocation edges.
• Release Operation (rel r, m): Process releases m units, deleting allocation edges.
• These transitions modify the state of the system.

Deadlock and Safe States

• A deadlocked process remains blocked indefinitely.
• A deadlock state contains two or more deadlocked processes.