25-Comp-A5 Operating Systems · December 2014

Question 4 of 7: Deadlocks, Starvation, and File Sharing

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, December 2014. 3 hours, closed book, 100 marks. Candidates were instructed to answer any five of the seven questions; all seven are answered below as a complete study resource.

Reference texts: Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.) — scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.

Question 4: Deadlocks, Starvation, and File Sharing (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) Given. $m=7$ identical resources; $n=3$ processes; each process's maximum simultaneous hold is $k=3$; resources requested/released one at a time; no deadlock-avoidance algorithm. Find. Whether deadlock can occur. Approach. Apply the standard sufficient condition: with $n$ processes each needing at most $k$ units of a single resource type and $m$ total units, deadlock is impossible whenever $m \ge n(k-1)+1$, because that many units guarantee at least one process can always complete.

Bound the resources tied up by processes that are still blocked. For all three processes to be simultaneously deadlocked, each must be holding some resources while blocked waiting for one more (a process holding its full need of 3 would have finished its request sequence, not be blocked). So each deadlocked process holds at most $k-1=2$ resources. $$\text{Max resources held by 3 blocked processes} = 3\times(3-1)=6$$
Compare against the total available. With only 6 of the 7 resources tied up in the worst case, at least $7-6=1$ resource remains free. That free unit can satisfy the very next request from whichever process is waiting, letting that process acquire its third resource, finish, and release all three back to the pool — which then unblocks the others in turn. $$\boxed{n(k-1)+1 = 3(3-1)+1 = 7 \le m=7 \implies \text{deadlock CANNOT occur}}$$

The system sits exactly on the safe threshold: $m=7$ is the minimum number of resources for which this guarantee holds for $n=3,\ k=3$ (one fewer, $m=6$, would allow all three processes to hold 2 each and block forever, a genuine deadlock).

(b) Deadlock is a state in which a set of processes are each waiting for an event (typically resource release) that only another process in the same set can cause, so none of them can ever proceed — it is provably permanent (formally, a cycle in the resource-allocation graph under the single-instance case) and requires all four Coffman conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) simultaneously. Starvation (indefinite postponement) is a process being perpetually denied a resource or CPU time it needs, not because of a circular dependency but because of how the scheduling/allocation policy makes its choices — e.g. a strict fixed-priority scheduler that always favours higher-priority processes can starve a low-priority process even though no deadlock cycle exists and the resource does become free repeatedly. Starvation is typically curable by aging (gradually raising a waiting process's priority); deadlock cannot be "waited out" and requires detection/recovery or prevention/avoidance.

(c) Sequential access requires reading or writing data in a fixed, ordered progression from wherever the last operation left off — to reach byte $N$, everything before it must first be traversed (the natural model for a linked-list-organized file, or physically for magnetic tape). Random access lets any block be reached directly, in roughly constant time regardless of what was accessed previously, by supplying an address (e.g. a track/sector or a byte offset) — disks support this natively because the head can seek directly to any track. Random access does still incur a variable seek-time-plus-rotational-latency cost that depends on the distance moved (which is exactly what SSTF/SCAN in part (b) are trying to minimize), but that cost is bounded and address-based, unlike sequential access's requirement to pass through every intervening block.

(d) No. Deadlock requires all four Coffman conditions to hold simultaneously, and the very first — mutual exclusion — is absent for pure read access: any number of processes can hold a shared (read) lock on the same file at the same time without conflict, since reading never modifies the file and there is nothing to protect one reader from another. With no process ever forced to wait for exclusive access to a read-only file, no process can be blocked waiting on another process's read-only file hold, so no circular-wait chain involving these files can ever form. (This changes immediately if even one process needs write access, since a writer requires exclusive access and reintroduces mutual exclusion.)

Final Results — Q4
Part	Result
(a) Deadlock possible?	No — $n(k-1)+1=7\le m=7$
(d) Deadlock from read-only file sharing?	No — mutual exclusion condition never arises

Topic: The four necessary (Coffman) conditions for deadlock and the resource-counting sufficient condition for deadlock-freedom.

Key relations: Deadlock-free guarantee: $m \ge n(k-1)+1$ for $n$ processes each needing at most $k$ units of a single resource type with $m$ total units. Coffman conditions: mutual exclusion, hold-and-wait, no preemption, circular wait — all four required.

Why this works: The resource-counting bound works because it computes the absolute worst case (every process holding one short of its declared maximum) and shows even that worst case leaves slack; if the worst case is safe, every case is safe. Removing mutual exclusion (as with read-only sharing) breaks the deadlock argument at its first premise, so no amount of hold-and-wait or circularity among readers can matter.

Common pitfall: Applying the $n(k-1)+1$ formula with $k$ = total resources per process ever requested rather than the maximum simultaneously held, or forgetting that a process holding its full need is, by definition, not blocked (so it cannot be part of a deadlock's held-and-waiting set). Also, conflating starvation with deadlock — a starved process's resource does eventually become available; it is just never granted to that particular process.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 8 (Deadlocks, §8.2 Coffman conditions, §8.6 the resource-counting deadlock-avoidance argument); ch. 11 (File-System Implementation, sequential vs. direct/random access methods, file-sharing semantics).

← Question 3 Next: Question 5 →