Andrew S. Tanenbaum (OS) Edition 4 Exercise 4 Question 24 (Page No. 334)

Question

Free disk space can be kept track of using a free list or a bitmap. Disk addresses require $D$ bits. For a disk with $B$ blocks, $F$ of which are free, state the condition under which the free list uses less space than the bitmap. For $D$ having the value $16$ bits, express your answer as a percentage of the disk space that must be free.

Comments

https://gateoverflow.in/1740/gate1998-25-a

Answer 1

The bit map would require $B$ bits. The free list would require $D \times F$ bits.

The free list requires fewer bits if $DF < B.$

Alternatively, the free list is shorter if $(F/B) < (1/D)$ , where $(F/ B)$ is the fraction of blocks free.

For $16-bit$ disk addresses, the free list is shorter if $6.25 \%$ or less of the disk is free.

Detailed Video Solution: GATE CSE 1998 | Question: 25-a - Free disk space using free list & a bit map 

"Free Disk Space Management" Complete Lecture: Free Disk Space Management - Bitmap, Free List  

Answer 2

We will assume block sizes of 1K. In terms of D, F and B, the formulae are as follows:

Free List Size (in bits):   (F*1024)*D
Bit Map Size (in bits):   B*1024

Thus the Free List will use less memory if F*D&leB.

If D=16, the ratio of F to B is 1/16. This is equivalent to 6.25% disk free space.

 

https://www.classes.cs.uchicago.edu/archive/1999/spring/CSPP530/hwSolutions/hw8/