Free Space Management , Bit Vector , Linked List , Grouping , Counting , Advantages of Free Space Management

 

Free Space Management

What is Free Space Management in OS ?

There is a system software in an operating system that manipulates and keeps track of free spaces to allocate and de-allocate memory blocks to files, this system is called a "file management system in an operating system". There is a "free space list" in an operating system that maintains the record of free blocks.

When a file is created, the operating system searches the free space list for the required space allocated to save a file. While deletion a file, the file system frees the given space and adds this to the "free space list"

Methods of Free Space Management in OS

It is not easy work for an operating system to allocate and de-allocate memory blocks (managing free space) simultaneously. The operating system uses various methods for adding free space and freeing up space after deleting a file. There are various methods using which a free space list can be implemented. We are going to explain them below-

A file system is responsible to allocate the free blocks to the file therefore it has to keep track of all the free blocks present in the disk. There are mainly two approaches by using which, the free blocks in the disk are managed.

1. Bit Vector

In this approach, the free space list is implemented as a bit map vector. It contains the number of bits where each bit represents each block.

If the block is empty then the bit is 1 otherwise it is 0. Initially all the blocks are empty therefore each bit in the bit map vector contains 1.

LAs the space allocation proceeds, the file system starts allocating blocks to the files and setting the respective bit to 0.

A Bitmap or Bit Vector is series or collection of bits where each bit corresponds to a disk block. The bit can take two values: 0 and 1: 0 indicates that the block is allocated and 1 indicates a free block.
The given instance of disk blocks on the disk in Figure 1 (where green blocks are allocated) can be represented by a bitmap of 16 bits as: 0000111000000110.

Advantages –

• Simple to understand.
• Finding the first free block is efficient. It requires scanning the words (a group of 8 bits) in a bitmap for a non-zero word. (A 0-valued word has all bits 0). The first free block is then found by scanning for the first 1 bit in the non-zero word.

The block number can be calculated as:
(number of bits per word) *(number of 0-values words) + offset of bit first bit 1 in the non-zero word .

For the Figure-1, we scan the bitmap sequentially for the first non-zero word.
The first group of 8 bits (00001110) constitute a non-zero word since all bits are not 0. After the non-0 word is found, we look for the first 1 bit. This is the 5th bit of the non-zero word. So, offset = 5.
Therefore, the first free block number = 8*0+5 = 5.

2. Linked List

It is another approach for free space management. This approach suggests linking together all the free blocks and keeping a pointer in the cache which points to the first free block.

Therefore, all the free blocks on the disks will be linked together with a pointer. Whenever a block gets allocated, its previous free block will be linked to its next free block.

In this approach, the free disk blocks are linked together i.e. a free block contains a pointer to the next free block. The block number of the very first disk block is stored at a separate location on disk and is also cached in memory.

In Figure-2, the free space list head points to Block 5 which points to Block 6, the next free block and so on. The last free block would contain a null pointer indicating the end of free list.
A drawback of this method is the I/O required for free space list traversal.

1. Grouping –
   This approach stores the address of the free blocks in the first free block. The first free block stores the address of some, say n free blocks. Out of these n blocks, the first n-1 blocks are actually free and the last block contains the address of next free n blocks.
   An advantage of this approach is that the addresses of a group of free disk blocks can be found easily.
2. Counting –
   This approach stores the address of the first free disk block and a number n of free contiguous disk blocks that follow the first block.
   Every entry in the list would contain:
   1. Address of first free disk block
   2. A number n

   For example, in Figure-1, the first entry of the free space list would be: ([Address of Block 5], 2), because 2 contiguous free blocks follow block 5.