/**/ Free-Space List Management - Dextutor Operating System

# Free-Space List Management

The capacity of any disk is limited (e.g., 500 GB, 1TB etc.). Thus, to accommodate our new files, the space freed by deleted files is reused by the system by maintaining a free-space list.
The free-space list keeps a record of all the free blocks of the disk. Whenever a new file is created by the user, the operating system searches for free blocks in the free-space list and allocates some blocks to the new file.
On deletion of a file, the blocks associated with that file are added to the free-space list. The free-space list is not always implemented as a list. Some common methods to implement free-space list:

1. Bit Vector
3. Grouping
4. Counting

#### Bit Vector

Free space is implemented using bit vector
Each block is represented by one bit
1 means free
0 means allocated
E.g 0011100101110001…………
which means that block 2,3,4,7,9,10,11,15 are free

• Simple
• Easy to find first free block
• Easy to find n consecutive free blocks

• Entire vector is to be kept in main memory – not possible for larger disks
• 1-Tb disk with 4Kb block size requires 32 Mb to store bit map

Keep pointer to first free block in disk
Traverse each block to find out the next free block.
E.g. in the above example, the pointer will point to first free block i.e., 2, Block 2 will contain the pointer to next free block i.e., 3 and so on

• Traversal is not easy and requires more time.

#### Grouping

Store addresses of n free blocks in the first free block
The first n-1 out of these are free while nth block contains addresses of another n free blocks.
E.g., Block 2 contains address of next 5 free blocks (3, 4, 5, 9, 10) out of which blocks 3, 4, 5 and 9 are free while block 10 contains the address of next five free blocks.

#### Counting

This approach is used hen several blocks are freed or allocated simultaneously (if contiguous memory allocation is used)
Keep address of first free block and the number(n) of free contiguous free blocks that follow
E.g., 001111001111110000111
Free-space list

```  address        count
2            3
8            5   ```

which means that starting from block 2, the next 3 blocks i.e., 3, 4 and 5 are free (total 4 blocks). Similarly, starting from block 8, the next 5 blocks are free.

```Previous                              Next