Question

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)

Hint:

In linked allocation, the space reserved for pointers in each data block contributes to internal fragmentation, especially in the last block, where it may not be fully utilized.

Answer 1

We are given the following information:
Disk size: 512M bytes = \( 512 \times 2^{20} \) bytes.
Block size: 64K bytes = \( 64 \times 2^{10} \) bytes.
File size: 1M bytes = \( 2^{20} \) bytes.
Each data block reserves 4 bytes for the pointer to the next block.
The last block reserves 4 bytes for a NULL pointer.

Step 1: Calculate the number of blocks required to store the file.
The file size is 1M bytes, and each data block is 64K bytes. Therefore, the number of data blocks required is: \[ \text{Number of blocks} = \frac{\text{File size}}{\text{Block size}} = \frac{2^{20}}{64 \times 2^{10}} = \frac{2^{20}}{2^{16}} = 2^{4} = 16 \text{ blocks}. \]
Step 2: Calculate the total space used by the blocks.
Each block is 64K bytes, and we have 16 blocks. Therefore, the total space used by all blocks is: \[ \text{Total space used} = 16 \times 64K = 16 \times 64 \times 2^{10} = 1024 \times 2^{10} = 2^{20} \text{ bytes}. \]
Step 3: Calculate the internal fragmentation in the last block.
The last block stores the data of the file, but it also reserves 4 bytes for the pointer. So, the amount of space that is wasted in the last block (internal fragmentation) is: \[ \text{Internal fragmentation} = \text{Block size} - (\text{Data size in last block} + 4 \text{ bytes for the pointer}). \] We already know that the last block contains \( 64K - 4 = 64 \times 2^{10} - 4 \) bytes of actual data. Therefore, the amount of internal fragmentation is: \[ \text{Internal fragmentation} = 64K - 4 = 64 \times 2^{10} - 4 = 65536 - 4 = 65468 \text{ bytes}. \]
Thus, the total internal fragmentation due to the last block is \( \boxed{65468} \) bytes.