First Fit Allocation Strategy
What is First Fit Algorithm?
When an operating system uses variable partitioning for memory, it maintains a list of free memory holes. When a new process arrives, the OS must decide which of the available holes to place the process into.
The First Fit Algorithm is the simplest and most intuitive approach: the OS scans the list of memory blocks from the very beginning and assigns the process to the FIRST hole it finds that is large enough to hold it.
Steps to Implement First Fit Algorithm
The algorithm follows a straightforward loop:
- Take the memory blocks (sizes) and the incoming processes (sizes) as input.
- Initialize an allocation array to keep track of which process is assigned to which block. Set all initial values to -1 (unallocated).
- Pick the first process from the process queue.
- Start searching the memory blocks from the VERY BEGINNING (Block 0).
- If a memory block's size is greater than or equal to the process size, assign the block to the process. Reduce the available size of that memory block, and immediately STOP searching for this process.
- If the search reaches the end of the memory blocks and no suitable hole is found, the process must wait.
- Repeat steps 3-6 for all remaining processes.
C++ Code for First Fit Algorithm
Here is how you would implement this logic programmatically in C++:
#include <iostream>
using namespace std;
void firstFit(int blockSize[], int m, int processSize[], int n) {
// Array to store the block id assigned to each process
int allocation[n];
// Initially, no block is assigned to any process
for (int i = 0; i < n; i++) {
allocation[i] = -1;
}
// Pick each process and find the first suitable block
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
// If the block is large enough
if (blockSize[j] >= processSize[i]) {
// Allocate block j to process i
allocation[i] = j;
// Reduce the available memory in this block
blockSize[j] -= processSize[i];
// Stop searching for this process
break;
}
}
}
// Print the results
cout << "\nProcess No.\tProcess Size\tBlock no.\n";
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[] = {100, 500, 200, 300, 600};
int processSize[] = {212, 417, 112, 426};
int m = sizeof(blockSize) / sizeof(blockSize[0]);
int n = sizeof(processSize) / sizeof(processSize[0]);
firstFit(blockSize, m, processSize, n);
return 0;
}In this example, Process 1 (212 units) skips the first block (100) and is assigned to the second block (500). The second block's remaining space shrinks to 288.
Advantages of First Fit Algorithm
- Fast Execution: Because it stops searching the moment it finds a suitable block, it requires fewer comparisons than Best Fit or Worst Fit.
- Simple Implementation: The logic is very straightforward and easy to program in hardware or software.
Disadvantages of First Fit Algorithm
- Front-End Fragmentation: Because the search always starts at the beginning of memory, the largest blocks at the front get repeatedly chopped into tiny, unusable pieces over time.
- Wasted Search Time Later: As the front of memory becomes cluttered with tiny leftover fragments, the algorithm has to scan past all of them every single time a new process arrives, slowing down the search.
Tracing First Fit
Question 1 of 1Test your understanding of how First Fit selects memory blocks.