Loading learning content...
If request edges represent desire, assignment edges represent possession. An assignment edge in a Resource Allocation Graph is a definitive statement: this specific resource instance belongs to this process, right now.
Assignment edges are the foundation of the 'hold' in 'hold and wait'—one of the four necessary conditions for deadlock. They record which processes have locked which resources, creating the ownership map that, when combined with request edges, can reveal circular dependencies.
This page examines assignment edges in depth: their precise semantics, how they originate from specific resource instances, their lifecycle from allocation to release, and their critical role in completing the picture needed for deadlock analysis.
By the end of this page, you will understand: assignment edge semantics and the instance-to-process mapping, the creation path during resource grants, removal during resource release, the relationship between assignment and request edges, and how assignment edges complete deadlock cycles.
An assignment edge Rⱼ → Pᵢ carries specific meaning that complements request edges:
Formal Definition:
An assignment edge (Rⱼ, Pᵢ) ∈ E indicates that one instance of resource type Rⱼ is currently allocated to and held by process Pᵢ.
Semantic Implications:
Exclusive ownership — That specific instance is not available to any other process
Process has control — Pᵢ can use the resource; it will not be taken away without Pᵢ's cooperation (no preemption)
Duration — The edge persists from grant until explicit release by Pᵢ or process termination
Instance specificity — For multi-instance resources, the edge indicates which specific instance is held
Visual Representation:
In RAG diagrams, assignment edges originate from the dot inside the resource rectangle (representing the specific instance) and point to the process circle. This distinguishes them from request edges, which point to the rectangle boundary.
Direction Significance:
The direction R → P is intentional: it shows the resource "flowing to" or "being held by" the process. Combined with request edges (P → R), we get the alternating pattern that enables cycle detection through the bipartite graph.
| Property | Description | Contrast with Request Edge |
|---|---|---|
| Direction | R → P (resource to process) | P → R (process to resource) |
| Visual origin | Dot inside rectangle (instance) | Arrow to rectangle boundary |
| Semantic meaning | Ownership/holding | Desire/waiting |
| Process state | May be RUNNING or BLOCKED | Always BLOCKED (on something) |
| Creation | At grant/allocation time | At request/block time |
| Removal | At release time | At grant, timeout, or cancel |
Assignment edges are created when a resource instance is granted to a process. Two primary scenarios exist:
Scenario 1: Immediate Grant (Fast Path)
When a process requests a resource and an instance is immediately available:
Scenario 2: Deferred Grant (Wake-Up Path)
When a process was blocked waiting and now receives the resource:
The Edge Transition:
Note the elegant symmetry: a request edge transforms into an assignment edge when the request is satisfied. The edges are duals:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475
/** * Assignment Edge Creation Scenarios */ /* Scenario 1: Immediate grant - resource available */int resource_acquire_immediate(struct resource *res, struct task_struct *task){ int instance_id = -1; spin_lock(&res->lock); /* Find available instance */ for (int i = 0; i < res->num_instances; i++) { if (res->instances[i].holder == NULL) { instance_id = i; break; } } if (instance_id < 0) { spin_unlock(&res->lock); return -EAGAIN; /* No instance available */ } /* Mark instance as held */ res->instances[instance_id].holder = task; res->available--; /* Create assignment edge: R[instance] -> P */ rag_add_assignment_edge(res, instance_id, task); spin_unlock(&res->lock); return 0; /* Success */} /* Scenario 2: Deferred grant - unblocking a waiter */void resource_release_and_grant(struct resource *res, int instance_id){ struct task_struct *waiter; spin_lock(&res->lock); /* Clear current holder */ struct task_struct *old_holder = res->instances[instance_id].holder; res->instances[instance_id].holder = NULL; /* Remove old assignment edge */ rag_remove_assignment_edge(res, instance_id, old_holder); /* Check for waiters */ waiter = dequeue_first_waiter(&res->waiters); if (waiter) { /* Grant to waiter: transition request -> assignment */ /* Remove the request edge */ rag_remove_request_edge(waiter, res); /* Assign instance to waiter */ res->instances[instance_id].holder = waiter; /* Create new assignment edge */ rag_add_assignment_edge(res, instance_id, waiter); /* Wake the waiter */ wake_up_process(waiter); } else { /* No waiters - just increment available */ res->available++; } spin_unlock(&res->lock);}For multi-instance resources, it's important to track which specific instance is assigned. This enables precise RAG visualization where each dot can independently have an outgoing assignment edge. Some implementations simplify by only tracking counts, losing instance-level granularity.
Assignment edges are removed when a process relinquishes ownership of a resource. This can happen voluntarily or involuntarily.
Voluntary Release:
The normal case—a process explicitly releases a resource:
Involuntary Release (Process Termination):
When a process terminates, all its held resources must be released:
Forced Preemption (Rare):
For preemptible resources (like CPU time or certain memory), the OS may forcibly remove resources. This involves:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182
/** * Assignment Edge Removal Scenarios */ /* Voluntary release by process */void resource_release(struct resource *res, struct task_struct *task){ int instance_id = -1; spin_lock(&res->lock); /* Find which instance this task holds */ for (int i = 0; i < res->num_instances; i++) { if (res->instances[i].holder == task) { instance_id = i; break; } } if (instance_id < 0) { /* Error: task doesn't hold this resource */ spin_unlock(&res->lock); return; } /* Remove assignment edge */ rag_remove_assignment_edge(res, instance_id, task); /* Mark instance as available */ res->instances[instance_id].holder = NULL; /* Try to grant to a waiter */ struct task_struct *waiter = dequeue_first_waiter(&res->waiters); if (waiter) { rag_remove_request_edge(waiter, res); res->instances[instance_id].holder = waiter; rag_add_assignment_edge(res, instance_id, waiter); wake_up_process(waiter); } else { res->available++; } spin_unlock(&res->lock);} /* Involuntary release during process exit */void cleanup_process_resources(struct task_struct *dying_task){ struct held_resource *hr, *tmp; /* Iterate over all resources held by dying process */ list_for_each_entry_safe(hr, tmp, &dying_task->held_list, list) { struct resource *res = hr->resource; int instance_id = hr->instance_id; spin_lock(&res->lock); /* Remove assignment edge */ rag_remove_assignment_edge(res, instance_id, dying_task); /* Release the resource */ res->instances[instance_id].holder = NULL; /* Grant to waiter if any */ struct task_struct *waiter = dequeue_first_waiter(&res->waiters); if (waiter) { rag_remove_request_edge(waiter, res); res->instances[instance_id].holder = waiter; rag_add_assignment_edge(res, instance_id, waiter); wake_up_process(waiter); } else { res->available++; } spin_unlock(&res->lock); /* Remove from held list */ list_del(&hr->list); kfree(hr); }}If a process terminates without the kernel properly cleaning up its held resources, assignment edges remain in the RAG pointing to a non-existent process. This corruption can cause false positives in deadlock detection or, worse, make resources permanently unavailable. Robust kernels always clean up on process exit.
Multi-instance resources add complexity to assignment edge handling. A single resource type may have multiple simultaneous assignment edges to different processes.
Instance Identification:
For a resource R with k instances, we can think of it as having k "slots" that can each have an assignment edge:
Instance Fungibility:
In many systems, instances are fungible—interchangeable. A process requesting "one instance of R" doesn't care which specific instance (0, 1, or 2) it receives. The resource manager can assign any available instance.
Instance-Specific Resources:
Some resources have non-fungible instances:
For these, processes may request specific instances, affecting which assignment edges can form.
| Resource State | Available | Assignment Edges | Can Satisfy Request? |
|---|---|---|---|
| R has 3 instances, none allocated | 3 | None | Yes, any instance |
| R has 3 instances, 2 allocated | 1 | R[0]→P₁, R[1]→P₂ | Yes, R[2] |
| R has 3 instances, all allocated | 0 | R[0]→P₁, R[1]→P₂, R[2]→P₃ | No, must wait |
| R has 3 instances, P₁ holds 2 | 1 | R[0]→P₁, R[1]→P₁ | Yes, R[2] |
Impact on Deadlock Detection:
With multi-instance resources, cycle detection alone is insufficient for deadlock determination. Consider:
There's potentially a cycle involving P₁'s request, but P₂ can complete and release R[1], satisfying P₁. The cycle is not a deadlock because it can be broken.
For multi-instance resources, algorithms like graph reduction or the Banker's safety algorithm must verify whether any execution sequence can satisfy all processes.
Assignment edges complete the circular wait pattern that defines deadlock. Let's trace how cycles form.
The Cycle Anatomy:
A deadlock cycle in a RAG alternates between edge types:
P₁ → R₁ → P₂ → R₂ → P₁
Each process in the cycle:
The Hold-and-Wait Pattern:
Notice that each process in a deadlock cycle exhibits 'hold and wait':
Without assignment edges (nothing held), there's no circular wait—waiting processes don't block each other.
Without request edges (nothing wanted), there's no waiting—each process can proceed independently.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
def trace_deadlock_cycle(rag, start_process: str) -> list: """ Trace a potential deadlock cycle starting from a process. Returns the cycle as alternating [P, R, P, R, ...] if found. """ cycle = [] visited_processes = set() current = start_process while True: if current in visited_processes: # Found cycle - extract the cycle portion cycle_start = cycle.index(current) return cycle[cycle_start:] visited_processes.add(current) cycle.append(current) # Find what this process is requesting (request edge) process = rag.processes[current] requested = list(process.requested_resources.keys()) if not requested: return [] # No request - no cycle from here resource = requested[0] # Follow first request cycle.append(resource) # Find who holds this resource (assignment edge) resource_obj = rag.resources[resource] holders = list(resource_obj.allocated_instances.keys()) if not holders: return [] # Resource available - no blocking # Follow assignment edge to holder current = holders[0] if current == start_process: cycle.append(current) return cycle # Completed cycle! def describe_cycle(cycle: list) -> str: """Generate human-readable cycle description.""" if not cycle: return "No cycle detected" parts = [] for i in range(0, len(cycle) - 1, 2): process = cycle[i] resource = cycle[i + 1] next_process = cycle[i + 2] if i + 2 < len(cycle) else cycle[0] parts.append( f"{process} --[wants]--> {resource} " f"--[held by]--> {next_process}" ) return "".join(parts) # Example deadlock cycledef demonstrate_deadlock_cycle(): rag = ResourceAllocationGraph() rag.add_process("P1") rag.add_process("P2") rag.add_resource("R1", 1) rag.add_resource("R2", 1) # Create classic deadlock rag.add_assignment_edge("R1", "P2") # P2 holds R1 rag.add_assignment_edge("R2", "P1") # P1 holds R2 rag.add_request_edge("P1", "R1") # P1 wants R1 rag.add_request_edge("P2", "R2") # P2 wants R2 cycle = trace_deadlock_cycle(rag, "P1") print("Cycle:", cycle) print(describe_cycle(cycle)) # Output: # Cycle: ['P1', 'R1', 'P2', 'R2', 'P1'] # P1 --[wants]--> R1 --[held by]--> P2 # P2 --[wants]--> R2 --[held by]--> P1Together, assignment and request edges provide a complete representation of resource allocation state. They are complementary abstractions that, when combined, reveal the dependencies that can cause deadlock.
Request and assignment edges are duals: when a request is satisfied, the request edge transforms into an assignment edge. The edge 'flips direction' as the relationship changes from 'wanting' to 'having'. This transformation is at the heart of resource state transitions.
You now understand assignment edge semantics, their lifecycle, and how they combine with request edges to form deadlock cycles. Next, we'll explore cycle detection algorithms that operate on these graph structures.