25-Comp-A5 Operating Systems · May 2014
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
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 disk drive is normally accessed through the operating system's I/O subsystem, which serializes and completes each disk request (a single read or write operation) in a bounded, short amount of time and then immediately releases the drive — no process is ever granted the disk and allowed to hold it indefinitely while also requesting another resource. Because a disk request is a brief, atomic transaction rather than a long-held allocation, the hold-and-wait condition required for deadlock essentially cannot arise around the disk itself: a process waiting for the disk is not simultaneously holding the disk and blocking on something else that depends on it in a cycle. In addition, on a well-designed system there is typically only one system-wide disk queue managed by the disk scheduler (e.g. LOOK/SCAN), so requests are served in a bounded order with no circular dependency possible — a process can wait for the disk, but nothing ever waits for that process while the process is waiting for the disk, breaking the circular-wait condition too. This is different from, say, a database lock or a printer held for an entire print job, where a process legitimately holds the resource across an extended period while doing other work, which is exactly when hold-and-wait cycles become possible.
(b) Deadlock prevention works by structurally ensuring that at least one of the four necessary (Coffman) conditions for deadlock — mutual exclusion, hold-and-wait, no preemption, circular wait — can never hold, so a deadlock is impossible by construction rather than merely detected or avoided at runtime. Examples for each condition: mutual exclusion is inherent to a truly exclusive-use resource (e.g. a printer) and generally cannot be eliminated, though it can sometimes be avoided by spooling (many "virtual" requests share one physical resource); hold-and-wait can be eliminated by requiring a process to request all resources it will ever need at once, before it starts execution (e.g. a batch job that declares "I need 2 tape drives and 1 printer" up front, and is not dispatched until all three are simultaneously available); no preemption can be eliminated by allowing the OS to forcibly take a resource away from a waiting process (releasing what it already holds) and restart it later, e.g. saving a process's held memory/registers and giving its resources to another; circular wait can be eliminated by imposing a strict global ordering on resource types and requiring every process to request resources only in strictly increasing order (e.g. always request the tape drive before the printer, never the reverse), which makes a cyclic wait-for chain topologically impossible.
(c) No — a deadlock cannot occur on this system. This follows from the standard sufficient-condition theorem for identical-resource systems: with $n$ processes each capable of holding at most $m$ resources of a single type, and $R$ total resource units available, if $\sum_i (\text{max}_i - 1) < R$ then deadlock is impossible, because there must always exist at least one process that can obtain its full maximum allocation and run to completion (releasing its resources for others), so the system can never get permanently stuck.
Applying it here: $n=7$ processes, each with a maximum simultaneous hold of $m=2$, and $R=8$ total resources.
$$\sum_{i=1}^{7}(\text{max}_i - 1) = 7\times(2-1) = 7$$ $$\boxed{7 < 8 = R \implies \text{deadlock is impossible}}$$Intuitively: in the worst case, imagine every one of the 7 processes has managed to acquire 1 resource each and is now blocked waiting for its 2nd (using up $7\times1=7$ resources, with 1 unit left over). That leftover 1 unit is enough to let at least one waiting process complete its request, reach its 2-resource maximum, finish its work, and release both units back to the pool — which then lets the next process proceed, and so on. Since it is provably impossible for all 7 processes to simultaneously hold 1 and be unable to get a 2nd (there would always be a free unit to hand to somebody), a circular-wait deadlock can never form. This is the same reasoning behind the classical "dining philosophers with one extra fork" style resolution, generalized to counting resources rather than named locks.
| Quantity | Value |
|---|---|
| Processes (n) | 7 |
| Max hold per process (m) | 2 |
| Worst-case resources consumed if every process holds (m−1) | 7 |
| Total resources (R) | 8 |
| Can deadlock occur? | No (7 < 8) |
