Consider using a bitmap versus a linked list of free blocks. The disk contains a total of B blocks, F of which are free. A disk address requires d bits. The bitmap uses one bit for each block. The linked list is a data structure maintained in a dedicated portion of the disk. Each list element points to a single free block. (a) State the condition under which the two methods use the same amount of disk space, assuming that the linked-list method connects all blocks individually.
(b) For d = 16 bits, determine the fraction of the disk that must be free for the above condition to hold.
(c) Repeat the two problems above, assuming that the linked-list method connects groups of adjacent blocks, rather than individual blocks. That means, each list element points to the first of block of a group, and contains a two-byte number indicating how many blocks are in the group. The average size of a group is five blocks.