File systems — practice with guided problems step by step: blocks and internal fragmentation, reads by allocation method, the i-node and an exercise in the exam format (and the block I counted from 1)

In the IC2 mock exam there was an i-node question that looked like a gift: 2 KiB blocks, 12 direct pointers, «which pointer leads to byte 23,000?». I divided 23,000 by 2048, got 11.2 and thought: «it is in block 12, so it is no longer direct: single indirect». Wrong. Logical blocks are counted from 0, like bytes: byte 23,000 is in block 11, which is the twelfth and last direct one. One block off and I went to the wrong level of indices. Since then, in any block calculation, I first write «block = byte / size, integer division, counting from 0».

This is the guided practice for file systems. In the file systems theory you saw attributes, directories, contiguous, linked, FAT and indexed allocation, the Unix i-node and free-space management, with the IC2 assignment folder. Here we solve four problems step by step: how many blocks a file takes and how much is lost, how many reads it costs to reach a block with each allocation method, the maximum size with an i-node and which pointer leads to each byte, and an exercise in the exam format. Afterwards, in the file systems exercises, it is your turn.

Before you start

It helps to be clear about:

• That sizes go in powers of 2: 1 KiB = 1024 B, 1 MiB = $2^{20}$ B, 1 GiB = $2^{30}$ B.
• That a file takes whole blocks: the number of blocks is rounded up and what is left in the last one is internal fragmentation.
• How each allocation method stores the links: in the directory (contiguous), in the blocks themselves (linked), in a table (FAT) or in an index block (indexed).
• The structure of the i-node: 12 direct pointers, one single indirect, one double and one triple; with N pointers per block, the maximum is $(12 + N + N^2 + N^3) \times$ block size.

If any of them sounds shaky, go over the theory before carrying on.

How to solve a file system problem

The four problems follow the same four-step method:

1. Convert everything to bytes or powers of 2 and note the block and pointer sizes.
2. Count in blocks: size / block rounding up to occupy; byte / block with integer division (from 0) to locate.
3. Apply the structure: what has to be read with each method, which i-node range a block falls in, how many bits or entries are needed.
4. Check with a sum the other way round: blocks × size ≥ file, ranges that add up to the total, sensible orders of magnitude.

Problem 1: blocks and internal fragmentation

Statement. A disk uses 2 KiB blocks. How many blocks does each file take and how many bytes are lost in its last block?

File	Size
photo.jpg	5000 B
thesis.docx	20 KiB
video.mp4	3 MiB + 100 B

The idea

A file cannot take half a block: if one byte is left over, it needs another whole block. So the blocks are the size divided by 2048 rounded up, and what is lost is what is left free in the last one: blocks × 2048 − size.

Step by step

File	Size (B)	Size / 2048	Blocks	Lost (B)
photo.jpg	5000	2.44	3	3 · 2048 − 5000 = 1144
thesis.docx	20,480	exactly 10	10	0
video.mp4	3,145,828	1536.05	1537	1537 · 2048 − 3,145,828 = 1948

In the video, 3 MiB is exactly $3 \cdot 2^{20} / 2^{11} = 1536$ blocks; the extra 100 bytes force one more, almost empty.

Check

• What is lost is always less than a block (0 ≤ lost < 2048): all three meet it.
• With sizes that are multiples of 2 KiB nothing is lost: thesis.docx.

Questions you might ask

Why not use very small blocks so as to lose nothing? Because each block is one more entry in the FAT, the bitmap or the indices, and more reads for a large file. Big blocks: less management and more internal fragmentation.

How much is lost on average? Half a block per file. With many small files, internal fragmentation can be a significant part of the disk.

Do the allocation methods need extra blocks? Indexed does: the index block. Linked does not use extra blocks, but each block stores the pointer to the next one and holds less data.

Try it yourself

• How many blocks does a 1-byte file take? And a 0-byte one?
• Repeat the table with 4 KiB blocks. Which file loses most now?

Problem 2: reads by allocation method

Statement. A program wants to read logical block 6 (the seventh, counting from 0) of a file it already has open. How many disk reads are needed with contiguous, linked, FAT (with the table in memory) and indexed allocation (with the index block on disk)?

The idea

The question is always the same: where is it recorded which physical block holds block 6? If it can be computed without reading anything (contiguous, or FAT already in memory), you only need to read the data. If you have to follow links on disk (linked), you have to read all the earlier blocks. If it is in an index block on disk, one more read.

Step by step

Method	How block 6 is found	Reads
Contiguous	physical = start + 6, computed	1
Linked	read block 0 to know where 1 is, … up to 5 to know where 6 is	7 (0 to 6)
FAT in memory	follow the chain in the table, which is in RAM	1
Indexed	read the index block and then the data	2

Check

• Contiguous and FAT have direct access; linked does not: the cost grows with the block number (for block k, k + 1 reads).
• Indexed always costs 2 (or more, with several index levels), whatever the block.

Questions you might ask

