What approaches are using for managing free disk spaces? Explain linked list approaches with example.

The operating system keeps a record of which disk blocks are free, so it can allocate them to files and take them back when files are deleted. The main approaches are:

1. Bit vector (bitmap): one bit per block; 1 = free, 0 = allocated (or the reverse). It is compact and makes it easy to find runs of free blocks, but the whole map must be kept in memory for speed.
2. Linked list: all free blocks are linked together.
3. Grouping: the first free block stores the addresses of n free blocks; the last of those stores the next n, and so on. Many free blocks can be found quickly.
4. Counting: store the address of the first free block and the count of contiguous free blocks that follow it, which suits runs of free space.

Linked list approach

The OS keeps a pointer to the first free block (in the superblock or in memory). Each free block holds a pointer to the next free block, and the last free block holds NULL.

Example: blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26 and 27 are free.

free-list head -> [2] -> [3] -> [4] -> [5] -> [8] -> [9] -> ... -> [26] -> [27] -> NULL

• Allocating a block: take the block at the head and move the head to the block it points to.
• Freeing a block: make it point to the current head and make it the new head.

Advantages: no extra space is needed, because the pointers are stored inside the free blocks themselves; allocating a single block is fast.

Disadvantages: to find many free blocks, or contiguous free blocks, the list must be traversed block by block, and each step is a disk read, so it is slow. A damaged pointer can lose the rest of the list.