25-Comp-A5 Operating Systems · December 2017
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) Safe, unsafe, and deadlock states. A safe state is one for which the operating system can find at least one ordering (a "safe sequence") of the currently running processes such that, granting each process's remaining maximum need in that order, every process is guaranteed to eventually obtain all resources it could ever request and finish, using only currently available resources plus what earlier-finishing processes release. An unsafe state is one where no such guaranteed-completion ordering exists — it does not mean the system is currently stuck (processes may still be running normally, holding less than their declared maximum), only that there is at least one future pattern of requests (up to each process's stated maximum) that the system could not satisfy without blocking somebody forever; an unsafe state is a risk of deadlock, not deadlock itself. A deadlock state is an actually-realized failure: every resource instance is committed, and every process in a cycle of the wait relationship is blocked waiting for a resource held by another blocked process in the same cycle, so none of them can ever make progress — not a future risk but a present, permanent halt.
(i) Unsafe-state example. Five processes P0–P4, three resource types A, B, C with totals $(6,5,4)$.
| Process | Allocation (A,B,C) | Max (A,B,C) | Need (A,B,C) |
|---|---|---|---|
| P0 | (1,1,0) | (4,3,2) | (3,2,2) |
| P1 | (1,0,1) | (2,2,2) | (1,2,1) |
| P2 | (2,1,1) | (5,3,3) | (3,2,2) |
| P3 | (1,2,0) | (2,3,1) | (1,1,1) |
| P4 | (0,1,1) | (3,2,3) | (3,1,2) |
Total allocated $=(5,5,3)$, so $\text{Available}=(6,5,4)-(5,5,3)=(1,0,0+1)=(1,0,1)$. Every process's Need has a strictly positive B-component (minimum need $=1$, for P3/P4), but $\text{Available}_B=0$ — so no process's full Need can ever be met from Available, and the Banker's safety algorithm terminates with zero processes finished: no safe sequence exists. Yet nothing is actually blocked right now: every process holds resources within its declared Allocation and none has yet issued a request the system can't grant, because none has asked for its full Max simultaneously. This is precisely what "unsafe" means — the state is one bad future request away from a real deadlock, but is not deadlocked today.
(ii) Deadlock-state example. Five processes P0–P4, three resource types A, B, C, one instance each of A, B and two instances of... to keep the cycle minimal, use totals $A{=}2, B{=}2, C{=}1$ (5 instances total, matching 5 processes holding exactly one instance each).
| Process | Holds | Requests |
|---|---|---|
| P0 | 1 × A | 1 × B |
| P1 | 1 × A | 1 × C |
| P2 | 1 × B | 1 × A |
| P3 | 1 × B | 1 × C |
| P4 | 1 × C | 1 × A |
All $2+2+1=5$ resource instances are held, so $\text{Available}=(0,0,0)$. Every process's outstanding request needs a positive amount of some resource type, and no type has any instance free — so no process can ever be granted its request, none can finish, and hence none can ever release what it holds. Concretely, P0 waits on B, which is held by P2, and P2 waits on A, which is held by P0 (and P1): a genuine circular-wait cycle $P0\to B\to P2\to A\to P0$ exists among currently blocked processes with zero available resources of any type — a true deadlock, not merely a risk.
| State | Available at that instant | Currently blocked? | Safe sequence exists? |
|---|---|---|---|
| Unsafe example | (1, 0, 1) | No | No |
| Deadlock example | (0, 0, 0) | Yes, all 5 | N/A (already failed) |
(b) Prefetching more than one page after a fault. Yes — bringing in additional pages beyond the one that faulted (a strategy generally called anticipatory paging or prepaging) can improve performance, but only when the program exhibits enough spatial/sequential locality that the extra pages are likely to be referenced soon. Example where it helps: a program scanning a large array or a file sequentially (e.g. reading a file block-by-block, or iterating a matrix row-major) — when page $k$ faults, pages $k+1, k+2,\dots$ are very likely to be referenced next, so fetching them together amortizes the fixed per-fault overhead (interrupt handling, disk seek/rotational setup) across several useful pages instead of paying it once per page, and hides the latency of the later pages' fetch behind the CPU's processing of the earlier ones. Example where it hurts: a program with scattered or pointer-chasing access patterns (e.g. hash-table lookups or a linked data structure spread across memory) — the "extra" prefetched pages are unlikely to be touched before eviction, wasting a scarce frame and disk bandwidth that could have served another process's real request, and can even trigger the eviction of a page that was about to be used, making things worse. So prepaging is a net win exactly when the working-set/locality assumption holds, and a net loss otherwise — real systems typically apply it selectively (e.g. only for sequentially-accessed files, or guided by an explicit `madvise`/readahead hint) rather than unconditionally.
(c) Multithreading: what it is, why it is used, its overhead. Multithreading allows a single process to contain multiple independent threads of execution (each with its own program counter, register set, and stack) that all share the process's address space, open files, and other resources. It is used because: (1) responsiveness — a GUI or server thread can keep responding to input/new connections while another thread of the same process does a long computation or blocking I/O; (2) resource sharing — threads share the address space directly, so they can communicate through ordinary memory without the OS-level IPC needed between separate processes; (3) economy — creating and context-switching a thread is far cheaper than a full process, since no new address space/page tables need to be built or swapped; (4) scalability on multicore hardware — independent threads of one process can genuinely run in parallel on separate cores. The overhead: each additional thread still needs its own stack and thread-control block, so memory use grows with thread count; context-switching between threads (though cheaper than between processes) still costs CPU cycles to save/restore registers; and because threads share memory, the program must add synchronization (locks, semaphores, monitors) to protect shared data, which introduces both a runtime cost (acquiring/releasing locks) and a design cost (risk of race conditions, deadlock, and priority inversion that a single-threaded program simply cannot have).
