GATE CS 2026 Set 2 Q.53: File Systems, I/O and Disk Scheduling

To keep track of free blocks in a file system, one of the two approaches is generally used - using bitmaps (bit vectors) or using linked lists. Consider that the linked list approach is used to keep track of free blocks in a file system. Assume that the disk size is 16 GB, block size is 2 KB, and block numbers used are 32-bit long. A single pointer of size 4 bytes is used in each block of the list to point to the next block of the list. 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}$

Your answer

Official answer and solution

Official answer: 16417
From: Official GATE 2026 answer key

Solution

Calculate the total number of disk blocks and divide by the number of free-block addresses stored per 2 KB index block.

Total number of blocks on the disk:

N = \frac{16\text{ GB}}{2\text{ KB}} = \frac{2^{34}}{2^{11}} = 2^{23} = 8,388,608 \text{ blocks}

Each $2\text{ KB} = 2048\text{ byte}$ block in the linked list uses $4$ bytes for the pointer to the next list block, leaving $2048 - 4 = 2044$ bytes to store 32-bit ( $4$ -byte) free block numbers:

\text{Addresses per block} = \frac{2044}{4} = 511

Therefore, the number of blocks required to hold all $2^{23}$ block numbers is:

\left\lceil \frac{2^{23}}{511} \right\rceil = \left\lceil \frac{8,388,608}{511} \right\rceil = \lceil 16416.0626 \rceil = 16417

Final answer

16417

Common trap

Dividing by 512 instead of 511 (forgetting the 4-byte next-block pointer in each block).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 2 (CS2)
Question: 53 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source