Bit Vector

• Frequently, the free-space list is implemented as a bit map or bit vector.
• 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

  001111001111110001100000011100000 ...
  

• The main advantage of this approach is its relative simplicity and its efficiency in finding the first free block or $n$ 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 ( $1.3*1020*1024*1024/512/8/1.024=332.8~KB$).
• A 40-GB disk with 1-KB blocks requires over 5 MB to store its bit map ( $40*1020*1024*1024/1024/8/1.024=5.12~MB$).
• 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 ( $(500x10^9/1KB)/1024/8$).