Next Fit Allocation Strategy
What is Next Fit Algorithm?
The Next Fit Algorithm is a direct modification and intended optimization of the First Fit algorithm. As we saw with First Fit, always starting the search from the very beginning of memory causes the front blocks to be chopped into tiny, useless fragments. This forces the OS to waste time scanning past those tiny fragments on every subsequent allocation.
Next Fit solves this by remembering where it left off. When a new process arrives, the algorithm begins its search from the EXACT POINT where the last allocation happened, rather than starting from the beginning. If it reaches the end of the memory blocks, it wraps around circularly to the beginning.
Steps to Implement Next Fit Algorithm
The logic requires maintaining a persistent pointer to track the search index:
- Take the memory blocks and the incoming processes as input.
- Initialize an allocation array to keep track of assignments (set all to -1).
- Create a variable `j` initialized to 0. This will track the last allocated block index.
- Pick the first process from the process queue.
- Start searching the memory blocks from index `j`.
- If the block at `j` is large enough, allocate it, reduce its available size, and immediately stop searching for this process. Keep `j` at this position for the next process.
- If the block at `j` is too small, increment `j`. If `j` reaches the end of the list, wrap it back to 0. Continue searching until you check every block exactly once.
- Repeat steps 4-7 for all remaining processes.
C++ Code for Next Fit Algorithm
Here is how the circular search is implemented in C++:
#include <iostream>
using namespace std;
void nextFit(int blockSize[], int m, int processSize[], int n) {
int allocation[n];
int j = 0; // Persistent pointer tracking the last allocated block
// Initially, no block is assigned
for (int i = 0; i < n; i++) {
allocation[i] = -1;
}
// Pick each process and find suitable block
for (int i = 0; i < n; i++) {
// Count keeps track of how many blocks we have checked
int count = 0;
// Loop until we check all blocks once
while (count < m) {
// If the current block is large enough
if (blockSize[j] >= processSize[i]) {
// Allocate block j to process i
allocation[i] = j;
// Reduce available memory in this block
blockSize[j] -= processSize[i];
// Break the while loop to stop searching for this process
break;
}
// Move to the next block, wrap around if necessary
j = (j + 1) % m;
count++;
}
}
// 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[] = {50, 200, 70, 115, 15};
int processSize[] = {100, 10, 35, 74};
int m = sizeof(blockSize) / sizeof(blockSize[0]);
int n = sizeof(processSize) / sizeof(processSize[0]);
nextFit(blockSize, m, processSize, n);
return 0;
}Advantages of Next Fit Algorithm
- Even Distribution: It distributes allocations much more evenly across the entire memory space, rather than heavily congesting the front.
- Faster Initial Searches: By avoiding the tiny fragments clustered at the beginning of memory (which plague First Fit), Next Fit often finds a suitable block faster for the first few allocations.
Disadvantages of Next Fit Algorithm
- Breaks Large Blocks: Because it simply picks up where it left off, it often chops up the largest block of memory sitting at the end of the address space. If a massive process arrives later, it will fail to load because that large block was needlessly fragmented by smaller processes.
- Poorer Real-World Performance: Despite being designed as an "optimization," extensive simulations by OS researchers have shown that Next Fit actually performs slightly WORSE than First Fit in terms of memory utilization and overall external fragmentation.
Tracing the Persistent Pointer
Question 1 of 1Test your understanding of how the Next Fit pointer behaves.