Home »
Operating System
Free Space Management in Operating System
In this tutorial, we will learn about the free space management and some techniques to implement the free space list in the operating system.
By Prerana Jain Last updated : May 06, 2023
What is Free space management in OS?
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. Thee 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.
What are the methods or techniques to implement a free space list?
There are some methods or techniques to implement a free space list. These are as follows:
- Bitmap
- Linked list
- Grouping
- Counting
Let's discuss each method in detail.
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.
The calculation of the block number is done by the formula:
(number of bits per words) X (number of 0-value word) + Offset of first 1 bit
For Example: Apple Macintosh operating system uses the bitmap method to allocate the disk space.
Assume the following are free. Rest are allocated:
Advantages
The following are the advantages of bitmap:
- This technique is relatively simple.
- This technique is very efficient to find the free space on the disk.
Disadvantages
The following are the disadvantages of bitmap:
- 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.
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
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
The following are the advantages of linked list:
- 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
The following are the disadvantages of linked list:
- 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.