File allocation — contiguous, linked, indexed (inode): Exercises

Throughout, we reuse three symbols. Let us define them once, in plain words, before any formula uses them:

Unless a problem says otherwise, take $B = 4096$ bytes, $p = 4$ bytes, so $k = 4096/4 = 1024$ .

L1 — Recognition

Exercise 1.1 (L1)

A directory entry for a file stores exactly two numbers: start = 200, length = 8. Which allocation scheme is this, and which physical blocks does the file occupy?

Recall Solution 1.1

WHAT the clue tells us: only two numbers, a start and a count. That is the fingerprint of contiguous allocation — the whole point of contiguous is that arithmetic replaces stored pointers, so the metadata is tiny: just $(b, L)$ . WHY: in linked you'd store a first (and maybe last) block; in indexed you'd point at an index block. Neither reduces to "start + length." Blocks occupied: consecutive run from $b = 200$ of length $L = 8$ : $200, 201, 202, 203, 204, 205, 206, 207.$ The last block is $200 + 8 - 1 = 207$ (we subtract 1 because block 200 is itself the first of the 8).

Exercise 1.2 (L1)

You corrupt one pointer somewhere in the middle of a file's block chain. In which scheme does this potentially lose the entire rest of the file, and why?

Recall Solution 1.2

Answer: linked allocation (the plain, in-block-pointer version). WHY: in linked allocation each block stores the address of the next block inside itself. The only way to reach block $i$ is to read block $i - 1$ 's pointer. If that pointer is garbage, you can no longer find block $i$ — or block $i + 1$ , $i + 2$ , … since each depends on the previous. One broken link orphans the whole tail. Contrast: in indexed allocation every data-block address sits independently in the index array, so a single corrupted entry loses only that one block, not the tail. This is the reliability advantage of indexing.

L2 — Application

Exercise 2.1 (L2)

A contiguous file starts at block $b = 50$ , block size $B = 4096$ bytes. Which physical block and byte-offset hold byte 30000?

Recall Solution 2.1

Step 1 — WHAT: find the logical block index $i$ . Bytes 0–4095 live in logical block 0, bytes 4096–8191 in block 1, etc. So $i = ⌊ \frac{30000}{4096} ⌋ = ⌊ 7.32 \dots ⌋ = 7.$ WHY the floor: we want how many whole blocks of 4096 fit before byte 30000; the fractional part is the leftover inside the current block. Step 2 — offset inside the block: $30000 mod 4096 = 30000 - 7 \times 4096 = 30000 - 28672 = 1328.$ Step 3 — physical block via the contiguous formula $phys (i) = b + i$ : $phys (7) = 50 + 7 = 57.$ Answer: read physical block 57, byte offset 1328.

Exercise 2.2 (L2)

Plain linked allocation, $B = 4096$ , pointer $p = 4$ . A file's blocks (in order) are $7 \to 3 \to 90 \to 12 \to 41$ . (a) How many disk reads to locate & read logical block 3? (b) How many usable data bytes does each block hold?

Recall Solution 2.2

(a) Logical blocks are numbered from 0: block 0 = physical 7, block 1 = 3, block 2 = 90, block 3 = 12. To reach logical block 3 there is no formula — you must chain-walk, reading each pointer to learn the next address: $read 1 7 \to read 2 3 \to read 3 90 \to read 4 12 .$ That is $i + 1 = 3 + 1 = 4$ disk reads. This is the $O (n)$ cost of linked allocation. (b) The next-pointer lives inside the block, stealing $p$ bytes: $B_{data} = B - p = 4096 - 4 = 4092 bytes .$

L3 — Analysis

Exercise 3.1 (L3)

Unix inode, $B = 4096$ , $p = 4$ , so $k = 1024$ . For each of these logical block numbers, say which pointer region holds it and how many disk reads (inode already in memory) are needed to fetch the data block: (a) $i = 5$ , (b) $i = 500$ , (c) $i = 100000$ .

Recall Solution 3.1

First define the region boundaries (see figure below):

Direct covers logical blocks $0$ through $11$ (12 pointers).
Single indirect covers the next $k = 1024$ blocks: $12$ through $12 + 1024 - 1 = 1035$ .
Double indirect covers the next $k^{2} = 1, 048, 576$ blocks: $1036$ through $1036 + 1048576 - 1 = 1, 049, 611$ .

Figure — File allocation — contiguous, linked, indexed (inode)

What to observe in the figure: the coloured bars are the four pointer regions laid on the logical-block number line, each labelled with its start and end block. Notice how each region begins exactly where the previous one ended + 1 — the boundaries are not $0..1023$ style round numbers but are offset by everything before them. The three arrows drop the exercise blocks $i = 5$ , $i = 500$ , $i = 100000$ into their regions, and each arrow's caption states the read count = (pointer levels crossed) + 1. Read the figure left-to-right and you can classify any block by seeing which bar it lands in.

