Free space management

As we know that the memory space in the disk is limited. So we need to use the space of the deleted files for the
allocation of the new file. one optical disk allows only one write at a time in the given sector and thus it is not physically
possible to reuse it for other files. The system maintains a free space list by keep track of the free disk space. The free
space list contains all the records of the free space disk block. Three free blocks are those which are not allocated to other
file or directory. When we create a file we first search for the free space in the memory and then check in the free space list
for the required amount of space that we require for our file. if the free space is available then allocate this space to the
new file. After that, the allocating space is deleted from the free space list. Whenever we delete a file then its free memory
space is added to the free space list.

The process of looking after and managing the free blocks of the disk is called free space management. There are some
methods or techniques to implement a free space list. These are as follows:

• Bitmap
• Linked list
• Grouping
• Counting

1. Bitmap
This technique is used to implement the free space management. When the free space is implemented as the bitmap or
bit vector then each block of the disk is represented by a bit. When the block is free its bit is set to 1 and when the block is
allocated the bit is set to 0. The main advantage of the bitmap is it is relatively simple and efficient in finding the first free
block and also the consecutive free block in the disk. Many computers provide the bit manipulation instruction which is
used by the users.

Assume the following are free. Rest are allocated:

Advantages:

• This technique is relatively simple.

Disadvantages:

• This technique requires a special hardware support to find the first 1 in a word it is not 0.
• This technique is not useful for the larger disks.

For example: Consider a disk where blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25,26, and 27 are free and the rest of the
blocks are allocated. The free-space bitmap would be: 001111001111110001100000011100000

2. Linked list
Linked List:

This is another technique for free space management. In this linked list of all the free block is maintained. In this, there is a
head pointer which points the first free block of the list which is kept in a special location on the disk. This block contains
the pointer to the next block and the next block contain the pointer of another next and this process is repeated. By using
this disk it is not easy to search the free list. This technique is not sufficient to traverse the list because we have to read
each disk block that requires I/O time. So traversing in the free list is not a frequent action.

Advantages:

• Whenever a file is to be allocated a free block, the operating system can simply allocate the first block in free
space list and move the head pointer to the next free block in the list.

Disadvantages:

• Searching the free space list will be very time consuming; each block will have to be read from the disk, which is
read very slowly as compared to the main memory.
• Not Efficient for faster access.

In our earlier example, we see that keep block 2 is the first free block which points to another block which contains the
pointer of the 3 blocks and 3 blocks contain the pointer to the 4 blocks and this contains the pointer to the 5 block then 5
block contains the pointer to the next block and this process is repeated at the last .

3. Grouping
This is also the technique of free space management. In this, there is a modification of the free-list approach which stores
the address of the n free blocks. In this the first n-1 blocks are free but the last block contains the address of the n blocks.
When we use the standard linked list approach the addresses of a large number of blocks can be found very quickly. In
this approach, we cannot keep a list of n free disk addresses but we keep the address of the first free block.
4. Counting
Counting is another approach for free space management. Generally, some contiguous blocks are allocated but some are
free simultaneously. When the free space is allocated to a process according to the contiguous allocation algorithm or
clustering. So we cannot keep the list of n free block address but we can keep the address of the first free block and then
the numbers of n free contiguous block which follows the first block. When there is an entry in the free space list it
consists the address of the disk and a count variable. This method of free space management is similar to the method of
allocating blocks. We can store these entries in the B-tree in place of the linked list. So the operations like lookup, deletion,
insertion are efficient.