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

Let us solve this by directly building the free list structure rather than just dividing totals.

Setting up the numbers:

Total disk capacity is \(16 \text{ GB} = 16 \times 2^{30}\) bytes, and each block is \(2 \text{ KB} = 2 \times 2^{10}\) bytes.

So the disk is divided into \(\dfrac{16 \times 2^{30}}{2 \times 2^{10}} = 2^{23} = 8388608\) blocks in total. Since every block could potentially be free at once (worst case), the free-block list must be able to reference all 8388608 blocks by their 32-bit (4 byte) block number.

How one list block is organized:

A block used in the free list is not entirely filled with block numbers - the file system needs to chain these blocks together, so 4 bytes of every 2048 byte block are used up by a 'next block' pointer.

That leaves \(2048 - 4 = 2044\) usable bytes per block for storing free block addresses. Since each address takes 4 bytes:

\(\dfrac{2044}{4} = 511\) addresses can be stored per block.

Chaining enough blocks together:

We now ask: how many such 511-address blocks, chained one after another, are needed to list all 8388608 free block numbers?

\(8388608 / 511 = 16417.05...\), which is not a whole number, so we cannot stop at 16416 blocks.

Indeed \(16416 \times 511 = 8388576\) addresses only, leaving \(8388608 - 8388576 = 32\) addresses unaccounted for. These 32 addresses need one extra block.

Therefore total blocks needed \(= 16416 + 1 = 16417\).

\[\boxed{16417}\]