25-Comp-A5 Operating Systems · December 2015
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) The webserver is a soft real-time system: its requirement is a statistical/aggregate guarantee ("at least 90% of requests within 5 s"), which explicitly tolerates a bounded fraction of late responses without the system being considered to have failed — an occasional slow response degrades quality of service but causes no safety or correctness catastrophe. The alarm system is a hard real-time system: the 900 ms deadline applies to EVERY trigger occurrence with no stated tolerance for misses, and a late alarm (e.g. a fire or intrusion alarm) can have safety-critical or catastrophic consequences — missing even a single deadline constitutes a system failure, not merely degraded performance. The general distinguishing test is exactly this: hard real-time systems treat a missed deadline as a failure of the system's core function (often safety-critical), while soft real-time systems treat timeliness as a quality-of-service metric that can be violated occasionally, and are typically specified with an explicit statistical tolerance as this webserver example is.
(b) FCFS (First-Come-First-Served) disk scheduling services pending track requests strictly in the order they arrived in the queue, with no reordering by proximity to the disk head's current position. It is trivially fair (no request can be indefinitely bypassed) and has essentially zero scheduling overhead (no computation beyond dequeuing), but it can produce very poor head-movement performance if the arrival order happens to bounce the head back and forth across the disk (e.g. requests for tracks 5, 90, 10, 85 in that order force four long seeks instead of two short sweeps). SSTF (Shortest Seek Time First) instead always dispatches whichever pending request is numerically closest to the head's CURRENT position, greedily minimizing each individual seek. This substantially reduces total head movement compared to FCFS on typical (non-adversarial) request patterns, at the modest scheduling overhead of scanning the pending queue for the nearest request before every dispatch (an $O(n)$ scan, or $O(\log n)$ with a suitable ordered structure). SSTF's weakness is that its greedy, purely-local optimization is not globally optimal and can strand distant requests indefinitely if a stream of nearby requests keeps arriving (starvation), and its performance can occasionally be surprisingly poor on specific arrival patterns even though it is good on average — a limitation that motivates the SCAN-family algorithms (which bound worst-case wait by sweeping the whole disk in one direction before reversing).
(c) A standard protection method is the access-control list (ACL) (or its coarser Unix-style special case, owner/group/other permission bits). Every file carries metadata that the OS consults on every open/read/write/execute attempt, comparing the requester's identity (and group memberships) against the permissions recorded for that file. Example: on a shared project directory, the file owner can grant read+write to their own team's group, read-only to the rest of the organization, and no access to external accounts — enforcing exactly the intended sharing policy without exposing the file to everyone or requiring per-user copies. The Unix bit-based scheme's overhead is minimal (a fixed few bits checked per access, already resident with the inode — see part (d)), but it is coarse (only three access classes); a full ACL, which lists arbitrary numbers of individual users/groups with their own permission sets, offers much finer-grained control at the cost of extra storage per file and a longer list to scan/maintain on every access.
(d) An inode (index node) is the fixed-size on-disk (and cached in-memory) data structure Unix uses to hold ALL of a file's metadata OTHER than its name and its actual data content: file type, owner and group IDs, permission bits, size, timestamps (access/modify/change), a link count, and — critically — the pointers to the disk blocks that actually hold the file's data (typically a mix of direct block pointers for small files plus single/double/triple indirect pointers to support arbitrarily large files without bloating every inode to a fixed enormous size). A directory entry maps a filename to an inode number, not to the data directly, which is precisely why a Unix file can have multiple names (hard links) pointing at the same inode — deleting one name only decrements the inode's link count, and the data is freed only once that count reaches zero. Because permission bits and ownership live in the inode rather than in the directory entry, permission checks are naturally colocated with the rest of a file's metadata and do not depend on which name/path was used to reach the file.
