Free-Space Management

Another important aspect of disk management is keeping track of and allocating free space.

Free space management can be done by:

1.      Bit Vector

·         One simple approach is to use a bit vector, in which each bit represents a disk block, set to 1 if free or 0 if allocated.

·         Fast algorithms exist for quickly finding contiguous blocks of a given size

·         The down side is that for example, a 40GB disk requires over 5MB just to store the bitmap.

2.      Linked List

·         A linked list can also be used to keep track of all free blocks.

·         Traversing the list and/or finding a contiguous block of a given size are not easy, but fortunately are not frequently needed operations. Generally the system just adds and removes single blocks from the beginning of the list.

·         The FAT table keeps track of the free list as just one more linked list on the table.

3.      Grouping

·         A variation on linked list free lists is to use links of blocks of indices of free blocks. If a block holds up to N addresses, then the first block in the linked-list contains up to N-1 addresses of free blocks and a pointer to the next block of free addresses.

4.      Counting

·         When there are multiple contiguous blocks of free space then the system can keep track of the starting address of the group and the number of contiguous free blocks. As long as the average length of a contiguous group of free blocks is greater than two this offers a savings in space needed for the free list.

5.      Space Maps

·         Sun's ZFS file system was designed for HUGE numbers and sizes of files, directories, and even file systems.

·         The resulting data structures could be VERY inefficient if not implemented carefully. For example, freeing up a 1 GB file on a 1 TB file system could involve updating thousands of blocks of free list bit maps if the file was spread across the disk.

·         ZFS uses a combination of techniques, starting with dividing the disk up into ( hundreds of ) metaslabs of a manageable size, each having their own space map.

·         Free blocks are managed using the counting technique, but rather than write the information to a table, it is recorded in a log-structured transaction record. Adjacent free blocks are also coalesced into a larger single free block.

·         An in-memory space map is constructed using a balanced tree data structure, constructed from the log data.

·         The combination of the in-memory tree and the on-disk log provide for very fast and efficient management of these very large files and free blocks.