25-Comp-A5 Operating Systems · May 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) Priority inversion occurs when a HIGH-priority process is forced to wait, indirectly, for a LOW-priority process, because scheduling priority alone does not account for shared-resource locking. Classic example: three processes L (low priority), M (medium priority), H (high priority) share a system; L acquires a lock on a shared resource, then M (which needs no lock) preempts L simply because M has higher scheduling priority; shortly after, H becomes ready and needs the SAME lock L is still holding — H must wait for L to release it, but L cannot run (and therefore cannot finish and release the lock) because M keeps preempting it. The NET effect is that H, the highest-priority process, is kept waiting by M, a strictly LOWER-priority process than H, with L's lock as the indirect mechanism — a priority inversion. (This is precisely the bug that nearly crippled NASA's 1997 Mars Pathfinder rover, caused by exactly this pattern between its information-bus, meteorological, and communications tasks.) The standard fix is priority inheritance: while L holds a lock that a higher-priority process (H) is waiting on, L temporarily INHERITS H's priority, so M can no longer preempt it, letting L finish and release the lock promptly.
(b) Protection is concerned with providing the internal MECHANISM by which a system controls access to resources (files, memory regions, CPU, devices) among the various already-authenticated users/processes it is running — e.g. access-control lists, permission bits, memory base/limit registers, and privileged-mode CPU instructions. Its goal is to ensure that every process/user can access ONLY the resources it has been explicitly granted, preventing one legitimate user's or process's mistake or misbehaviour from corrupting another's data or the OS itself. Security, by contrast, is concerned with defending the system against EXTERNAL and internal THREATS — unauthorized users attempting to gain access at all, malware, and attacks that try to bypass or subvert the protection mechanisms themselves. Its goals are broader: authentication (verifying identity before any protection check even applies), confidentiality, integrity, and availability of the system and its data against adversarial actors, not merely well-behaved-but-imperfect authorized users. In short: protection is an INTERNAL policy-enforcement mechanism assuming users are who they claim to be; security is the OUTER defence that establishes and defends that assumption in the first place, including against actors who never should have gotten in.
(c) On a single-CPU system, job (long-term) and CPU (short-term) scheduling reduce to choosing, at each decision point, ONE process to run from a single ready queue — a comparatively simple, well-studied problem (FCFS, SJF, priority, Round Robin, all defined over a single queue and a single server). On a multiprocessor system, scheduling is substantially more complex for several compounding reasons: (1) the system must decide not just WHICH process runs next but on WHICH of several CPUs, introducing a load-balancing problem absent on a uniprocessor; (2) it must choose between asymmetric multiprocessing (one designated master CPU makes all scheduling decisions, simpler but that CPU can become a bottleneck) and symmetric multiprocessing (SMP) (every CPU is self-scheduling from a shared or per-CPU ready queue, requiring the ready-queue data structure itself to be protected by fine-grained locking to avoid becoming a scalability bottleneck); (3) processor affinity becomes a real concern — migrating a process to a different CPU invalidates its cache state on the original CPU, so schedulers try to keep a process on the same CPU (soft or hard affinity) to preserve cache warmth, a consideration that simply does not exist with one CPU; (4) with per-CPU ready queues, load balancing (push/pull migration between queues) must be actively managed to avoid one CPU sitting idle while another has a long queue; (5) further techniques unique to multiprocessors, like multicore processor awareness (avoiding scheduling two cache-thrashing threads on cores sharing an L2/L3 cache) add still more dimensions absent from single-CPU scheduling. In short, multiprocessor scheduling is a strictly harder, higher-dimensional problem: uniprocessor scheduling is the special case of multiprocessor scheduling with exactly one CPU (no placement, affinity, or load-balancing decisions needed at all).
(d) Compile-time binding generates ABSOLUTE final memory addresses directly into the compiled code, on the assumption that the process is known in advance to always load starting at one fixed, predetermined memory location; if that starting location ever needs to change, the program must be recompiled. This is rare in modern general-purpose systems (found mainly in old-style embedded/ROM code with a fixed known load address) because it is the least flexible option, but it has zero runtime translation overhead. Execution-time (dynamic) binding instead keeps all addresses as offsets from an as-yet-undetermined base, and defers the actual absolute-address computation until the instruction/data is REFERENCED during execution, typically via hardware support (a base/relocation register, or a full MMU with paging/segmentation) that adds the base to every generated logical address on the fly. This allows a process to be relocated in physical memory at any time (even swapped out and back in at a DIFFERENT location) without recompilation, at the cost of a small hardware-assisted address-translation overhead on every memory reference. (A third option, load-time binding, sits in between: addresses are fixed once at load time, permitting the load address to vary between runs, but not to move again once loading is complete, without hardware relocation support.)
(e) Dynamic loading is a technique where a program's routines (e.g. an error-handling routine, or a rarely-used feature module) are NOT all loaded into memory at program start; instead, each routine is kept on disk in a relocatable-load format and is only actually brought into memory the FIRST time it is called at runtime, via a small relocatable stub that checks whether the routine is already loaded and, if not, invokes the loader to bring it in before transferring control to it. Because routines that are never actually invoked during a given run (e.g. an error path that never triggers) are simply never loaded at all, dynamic loading can give substantially better memory utilization for programs with large amounts of infrequently-used code, without requiring any special operating-system support beyond the loader itself — the responsibility for using it is entirely the application's/language-runtime's design choice, unlike demand PAGING, which achieves a similar effect transparently and automatically at the OS level for ALL code and data, not just designated optional routines.