Why does the FAT not count as reads? Because it is in memory: following the chain is looking at RAM. If the FAT did not fit in memory and had to be read from disk, it would cost reads.

Then why is contiguous not always used? Because it needs a contiguous hole the size of the file and suffers from external fragmentation; also, the file cannot grow if it runs out of room.

And with the i-node? For a direct block, 1 read (the i-node is already in memory once the file is open); through the single indirect, 2; through the double, 3; through the triple, 4.

Try it yourself

• How many reads does block 0 cost with each method?
• With linked, how many reads does reading a whole 10-block file from start to finish cost? And block 9 alone?

Problem 3: the i-node

Statement. A Unix-style file system uses 2 KiB blocks, 4-byte pointers and an i-node with 12 direct pointers, one single indirect, one double and one triple. a) What is the maximum file size? b) Which pointer leads to bytes 20,000, 600,000 and 2,000,000,000?

The idea

The first thing is to know how many pointers fit in an index block: $N = 2048 / 4 = 512$. Each level multiplies by N: the single reaches 512 blocks, the double $512^2$ and the triple $512^3$. To locate a byte, convert it to a logical block (integer division, from 0) and see which range it falls in.

Step by step

a) Blocks reachable through each pointer:

Pointer	Blocks	Cumulative (logical blocks)
12 direct	12	0 … 11
Single indirect	512	12 … 523
Double indirect	$512^2 = 262\,144$	524 … 262,667
Triple indirect	$512^3 = 134\,217\,728$	262,668 … 134,480,395

Almost all of it comes from the triple: $512^3 \times 2 \text{ KiB} = 2^{27} \times 2^{11} = 2^{38}$ B = 256 GiB.

b)

Byte	Logical block (byte / 2048)	Range	Pointer
20,000	9	0 … 11	direct
600,000	292	12 … 523	single indirect
2,000,000,000	976,562	≥ 262,668	triple indirect

Check

• 9 · 2048 = 18,432 ≤ 20,000 < 20,480 = 10 · 2048: byte 20,000 is in block 9.
• The triple’s range starts at 12 + 512 + 262,144 = 262,668: 976,562 is larger, so the double is not enough.
• The total number of blocks is the sum of the four ranges: 12 + 512 + 262,144 + 134,217,728 = 134,480,396.

Questions you might ask

Why is the triple pointer hardly ever used and yet it is there? Because most files are small and fit in the direct pointers (fast), but the triple lets the few huge files exist without changing the structure.

How many reads does it cost to reach byte 2,000,000,000? With the i-node in memory, 4: the three levels of indices of the triple and the data block.

What if pointers were 8 bytes? $N = 256$: the triple would reach $256^3$ blocks and the maximum would drop to about 32 GiB. Bigger pointers allow bigger disks, but smaller files with the same structure.

Is the real maximum limited only by the i-node? No: also by the file size field in the i-node and by the disk size. In the exam, what is asked is the limit of the structure.

Try it yourself

• Which pointer leads to byte 1,073,741,824 (1 GiB)?
• Repeat part a) with 4 KiB blocks and 4-byte pointers.

Problem 4: an exercise in the exam format

In the written part and the test calculations of IC2 there are free-space and table questions: how much the bitmap or the FAT of a disk takes. Marking values doing everything in powers of 2 and showing the units. This exercise is original and written in that format.

Exercise. A 256 GiB disk uses 4 KiB blocks. a) How many blocks does it have? b) How much space does a bitmap take to manage free space? c) How much would a FAT with 4-byte entries take? d) Which of the two fits more comfortably in the memory of an 8 GiB laptop?

Concept	Result
Disk blocks	___
Bitmap	___
FAT with 4-byte entries	___

The idea

It is all dividing powers of 2: the disk divided by the block gives the blocks; the bitmap has one bit per block; the FAT, one entry per block. Care is needed with the units: bits and bytes, MiB and GiB.

Step by step

a) $256 \text{ GiB} = 2^{8} \cdot 2^{30} = 2^{38}$ B and $4 \text{ KiB} = 2^{12}$ B:

b) One bit per block: $2^{26}$ bits $= 2^{26} / 8 = 2^{23}$ B = 8 MiB.

c) 4 B per block: $2^{26} \cdot 2^{2} = 2^{28}$ B = 256 MiB.

d) Both fit, but the bitmap takes 32 times less (4 bytes are 32 bits): 8 MiB versus 256 MiB.

Concept	Result
Disk blocks	$2^{26} = 67\,108\,864$
Bitmap	$2^{23}$ B = 8 MiB
FAT with 4-byte entries	$2^{28}$ B = 256 MiB

Check and how it is marked

• FAT / bitmap = 32: it is the ratio between 4 bytes and 1 bit, whatever the disk.
• Order of magnitude: the bitmap of a 256 GiB disk with 4 KiB blocks is «in the MiB range», never GiB.

Marking values seeing the exponents at each step and the units right. An 8 without a unit, or confusing bits and bytes (64 MiB for the bitmap), counts as a mistake even if the power of 2 is right.

