Dark Mode

52 votes

Best answer

Bit map maintains one bit for each block, If it is free then bit will be "$0$" if occupied then bit will be "$1$".

For space purpose, it doesn't matter what bit we are using, only matters that how many blocks are there.

For $B$ blocks, Bit map takes space of "$B$" bits.

Free list is a list that maintains addresses of free blocks only. If we have $3$ free blocks then it maintains $3$ addresses in a list, if $4$ free blocks then $4$ address in a list and like that.

Given that we have $F$ free blocks, therefore $F$ addresses in a list, and each address size is d bits therefore Free list takes space of "$Fd$".

condition under which the free list uses less space than the bit map: $Fd<B$

0

0

Anyone please let me know if the below approach is correct:

My attempt)

# of disks = 2$^{d}$

# of blocks free in each disk = F

Total # of blocks in each disk = B

# of bits in block address = log B

We require (d + log B) bits to address a free block in a disk and there are 2$^{d}$ $\times$ F free blocks in total.

So, free list size = 2$^{d}$ $\times$ F $\times$ (d + log B)

For, free list to occupy less size than bit map, we need to have 2^d $\times$ F $\times$ (d + log B) < 2$^{d}$ $\times$ B

Canceling the common terms that would give, F $\times$ (d + log B) < B

1

11 votes

Solution for Part a :-

Assume that size of each block is S bits.

Then no of bits required for free list is = Fd, No of blocks required = Fd/S

No of bits required for Bit map = B (No of blocks ) , No of block required is = B /S

Condition under which free list uses less space than the bit map.

Fd / S < B / S

Assume that size of each block is S bits.

Then no of bits required for free list is = Fd, No of blocks required = Fd/S

No of bits required for Bit map = B (No of blocks ) , No of block required is = B /S

Condition under which free list uses less space than the bit map.

Fd / S < B / S

0