Operating System - First Fit Algorithm

---

---

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

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

What is First Fit Algorithm?

The First Fit Algorithm allocates the first available block of memory that is large enough to accommodate the process. Meaning, the algorithm scans the memory from the starting and allocates the first block that is big enough for the processes need. If no suitable block is found, the process is marked as "Not Allocated". So the process needs to wait until a suitable block becomes free.

Example

Consider the following example where we have three memory blocks of sizes 6, 12, and 25 units, and three processes of sizes 12, 25, and 30 units respectively. We will allocate memory to these processes using the First Fit Algorithm.

 Input : blockSize[] = {6, 12, 25}; processSize[] = {12, 25, 30}; Output: Process No. Process Size Block no. 1 12 2 2 25 3 3 30 Not Allocated; 

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

Steps to Implement First Fit Algorithm

The First Fit Algorithm can be implemented using the following steps:

• Initialize a pointer to keep track of the last allocated block.
• For each process, start searching for a suitable hole from the beginning of the memory.
• If a suitable hole is found, allocate the process to that hole.
• On reaching the end of the memory, if no suitable hole is found, mark the process as "Not Allocated".

C++ Code for First Fit Algorithm

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

 #include <iostream> using namespace std; void firstFit(int blockSize[], int m, int processSize[], int n) { int allocation[n]; for (int i = 0; i < n; i++) allocation[i] = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (blockSize[j] >= processSize[i]) { allocation[i] = j; blockSize[j] -= processSize[i]; break; } } } cout << "Process No.\tProcess Size\tBlock no." << endl; for (int i = 0; i < n; i++) { cout << " " << i + 1 << "\t\t" << processSize[i] << "\t\t"; if (allocation[i] != -1) cout << allocation[i] + 1; else cout << "Not Allocated"; cout << endl; } } int main() { int blockSize[] = {6, 12, 25}; int processSize[] = {12, 25, 30}; int m = sizeof(blockSize) / sizeof(blockSize[0]); int n = sizeof(processSize) / sizeof(processSize[0]); firstFit(blockSize, m, processSize, n); return 0; } 

The output of the above code will be −

 Process No. Process Size Block no. 1 12 2 2 25 3 3 30 Not Allocated 

Advantages of First Fit Algorithm

The First Fit Algorithm is considered as a simple and efficient memory allocation strategy. Some of its advantages are:

• Speed − The First Fit Algorithm is generally faster than other algorithms like Best Fit and Worst Fit because it allocates the first suitable block it finds.
• No Complex Data Structures − The First Fit Algorithm does not require any complex data structures or any other complex calculations.
• Reduced Fragmentation − The First Fit Algorithm leaves larger gaps in memory compared to other algorithms. This will help in reducing fragmentation.

Disadvantages of First Fit Algorithm

Sometimes, the First Fit Algorithm is not preferred, due to the following drawbacks −

• Wasted Memory − The First Fit Algorithm can lead to wastage of memory as it may leave large unusable gaps in memory.
• Poor Utilization − The First Fit Algorithm is considered as worst in term of memory utilization compared to other algorithms like Best Fit and Worst Fit.
• Not Optimal − The First Fit Algorithm does not guarantee optimal memory allocation. It may lead to situations where a process cannot be allocated memory even though there is enough total memory available.

Conclusion

The First Fit Algorithm is a simple algorithm for memory allocation in operating systems. It is fast and easy to implement. The idea behind the algorithm is to allocate the first available block of memory that is large enough to accommodate the process. However, it comes with certain drawbacks like wasted memory and poor utilization.