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

Hint:

Each 2 KB list block loses 4 bytes to its next pointer, leaving room for 511 four byte block numbers per block.

Answer 1

Correct Answer: 16417

Step 1: Count how many blocks exist on the whole disk.
\[ \text{Total blocks} = \frac{16\text{ GB}}{2\text{ KB}} = \frac{2^{34}}{2^{11}} = 2^{23} = 8388608 \]
This is the largest possible number of free block numbers we might have to store.

Step 2: Work out the raw byte requirement for storing all these numbers.
Each block number takes $4$ bytes ($32$ bits), so storing all of them, ignoring the pointer overhead for a moment, would take
\[ 8388608 \times 4 = 33554432 \text{ bytes} \]

Step 3: Work out the usable space inside one list block.
Each list block is $2048$ bytes, but $4$ of those bytes are used up by the next block pointer, so only $2048-4=2044$ bytes in each block actually store block numbers, which is $511$ numbers per block, since $2044/4=511$.

Step 4: Find how many list blocks are needed using a ceiling division.
We need the smallest whole number of blocks $n$ such that $511\,n \geq 8388608$. Dividing directly,
\[ n \geq \frac{8388608}{511} \approx 16416.06 \]
so $n$ must be at least $16417$, the next whole number up from $16416.06$, since $16416$ blocks alone can only hold
\[ 511 \times 16416 = 8388576 \]
which is $32$ short of the full $8388608$ block numbers we need to store.

Step 5: Confirm with the extra block.
One more block adds room for another $511$ numbers, comfortably covering the missing $32$, so $16417$ blocks are enough and $16416$ are not.
\[ \boxed{16417} \]