GATE 2026 CS (CS2) – Question 53
To keep track of free blocks in a file system, the linked-list approach is used. The disk size is 16 GB, the block size is 2 KB, and block numbers are 32 bits long. Each block of the linked list uses one 4-byte pointer to the next block. The number of blocks required to hold the free disk block numbers is __________. (answer in integer)
Note: $1\text{ K}=2^{10}$ and $1\text{ G}=2^{30}$.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 16417
Explanation
The number of disk blocks is $$\frac{2^{34}}{2^{11}}=2^{23}.$$ Each 2 KB block can store one 4-byte pointer to the next list block plus block numbers in the remaining $2048-4=2044$ bytes. Since each block number needs 4 bytes, one list block can hold $$\frac{2044}{4}=511$$ free-block numbers. Therefore, the number of blocks required is $$\left\lceil\frac{2^{23}}{511}\right\rceil=16417.$$ Hence the answer is 16417.