GATE CSE 2026 | Set 2 | Question: 43

Question

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 \mathrm{K}=2^{10}$ and $1 \mathrm{G}=2^{30}$

Comments

$$\text{Block number size} = 32 \text{ bits} = 4B$$ $$\text{Entries per block} = \frac{\text{block size} - \text{pointer size}}{\text{entry size}} = \frac{2048 - 4}{4} = 511$$ $$\text{Total disk blocks} = \frac{16 \times 2^{30}}{2 \times 2^{10}} = 2^{23} = 8388608$$ $$\text{Blocks required} = \lceil \frac{8388608}{511} \rceil = 16416$$ $$Answer = 16416$$

---

someone please help here ,  why we are not excluding number of blocks use for storing free block data
this equal we say let x = number of blocks used for storing free block
then its 511*X = 2^23 - X
which is 2^14

please help

---

i think this is due to the question wording like  :

"the number of blocks required to hold the free disk block numbers"

It  not say that the blocks used to hold this list are themselves to be substracted from the set of blocks whose numbers are being stored. 

its my perspective if you get better explaination please share 

---

We ARE excluding the blocks used for storing the free-block information.
That is precisely why the equation has -x.

Answer 1

Answer : (16417)

Comments

Where did you learned COA from, I am weak at this subject can you share resources please 🙏

---

@S_Sandeep I have learnt Complete COA from Deepak Sir @GO Classes , And if you don't have subscription of GO Classes then please visit their you tube channel , almost 80% syllabus of COA is there.

---

@Rich Amrutiya is this question from topic file organization OS 

---

Yes you can consider this question from file organization.

Answer 2

disk size = 16gb

block size (single) = 2kb

total no. of blocks = disk size / block size 

= 16gb / 2 kb = 2^23 ( = 8388608 )

now, 

each block size = 2kb = 2048 bytes

extra pointer size = 4 bytes 

usable or left space for storing block number = 2048 - 4 bytes = 2044 bytes 

block no.  used = 32-bits = 32/8 bytes = 4 bytes

No. of entries per block = total available space / space utilised by each block = 2044 / 4 = 511 

no. of blocks required = total no. of blocks / no. of entries per block = 8388608 / 511 = 16416.06

(always take Ceil Value) i.e., if decimal present remove decimal and add 1 to value before decimal 

= 16416+1= 16417 (final ans)    

Answer 3

Long but better to understand 

Answer 4

$$\text{Block number size} = 32 \text{ bits} = 4B$$

$$\text{Entries per block} = \frac{\text{block size} - \text{pointer size}}{\text{entry size}} = \frac{2048 - 4}{4} = 511$$

$$\text{Total disk blocks} = \frac{16 \times 2^{30}}{2 \times 2^{10}} = 2^{23} = 8388608$$

$$\text{Blocks required} = \lceil \frac{8388608}{511} \rceil = 16417$$

$$Answer = 16417$$

Comments

It should be 16417 .. ceil value of (16416.06) = 16417

---

@Chirag P changed . thanxs for pointing out

Answer 5

Linked List Approach

In the linked-list approach for managing free disk blocks, we maintain a list of disk blocks that contain the addresses of free blocks.

Since it is generally not possible to store the addresses of all free blocks in a single block, multiple list blocks are used.

Each list block contains:

Pointers to free blocks + 1 pointer to the next list block

Given

• Block number size = 32 bits = 4 B
• Block size = 2 KB = 2048 B

Since 1 pointer is required to point to the next list block:

Space available for free-block pointers

= 2048 − 4

= 2044 B

Therefore, the number of free-block pointers that can be stored in one list block is:

⌊2044 / 4⌋ = 511 pointers

Thus, 1 list block can store the addresses of 511 free blocks.

Total Number of Blocks

Total disk size = 16 GB

Block size = 2 KB

Therefore,

Number of blocks

= 16 GB / 2 KB

= 2³⁴ / 2¹¹

= 2²³ blocks

Number of List Blocks Required

Since one list block can store 511 free-block addresses:

Number of list blocks

= ⌈2²³ / 511⌉

= 16,417 list blocks

Therefore, 16,417 list blocks are required to store the addresses of all 2²³ disk blocks.

Answer 6

Free-Space Management: Linked List Allocation

1. Problem Parameters

• Disk Capacity: $16\text{ GB} = 2^{34}\text{ bytes}$

• Block Size: $2\text{ KB} = 2^{11}\text{ bytes}$

• Block Number Size: $32\text{ bits} = 4\text{ bytes}$

• Pointer Size: $4\text{ bytes}$ (1 per list block)

2. Step-by-Step Solution

Step 1: Calculate Total Disk Blocks

Divide total disk capacity by the block size to find the maximum number of blocks the disk can hold.

 

$$\frac{2^{34}\text{ bytes}}{2^{11}\text{ bytes}} = 2^{23}\text{ blocks} = 8,388,608\text{ blocks}$$

Step 2: Determine Usable Slots per Linked-List Block

Subtract the space required for the next-block pointer from the total block size, then divide by the size of a single block number.

 

$$\frac{2048\text{ bytes} - 4\text{ bytes (pointer)}}{4\text{ bytes (per block number)}} = 511\text{ block numbers}$$

Step 3: Calculate Required Linked-List Blocks

Divide the total number of disk blocks by the capacity of a single linked-list block. Always apply the ceiling function, as a fractional block requires a full physical block.

 

$$\left\lceil\frac{2^{23}}{511}\right\rceil = \left\lceil\frac{8,388,608}{511}\right\rceil = 16,417\text{ blocks}$$

The "Pointer Trap"

A common error is dividing $2048$ by $4$ to get $512$ slots. This fails to account for the mandatory $4\text{-byte}$ pointer required to link to the next block, leaving only $511$ usable slots.

 

3. Comparison: Bitmap vs. Linked List

For a disk of this size ($2^{23}$ total blocks), the free-space management footprint differs heavily based on the chosen method.

 

Feature	Bitmap (Bit Vector)	Linked List (Empty Disk)
Storage Mechanism	$1\text{ bit}$ per block	$4\text{ bytes}$ per free block
Maximum Overhead	$2^{23}\text{ bits} = 1\text{ MB}$	$16,417\text{ blocks} \times 2\text{ KB} \approx 32.8\text{ MB}$
Overhead Type	Static: Always consumes $1\text{ MB}$ regardless of disk utilization.	Dynamic: Shrinks as the disk fills and blocks are allocated.
Lookup Speed	Fast contiguous scanning for multiple blocks.	Slow sequential traversal for multiple blocks.

 

4. Advanced Variation: Grouping

Instead of maintaining a continuous chain where every block holds one pointer to the next, Grouping stores the addresses of $n$ free blocks inside the first free block.

 

• The first $n-1$ addresses point to actual free data blocks.

• The $n^{th}$ address points to another index block containing the next batch of addresses.

This drastically reduces traversal time and the number of blocks strictly dedicated to overhead, allowing the OS to allocate large chunks of space rapidly.