What is the "free list" method and the bitmap method for disk space allocation?

I understand that the free list method lists all sectors that are free and the bitmap method lists all sectors regardless, but this question confuses me:

Compare the bit-map and hole-list methods for

keeping track of free space on a disk with 800

cylinders, each one having 5 tracks of 32

sectors.

How many holes would it take before the holelist

would be larger than the bit-map? Assume the

allocation unit is the sector, a hole requires a 32-

bit word in the free-list and the bit-map uses a

32-bit word per allocation unit (or sector).

Surely if they are both 32 bit then you wouldn't be able to get a free list that was larger than the bit map?

1 Answer

Relevance
  • Anonymous
    1 decade ago
    Favorite Answer

    another warwick engineer sitting the ES2A2 module?

    I don't really understand it either, however, here is the answer that I copied down in the lecture

    Disk has 800 x 5 x 32 = 128000 sectors

    Bit-map requires 128000 / 32 = 4000 words (irrespective of number of free sectors or holes) 128000 is used here because the allocation unit is the sector. And of course the word length is 32.

    So, if there are fewer than 4000 holes --> free list wins

    If there are more than 4000 holes --> bit map wins.

    The thing I can't understand is, why would a free list not win all the time? I mean, it can shrink and grow according to the number of free sectors, so surely it is more favourable in all instances? The only thing I can conclude is that, for some reason, a free list is more efficient for small amounts of free space, and a bit map is more efficient for large amounts of free space. Can't really comment any more than that!! Best ask Crofty. And if you do, please let me know the answer! Email A.T.Lord@warwick.ac.uk I would email him but I've been bombarding him with questions throughout the year and I don't want to annoy or overwhelm him lol.

    Source(s): es2a2 warwick engineering lecture 12 by dr bill crofts
    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.