GATE 2025 CS (CS1) – Question 51
A disk of size 512M bytes is divided into blocks of 64K bytes. A file is stored in the disk using linked allocation. In linked allocation, each data block reserves 4 bytes to store the pointer to the next data block. The link part of the last data block contains a $NULL$ pointer (also of 4 bytes). Suppose a file of 1M bytes needs to be stored in the disk. Assume, 1K = $2^{10}$ and 1M = $2^{20}$. The amount of space in bytes that will be wasted due to internal fragmentation is ______. (Answer in integer)
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 65468
Explanation
Disk blocks are $64\text{ KB}=65536$ bytes. In linked allocation each block stores 4 bytes of pointer, so it holds $65536-4=65532$ bytes of data.
File size $=1\text{ MB}=1\,048\,576$ bytes. Number of blocks needed:
$$\left\lceil\frac{1\,048\,576}{65\,532}\right\rceil=\lceil16.0006\rceil=17.$$
The first 16 blocks hold $16\times65532=1\,048\,512$ bytes, so the last block holds only $1\,048\,576-1\,048\,512=64$ bytes of data. Its unused part is the internal fragmentation:
$$65\,532-64=\mathbf{65\,468}\text{ bytes}.$$