File systems & disks formulas

File systems and disk scheduling. 12 formulas for GATE CS Operating Systems, each with when to use it. Each is explained in the topic notes.

All 12 File systems & disks formulas

LINKED ALLOCATION

usable bytes per block (linked) = B - p, blocks for a file of S bytes = ⌈ \frac{S}{B - p} ⌉

Applies when each data block stores its own next-block pointer of $p$ bytes.

WIDTH OF A BLOCK ADDRESS

bits per block address \geq ⌈ lo g_{2} N_{blocks} ⌉

A pointer or FAT entry must be able to name every one of the $N_{blocks}$ blocks; questions usually round this up to whole bytes.

FAT SIZE

FAT size = N_{blocks} \times (entry size in bytes)

One entry per disk block; the entry must be wide enough to hold any block number.

POINTERS PER BLOCK

P = \frac{B}{p}

Number of block addresses that fit in one index (indirect) block.

LARGEST FILE WITH AN I-NODE

Max file size = (D + P + P^{2} + P^{3}) \times B

With direct, single, double and triple indirect pointers. Drop the terms for levels the i-node does not have. This is the limit imposed by the pointer scheme; a pointer width or file-size field can impose a smaller limit.

BIT VECTOR SIZE

Bit vector size (bytes) = \frac{N _{blocks}}{8} = \frac{disk size}{8 \times B}

One bit per block of size $B$ bytes.

DISK CAPACITY

Capacity = surfaces \times \frac{tracks}{surface} \times \frac{sectors}{track} \times \frac{bytes}{sector}

Assumes the same number of sectors on every track.

LINEAR SECTOR NUMBER FROM (CYLINDER, HEAD, SECTOR)

sector number = (c \times H + h) \times S + s

$H$ heads (surfaces), $S$ sectors per track, and $c$ , $h$ , $s$ all numbered from 0, with sectors numbered across a whole cylinder before moving to the next cylinder. If sectors are numbered from 1, use $s - 1$ in place of $s$ .

DISK ACCESS TIME

T_{access} = T_{seek} + T_{rotational latency} + T_{transfer}

Add controller or queueing overhead only if the question gives it.

ROTATION TIME AND AVERAGE LATENCY

T_{rot} = \frac{60}{RPM} s, average rotational latency = \frac{T _{rot}}{2}

On average the wanted sector is half a turn away. If the question says worst case, use a full $T_{rot}$ .

TRANSFER TIME

T_{transfer} = \frac{bytes to transfer}{bytes per track} \times T_{rot}

The head reads one full track per rotation, so time is the fraction of a track passed under the head times the rotation time.

DATA TRANSFER RATE

data transfer rate = bytes per track \times \frac{RPM}{60} bytes/s

One track passes under the head per rotation.

Where this was asked: 2018 (1), 2020 (1), 2022 (1), 2025 (1), 2026 (2). See the 6 previous-year questions on File systems & disks. This shows what was asked, not what will be asked.

KEEP GOING

File systems & disks: the notes and 6 solved previous-year questions