25-Comp-A5 Operating Systems · May 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.
Given (a). A 125-block file under contiguous allocation; the directory and the file's known length reside entirely in main memory (free, uncounted); no room to extend the file at the beginning, room to extend at the end; ignore free-space bookkeeping.
Find. The minimum disk-operation count (1 op = 1 block read or 1 block write) for cases (A), (B), (C).
Approach. (A) and (B) are plain in-place content operations on blocks that already belong to the file — no shifting is needed since neither changes the file's length or block count. (C) inserts into the middle of a contiguous run, which (with room only at the end) forces every block after the insertion point to physically shift one slot toward the end before the new content can be written in.
| Case | Operation | Minimum disk operations |
|---|---|---|
| (A) | Copy block 100 → block 2 | 2 |
| (B) | Exchange blocks 110 and 101 | 4 |
| (C) | Insert new block after block 90 (35 blocks shift) | 72 |
Under contiguous (variable-partition) allocation, files of different sizes are repeatedly created, extended, and deleted; each deletion leaves behind a hole exactly the size of the file that vacated it, and over time these holes end up as many small, scattered gaps — external fragmentation — where the sum of all free space may be large, yet no single hole is big enough to satisfy the next request (exactly the mechanism behind Question 2(b)'s blocked Job 3, whose 204K request could not be met even though 100+42+85+76+70+91+125+150K of scattered free space existed in aggregate). A standard control technique is compaction: periodically relocate all currently-allocated files so that every hole is coalesced into one single contiguous free region at one end of the disk/partition — though on a physical disk (as opposed to main memory) compaction is expensive, since it means physically copying large amounts of data across the platters, so it is normally done rarely (e.g. offline defragmentation) rather than continuously. A more structural alternative used by nearly all modern file systems is to abandon contiguous allocation altogether in favour of linked or indexed (block-based) allocation, where a file's blocks need not be physically adjacent at all — external fragmentation is then eliminated by construction, since any free block anywhere on the disk can satisfy any request.
The standard technique is RAID (Redundant Array of Independent Disks). The simplest form, mirroring (RAID 1), duplicates every block written onto a second physical disk, so a single-disk failure is survived by simply redirecting all reads to the surviving copy, at the cost of 100% extra storage and doubled write traffic. Parity-based schemes (RAID 4/5) instead dedicate the equivalent of one disk's capacity across the array to a parity block computed (via XOR) across the corresponding blocks of every other disk; if any single disk fails, its data is reconstructed by XOR-ing the surviving disks together with the parity, at a much lower storage cost ($1/N$ extra) but a "small write penalty" (a single-block write requires reading the old data and old parity, then writing new data and new parity — four operations for what would be one operation on an unprotected disk). Both schemes tolerate exactly one simultaneous disk failure; surviving two at once requires a higher-redundancy scheme (e.g. RAID 6, dual parity).
A multi-user system stores many different users' files on shared physical storage, so without protection any user's process could read, alter, or destroy any other user's data, whether by an honest mistake (a wrong path, a buggy script) or deliberate malice. The goals of file-system protection are therefore: confidentiality — preventing unauthorized users from reading a file's contents; integrity — preventing unauthorized users from modifying or deleting a file; controlled sharing — letting an owner grant specific other users or groups exactly the subset of access (read/write/execute) intended, no more and no less, rather than an all-or-nothing choice; and availability — ensuring one user's (or process's) actions cannot deny legitimate access to another user's own files. Mechanisms such as owner/group/other permission bits, access-control lists, and capability lists all exist to serve these same four goals with different trade-offs in flexibility, storage cost, and revocation ease.
