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

Correct Answer: 65468

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 effective data capacity per block.Since every block (including the last one) must set aside 4 bytes for a pointer, the actual space available for file data in each block is:$$\text{Effective Capacity} = \text{Block size} - \text{Pointer size} = (64 \times 2^{10}) - 4 = 65,532 \text{ bytes}.$$Step 2: Determine the total number of blocks needed to accommodate the file.To find the number of blocks, we divide the total file size by the effective capacity per block:$$\text{Number of blocks} = \left\lceil \frac{\text{File size}}{\text{Effective Capacity}} \right\rceil = \left\lceil \frac{1,048,576}{65,532} \right\rceil = \lceil 16.0009 \rceil = 17 \text{ blocks}.$$Step 3: Calculate the internal fragmentation in the 17th block.The first 16 blocks are completely filled with data. The amount of data spilling into the 17th block is:$$\text{Data in last block} = 1,048,576 - (16 \times 65,532) = 1,048,576 - 1,048,512 = 64 \text{ bytes}.$$The total space occupied in the last block is the data plus the 4-byte NULL pointer ($64 + 4 = 68$ bytes). The remaining unused space (internal fragmentation) is:$$\text{Internal fragmentation} = \text{Block size} - (\text{Data in last block} + \text{Pointer})$$$$\text{Internal fragmentation} = 65,536 - 68 = 65,468 \text{ bytes}.$$Thus, the total internal fragmentation due to the last block is $\boxed{65468}$ bytes.