Deadlock and Resource Allocation Graphs

Overview

Lecture explains deadlock system model using Resource Allocation Graphs (RAG).
Reviews four necessary conditions for deadlock and how RAG represents processes, resources, requests, and assignments.
Includes an example with processes P1, P2, P3 and resources R1–R4 drawn as a RAG.
Algorithmic detection of deadlock from the graph is referenced and continued in a later lecture.

Mutual Exclusion
- Some resources are nonshareable; only one process can use them at a time.
- Example: a printer can be used by only one process; others wait.
Hold and Wait
- A process holds at least one resource while waiting to acquire additional resources.
- Example: P1 holds R1 and waits for R2, which is held by P2.
No Preemption (Voluntary Release)
- Resources cannot be forcibly taken; the holding process must release them voluntarily after use.
Circular Wait
- A circular chain exists where each process requests a resource held by the next process.
- Example: P1 requests R2 held by P2; P2 requests R1 held by P1, forming a cycle.

Graph components
- Vertex set V divided into processes (P) and resources (R).
- Processes depicted as circles; resources as rectangles.
- Resource instances shown as dots inside resource rectangles.
Edges
- Request edge: directed from process to resource (P → R).
- Assignment edge: directed from resource to process (R → P).
Resource instances
- A resource may have multiple identical instances (e.g., R2 with two instances).
- Each instance can be assigned to at most one process at a time.
- If resource has multiple instances, multiple assignment dots/edges represent that capacity.

Given sets
- Processes: P1, P2, P3.
- Resources: R1, R2, R3, R4.
Notation used in drawing
- r1(1) means R1 has one instance; r2(2) means R2 has two instances, etc.
- Request edges drawn from processes to required resources.
- Assignment edges drawn from resource instances to the processes currently holding them.
Specifics described
- P1 → R1 (P1 requests R1).
- P2 → R3 (P2 requests R3).
- Resource R1 has an assignment edge to P2 (R1 → P2) in the example.
- R2 has two instances; edges show one instance assigned to P2 and the other can be assigned to P1.
- R3 and R4 instances are included; R4 has instances but no current connections to processes.
Graph completeness
- All resource nodes must be represented even if currently unconnected.
- Arrow directions must not intersect in the drawing to keep clarity.

Term	Definition
Process (P)	Active entity requesting and holding resources (depicted as a circle).
Resource (R)	Passive entity to be requested/held (depicted as a rectangle).
Instance (dot)	Individual unit of a resource; multiple dots = multiple instances.
Request Edge (P → R)	Indicates a process is requesting a resource.
Assignment Edge (R → P)	Indicates a resource instance is allocated to a process.
Mutual Exclusion	Resource can be used by only one process at a time.
Hold and Wait	Process holds resources while waiting for others.
No Preemption	Resources released only voluntarily by holding process.
Circular Wait	Cycle of processes each waiting for a resource held by next.

A deadlock can occur if all four conditions hold simultaneously.
In RAGs, presence of a directed cycle often indicates potential deadlock when each involved resource has only one instance.
For resources with multiple instances, a cycle in the graph does not always imply deadlock; instance counts matter.
Specific detection algorithm discussion (how to decide deadlock from the provided graph) is deferred to the next lecture.

Review how to detect deadlock from RAGs when resources have multiple instances.
Study the Banker's Algorithm (previous video) as another deadlock handling method.
Follow-up lecture will continue the RAG deadlock detection algorithm and examples.