Operating System - Best Fit Algorithm

---

---

The Best Fit Algorithm is a memory allocation strategy used in contiguous memory allocation systems. This chapter will explain the Best Fit Algorithm, how it works, and its implementation in operating systems.

• What is Best Fit Algorithm?
• Steps to Implement Best Fit Algorithm
• C++ Code for Best Fit Algorithm
• Advantages of Best Fit Algorithm
• Disadvantages of Best Fit Algorithm

What is Best Fit Algorithm?

The Best Fit Algorithm allocates searches the entire memory to find the smallest available block that is large enough to accommodate the process. This means that, the algorithm looks for the block that will leave the least amount of unused space after allocation. The main aim of the Best Fit Algorithm is reduce fragmentation and wastage of memory.

Example

Consider the following example where we have five memory blocks of sizes 6, 5, 50, 20, and 14 units, and five processes of sizes 4, 10, 15, 20, and 23 units respectively. We will allocate memory to these processes using the Best Fit Algorithm.

 Input : blockSize[] = { 6, 5, 50, 20, 14}; processSize[] = {4, 10, 15, 20, 23}; Output: Process No. Process Size Block no. 1 4 5 2 10 14 3 15 20 4 20 50 5 23 Not Allocated; 

When process 4 comes to memory allocation, it is allocated to block of size 5, as it is the smallest block that can accommodate the process. Similarly, process 10 is allocated to block of size 14, and process 15 is allocated to block of size 20.

The process size 23 cannot be allocated as there is no block large enough to accommodate it.

Steps to Implement Best Fit Algorithm

The Best Fit Algorithm can be implemented using the following steps −

• Initialize a pointer to keep track of the last allocated block.
• For each process, search the entire memory to find the smallest block that is large enough to hold the process.
• If a suitable block is found, allocate the process to that block.
• After searching the entire memory, if no suitable block is found, mark the process as "Not Allocated".

C++ Code for Best Fit Algorithm

Below is a sample C++ code that demonstrates the implementation of the Best Fit Algorithm −

 #include <iostream> using namespace std; void bestFit(int blockSize[], int m, int processSize[], int n) { int allocation[n]; int originalBlockSize[m]; // Store original block sizes before modification for (int i = 0; i < m; i++) originalBlockSize[i] = blockSize[i]; // Initialize allocation array for (int i = 0; i < n; i++) allocation[i] = -1; // Best Fit Allocation for (int i = 0; i < n; i++) { int bestIdx = -1; for (int j = 0; j < m; j++) { if (blockSize[j] >= processSize[i]) { if (bestIdx == -1 || blockSize[bestIdx] > blockSize[j]) bestIdx = j; } } // Allocate if found if (bestIdx != -1) { allocation[i] = bestIdx; blockSize[bestIdx] = -1; // mark the block as used } } // Print result cout << "Process No.\tProcess Size\tAllocated Block Size" << endl; for (int i = 0; i < n; i++) { cout << " " << i + 1 << "\t\t\t" << processSize[i] << "\t\t\t"; if (allocation[i] != -1) cout << originalBlockSize[allocation[i]]; else cout << "Not Allocated"; cout << endl; } } int main() { int blockSize[] = {6, 5, 50, 20, 14}; int processSize[] = {4, 10, 15, 20, 23}; int m = sizeof(blockSize) / sizeof(blockSize[0]); int n = sizeof(processSize) / sizeof(processSize[0]); bestFit(blockSize, m, processSize, n); return 0; } 

The output of the above code will be −

 Process No. Process Size Allocated Block Size 1 4 5 2 10 14 3 15 20 4 20 50 5 23 Not Allocated 

Advantages of Best Fit Algorithm

The Best Fit Algorithm have the following advantages −

• Reduced External Fragmentation − By allocating the smallest possible block to a process, the Best Fit Algorithm helps in reducing external fragmentation.
• Efficient Memory Utilization − The Best Fit Algorithm ensures that memory is utilized efficiently by minimizing the amount of wasted space after allocation.
• Best for Small Processes − The Best Fit Algorithm is considered to be more suitable for small processes.

Disadvantages of Best Fit Algorithm

The Best Fit Algorithm has some drawbacks −

• High Search Time − The Best Fit Algorithm requires searching the entire memory for the smallest suitable block, which can increase allocation time.
• Fragmentation − Even though it reduces external fragmentation, it can cause internal fragmentation. Because processes may not fully utilize the allocated blocks.
• Not Suitable for Large Processes − The Best Fit Algorithm may struggle to find suitable blocks for larger processes. This leads to more "Not Allocated" statuses.

Conclusion

The Best Fit Algorithm is a memory allocation strategy that allocates the smallest available block that can accommodate a process. This ensures reduced fragmentation and efficient memory utilization. However, it has high search time and can cause internal fragmentation. The Best Fit Algorithm is suitable for systems where memory efficiency is a priority, especially when working with small processes.