Frequently, the free-space list is implemented as a
Each block is represented by 1 bit.
If the block is free, the bit is 1;
If the block is allocated, the bit is O.
For example, consider a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18,25,26, and 27 are free and the rest of the blocks are allocated.
The free-space bit map would be
The main advantage of this approach is its relative simplicity and its efficiency in finding the first free block or
consecutive free blocks on the disk.
Unfortunately, bit vectors are inefficient unless the entire vector is kept in main memory (and is written to disk occasionally for recovery needs).
Keeping it in main memory is possible for smaller disks but not necessarily for larger ones.
A 1.3-GB disk with 512-byte blocks would need a bit map of over 332 KB to track its free blocks, although clustering the blocks in groups of four reduces this number to over 83 KB per disk (
A 40-GB disk with 1-KB blocks requires over 5 MB to store its bit map (
A 500-GB disk with a 1-KB block and a 32-bit (4 bytes) disk block number, we need 488 million bits for the map, which requires just under 60000 1-KB blocks to store (
Cem Ozdogan 2011-02-14