Free Space Management in Operating System (OS)

Commonly used free space management techniques

Linked Allocation

In this technique, files are stored in a linked list manner in disk blocks. Each block contains the address to the next block.

Contiguous Allocation 

In this technique, files are stored in a contiguous block in disk space.

Indexed Allocation 

In this technique, files are stored in a linked list of disk blocks where the directory entry for the file also contains an index block. The index block contains the addresses of the first few blocks in a linked list.

File Allocation Table (FAT) 

In this technique, tables are used to track the allocation of disk space. Each entry indicates whether the block is free or allocated, and if allocated, then it indicates to which block it belongs.

Volume Shadow Copy

It is a feature of some operating systems that creates a snapshot of a volume at a specific point in time.

Methods of Free Space Management in OS

There are four methods of doing free space management in operating systems. These are as follows-

• Bit Vector
• Linked List
• Grouping
• Counting

First, we will discuss the Bit Vector method.

Bit Vector

The first method that we will discuss is the bit vector method. Also known as the bit map, this is the most frequently used method to implement the free space list. In this method, each block in the hard disk is represented by a bit (either 0 or 1). If a block has a bit 0 means that the block is allocated to a file, and if a block has a bit 1 means that the block is not allocated to any file, i.e., the block is free.

For example, consider a disk having 16 blocks where block numbers 2, 3, 4, 5, 8, 9, 10, 11, 12, and 13 are free, and the rest of the blocks, i.e., block numbers 0, 1, 6, 7, 14 and 15 are allocated to some files. The bit vector for this disk will look like this-

We can find the free block number from the bit vector using the following method-

Block number = (Number of bits per word )* (number of 0-value words) + (offset of first bit)

We will now find the first free block number in the above example.

The first group of 8 bits (00111100) constitutes a non-zero word since all bits are not 0. After finding the non-zero word, we will look for the first 1 bit. This is the third character of the non-zero word. Hence, offset = 3.

Therefore, the first free block number = 8 * 0 + 3 = 3.

Advantages

The advantages of the bit vector method are-

• It is simple to understand.
• It is an efficient method.
• It occupies less memory.

Disadvantages

The disadvantages of the bit vector method are-

• For finding a free block, the operating system may need to search the entire bit vector.
• To detect the first 1 in a word that is not 0 using this method, special hardware support is needed.
• Keeping the bit vector in the main memory is possible for smaller disks but not for larger ones. For example, a 1.3 GB disk with 512-byte blocks would need a bit vector of over 332 KB to track its free blocks. Giving away 332 KB just to maintain its free block space is not so efficient in the long run.

Linked List

Another method of doing free space management in operating systems is a linked list. In this method, all the free blocks existing in the disk are linked together in a linked list. The address of the first free block is stored somewhere in the memory. Each free block contains a pointer that contains the address to the next free block. The last free block points to null, indicating the end of the linked list.

For example, consider a disk having 16 blocks where block numbers 3, 4, 5, 6, 9, 10, 11, 12, 13, and 14 are free, and the rest of the blocks, i.e., block numbers 1, 2, 7, 8, 15 and 16 are allocated to some files. If we maintain a linked list, then Block 3 will contain a pointer to Block 4, and Block 4 will contain a pointer to Block 5. 

Similarly, Block 5 will point to Block 6,  Block 6 will point to Block 9,  Block 9 will point to Block 10,  Block 10 will point to Block 11,  Block 11 will point to Block 12,  Block 12 will point to Block 13 and  Block 13 will point to Block 14. Block 14 will point to null. The address of the first free block, i.e., Block 3, will be stored somewhere in the memory. This is also represented in the following figure- 

Advantages

The advantages of the linked list method are-

• External fragmentation is prevented by linked list allocation. As opposed to contiguous allocation, this prevents the wasting of memory blocks.
• It is also quite simple to make our file bigger. All we have to do is link a new file block to our linked list. The file can so expand as long as memory blocks are available.
• Since the directory only needs to hold the starting and ending pointers of the file, linked list allocation places less strain on it.

Disadvantages

The disadvantages of the linked list method are-

• This method is inefficient since we need to read each block to traverse the list, which takes more I/O time.
• There is an overhead in maintaining the pointer.
• There is no provision for random or direct memory access in linked list allocation. We must search through the full linked list to locate the correct block if we wish to access a certain file block.
  You can also read about the Multilevel Queue Scheduling.

Grouping

The third method of free space management in operating systems is grouping. This method is the modification of the linked list method. In this method, the first free block stores the addresses of the n free blocks. The first n-1 of these blocks is free. The last block in these n free blocks contains the addresses of the next n free blocks, and so on. 

For example, consider a disk having 16 blocks where block numbers 3, 4, 5, 6, 9, 10, 11, 12, 13, and 14 are free, and the rest of the blocks, i.e., block numbers 1, 2, 7, 8, 15 and 16 are allocated to some files. 

