Question 4 of 7

Question 4 (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) A cycle is necessary but not sufficient for deadlock in general. If every resource type in the graph has exactly one instance, a cycle in the resource-allocation graph (RAG) is both necessary and sufficient for deadlock — every process on the cycle is waiting for a resource held by the next process on the cycle, and none can ever proceed. But if a resource type has multiple instances, a cycle can exist without deadlock: a process's request can still be granted from a different, currently-free instance of the same resource type held by no one on the cycle. Example: resource types $R_1$ and $R_2$ each have 2 instances. $P_1$ holds one instance of $R_2$ and requests $R_1$; $P_3$ holds one instance of $R_1$ and requests $R_2$; the other instance of $R_1$ is held by $P_2$ and the other instance of $R_2$ by $P_4$, and neither $P_2$ nor $P_4$ requests anything. The graph contains the cycle $P_1\to R_1\to P_3\to R_2\to P_1$, yet there is no deadlock: $P_4$ finishes and releases its instance of $R_2$, which is granted to $P_3$; $P_3$ then finishes and releases $R_1$, which satisfies $P_1$. So: deadlock $\Rightarrow$ cycle always; cycle $\Rightarrow$ deadlock only when every resource type on the cycle is single-instance.

(b) Resource-allocation graph for a three-resource deadlock. Three processes $P_0,P_1,P_2$ each hold one single-instance resource and request the resource held by the next process, forming a closed cycle with no exit:

Following the arrows: $P_0$ holds $R_1$ and wants $R_2$; $P_1$ holds $R_2$ and wants $R_3$; $P_2$ holds $R_3$ and wants $R_1$. Since every resource here is single-instance, this cycle by itself proves deadlock (per part (a)). Detecting it from the graph uses the same reduction procedure as the deadlock-detection algorithm: repeatedly find a process all of whose outstanding requests can currently be satisfied from unallocated instances, "remove" it (release its held resources back to the free pool, delete its edges), and repeat. If this reduction removes every process, the system was not deadlocked; if it terminates with processes still remaining (as here — no process's single request can ever be granted because the resource it wants is always held by another un-removable process), those remaining processes are deadlocked. Visually, a cycle that cannot be "walked out of" — every node on it is only reachable by following more request/assignment edges that lead back into the same cycle — is exactly this irreducible remainder.

(c) Detection-and-recovery based deadlock handling. Rather than trying to prevent deadlocks from ever forming (prevention) or refusing unsafe requests up front (avoidance, e.g. Banker's algorithm), this approach lets deadlocks occur and periodically runs a detection algorithm (the graph-reduction/wait-for-graph procedure of part (b), generalized to multi-instance resources via the same matrix-based algorithm as Banker's safety check but using current allocation only, not maximum claims) to identify which processes are deadlocked, then recovers. Two recovery strategies:

• Process termination. Either abort all deadlocked processes at once (simple but wastes all their partial work), or abort them one at a time, re-running detection after each abort, until the cycle breaks (more expensive in detection overhead, but preserves more completed work). Victim selection should weigh process priority, CPU time already invested, resources still needed, and how many other processes would need to be aborted.
• Resource preemption. Take a resource away from one victim process and give it to another, rolling the victim back to a safe earlier state so it can re-request the resource later. Three practical sub-problems: choosing a cost-minimizing victim, deciding how far to roll back (usually a total rollback to the process's start, since partial rollback needs the OS to track intermediate consistent states), and preventing starvation of any one process being repeatedly selected as the victim (e.g. by including "number of times already rolled back" in the cost function).

Worked example using the graph in (b): the detection algorithm's reduction step finds no process's single outstanding request can be granted ($R_1,R_2,R_3$ are all currently held), so it reports $\{P_0,P_1,P_2\}$ deadlocked. Recovery by resource preemption: preempt $R_1$ from $P_0$ and give it to $P_2$ (whose request it satisfies), rolling $P_0$ back to before it acquired $R_1$. $P_2$ now completes and releases both $R_1$ and $R_3$; $R_3$ satisfies $P_1$'s request, which completes and releases $R_2$; $R_2$ then satisfies $P_0$'s original request when it re-attempts, so all three processes eventually finish having lost only $P_0$'s partial progress.