Try it yourself

• Repeat the exercise with 1 KiB blocks. By how much do the bitmap and the FAT multiply?
• How many bits would each FAT entry need at least to number every block of this disk?

Common mistakes in this practice

• Using powers of 10: 1 KiB is 1024 bytes and 1 GiB is $2^{30}$.
• Rounding down the blocks a file takes.
• Counting logical blocks from 1 when locating a byte.
• Miscounting linked reads: for block k, k + 1.
• Confusing bits and bytes in the bitmap.
• Forgetting the index block in indexed allocation.

Check it with Python

This program does the sums of the four problems: blocks with math.ceil, reads, the i-node ranges and free space. Do it by hand first.

# File systems on paper: blocks, reads by allocation, i-node and free space.
import math
KiB, MiB, GiB = 1024, 1024 ** 2, 1024 ** 3
B = 2 * KiB                                    # block size
for name, size in (("photo.jpg", 5000), ("thesis.docx", 20 * KiB), ("video.mp4", 3 * MiB + 100)):
    n = math.ceil(size / B); print(f"{name}: {n} blocks, {n * B - size} B lost inside the last one")

k = 6                                          # read logical block 6 (counting from 0)
print("reads for block 6: contiguous 1, linked", k + 1, "| FAT in RAM 1 | indexed", 1 + 1)

N = B // 4                                     # 4-byte pointers per index block
direct = 12
levels = [direct, N, N ** 2, N ** 3]
total = 0
for name, n in zip(("direct", "single", "double", "triple"), levels):
    total += n; print(f"{name}: {n} blocks, cumulative {total} blocks = {total * B / GiB:.4f} GiB")
print(f"maximum: {total * B} B = {total * B / GiB:.2f} GiB")
for byte in (20000, 600000, 2 * 10 ** 9):
    b = byte // B
    level = "direct" if b < 12 else "single" if b < 12 + N else "double" if b < 12 + N + N ** 2 else "triple"
    print(f"byte {byte}: logical block {b}, pointer {level}")

disk = 256 * GiB; blocks = disk // (4 * KiB)
print(f"disk 256 GiB, 4 KiB blocks: {blocks} blocks; bitmap {blocks // 8 // MiB} MiB; 4-byte FAT {blocks * 4 // MiB} MiB")

Output (run once):

photo.jpg: 3 blocks, 1144 B lost inside the last one
thesis.docx: 10 blocks, 0 B lost inside the last one
video.mp4: 1537 blocks, 1948 B lost inside the last one
reads for block 6: contiguous 1, linked 7 | FAT in RAM 1 | indexed 2
direct: 12 blocks, cumulative 12 blocks = 0.0000 GiB
single: 512 blocks, cumulative 524 blocks = 0.0010 GiB
double: 262144 blocks, cumulative 262668 blocks = 0.5010 GiB
triple: 134217728 blocks, cumulative 134480396 blocks = 256.5010 GiB
maximum: 275415851008 B = 256.50 GiB
byte 20000: logical block 9, pointer direct
byte 600000: logical block 292, pointer single
byte 2000000000: logical block 976562, pointer triple
disk 256 GiB, 4 KiB blocks: 67108864 blocks; bitmap 8 MiB; 4-byte FAT 256 MiB

Things to notice:

1. math.ceil(size / B) is rounding up: for photo.jpg it gives 3, not 2.44.
2. The i-node’s cumulative total comes out in GiB: the direct and single pointers barely contribute; the double reaches half a GiB and the triple adds the 256.
3. To locate a byte, byte // B is the integer division that counts from 0; byte 2,000,000,000 falls in block 976,562.
4. The bitmap and the FAT come from the same number of blocks; the FAT is 32 times larger.

Summary

• Blocks taken = size / block, rounded up; what is left in the last one is internal fragmentation.
• Reads for block k: contiguous 1, linked k + 1, FAT in memory 1, indexed 2.
• i-node: N = block / pointer; maximum $(12 + N + N^2 + N^3) \times$ block.
• Logical block of a byte = byte / block, integer division, from 0; then, which range it falls in.
• Bitmap: one bit per block; FAT: one entry per block.
• Everything in powers of 2 and with units.

Checklist: have you practised it?

• Have you done the four problems on paper before reading the step by step?
• Do you know when to round up and when it is integer division?
• Can you say how many reads a block costs with each method?
• Can you work out the i-node maximum and locate a byte in its ranges?
• Have you checked the problems with the Python program?
• Have you tried the «Try it yourself» tasks without looking at the theory?

If you answered yes to almost everything, you are ready for the file systems exercises, with a test on the whole topic and calculations of blocks, i-nodes and bitmaps with boxes that mark themselves. See you there!

Next step: exercisesFile systems — exam-style exercises with blocks, FAT, i-nodes and links (and the shortcut that pointed to nothing)

Did this article help you? Here is how you can support SergioLearns →