If we apply the Grouping method considering n to be 3, Block 3 will store the addresses of Block 4, Block 5, and Block 6. Similarly, Block 6 will store the addresses of Block 9, Block 10, and Block 11. Block 11 will store the addresses of Block 12, Block 13, and Block 14. This is also represented in the following figure-

This method overcomes the disadvantages of the linked list method. The addresses of a large number of free blocks can be found quickly, just by going to the first free block or the nth free block. There is no need to traverse the whole list, which was the situation in the linked list method.

Advantages

The advantages of the grouping method are-

• The addresses of a large number of free blocks can be found quickly.
• This method has the benefit of making it simple to locate the addresses of a collection of empty disk blocks.
• It's a modification of the free list approach. So, there is no need to traverse the whole list.

Disadvantages

The advantages of the grouping method are-

• The space of one block is wasted in storing addresses. Since the nth block is used to store the addresses of next n free blocks.
• We only save the address of the first free block since we are unable to maintain a list of all n free disk addresses.
• There is an overhead in maintaining the index of blocks.

Counting

This is the fourth method of free space management in operating systems. This method is also a modification of the linked list method. This method takes advantage of the fact that several contiguous blocks may be allocated or freed simultaneously. In this method, a linked list is maintained but in addition to the pointer to the next free block, a count of free contiguous blocks that follow the first block is also maintained. Thus each free block in the disk will contain two things-

1. A pointer to the next free block.
2. The number of free contiguous blocks following it.

For example, consider a disk having 16 blocks where block numbers 3, 4, 5, 6, 9, 10, 11, 12, 13, and 14 are free, and the rest of the blocks, i.e., block numbers 1, 2, 7, 8, 15 and 16 are allocated to some files.

If we apply the counting method, Block 3 will point to Block 4 and store the count 4 (since Block 3, 4, 5, and 6 are contiguous). Similarly, Block 9 will point to Block 10 and keep the count of 6 (since Block 9, 10, 11, 12, 13, and 14 are contiguous). This is also represented in the following figure-

This method also overcomes the disadvantages of the linked list method since there is no need to traverse the whole list.

Advantages

The advantages of the counting method are-

• Fast allocation of a large number of consecutive free blocks.
• Random access to the free block is possible.
• The overall list is smaller in size.

Disadvantages

The disadvantages of the counting method are-

• Each free block requires more space for keeping the count in the disk.
• For efficient insertion, deletion, and traversal operations. We need to store the entries in B-tree.
• The entire area is reduced.

Advantages of free space management techniques in operating systems

• Efficient use of storage space: space management techniques help to optimize the use of storage space on the hard disk as well as secondary storage devices. 
   
• Easy to implement: some techniques in space management are easy to implement, like linked allocation. It requires less overhead in terms of processing and memory resources.
   
• Reduce Fragmentation: Free space management techniques like contiguous allocation help in reducing disk fragmentation which results in faster access to files.

Disadvantages of free space management techniques in operating systems

• Complex: some space management techniques are complex to implement and manage. 
   
• Performance overhead: Free space management techniques can contribute to adding some performance overhead because some techniques require frequent updates to the free space list.
   
• Vulnerability to corruption:  If the free space list is not properly maintained, there is a chance of corruption.

Frequently Asked Questions

What is free space management in Operating System?

As we know in our system, the hard disk space is limited. We need to use this space wisely. So, the operating system manages the free space in the hard disk created by the leftover spaces in memory or by deleting files using the free space management techniques. There are four free space management methods available in OS. These are - Bit vector, linked list, grouping, and counting.

What is space management in OS?

A procedure called "space management" makes sure that user volumes have enough room for our data's storage needs. We may see two actions that space management carries out: Data sets that have reached their expiration dates are deleted, and Data sets that have not been used for a certain amount of time are moved.

What is the use of free space?

Free space on storage devices, such as hard drives or memory, is essential for storing new data, applications, or updates. It allows the system to write, modify, or expand files without running out of available storage capacity.

What are the benefits of space management?

Space management offers several benefits, including efficient resource allocation, reduced storage costs, improved data organization, optimized system performance, and better disaster recovery. It helps maintain a well-structured and high-performing IT environment.

Conclusion

In this article, we studied free space management in operating systems. We discussed four methods of doing free space management in the operating system. These are - bit vector or bit map, linked list, grouping, and counting. This article thoroughly discusses all the methods along with their advantages and disadvantages. You can also find other articles on the operating system topics on Coding Ninjas Studio.

Recommended Reading:

• Android Operating System
• Disk Management in OS
• Buddy System In OS

Reader, don’t stop here. Start your learning journey in the operating system with Coding Ninjas by taking the OS course.

Happy Learning!