25-Comp-A5 Operating Systems · May 2017

Question 5 of 7: Deadlocks

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Question 5: Deadlocks (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) Yes — sharing files (or more generally, any exclusively-lockable shared resource) can absolutely cause deadlock on a multiprogrammed multi-user system, because file locks satisfy all four necessary conditions for deadlock. Example: two users, U1 and U2, are each editing two shared files, F1 and F2, and each acquires an EXCLUSIVE lock before writing. U1 locks F1 and then requests a lock on F2; concurrently U2 has already locked F2 and now requests a lock on F1. Neither can proceed (mutual exclusion on each lock; each holds one lock while requesting another — hold-and-wait; locks cannot be forcibly taken away — no preemption; U1 waits on U2 who waits on U1 — circular wait), so both users' processes block forever unless the OS or database intervenes. This is exactly the classic two-resource deadlock pattern, just instantiated with files as the contested resource instead of, say, printers or memory.

(b) The deadlock detection and recovery approach makes no attempt to prevent deadlocks from forming; instead the system periodically runs a detection algorithm (e.g. constructing a resource-allocation/wait-for graph and checking for cycles, or for multiple-instance resources, running a Banker's-Algorithm-style reduction to see if all processes can eventually finish) and, if a deadlock is found, takes recovery action. Example: with single-instance resources, the OS builds a wait-for graph — an edge $P_i\to P_j$ meaning $P_i$ awaits a resource held by $P_j$ — and a cycle in that graph (e.g. $P_1\to P_2\to P_1$) proves a deadlock exists among exactly those processes. Recovery then typically uses one of: (1) process termination — abort all deadlocked processes at once (simple but wasteful, since work in progress is lost), or abort them one at a time (re-running detection after each) until the cycle breaks (more work, but only the minimum necessary processes are killed); (2) resource preemption — forcibly take a resource away from one process in the cycle and give it to another, rolling the victim back to a safe earlier checkpoint state, being careful to avoid repeatedly choosing the same victim (starvation). The approach's overhead is running the detection algorithm itself (proportional to how often it is invoked and how large the resource-allocation graph is), traded against the benefit of never restricting resource requests up front the way avoidance/prevention schemes do.

(c) Given. $R=8$ identical resources; $P_1..P_4$ each need at most $2$ simultaneously; $P_5..P_7$ each need at most $3$ simultaneously; one resource requested/released at a time; no avoidance/detection in force. Find. Whether deadlock can occur. Approach. Deadlock is possible here precisely when it is feasible for every process to simultaneously hold ONE FEWER resource than its stated maximum (so every process still wants at least one more) while ALL 8 resources are already allocated — check whether such an allocation exists.

1. Compute the worst-case "everyone stuck one short of their max" total. If every one of the 7 processes held exactly (its own max $-1$) resources, the total held would be $$\sum_i(\text{max}_i-1)=4\times(2-1)+3\times(3-1)=4\times1+3\times2=4+6=10$$ Since $10 > R=8$, the standard sufficient-for-deadlock-freedom bound ($\sum(\text{max}_i-1) < R$) does not hold — the system cannot be guaranteed deadlock-free, so an explicit deadlocked allocation must be sought.
2. Exhibit a concrete deadlocked allocation using exactly the 8 available resources. Let P1, P2, P3, P4 each hold $1$ resource (one short of their max of 2 — each wants one more), and let P5, P6 each hold $2$ resources (one short of their max of 3 — each wants one more), and let P7 hold $0$ (wants its first resource). Total allocated: $$4(1)+2(2)+1(0)=4+4+0=8=R$$ All 8 resources are now allocated, EVERY process (P1–P7) still wants at least one more resource to proceed (P1–P4 need a 2nd, P5–P6 need a 3rd, P7 needs its 1st), and since no more resources exist and none will be released until a process gets what it needs to finish, EVERY process is permanently blocked. $$\boxed{\text{Deadlock CAN occur} \text{ (e.g. holdings } (1,1,1,1,2,2,0)\text{ summing to }8\text{)}}$$