1,010 views
1 votes
1 votes
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.

2 Answers

1 votes
1 votes

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  

edited by
0 votes
0 votes

We will assume block sizes of 1K. In terms of DF 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/

Related questions

1 votes
1 votes
3 answers
3
admin asked Oct 27, 2019
1,870 views
Consider a $4-TB$ disk that uses $4-KB$ blocks and the free-list method. How many block addresses can be stored in one block?
0 votes
0 votes
1 answer
4