25-Comp-A5 Operating Systems · December 2013
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) Real-time systems are usually preemptive because correctness in a real-time system is defined partly by TIMING, not just by producing the right output eventually: if a high-priority, deadline-bound task becomes ready while a lower-priority task is running, the system must be able to interrupt the lower-priority task immediately, or the high-priority task risks missing its deadline — a non-preemptive kernel could force it to wait for the current task (or worse, a long system call) to finish, which is unacceptable when a missed deadline is treated as a failure (in a hard real-time system) or a quality degradation (soft real-time). Priority inversion occurs when a HIGH-priority task is forced to wait, indirectly, for a LOW-priority task — inverting the intended priority order. Classic example: a low-priority task L acquires a mutex protecting a shared data structure; a high-priority task H then becomes ready and preempts L, but H itself needs that same mutex and blocks waiting for L to release it; if a MEDIUM-priority task M (which needs neither the mutex nor cares about H) is also ready, the scheduler will run M in preference to L (since M outranks L), and L never gets to run to finish its critical section and release the mutex — so H is effectively blocked by M, a task with no direct relationship to the resource H is waiting for, and for an unbounded amount of time if more medium-priority tasks keep arriving. (This is precisely the failure that famously caused watchdog resets on the Mars Pathfinder mission.) The standard fixes are priority inheritance (L temporarily inherits H's priority while holding the mutex H is waiting for, so M can no longer preempt it) or priority ceiling protocols (a mutex is assigned in advance the priority of the highest task that could ever lock it).
Given. A hypothetical system running four processes ($P_1,P_2,P_3,P_4$) that use at least two resource types, here $A$ (6 instances) and $B$ (5 instances), used to construct one concrete state that is unsafe and, upon one further step, becomes deadlocked.
Find. A worked example each of (i) an unsafe (but not-yet-deadlocked) state and (ii) a genuine deadlock state.
(b) A state is safe if there exists at least one ordering in which every currently-existing process could still run to completion, even in the worst case where each demands its full declared maximum before releasing anything (the Banker's-algorithm safety test). A state is unsafe if NO such ordering exists — unsafe does not mean deadlock has already happened, only that the system has manoeuvred itself into a position from which SOME future request pattern (the worst case, which a Banker's-style avoidance algorithm must plan for) will produce a real deadlock; an unsafe state can, with favourable luck, still avoid ever actually deadlocking if processes happen to need less than their declared maximum. A state is deadlocked when a set of processes exist such that every process in the set is blocked waiting for a resource that can only be released by another process in the same set — at that point, no further progress for that set is possible under any future event, not merely under the worst case.
| Process | Allocation (A,B) | Max (A,B) | Need = Max−Alloc |
|---|---|---|---|
| P1 | (5,4) | (10,7) | (5,3) |
| P2 | (2,2) | (4,3) | (2,1) |
| P3 | (2,2) | (9,8) | (7,6) |
| P4 | (1,1) | (7,5) | (6,4) |
| State | Available (A,B) | Outcome |
|---|---|---|
| Unsafe (before P2 runs) | (2,1) | Only P2 can proceed; no complete safe order exists for all four |
| Deadlock (after P2 exits) | (4,3) | P1, P3, P4 permanently blocked — no process can ever finish |
(c) The optimal (Belady/MIN) page-replacement strategy evicts, on every page fault, whichever resident page will NOT be referenced again for the longest time into the future (or never again, if some resident page is never referenced again at all) — this provably produces the fewest possible page faults for any FIXED number of allocated frames, since deferring the eviction of a soon-to-be-needed page for as long as possible is, by a straightforward exchange argument, never worse than any alternative choice. For example, with 3 frames and reference string $1,2,3,4,1,2,5,1,2,3,4,5$: after the first three references fault to fill the frames with $\{1,2,3\}$, reference $4$ faults and the optimal choice evicts $3$ (its next use, position 11, is farther away than $1$'s at position 5 or $2$'s at position 6); this kind of look-ahead repeats at every subsequent fault. Why it is hard to implement on a real system: the algorithm needs to know, at the moment of each fault, exactly which resident page will be referenced farthest in the future — but a running program's future memory references depend on data-dependent branches, loop bounds and user input that have not executed yet, so the OS simply does not have this information available in real time. Consequently OPT is used only as a theoretical yardstick (computed after the fact from a recorded execution trace) against which real, causal algorithms such as LRU, clock/second-chance, or the working-set algorithm are measured, since those substitute a computable proxy (recency of past use) for the uncomputable ideal (exact future use).
(d) On a system supporting multiple users, protection and security mechanisms play complementary roles. Protection mechanisms are the internal, structural controls that mediate every access a process makes to a resource according to a defined policy — access-control lists and permission bits (Q6(b)), memory protection via base/limit registers or page-table permission bits (preventing one process from reading or writing another's memory), and privilege separation between kernel mode and user mode (preventing an ordinary process from directly executing privileged instructions or touching hardware registers it should not). Their role is to ENFORCE a stated policy consistently, regardless of whether any given access attempt is malicious or merely an innocent bug. Security mechanisms address a broader, adversarial threat model: authentication (verifying a user genuinely is who they claim, e.g. passwords, multi-factor tokens) establishes the IDENTITY that protection mechanisms then act on; auditing/logging records what happened so a breach can be detected and investigated after the fact; and encryption protects data confidentiality even if the storage or network medium itself is compromised, which pure access-control protection cannot address (an attacker who steals the physical disk bypasses OS-level ACL checks entirely, but not disk encryption). In short, protection answers "does this ALREADY-authenticated request follow the rules," while security additionally answers "IS this request really from who it claims, and can I detect/prevent it even if the internal rules are somehow bypassed" — a multi-user system needs both, since perfect internal protection is worthless if authentication is weak, and strong authentication is worthless without protection mechanisms to act on the identity it establishes.
