(a) Minimum disk operations, singly-linked allocation
Given. 120-block file, blocks logically numbered 1–120; singly linked allocation (each block holds its data plus a pointer to the next block); the directory (holding only the head/first-block pointer) is in main memory, so following the chain from the head is the only way to reach any interior block — there is no shortcut, no last-block pointer, and no index.
Find. Minimum disk operations (reads + writes) for cases A–D.
Approach. Reaching logical block $N$ from the head costs exactly $N$ sequential reads (block 1 reveals block 2's address, and so on) — and if several targets are needed within one case, traverse once in increasing order so every target is captured along a single pass (cost $=\max$ of the targets, not their sum). Add one write per block whose content or pointer must actually change.
(A) Read blocks 100, 87, 101. A single traversal in increasing order (1→87→100→101) captures all three along the way.
$$\boxed{M_A=\max(100,87,101)=101\text{ reads, }0\text{ writes}=101}$$
(B) Exchange contents of blocks 101 and 91. One traversal to position 101 passes through 91 (91<101), capturing both original contents in 101 reads; then two writes place the swapped contents back into blocks 91 and 101 (pointers are untouched — only the data payload moves).
$$\boxed{M_B=\max(101,91)+2\text{ writes}=101+2=103}$$
(C) Insert a new block after block 90, content copied from block 110. One traversal to position 110 passes through block 90 along the way, capturing block 90's current next-pointer (needed for the new block) and block 110's content to copy (110 reads). Allocating a free block costs nothing per the "ignore free-space bookkeeping" rule. Two writes finish the job: initialize the new block (content = block 110's content, next-pointer = old block 90's next-pointer), and update block 90's next-pointer to address the new block.
$$\boxed{M_C=\max(90,110)+2\text{ writes}=110+2=112}$$
(D) Delete block 85. To unlink block 85, block 84's next-pointer must be changed to skip straight to block 86 — but block 86's address is only known by reading block 85 itself. A single traversal to position 85 (passing through 84 along the way) supplies both addresses in 85 reads; one write updates block 84's next-pointer.
$$\boxed{M_D=85+1\text{ write}=86}$$
Final Results – Question 4(a)
Case
Reads
Writes
Total disk operations
A – read blocks 100, 87, 101
101
0
101
B – exchange blocks 101, 91
101
2
103
C – insert after block 90 (copy of block 110)
110
2
112
D – delete block 85
85
1
86
(b) Multi-level directories. A multi-level (hierarchical/tree-structured) directory lets a directory contain both files and subdirectories, so the whole file system forms a tree rather than one flat list. Advantages over a single-level directory: (1) no global name-uniqueness requirement — two users (or two projects) can each have a file named the same thing, since each occupies its own subtree/namespace, whereas a single-level directory forces every file on the entire system to have a unique name; (2) logical grouping — related files (a user's, or a project's) can be kept together and searched/manipulated as a unit, instead of one enormous flat listing; (3) faster, scoped search — a search can be confined to a subtree instead of scanning every file in the system; (4) per-directory access control is natural (e.g. protect a whole subtree), which a flat namespace cannot express structurally.
(c) Linked-list free-space management. The operating system threads a linked list through the free blocks themselves: each free block stores a pointer to the next free block, and a single head pointer (kept in memory, or at a fixed disk location) references the first free block. Allocating a block pops the head of the list; freeing a block pushes it back onto the head. Advantages: essentially zero space overhead beyond the blocks themselves — no separate bitmap or table is needed, since the "bookkeeping" data lives inside blocks that are unused anyway; and push/pop are $O(1)$. Shortcomings: finding a block matching any criterion beyond "any free block" (e.g. a contiguous run, or best-fit) requires walking the list block by block, each hop costing a disk read — there is no fast way to answer "how much total free space is there?" without a full traversal (unless a running counter is separately maintained), and a single corrupted pointer breaks the chain for everything beyond it, unlike a bitmap where damage stays localized to individual bits.
