25-Comp-A5 Operating Systems · May 2014

Question 4 of 7: Disk Block Allocation and Free-Space Management

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

Notes on this paper

98-COMP A-5 Operating Systems — National Examinations, May 2014. 3 hours, closed book (approved calculator only). 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 4: Disk Block Allocation and Free-Space Management (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 110-block file; the directory (including, for the linked case, the head pointer and the known file length) resides entirely in main memory, so directory accesses are free. Contiguous allocation occupies one physically consecutive run of blocks with free space only after the file. Linked allocation stores a next-pointer in each block, so reaching any block requires sequentially reading every block before it.

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

Approach. For contiguous allocation, only an interior insertion forces existing blocks to be physically shifted (removals at either end are pure metadata edits). For linked allocation, any operation away from the head requires traversing (reading) every preceding block first, since a singly linked list gives no random access.

(A) Contiguous, remove first block. Contiguous files are located by a (start, length) pair kept in the in-memory directory. Removing the first block only advances the stored start pointer by one and decrements length — no block's physical content or position changes. $$\boxed{\text{Ops}_A = 0}$$
(B) Contiguous, insert after block 61. The new block must occupy the slot immediately after block 61, but blocks 62–110 (110−61 = 49 blocks) already sit exactly there and must each be shifted one position later (using the known free room at the end). Each shifted block costs 1 read + 1 write = 2 operations; the new block's content is already in memory, so it costs only 1 write. $$\boxed{\text{Ops}_B = 49\times2 + 1 = 99}$$
(C) Contiguous, remove last block. Symmetric to (A): decrement the stored length by one; the vacated block needs no read or write. $$\boxed{\text{Ops}_C = 0}$$
(D) Linked, add at beginning. The in-memory directory already holds the address of the current first block, so the new block's next-pointer can be set without reading anything; only the new block (already in memory) needs writing. $$\boxed{\text{Ops}_D = 1 \text{ write}}$$
(E) Linked, insert after block 61. Reaching block 61 to update its next-pointer requires walking the list from the head: read block 1 to learn block 2's address, read block 2 for block 3's, …, read block 61 itself (to obtain its current next-pointer, which becomes the new block's next-pointer) — 61 reads. Then write the updated block 61 (now pointing at the new block) and write the new block (pointing at old block 62): 2 writes. $$\boxed{\text{Ops}_E = 61 + 2 = 63}$$
(F) Linked, remove last block. The new last block will be block 109; its next-pointer must become NULL. Even though the known file length (110) tells us in advance which block is second-to-last, the singly linked structure still forces a full walk to physically reach it: reading blocks 1 through 109 costs 109 reads. One write commits block 109's cleared next-pointer; the freed block 110 needs no I/O. $$\boxed{\text{Ops}_F = 109 + 1 = 110}$$

Final Results — Q4(a): minimum disk operations, 110-block file, insertion point after block 61
Case	Allocation	Operation	Disk operations
A	Contiguous	Remove first block	0
B	Contiguous	Add after block 61	99
C	Contiguous	Remove last block	0
D	Linked (singly)	Add at beginning	1
E	Linked (singly)	Add after block 61	63
F	Linked (singly)	Remove last block	110

(b) Free-space management lets the file system quickly find unallocated disk blocks whenever a file is created or grows, without scanning the entire disk on every allocation, and reclaim blocks promptly when a file shrinks or is deleted — its efficiency directly determines how fast allocation-heavy operations (file creation, appends) run and how well the disk's free space stays usable rather than pathologically scattered. (i) Bit vector (bitmap): one bit per disk block, 0 = free, 1 = allocated. To satisfy a request for $n$ contiguous free blocks, the allocator scans for a run of $n$ consecutive 0-bits, which can be done efficiently a machine-word at a time (skipping over all-1s words instantly). Example: a 1 TB disk with 4 KB blocks needs roughly $\frac{2.5\times10^8\text{ blocks}}{8} \approx 31\ \text{MB}$ of bitmap — small enough to keep resident in memory for fast lookup; its drawback is that a nearly-full or badly fragmented disk can force a long linear scan to find even a single free block. (ii) Linked list of free blocks: every free block stores a pointer to the next free block, and the file system keeps only a single head pointer to the first free block; allocating a block is O(1) (unlink the head), and freeing a block is O(1) (push it back onto the head), with no space overhead beyond the pointer already embedded in each (otherwise-unused) free block. Its drawback is that finding several contiguous free blocks is expensive (the list is not sorted by address, so contiguity checking requires following many links), and the free list itself receives no benefit from caching the way a small bitmap does, since it can be arbitrarily long and scattered.

Topic: Contiguous vs. linked file allocation and the cost asymmetry of interior modification; bit-vector vs. linked-list free-space management.

Key relations: Contiguous shift cost per relocated block $=2$ (read+write); linked-list traversal cost to reach block $k$ from the head $=k$ reads; bitmap size $\approx \dfrac{\text{disk blocks}}{8}$ bytes.

Why this works: Contiguous allocation buys fast sequential and random access at the cost of expensive interior insertion, because "contiguous" is a physical invariant that must be re-satisfied after every structural change; linked allocation gives that up (interior insertion needs no shifting) in exchange for expensive random access, since locating a block requires following every link before it. A bitmap trades a small, fixed, cacheable footprint for a scan cost when the disk is fragmented; a free list trades O(1) allocate/free for poor contiguous-run discovery.

Common pitfall: Forgetting that the "room to grow at the end" assumption is precisely what makes case (B) solvable by shifting at all — without it, an interior insertion into a full contiguous file would force relocating the entire file elsewhere on disk. For free-space management, a common error is assuming a bitmap is always more space-efficient than a linked list; per-free-block, the linked list actually costs zero extra bytes (it reuses the free block's own storage), while the bitmap costs a fixed fraction of the whole disk regardless of how full it is.

Source: Silberschatz, Galvin & Gagne, Operating System Concepts, ch. 11 (File-System Implementation) §11.4 (allocation methods), §11.5 (free-space management).

← Question 3 Next: Question 5 →