(a) $i = 5$ : $5 \leq 11$ → direct. The inode already holds the direct pointers, so we read straight to data = 1 read. (b) $i = 500$ : $12 \leq 500 \leq 1035$ → single indirect. We (1) read the single-indirect block to get the address, then (2) read the data block = 2 reads. (c) $i = 100000$ : since $1036 \leq 100000 \leq 1049611$ → double indirect. We (1) read the double-indirect block, (2) read the single-indirect block it points to, then (3) read the data block = 3 reads. WHY the read count = number of pointer levels + 1: each level of indirection is one pointer block that must be fetched before we know the next address; the final +1 is the data block itself.

Exercise 3.2 (L3)

Same inode parameters. Compute the maximum file size and identify which term dominates.

Recall Solution 3.2

Reach per region = (number of data blocks) $\times B$ : $Max = direct 12 B + single k B + double k^{2} B + triple k^{3} B .$ Plug $B = 4096$ , $k = 1024$ :

Direct: $12 \times 4096 = 49, 152$ B $\approx 48$ KB
Single: $1024 \times 4096 = 4, 194, 304$ B $= 4$ MB
Double: $102 4^{2} \times 4096 = 4, 294, 967, 296$ B $= 4$ GB
Triple: $102 4^{3} \times 4096 = 4, 398, 046, 511, 104$ B $= 4$ TB

Total $= 49, 152 + 4, 194, 304 + 4, 294, 967, 296 + 4, 398, 046, 511, 104 = 4, 402, 345, 721, 856$ bytes. Dominant term: the triple indirect ( $4$ TB) — each extra level multiplies reach by $k = 1024$ , so the top level is ~1024× the one below it. The geometric growth is why three levels suffice for enormous files.

L4 — Synthesis

Exercise 4.1 (L4)

Design question. You must store $10$ million tiny log files, each exactly one 4 KB block, that are frequently appended to (so they occasionally grow by a block). Rank the three schemes for this workload and justify, then name the External vs Internal Fragmentation type each suffers.

Recall Solution 4.1

Workload facts that matter: files are tiny and grow. Contiguous: growing a file means the next physical block may already be taken → you'd have to relocate the whole file to a larger free run. With 10 M files churning, that is catastrophic. Also suffers external fragmentation (free space shatters into holes too small to reuse). Worst here. Linked: any free block joins any file, so growth is trivial (append a block, patch the last pointer) and there is no external fragmentation. Downside: each block loses $p$ bytes to the next-pointer — this is metadata overhead (a fixed tax paid inside every allocated block), not true internal fragmentation. Random access is $O (n)$ — but these files are 1 block, so $O (n) = O (1)$ in practice. Good. Indexed (inode): growth is easy (add a pointer to the index). For a 1-block file the address sits in a direct pointer → 1-read access, no external fragmentation. The cost is the inode/index metadata (again metadata overhead, not fragmentation). Best overall for real filesystems because it also keeps random access $O (1)$ if files later grow large. Ranking: Indexed $>$ Linked $≫$ Contiguous. Fragmentation vs overhead map: Contiguous → true external fragmentation (unusable gaps between files). Linked → metadata overhead (pointer bytes taxed inside each data block) plus internal fragmentation only in the file's last partly-filled block. Indexed → metadata overhead (index/inode blocks) plus last-block internal fragmentation. See Free Space Management (bitmap, free list) for how the OS finds those free blocks.

Exercise 4.2 (L4)

An engineer proposes: "Drop the triple-indirect pointer to save inode space — nobody has files that big." With $B = 4096$ , $p = 4$ , what maximum file size does the truncated inode now support, and what fraction of the original capacity is that?

Recall Solution 4.2

Remove only the triple term: $Max_{no-triple} = 12 B + k B + k^{2} B = 49, 152 + 4, 194, 304 + 4, 294, 967, 296 = 4, 299, 210, 752 bytes \approx 4 GB .$ Original total (from Ex 3.2) $= 4, 402, 345, 721, 856$ bytes. Fraction retained: $\frac{4 , 299 , 210 , 752}{4 , 402 , 345 , 721 , 856} \approx 0.000977 \approx 0.098%.$ Interpretation: dropping one 4-byte pointer per inode collapses the maximum file size by ~1000×, from $\sim 4$ TB to $\sim 4$ GB. Saving 4 bytes per inode to lose 3 orders of magnitude of reach is a terrible trade — this is exactly why the triple pointer exists despite being rarely used.

L5 — Mastery

Exercise 5.1 (L5)

Generalize. A filesystem uses $B = 8192$ bytes, $p = 8$ bytes, and an inode with $D$ direct pointers, one single-, one double-, and one triple-indirect pointer. (a) Find $k$ . (b) Write the general max-size formula. (c) Compute the max size for $D = 12$ . (d) How many disk reads to fetch logical block $i = 2, 000, 000$ ?

