The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+17 votes
Free disk space can be used to keep track of using a free list or a bit map. 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 bit map.
in Operating System by Veteran (52.1k points)
edited by | 1.4k views

2 Answers

+30 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$

by Boss (17.5k points)
edited by
what is tree list ?? or is it free list ??
its free list. tree list typo
Free  list  = Fd bits = F * $\left \lceil log B \right \rceil$

Bit map  = B bits

if all bocks are free then F=B

so  B * $\left \lceil log B \right \rceil$ $\geqslant$ B
+10 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
by Boss (41.3k points)
why divide by S ??

in the above selected answer there is no such division and condition FD<B is sufficient i think ?

explain your approach please .

@nikunj he just explained in terms of disk blocks assuming size of each block to be S bits. 

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,288 questions
55,716 answers
90,102 users