Worst Fit Allocation Strategy
What is Worst Fit Algorithm?
The Worst Fit Algorithm is the exact opposite of the Best Fit algorithm. While Best Fit tries to squeeze a process into the tightest space possible, Worst Fit intentionally searches for the ABSOLUTE LARGEST hole available in memory and places the process there.
Just like Best Fit, this algorithm must scan the entire list of memory blocks to guarantee it has found the single largest block.
The Core Philosophy
The rationale behind Worst Fit is to avoid the "tiny splinters" problem caused by Best Fit. If you place a small process inside a massive block of memory, the leftover space will still be quite large-large enough, hopefully, to comfortably fit another process later.
Steps to Implement Worst Fit Algorithm
The logic is nearly identical to Best Fit, except the comparison operator is flipped to find the maximum rather than the minimum:
- Take the memory blocks and the incoming processes as input.
- Initialize an allocation array to keep track of assignments (set all to -1).
- Pick the first process from the process queue.
- Initialize a variable `worstIdx` to -1. This will track the index of the largest candidate block found so far.
- Scan through EVERY single memory block.
- If the current block is large enough for the process AND it is larger than the block currently at `worstIdx` (or if `worstIdx` is still -1), update `worstIdx` to this current block's index.
- After checking all blocks, if `worstIdx` is not -1, allocate the process to that block and reduce its available size.
- Repeat steps 3-7 for all remaining processes.
C++ Code for Worst Fit Algorithm
Here is the programmatic implementation of the full-scan Worst Fit logic in C++:
cpp
#include <iostream>
using namespace std;
void worstFit(int blockSize[], int m, int processSize[], int n) {
int allocation[n];
// Initially, no block is assigned
for (int i = 0; i < n; i++) {
allocation[i] = -1;
}
// Pick each process and find the worst fit block
for (int i = 0; i < n; i++) {
// Find the worst fit block for current process
int worstIdx = -1;
for (int j = 0; j < m; j++) {
// If the block is large enough
if (blockSize[j] >= processSize[i]) {
// If it's the first one found, or if it's LARGER than the current worst
if (worstIdx == -1 || blockSize[j] > blockSize[worstIdx]) {
worstIdx = j;
}
}
}
// If we found a block, allocate it
if (worstIdx != -1) {
// Allocate block to process
allocation[i] = worstIdx;
// Reduce available memory in this block
blockSize[worstIdx] -= processSize[i];
}
}
// 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]);
worstFit(blockSize, m, processSize, n);
return 0;
}Advantages of Worst Fit Algorithm
- Prevents Tiny Splinters: Because it allocates from the largest available blocks, the remaining leftover space is usually quite large. This avoids the microscopic, unusable fragments created by Best Fit.
- Good for Dynamic Growth: If a process is known to grow dynamically during execution (like a process dynamically extending its heap), placing it in the largest possible hole gives it plenty of room to expand.
Disadvantages of Worst Fit Algorithm
- Slow Execution Speed: Just like Best Fit, it must scan the ENTIRE list of memory blocks every single time a process arrives to guarantee it has found the maximum size block.
- Wastes the Largest Blocks: This is the critical flaw. By constantly attacking the largest blocks of memory first, it rapidly eliminates the only places a massive process could potentially fit. If a very large process arrives later, it will almost certainly fail to load.
Tracing Worst Fit
Question 1 of 1Test your understanding of how Worst Fit selects blocks.