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}\)

Hint:

Find total disk blocks as (disk size)/(block size). Each list block uses 4 bytes for the next pointer, leaving (block size - 4)/4 slots for free block numbers. Divide total blocks by this count and round up.

Answer 1

Correct Answer: 16417

This question is about the linked list method of free space management in a file system.

Step 1: Find the total number of blocks on the disk.

Disk size = 16 GB = \(16 \times 2^{30}\) bytes

Block size = 2 KB = \(2 \times 2^{10}\) bytes

Total blocks on disk = \(\dfrac{16 \times 2^{30}}{2 \times 2^{10}} = 8 \times 2^{20} = 2^{23} = 8388608\) blocks

In the worst case, all these blocks can be free, so the free list must be able to hold up to 8388608 block numbers.

Step 2: Find how many free block numbers fit in one list block.

Each block number is 32-bit long, so it needs 4 bytes.

In the linked list scheme, every block that is part of the free list reserves the first 4 bytes for a pointer to the next block of the list, and the remaining space in that block is used to store actual free block numbers.

Space available for storing block numbers in one block = \(2048 - 4 = 2044\) bytes

Number of free block numbers that fit in one block = \(\dfrac{2044}{4} = 511\)

Step 3: Compute the number of blocks needed to hold all free block numbers.

Number of blocks required = \(\left\lceil \dfrac{8388608}{511} \right\rceil\)

Check: \(511 \times 16416 = 8388576\), which is 32 less than 8388608.

Since 16416 blocks are not enough (they can only store 8388576 numbers), one more block is needed to store the remaining 32 block numbers.

So the number of blocks required = \(16416 + 1 = 16417\)

Final Answer:

\[\boxed{16417}\]