Since there is only a limited amount of space available on a disk, it is useful to reuse the space of deleted files for new files, if possible, since write-only media (optical media) only allow one write and reuse is physically impossible. To keep track of free space on the disk, the system maintains a free space list. This list stores all the free disk blocks that are not allocated to a file or directory. To create a new file, the system searches the list for the required free space, and then removes it from the list. When a file is deleted, the address of the file is added to the list.
1. Using Vector Bits
Often the empty space list is implemented as a bit map or bit vector. Each block is represented as 1 bit. If the block is empty then the bit is 1 and if the block is being allocated then the bit is 0. For example, a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 and 27 are empty, and the rest are allocated. The bit map would look like this:
001111001111110001100000011100000...The main advantage of this approach is that it is relatively simple and efficient to find the first free block or n consecutive free blocks on the disk. Many computers provide bit manipulation instructions that can be used effectively for this purpose. For example, the Intel family of processors starting with the 80386 and the Motorola family starting with the 68020 (the processors found in both the PC and Macintosh) have instructions that return the distance in a word from the first bit of 1. The Apple Macintosh operating system uses a bit vector method to allocate disk space. The hardware supports the software, but bit vectors are inefficient unless the entire vector is stored in main memory (and written to disk for recovery purposes). Storing in main memory is possible for small disks on microcomputers, but not for large disks. A 1.3 GB disk with 512-byte blocks would require a bit map of 332K to keep track of the free blocks.
2. Linked List
Another approach is to connect all the free blocks, store a pointer to the first free block in a special place on disk and store it in memory. This first block stores a pointer to the next free block and so on. In the previous example we would store the pointer to block 2 as the first free block, block 2 would store a pointer to block 3, which would point to block 4 and so on. However this method is inefficient because to traverse the list we need to read each block which takes I/O time. Fortunately this traverse is not used very often. Generally, the operating system needs free blocks to allocate them to a file, so the first block in the free space list is used.
3. Grouping
Another modification is to store the addresses of n empty blocks in the first empty block. The first n-1 of these blocks are empty. The last block stores the addresses of another n empty blocks and so on. The advantage of this implementation is that the addresses of very large empty blocks can be found quickly, unlike the standard linked-list approach.
4. Counting
Another approach is to take advantage of the fact that several contiguous blocks will be allocated or freed simultaneously. So instead of keeping a list of many disk addresses, we can keep the address of the first free block and the number of contiguous free blocks that follow the first free block. Each entry in the list holds a disk address and a counter. Although each entry takes up more space, the overall list is shorter, as long as count is greater than one.