GATE 2026 CS2 Q.53: solution and answer

GATE 2026 · CS2Q.53 · 2 marks · NAT

To keep track of free blocks in a file system, one of the two approaches is generally used – using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is 16 GB, block size is 2 KB, and block numbers used are 32-bit long. A single pointer of size 4 bytes is used in each block of the list to point to the next block of the list. The number of blocks required to hold the free disk block numbers is ____________. (answer in integer)
Note: 1K=2^10 and 1G=2^30

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The free list needs 16417 blocks.

Official answer: 16417Source: Official answer key, GATE 2026 CS2 (IIT Guwahati)

Number of disk blocks: $\frac{16 GB}{2 KB} = \frac{2 ^{34}}{2 ^{11}} = 2^{23} = 8388608$ . The free list must be able to hold the numbers of all these blocks, so $2^{23}$ block numbers are stored.
Each block number is 32 bits $= 4$ bytes.
Each list block is $2 KB = 2048$ bytes, and 4 bytes of it hold the pointer to the next list block. Space for block numbers $= 2048 - 4 = 2044$ bytes.
Block numbers per list block $= \frac{2044}{4} = 511$ .
List blocks needed $= ⌈ \frac{2 ^{23}}{511} ⌉ = ⌈ \frac{8388608}{511} ⌉$ .
$511 \times 16416 = 8388576$ , so $8388608 - 8388576 = 32$ block numbers are left over and need one more block.
Number of blocks $= 16416 + 1 = 16417$ .

KEY IDEA

Count the blocks on the disk, then see how many 4-byte block numbers fit in one list block after setting aside 4 bytes for the next-block pointer. Divide and round up.

WATCH OUT FOR

Using all 2048 bytes for block numbers gives 512 per block and $2^{23} /512 = 16384$ . This forgets that 4 bytes of each list block hold the pointer to the next list block.

From the GATE 2026 CS2 paper. Every question of this paper · Download the full paper · All 6 File systems & disks questions, with notes

GATE 2026 CS2 Q.53: solution and answer

Answer and solution

More File systems & disks questions