25-Comp-A5 Operating Systems · May 2018
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) Protection and the access matrix. Protection is the OS mechanism that controls which processes/users may perform which operations on which system resources (files, memory segments, devices, CPU time), enforcing the policy decisions access control (Q6a) sets out to achieve; without it, one faulty or malicious process could read another's memory, corrupt shared files, or monopolize devices. The access matrix models this abstractly as a table with one row per domain (a process, user, or role) and one column per object (a file, device, memory segment); entry $A[i,j]$ lists the operations domain $i$ may perform on object $j$ (e.g. read, write, execute, own). Example: domain "Editor-User" might have {read, write} on file report.docx and {execute} on the editor program itself, while domain "Guest" has no entry at all for report.docx. In practice the matrix is sparse (most cells are empty) so it is stored either by row (a capability list per domain: "what can I access?") or by column (an access-control list per object: "who can access me?", the technique used in Q6(b)) rather than as a literal dense table.
Given (b). Base (relocation) register $=1000$; limit register $=1400$.
Find. Physical address for logical addresses (i) 705 and (ii) 1500.
Approach. A logical address is valid iff $0\le\text{logical}<\text{limit}$; if valid, physical $=$ base $+$ logical; otherwise the MMU raises an addressing-error trap and no physical address is generated.
| Logical address | In bounds? | Physical address |
|---|---|---|
| 705 | Yes (705 < 1400) | 1705 |
| 1500 | No (1500 ≥ 1400) | Addressing error (trap) |
(c) Turnaround-time vs. starvation trade-off. Strategies that minimize average turnaround time (SJF/SRTF, or any scheme that always favours whichever job finishes soonest) achieve their gain specifically by repeatedly deprioritizing long jobs in favour of a steady stream of shorter ones. If short jobs keep arriving, a long job can be pushed back indefinitely — it is never literally "denied," but every time it is about to be scheduled, a newly-arrived shorter job jumps the queue ahead of it, so its wait grows without bound. Example: with SRTF, a single 100-second batch job arriving at $t=0$ alongside a continuous stream of 2-second interactive jobs arriving every few seconds will see its remaining time always exceed the newest arrival's full burst, so it is preempted every time a new short job appears — it may never complete while short jobs keep arriving, i.e. it starves, even though the average turnaround across all jobs is genuinely minimized by this policy. The standard mitigation is aging: gradually increase a waiting job's effective priority the longer it waits, so that eventually even the long job's aged priority exceeds that of new arrivals and it is guaranteed to run — trading a small amount of average-turnaround optimality for a bound on maximum wait.
(d)(i) RAID. A Redundant Array of Inexpensive (Independent) Disks combines multiple physical disks into one logical unit to improve reliability, performance, or both, via striping (spreading data across drives to parallelize I/O) and/or redundancy (mirroring or parity, allowing reconstruction after a drive failure). RAID 0 (pure striping) improves throughput by serving parts of a request from multiple drives in parallel but has zero redundancy — a single drive failure loses the whole array, so it trades reliability away entirely for speed. RAID 1 (mirroring) duplicates every write across two drives, so a single-drive failure loses no data (the mirror still has it) at the cost of doubling the storage needed and providing no capacity gain. RAID 5 (striping with distributed parity) spreads a parity block across the array so that any single drive's failure can be reconstructed from the remaining drives' data plus parity, giving good read performance and only one drive's worth of capacity overhead, at the cost of a write penalty (every write must also update the relevant parity block) and a rebuild window during which a second failure would be unrecoverable. Overall, RAID's central trade-off is using extra drives (redundancy) and/or parallel access (striping) to buy back the reliability and/or performance that a single disk cannot provide alone.
(d)(ii) Acyclic-graph directories vs. two-level directories. A two-level directory gives each user their own directory but forbids any sharing between users' files without making a full physical copy (wasting space and letting the copies drift out of sync as one is edited). An acyclic-graph directory allows a single file (or subdirectory) to be linked into multiple parent directories simultaneously (via hard/symbolic links), so two users (or a user and a shared project directory) can reference the exact same underlying file without duplicating it — edits are instantly visible to everyone sharing the link, and only one copy of the data ever exists on disk. The cost is added bookkeeping complexity: the structure is no longer a simple tree (a file can have several "parents"), so the system must track a link/reference count per file and can no longer identify "the" path to a file uniquely. File deletion under an acyclic-graph directory must NOT simply free the file's blocks the moment one link is removed, since other directories may still reference it: each delete decrements the file's reference count, and the underlying blocks are only actually freed when the reference count reaches zero (no directory entries reference it any longer) — exactly the same reference-counting discipline used for hard links in Unix-style file systems.
