File allocation — contiguous, linked, indexed (inode): Question bank

Reminders of the plain-word meanings used throughout, so nothing here relies on unexplained notation. Read this once and every trap below is self-contained:

Recall

A block is a fixed-size chunk of disk (e.g. $B = 4096$ bytes) — the smallest unit the OS allocates. So $B$ = bytes per block.
A pointer is a disk address (a number naming a physical block). Its size in bytes is written $p$ (e.g. $p = 4$ bytes). So $p$ = bytes needed to store one block address.
$k = B / p$ = how many pointers fit inside one block. Why this ratio? A pointer-block is just a block ( $B$ bytes) packed full of addresses ( $p$ bytes each), so it holds $B \div p$ of them. With $B = 4096, p = 4$ : $k = 1024$ .
Logical block $i$ = the $i$ -th block of the file (0, 1, 2, …). Physical block = the actual slot on disk.
Index array Index[] (indexed allocation): a table where entry Index[i] stores the physical block that holds logical block $i$ . It lives in the file's index block. Looking up Index[i] is a single array read — no chain to walk.
inode (Unix index node): a small per-file structure holding the file's metadata plus its pointer array — 12 direct pointers (straight to data blocks), then 1 single, 1 double, 1 triple indirect pointer (each pointing at a block-of-pointers, one level deeper than the last). Once a file is open its inode sits in RAM.
$O (1)$ means "constant work, independent of file size"; $O (n)$ means "work grows with the number of blocks".
External fragmentation = free space exists but is split into holes too small to use — see External vs Internal Fragmentation.
Internal fragmentation / overhead = wasted space inside a block you did allocate.

The whole topic is one three-way tension — keep this picture in mind for every "why" below:

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

True or false — justify

True or false: Contiguous allocation gives

O (1)

random access, so it is the best scheme overall.

False on "best overall". The

O (1)

is real (address is just start + i, one addition), but it pays with external fragmentation and the need to know file size in advance — it wins one corner of the trade-off triangle (fast access) while losing the other two.

True or false: Linked allocation has zero wasted space because any free block can join any file.

Only the external half is true — no free block is ever unusable. But each block still spends

p

bytes (one pointer) on the next-pointer, so there is internal overhead; usable data per block is

B - p

, not

B

True or false: The FAT scheme eliminates the pointer overhead inside data blocks.

True. FAT pulls every "next" pointer out of the data blocks into one central table, so each data block holds a full

B

bytes; the pointers now live in the table instead.

True or false: Indexed (inode) allocation completely avoids fragmentation of every kind.

False. It avoids external fragmentation (data blocks may sit anywhere), but the index block itself is metadata overhead, and the last data block of a file is still partly empty (internal fragmentation).

True or false: A file using only the 12 direct pointers needs zero extra pointer-block reads to fetch any of its blocks.

True. The 12 direct pointers sit inside the inode, which is already in memory once the file is open, so each of blocks 0–11 costs exactly one data read and no pointer-block read.

True or false: In linked allocation, if the pointer in the third block gets corrupted, you lose only that one block.

False. A broken pointer orphans the entire remainder of the chain — every block after the corruption becomes unreachable, since their addresses were only knowable by following that pointer.

True or false: Contiguous allocation never needs a disk seek while reading a file sequentially.

Essentially true. Because the blocks are physically consecutive, a sequential read walks adjacent locations with no head repositioning — this is exactly why it excels at streaming reads.

True or false: The triple-indirect pointer is the main contributor to a Unix file's maximum size.

True. Each indirection level multiplies reach by

k

(pointers per block), so the triple level contributes

k^{3} B

— geometrically dominating the direct, single (

k B

), and double (

k^{2} B

) contributions combined.

True or false: Growing a contiguous file is always cheap because you just append blocks.

False. You can only append if the next physical block is free. If a neighbour file already sits there, the whole file must be relocated to a larger free run — potentially very expensive.

Spot the error

Spot the error: "For logical block

i

in indexed allocation, the physical address is start + i."

That is the contiguous formula. Indexed allocation has no start; the address is Index[i], a direct lookup in the index array, precisely because the data blocks need not be consecutive.

Spot the error: "Linked allocation gives

O (1)

access if we store both the first and last block in the directory."

