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) Given. A contiguously-allocated file of 120 blocks (numbered 1–120); directory resident in memory; room to grow only at the end. Find. Minimum disk operations for cases A–D. Approach. Under contiguous allocation, block $k$'s disk location is computable directly from the file's known start address (no traversal needed), so a simple read/write of an UNMOVED block costs exactly one disk operation each; inserting or deleting a block, however, forces every block after the insertion/deletion point to physically shift by one position (since the blocks must remain contiguous), each shifted block costing one read + one write.
| Case | Operation | Minimum disk operations |
|---|---|---|
| A | Read blocks 101, 97, 102 | 3 |
| B | Exchange blocks 100 ↔ 95 | 4 |
| C | Insert new block after block 70 | 101 |
| D | Delete block 75 | 90 |
(b) An acyclic graph directory generalizes the strict tree-structured directory by allowing a file (or subdirectory) to have MULTIPLE parent directory entries pointing to it — i.e. the same underlying file can appear, under possibly different names, in several directories at once — while still forbidding cycles (a directory can never be its own descendant, which would break traversal and space-reclamation algorithms). It is implemented via links (a directory entry that names another file/directory rather than containing an independent copy) or by having multiple directory entries share one underlying inode/file-control-block. Use for file sharing: two users collaborating on a project can each have the shared file appear in their own directory under their own convenient name, with edits made through either link visible through the other, since both entries reference the same underlying data — no wasteful duplication of the file's content. Merits: avoids duplicate storage of shared data, keeps a single edit consistent everywhere the file is referenced, and lets each user organize shared files within their own naming scheme. Overheads: file creation is simple (just add a link), but file deletion is genuinely harder than in a strict tree: the OS must not physically free the data merely because ONE link to it is removed, since other directories may still reference it, so a reference count (or equivalent, e.g. periodic garbage collection) must be maintained per file and the actual disk space reclaimed only once the last reference is removed — naive unlink-and-free logic would leave other directories with dangling pointers. Every traversal or size-accounting utility must also guard explicitly against acyclic graphs still double-counting a multiply-linked file's size, and against the graph's cycle-freedom being violated by pathological link creation.
(c) The bit vector (bitmap) technique for free-space management represents the disk's blocks as a single array of bits, one bit per block, where a $1$ conventionally means the block is free and $0$ means it is allocated (or vice versa by convention). To allocate a block, the OS scans the bitmap for the first (or a suitably-sized run of) set bit(s), clears it, and returns that block number; to free a block, it simply sets the corresponding bit back. Advantages: the representation is extremely compact (one bit per block — a 1 TB disk with 4 KB blocks needs only about 32 MB of bitmap), finding contiguous runs of free blocks (useful for contiguous allocation, or for reducing fragmentation) is straightforward by scanning for consecutive set bits, and simple bitwise operations make the scan for a free block fast on modern hardware (e.g. finding the first set bit within a word using a hardware instruction). Shortcomings: a linear scan over the whole bitmap can still be slow on a nearly-full disk (long runs of zero-bits to skip over before finding a free block), and the ENTIRE bitmap generally needs to be resident in memory for fast access, consuming memory proportional to disk size even though most of it is never touched at once. Must it be stored on disk? Yes — keeping the bitmap only in volatile memory would lose all free-space information on a crash or power loss, so the authoritative copy must be persisted to disk (updated as allocations/frees occur, or reconstructed at boot by scanning the file system), with an in-memory cached copy used for fast day-to-day allocation decisions.
