To keep track of free blocks in a file system, one of the two approaches is…
2026
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: 16417 — CONCEPTA linked-list storage block must reserve space for its link to the next storage block. Only the remaining bytes can hold free-block numbers. The…
Attempted by 42 students.
Show answer & explanation
Correct answer: 16417
CONCEPT
A linked-list storage block must reserve space for its link to the next storage block. Only the remaining bytes can hold free-block numbers.
The required number of storage blocks is the ceiling of total free-block numbers divided by the number of block numbers that fit in one storage block.
APPLICATION
Total disk blocks = (16 × 230) / (2 × 210) = 223 = 8,388,608.
Each 2 KB block has 2,048 bytes. After reserving the 4-byte next pointer, 2,048 − 4 = 2,044 bytes remain for block numbers.
A 32-bit block number occupies 4 bytes, so one list block stores 2,044 / 4 = 511 free-block numbers.
Storage blocks required = ⌈8,388,608 / 511⌉ = ⌈16,416.0626…⌉ = 16,417.
CROSS-CHECK
With 16,416 list blocks, the capacity is 16,416 × 511 = 8,388,576 block numbers, which is 32 short. One additional list block is therefore necessary.
Result: 16,417 blocks.