Recall Solution 5.1

(a) WHY $k$ first: every later count is measured in "pointers per block," so we compute the fan-out before anything else. $k = B / p = 8192/8 = 1024 .$ (Coincidentally still 1024 — both block and pointer doubled, so their ratio is unchanged.)

(b) WHY this formula: direct pointers reach $D$ blocks with no indirection; each indirection level multiplies reach by the fan-out $k$ (single = $k$ , double = $k \cdot k = k^{2}$ , triple = $k^{3}$ ). Multiply every block-count by $B$ bytes/block and sum: $Max = D \cdot B + k B + k^{2} B + k^{3} B = B (D + k + k^{2} + k^{3}) .$ Factoring out $B$ keeps the arithmetic clean — do the integer sum inside the parentheses first, multiply once at the end.

(c) With $D = 12$ , $k = 1024$ : build the sum term-by-term (WHY: this exposes which level dominates). $D + k + k^{2} + k^{3} = 12 + 1024 + 1, 048, 576 + 1, 073, 741, 824 = 1, 074, 791, 436.$ Now multiply once by $B = 8192$ : $Max = 8192 \times 1, 074, 791, 436 = 8, 804, 691, 443, 712 bytes \approx 8 TB .$ The triple term ( $k^{3} = 1, 073, 741, 824$ ) is ~99.99% of the sum — same geometric domination as Ex 3.2.

(d) WHY we classify by region first: the read count equals (number of pointer-block levels we must dereference) $+ 1$ for the final data block, so we only need to know which region block $2, 000, 000$ lands in. Compute the boundaries, offsetting each region by all earlier ones:

Direct: blocks $0.. D - 1 = 0..11$ .
Single indirect: next $k$ blocks $= 12..12 + 1024 - 1 = 12..1035$ .
Double indirect: next $k^{2}$ blocks $= 1036..1036 + 1, 048, 576 - 1 = 1036..1, 049, 611$ .
Triple indirect: next $k^{3}$ blocks, starting at $1, 049, 612$ .

Since $2, 000, 000 > 1, 049, 611$ , block $2, 000, 000$ falls in the triple-indirect region. WHY the count is 4: we must fetch the triple-indirect block, then the double-indirect block it points to, then the single-indirect block that points to (3 pointer levels), then the data block itself: $reads = 3 + 1 = 4 disk reads (inode already in memory) .$

Exercise 5.2 (L5)

Prove that for a fixed disk of $N$ blocks (let $N$ = total number of blocks on the whole disk), plain linked allocation can always satisfy an allocation request of any size $s \leq$ (free blocks), but contiguous allocation may fail even when $s \leq$ (free blocks). Give the smallest concrete counterexample for contiguous.

Recall Solution 5.2

Linked always succeeds: a linked file needs $s$ free blocks in any positions, because each block only needs to point to the next — position is irrelevant. So if the number of free blocks $\geq s$ , we can always pick $s$ of them and chain them. Formally: the free blocks form a set; any $s$ -subset works. No positional constraint ⇒ no failure. ∎ Contiguous can fail: it needs $s$ consecutive free blocks — a positional constraint linked lacks. This is external fragmentation. Smallest concrete counterexample. Take the tiniest disk on which the failure can appear: $N = 3$ blocks with the pattern free, used, free — i.e. block 0 free, block 1 used, block 2 free.

Free blocks $= 2$ , so a request of size $s = 2$ satisfies $s \leq$ (free blocks).
Linked on this request: pick blocks 0 and 2, chain $0 \to 2$ . ✔ succeeds (positions don't matter).
Contiguous on this request: needs 2 adjacent free blocks, but the only free blocks (0 and 2) are separated by used block 1 — no run of length 2 exists. ✘ fails despite $s = 2 \leq 2$ free blocks.

Why $N = 3$ is smallest: with $N = 1$ or $N = 2$ you cannot build a "free–used–free" split (you need at least one used block between two free ones, so at least 3 blocks). Hence $N = 3$ is the minimal disk that proves "enough free space" $\neq =$ "enough contiguous free space." ∎

Recall One-line self-checks (cover the answer)

Contiguous file (start=200, len=8) last block ::: 207 Reads to reach logical block 3 in a linked file ::: 4 Region of logical block 500 in a 4096/4 inode ::: single indirect (2 reads) Region of logical block 100000 ::: double indirect (3 reads) Max file size, 4096/4 inode, in bytes ::: 4,402,345,721,856 ( $\approx$ 4 TB) Dropping triple-indirect max (4096/4) ::: $\approx$ 4 GB (about 0.098% of original) $k$ when $B = 8192$ , $p = 8$ ::: 1024