25-Comp-A5 Operating Systems · May 2013

Question 3 of 7: Disk Allocation Methods

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, May 2013. 3 hours, closed book, 100 marks. Candidates were instructed to answer any five of the seven questions; all seven are answered below as a complete study resource.

Reference texts: Silberschatz, Galvin & Gagne, Operating System Concepts (10th ed.) — scheduling (ch. 5), process synchronization/monitors (ch. 6–7), deadlocks (ch. 8), memory management/paging (ch. 9–10), file systems and disk scheduling (ch. 11–12); Tanenbaum, Modern Operating Systems (5th ed.), corroborating chapters on scheduling and file systems.

Question 3: Disk Allocation Methods (20 marks)

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 120-block file; the directory (including, for linked allocation, the head pointer and the known file length) resides entirely in main memory and directory accesses are free. For contiguous allocation the file occupies a physically consecutive run of blocks with free space only after it. For linked allocation each block stores a pointer to the next block, and reaching any block requires traversing every link before it, one disk read per block traversed.

Find. The minimum disk operation count (reads + writes) for cases A–F.

Approach. For contiguous allocation, only an insertion in the interior forces blocks to be re-positioned (since blocks must stay physically adjacent); removals at either end are pure metadata updates. For linked allocation, any operation away from the head requires sequentially reading every preceding block to reach the point of modification, since a singly linked list offers no random access.

(A) Contiguous, remove first block. Contiguous files are located by a (start, length) pair in the (in-memory) directory. Removing the first block only requires advancing the stored start pointer by one block and decrementing length — no block's physical position or content needs to change. $$\boxed{\text{Ops}_A = 0}$$
(B) Contiguous, insert after block 90. The new block must occupy the position right after block 90, but blocks 91–120 (30 blocks) are already sitting exactly there and must be shifted one position later to make room (using the free space known to exist at the end). Each of the 30 blocks costs 1 read (fetch its content) + 1 write (place it at its new position) $= 2$ operations; the new block's content is already in memory, so it costs only 1 write. $$\boxed{\text{Ops}_B = 30\times2 + 1 = 61}$$
(C) Contiguous, remove last block. Symmetric to (A): just decrement the stored length by one; the vacated last block needs no read or write. $$\boxed{\text{Ops}_C = 0}$$
(D) Linked, add at beginning. The in-memory directory holds the address of the current first block, so the new block's next-pointer can be set to it without reading anything; the new block's content is already in memory. $$\boxed{\text{Ops}_D = 1 \text{ write}}$$
(E) Linked, insert after block 90. To modify block 90's next-pointer we must physically reach it, and a singly linked list can only be walked from the head: read block 1 to learn block 2's address, read block 2 for block 3's address, …, read block 90 itself (to obtain its current next-pointer, which becomes the new block's next-pointer). That is 90 reads. Then write the updated block 90 (now pointing at the new block) and write the new block (pointing at old block 91): 2 writes. $$\boxed{\text{Ops}_E = 90 + 2 = 92}$$
(F) Linked, remove last block. The new last block is block 119; its next-pointer must become NULL. Reaching block 119 by traversal costs reading blocks 1 through 119 $=119$ reads (knowing the file length, 120, tells us in advance which block is second-to-last, but the singly linked structure still forces us to walk every link to physically get there). One write commits block 119's cleared next-pointer; the freed block 120 needs no I/O. $$\boxed{\text{Ops}_F = 119 + 1 = 120}$$

Final Results — Q3(a): minimum disk operations, 120-block file
Case	Allocation	Operation	Disk operations
A	Contiguous	Remove first block	0
B	Contiguous	Add after block 90	61
C	Contiguous	Remove last block	0
D	Linked (singly)	Add at beginning	1
E	Linked (singly)	Add after block 90	92
F	Linked (singly)	Remove last block	120

(b) An acyclic-graph directory generalizes the strict directory tree by allowing a file (or subdirectory) to have more than one parent — the same underlying file can appear under several directory paths simultaneously — while still forbidding cycles, so that traversal (and deletion) algorithms remain well-defined and always terminate. It is implemented by having two or more directory entries point to the same underlying file, either as a hard link (a second directory entry referencing the same inode/data blocks) or a symbolic link (a directory entry holding the path name of the target). This directly supports file sharing: several users, or several directories belonging to the same user, can each have their own path to one physical copy of a file, and any edit made through one path is instantly visible through every other path, since there is only one copy of the data.

The merits are storage economy (no duplicated data for shared files) and consistency (a single edit is seen everywhere, with no risk of stale copies diverging). The overheads show up specifically at creation and deletion: at creation of a shared link the system must maintain a reference (link) count on the file so it knows how many directory entries point to it, which slightly complicates every link-creating operation; at deletion, a naive "delete the file when one directory entry is removed" would leave the other directory entries dangling, so the system must instead decrement the link count and only actually reclaim the file's disk blocks when the count reaches zero — this is exactly the reference-counting scheme UNIX file systems use. A further subtlety is that a symbolic link can dangle (point to a since-deleted file) without affecting any reference count, so the two link types have different failure behaviours that a design must document.

Topic: Contiguous vs. linked file allocation, cost of interior modification; acyclic-graph directories and reference counting.

Key relations: Contiguous shift cost per relocated block $= 2$ (read+write); linked traversal cost to reach block $k$ from the head $= k$ reads; reference count $\ge 1$ while any directory entry points to a file, reclaim only at count $=0$.

Why this works: Contiguous allocation trades cheap sequential/random access for expensive interior insertion, because "contiguous" is a physical constraint that must be re-satisfied after every structural change. Linked allocation trades that away (interior insertion needs no shifting) for expensive random access, because the only way to find "where" a block is, is to follow every link before it. An acyclic-graph directory keeps the graph free of cycles specifically so a garbage-collection or deletion traversal is guaranteed to terminate; allowing cycles would require a true garbage collector rather than simple reference counting.

Common pitfall: Forgetting that the "room to grow at the end" assumption is what makes (B) solvable at all with pure shifting — without it, an interior insertion in a contiguous file would require relocating the entire file elsewhere. For directories, a common error is treating link count and disk usage as the same thing, or assuming a directory tree (no shared parents) can represent hard links at all — it cannot, which is precisely why the acyclic-graph structure is needed.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 11 (File-System Implementation) §11.4 (allocation methods) and ch. 11 §11.3.2 (acyclic-graph directories).

← Question 2 Next: Question 4 →