Storing the last block only helps appends, not random access. To reach some middle block

i

you still must follow

i + 1

pointers from the front — nothing lets you jump into the middle.

Spot the error: "With

B = 4096

and

p = 4

, a single index block can address a file of at most

4096

blocks."

It holds

k = B / p = 4096/4 = 1024

pointers, so it addresses

1024

blocks (about 4 MB), not

4096

. The confusion swaps bytes-per-block (

B

) for pointers-per-block (

k

Spot the error: "In the FAT scheme, reading logical block

i

still needs

i + 1

disk reads to walk the chain."

The chain now lives in an in-memory table, so walking it costs RAM lookups, not disk reads. You do only one disk read: the final data block itself.

Spot the error: "Fetching logical block 100000 with double-indirection takes 2 disk reads: the double-indirect block and the data block."

You forgot the middle level. Double indirection means inode → double-indirect block → single-indirect block → data block, so it is 3 disk reads (two pointer blocks then the data).

Spot the error: "Contiguous allocation stores a next-pointer in every block like linked does, just consecutively."

No. Contiguous stores no per-block pointers at all — the "next" block is implied by arithmetic (b + i). That absence of pointers is exactly why its metadata is only (start, length).

Spot the error: "The 12 direct pointers in an inode point to a block that lists 12 data addresses."

They point straight to 12 data blocks, not to a list. Only the single/double/triple indirect pointers point at intermediate blocks-of-pointers.

Why questions

Why do three allocation schemes exist rather than one winner?

Because the three goals — fast random access, no wasted space, easy growth — conflict (see the triangle figure). Each scheme sacrifices one to buy the others, so the "right" choice depends on the workload.

Why does linked allocation subtract the pointer size

p

from usable capacity but contiguous does not?

Linked stores the next-block pointer inside each data block, stealing

p

bytes; contiguous needs no such pointer because the next block is found by arithmetic (b + i), so all

B

bytes stay data.

Why does Unix use multiple levels of indirection instead of one giant index block?

One flat index big enough for huge files would waste space on the overwhelming majority of tiny files. The tiered inode gives small files zero-overhead direct pointers while still making huge files possible via

k

-fold fan-out — an 80/20 optimisation.

Why is external fragmentation impossible under linked and indexed allocation?

Both let data blocks live anywhere on disk, so any single free block is usable by any file. External fragmentation only arises when you demand a large contiguous run, which only contiguous allocation does.

Why can indexed allocation restore

O (1)

random access when linked cannot?

The index block holds all block addresses side by side, so Index[i] is a direct array lookup. Linked scatters the addresses inside the blocks themselves, forcing a sequential walk to discover each one.

Why does knowing a file's maximum possible size not require actually allocating that many blocks up front?

Indirect pointer blocks are created lazily — only when a file grows into that range. The formula gives the reachable ceiling; a small file allocates only the direct blocks it uses.

Edge cases

Edge case: What happens to phys(i) = b + i when a contiguous file has length

L = 1

Only block 0 is valid (

i = 0 \Rightarrow

physical

b

); any

i \geq 1

is out of range. The formula is still correct — it is the bound

0 \leq i < L

that guards it.

Edge case: In indexed allocation, what does a brand-new empty file's index block contain?

No valid data pointers yet (all Index[] entries unused/null). The index block may exist but maps zero logical blocks until data is written.

Edge case: A Unix file has exactly 12 blocks — does it ever touch the single-indirect pointer?

No. Blocks 0–11 fill precisely the 12 direct pointers, so the single-indirect pointer stays unused and reading any block costs one data read only.

Edge case: What is the access cost of logical block 0 in linked allocation?

It is the cheapest case: block 0 is the directory's stored first block, so it costs a single read (

i + 1 = 1

) — linked allocation only hurts for later blocks.

Edge case: In contiguous allocation, what does "must know file size in advance" mean for a file that shrinks?

Shrinking is easy — just reduce the length and free the tail blocks, leaving a hole. The pain is growth, because the freed hole may not be reusable by a larger neighbour, feeding external fragmentation.

Edge case: If a file's size is an exact multiple of the block size, is there still internal fragmentation in its last data block?

No — a perfect multiple fills the final block completely, leaving zero internal waste. Internal fragmentation only appears when the last block is partially used.