25-Comp-A5 Operating Systems · December 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) File Allocation Table (FAT). FAT is a variant of linked allocation that fixes linked allocation's main weakness — slow, disk-bound random access — by moving every block's "next" pointer out of the data blocks and into a single table (the FAT) held in a reserved area of the disk, one entry per block, containing either the block number of the next block in the file, a special end-of-file marker, or a free-block marker. A file's directory entry then only needs the number of its first block; the rest of the chain is found by walking FAT entries. Because the FAT for the whole disk is typically small enough to be cached entirely in memory, once it is loaded, finding the $n$-th block of any file is a fast in-memory chain walk rather than $n$ separate disk reads — this is the practical advantage FAT has over plain singly linked allocation (as used, for contrast, in Question 5(a) above, where every hop cost a real disk read). The FAT itself is also exactly where free-space management lives: any entry marked "free" is an available block, so a single scan of the (cached) table finds free space with no extra data structure.
(b) Sequential vs. random file access — applications. Sequential access (records/bytes read or written strictly in order, one after another) fits: log files (appended and later read start-to-end for auditing), media playback (streaming an audio/video file front-to-back), batch payroll processing (reading employee records in a fixed order to produce paycheques), and tape backup/restore utilities. Random access (jumping directly to an arbitrary offset without reading everything before it) fits: a relational database engine looking up a specific record by its row offset/index, a virtual-memory pager reading an arbitrary page of a swap file, a video editor seeking to an arbitrary timestamp in a large file, and a spreadsheet application loading/saving specific cell ranges.
(c) Advantages of multiple disks for information storage. Spreading storage across multiple physical disks (as in RAID and similar schemes) gives: higher throughput — data striped across disks can be read/written in parallel, multiplying aggregate bandwidth roughly by the number of disks; reliability/fault tolerance — mirroring or parity redundancy across disks means the failure of one disk does not lose data, which a single disk cannot offer; increased effective capacity and easier capacity growth (add another disk rather than replacing one with a larger, costlier unit); and reduced contention — independent, concurrently issued I/O requests from different processes can be serviced by different disks' independent arms/queues simultaneously, rather than serializing on one disk's single head.
(d) Goals of protection in a multi-user system. Protection mechanisms exist to: (1) prevent one user's or process's errors or malicious actions from affecting another user's data, programs, or the operating system itself (containment/isolation); (2) ensure that access to any resource (files, memory, devices, CPU time) is mediated according to an explicit, checkable policy (e.g. an access-control list or capability), so that only authorized subjects can perform specific operations on specific objects; (3) enforce the principle of least privilege, giving each process/user exactly the access needed to accomplish its task and no more, which limits the damage any single compromised or buggy component can do; and (4) provide a consistent, auditable mechanism (permission bits, ACLs, capabilities) that both the OS and user-level programs can rely on, rather than each application inventing its own ad-hoc security.
(e) Valid/invalid bit and dirty (modify) bit. The valid/invalid bit, one per page-table entry, records whether the logical page currently maps to a page actually resident in a physical frame ("valid") or not ("invalid" — either the page has never been loaded, belongs to another process, or lies outside the process's legal address space). Every memory reference checks this bit first: valid means the MMU translates and proceeds directly; invalid triggers a page fault trap into the OS, which decides whether to fetch the page from backing store or terminate the process for an illegal reference. The dirty (modify) bit, also one per page-table/frame entry, is set by hardware automatically the first time a resident page is written to, and records whether that page's in-memory copy differs from its on-disk copy. Its role is purely a performance optimization for eviction: when the page-replacement algorithm selects a victim frame, a clean (unmodified) page can simply be discarded and the frame reused immediately, since an identical copy still exists on disk (or is easily re-derived, as for code pages), whereas a dirty page must first be written back to backing store before its frame can be reused — this is precisely the modified-vs-unmodified distinction that made the 60 ms vs. 25 ms page-fault service times different in Question 2(b) above.
