25-Comp-A5 Operating Systems · December 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 file system must know, at all times, which disk blocks are currently unused so it can satisfy allocation requests without ever handing out a block that is already part of some file. Free-space management is the bookkeeping structure that tracks this. One common technique is the bit vector (bitmap): one bit per disk block, set to 1 if free and 0 if allocated (or vice-versa); finding a free block is a linear (or word-at-a-time) scan for a set bit, and finding $n$ contiguous free blocks is a scan for a run of $n$ set bits, which a bitmap supports naturally, unlike a linked free list. (A linked free-list technique is the common alternative, chaining free blocks together with each free block storing a pointer to the next; it avoids the bitmap's fixed overhead but cannot easily locate contiguous runs.)
It is essential that free-space information itself be persisted on disk (not just held in volatile memory) because the file system must survive a crash or power loss: if the free-block map existed only in RAM, a crash would lose all record of which blocks are actually free, and on reboot the system would have no reliable way to distinguish "free" from "allocated to some file" — leading either to corruption (allocating a block that is actually part of a live file, silently corrupting that file) or to permanently leaked space (blocks that are genuinely free being conservatively treated as allocated forever, since there is no ground truth left to check them against).
(b) Optimal resource-management strategies (the optimal page-replacement algorithm from Q2(c)(iv), or a burst-length-clairvoyant SJF/SRTF CPU scheduler) require knowledge of future behaviour — the exact page reference string still to come, or the exact remaining CPU burst of a process that hasn't finished yet. A running operating system fundamentally cannot know the future: it can only observe the past (reference history, prior burst lengths) and, at best, use that history to build a statistical estimate (e.g. exponential-average burst-length prediction for SJF-approximation, or LRU/working-set as locality-based stand-ins for the optimal replacement decision). Because these estimates are never perfectly accurate, real systems can only approximate optimal behaviour, not achieve it, which is precisely why the optimal algorithms exist chiefly as theoretical benchmarks (e.g. "how close does LRU get to Optimal?") rather than deployable policies.
(c) A shared file is a single stored file that more than one user (or more than one directory entry) can access, so that changes made through one access path are visible through the others — rather than each user holding an independent copy. On a multi-user system, sharing is commonly supported via links: a hard link makes a second directory entry point at the same underlying inode/file-control-block (with a reference count tracking how many directory entries reference it), while a symbolic link is a separate small file that simply stores the path of the target, resolved at access time. Group/owner-based access-control bits (or ACLs) then govern which of the sharing users may read vs. write.
Deletion raises real problems: with a hard link, deleting one directory entry must only decrement the reference count and physically free the file's blocks once the count reaches zero — deleting it outright the first time any one user "removes" it would corrupt the file for every other user still referencing it. With a symbolic link, deleting the target file leaves the symbolic link dangling (pointing at a path that no longer resolves to anything), which is not caught until some process actually tries to follow the link and fails — unlike the hard-link case, there is no reference count to prevent premature deletion, since the link and the file it names are entirely independent objects.
(d) Telephone switch (soft real-time). The requirement is explicitly statistical — "within 500 ms for at least 98% of the calls" tolerates up to 2% of calls missing the deadline without declaring the system a failure; an occasional late call-switching event degrades quality of service (a caller notices a brief delay) rather than causing catastrophic or safety-critical failure. This bounded, probabilistic tolerance for missed deadlines is the defining signature of a soft real-time system.
Furnace shutoff (hard real-time). There is no stated tolerance for missing the 150 ms deadline, and the physical consequence of a late shutoff — a furnace continuing to run over-temperature — is a genuine safety hazard (equipment damage, fire risk, or worse), not a mere quality degradation. A single missed deadline here is a system failure in the sense that matters (safety), which is exactly what characterizes a hard real-time system: correctness depends on both the logical result and the timeliness of that result, with zero tolerance for lateness on safety-critical actions.
| System | Classification | Why |
|---|---|---|
| Telephone switch (500 ms, 98% of calls) | Soft real-time | Explicit statistical tolerance for missed deadlines; late switching degrades but doesn't endanger |
| Furnace shutoff (150 ms, over-temperature) | Hard real-time | No tolerance stated; a missed deadline is a safety failure |
