GATE2025_CS1_Q51

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¹⁰ and 1M = 2²⁰. The amount of space in bytes that will be wasted due to internal fragmentation is ______. (Answer in integer)

✅ Final Answer:

The correct answer is 65468.

🔹 Short Answer:

Internal fragmentation occurs in the last block of the file. First, calculate the usable data space per block: 64K bytes (65536) - 4 bytes (pointer) = 65532 bytes. Next, determine how many blocks are needed for a 1M byte (1048576) file: 1048576 / 65532 = 16.01..., so 17 blocks are needed. The first 16 blocks store 16 * 65532 = 1048512 bytes. The last block stores the remaining 1048576 - 1048512 = 64 bytes. The wasted space in this last block is 65532 (usable space) - 64 (data) = 65468 bytes.

🔸 Long Answer:

This problem requires us to calculate the internal fragmentation for a file stored using linked allocation. Internal fragmentation is the wasted space *within* an allocated block.

Step 1: Convert all sizes to bytes

• File Size: 1M bytes = 1 × 2²⁰ bytes = 1,048,576 bytes
• Block Size: 64K bytes = 64 × 2¹⁰ bytes = 2⁶ × 2¹⁰ = 2¹⁶ bytes = 65,536 bytes
• Pointer Size: 4 bytes

Step 2: Calculate the Effective (Usable) Block Size

In linked allocation, each block must reserve some space for the pointer to the next block. This space cannot be used for file data.

Effective Block Size = Total Block Size - Pointer Size
Effective Block Size = 65,536 - 4 = 65,532 bytes

Step 3: Determine the Number of Blocks Required

The file's data will be stored in chunks of this effective size. We need to find how many such blocks are required to store the entire file.

Number of Blocks = ceil( Total File Size / Effective Block Size )
Number of Blocks = ceil( 1,048,576 / 65,532 )
Number of Blocks = ceil( 16.017... ) = 17 blocks

Step 4: Calculate Internal Fragmentation in the Last Block

The first 16 blocks will be completely filled with data. The internal fragmentation occurs only in the 17th (last) block, which will be partially filled.

• Data in first 16 blocks: 16 × 65,532 bytes = 1,048,512 bytes.
• Data remaining for the last block: Total File Size - Data in first 16 blocks = 1,048,576 - 1,048,512 = 64 bytes.

The last block has 65,532 bytes of usable space but only stores 64 bytes of data.

The wasted space is the unused portion of the data area in this last block.

Wasted Space = Usable Space in Last Block - Data in Last Block
Wasted Space = 65,532 - 64 = 65,468 bytes

Bibliography:
- Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts. Wiley. (Chapter 11: File-System Implementation).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.