Free Space Management in OS

What is Free Space Management in OS?

There is a system software in an operating system that manipulates and keeps a 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-

Bitmap or Bit Vector

A bit vector is a most frequently used method to implement the free space list. A bit vector is also known as a Bit map. It is a series or collection of bits in which each bit represents a disk block. The values taken by the bits are either 1 or 0. If the block bit is 1, it means the block is empty and if the block bit is 0, it means the block is not free. It is allocated to some files. Since all the blocks are empty initially so, each bit in the bit vector represents 0.

Let us take an example:

Given below is a diagrammatic representation of a disk in which there are 16 blocks. There are some free and some occupied blocks present. The upper part is showing block number. Free blocks are represented by 1 and occupied blocks are represented by 0.

"Free block number" can be defined as that block which does not contain any value, $i.e.$, they are free blocks. The formula to find a free block number is :

We will consider the first 8 bits group ($0011110$) to constitute a non-zero word since all bits are not 0 here. Non-zero word is that word that contains the bit value 1 (block that is not free). Here, the first non-zero word is the third block of the group. So, the offset will be 3.

Hence, the block number $= 8 * 0 + 3 = 3$

Advantages of Bit vector method

• Simple and easy to understand.
• Consumes less memory.
• It is efficient to find free space.

Disadvantages of the Bit vector method

• The operating system goes through all the blocks until it finds a free block. (block whose bit is '0').
• It is not efficient when the disk size is large.

Linked List

A linked list is another approach for free space management in an operating system. In it, all the free blocks inside a disk are linked together in a linked list. These free blocks on the disk are linked together by a pointer. These pointers of the free block contain the address of the next free block and the last pointer of the list points to null which indicates the end of the linked list. This technique is not enough to traverse the list because we have to read each disk block one by one which requires I/O time.

In the above example, we have three blocks of free memory, each represented by a node in the linked list. The first block has 20 bytes of free memory, the second block has 20 bytes of free memory, and the third block has 60 bytes of free memory. The operating system can use this linked list to allocate memory blocks to processes as needed.

Advantage of the Linked list

• In this method, available space is used efficiently.
• As there is no size limit on a linked list, a new free space can be added easily.

Disadvantages

• In this method, the overhead of maintaining the pointer appears.
• The Linked list is not efficient when we need to reach every block of memory.

Grouping

The grouping technique is also called the "modification of a linked list technique". In this method, first, the free block of memory contains the addresses of the n-free blocks. And the last free block of these n free blocks contains the addresses of the next n free block of memory and this keeps going on. This technique separates the empty and occupied blocks of space of memory.

Example

Suppose we have a disk with some free blocks and some occupied blocks. The free block numbers are $3, 4, 5, 6, 9, 10, 11, 12, 13,$, and $14$. And occupied block numbers are $1, 2, 7, 8, 15,$ and $16$ $i.e.$, they are allocated to some files.

When the "grouping technique" is applied, block 3 will store the addresses of blocks 4, 5, and 6 because block 3 is the first free block. In the same way, block 6 will store the addresses of blocks 9, one 0, and one 1 because block 6 is the first occupied block.

Advantage of the Grouping method

1. By using this method, we can easily find addresses of a large number of free blocks easily and quickly.

Disadvantage

1. We need to change the entire list if one block gets occupied.

Counting

In memory space, several files are created and deleted at the same time. For which memory blocks are allocated and de-allocated for the files. Creation of files occupy free blocks and deletion of file frees blocks. When there is an entry in the free space, it consists of two parameters- "address of first free disk block (a pointer)" and "a number 'n'".

Example

Let us take an example where a disk has 16 blocks in which some blocks are empty and some blocks are occupied as given below :

When the "counting technique" is applied, the block number 3 will represent block number 4 because block 3 is the first free block. Then, the block stores the number of free blocks $i.e.$ - there are 4 free blocks together. In the same way, the first occupied block number 9 will represent block number 10 and keeps the number of rest occupied blocks i.e.- there are 6 occupied blocks as shown in the above figure.

Advantages

• In this method, a bunch of free blocks takes place fastly.
• The list is smaller in size.

Disadvantage

• In the counting method, the first free block stores the rest free blocks, so it requires more space.

Advantages and Disadvantages of Free Space Management Techniques in Operating Systems

Free space management is a critical component of operating systems, aiming to optimize the utilization of storage space. Below are the general advantages and disadvantages associated with these techniques.

Advantages

• Efficient Use of Storage Space: These techniques ensure optimal utilization of available space on hard disks and other secondary storage devices, minimizing wastage.
• Ease of Implementation: Some methods, like linked allocation, are straightforward and require minimal overhead in terms of processing and memory resources.
• Faster File Access: Techniques such as contiguous allocation help in reducing disk fragmentation, leading to quicker access times for files and improved system performance.

Disadvantages

• Fragmentation: Certain techniques, particularly linked allocation, can lead to fragmentation of disk space, reducing the efficiency of storage operations.
• Overhead: Techniques like indexed allocation may introduce additional overhead, necessitating more memory and processing power to maintain structures like index blocks.
• Limited Scalability: Some methods, such as the File Allocation Table (FAT), may not scale well, limiting the number of files that can be efficiently managed on the disk.
• Risk of Data Loss: In methods like contiguous allocation, if a file becomes corrupted or damaged, it may be challenging to recover the entire data, leading to potential data loss.