SME
Operating Systems
File systems
Use this for “An inode has 12 direct pointers and single, double and triple indirect ones. With 4 KiB blocks, what is the largest file?”
Diagram
k
=
4,096
4
=
1,024
pointers
a
block.
Largest file: 12 + 1,024 + 1,048,576 + 1,073,741,824 = 1,074,791,436 blocks.
1,074,791,436 × 4,096 B = 4,402,345,721,856 B.
This is an example. Type your own values to start a new problem.
k
=
B (B)
p (B)
N
=
d
+
k
+
k
2
+
k
3
size (B)
=
N
×
B (B)
Formulas
k
=
B
p
1,024
=
4,096
4
N
=
d
+
k
+
k
2
+
k
3
1,074,791,436
=
12
+
1,024
+
1,
024
2
+
1,
024
3
size
=
N
×
B
4.4023 ×
10
12
=
1,074,791,436
×
4,096
Assumptions
•
The inode holds d direct pointers, then one single, one double and one triple indirect pointer.
•
A block of pointers holds k = B ÷ p of them, and 1 KiB = 1024 bytes (many texts write KB).
•
The largest file uses every pointer; its bytes are its blocks times the block size.
Step-by-step
WE KNOW
B = 4,096 B, p = 4 B, d = 12
FIND
pointers per block (k), largest file in blocks (N), largest file (size)
Step 1 · Find pointers per block (k)
Use k = B ÷ p
A
block
of
B
bytes
holds
B
p
pointers
of
p
bytes
each.
k
=
4,096
4
k
=
1,024
Step 2 · Find largest file in blocks (N)
Use N = d + k + k² + k³
The
direct
pointers
reach
d
blocks,
the
single
indirect
k
,
the
double
k
2
and
the
triple
k
3
.
N
=
12
+
1,024
+
1,
024
2
+
1,
024
3
N
=
12
+
1,024
+
1,048,576
+
1,073,741,824
N
=
1,074,791,436
Step 3 · Find largest file (size)
Use size = N × B
Every
data
block
holds
B
bytes.
size = 1,074,791,436 × 4,096
size
=
4.4023 ×
10
12
B
Check
Put the numbers back in. Both sides should match.
1,024
=
4,096
4
✓
1,074,791,436
=
12
+
1,024
+
1,
024
2
+
1,
024
3
✓
4.4023 ×
10
12
=
1,074,791,436
×
4,096
✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
More problem types
Disk access time
Use this for “A disk seeks in 9 ms and spins at 7200 rpm. How long does reading 4 KiB at 100 MB/s take?”
Blocks and wasted space
Use this for “A 10,000-byte file is stored in 4096-byte blocks. How many blocks does it use, and how many bytes are wasted?”
Which allocation method?
Use this for “Each block holds the address of the next one. Which allocation method is it?”