Worst-Fit Allocation in Operating
Systems
Last Updated : 03 Feb, 2021
For both fixed and dynamic memory allocation schemes, the operating system must keep
a list of each memory location noting which are free and which are busy. Then as new
jobs come into the system, the free partitions must be allocated.
These partitions may be allocated in 4 ways:
1. First-Fit Memory Allocation
2. Best-Fit Memory Allocation
3. Worst-Fit Memory Allocation
4. Next-Fit Memory Allocation
These are Contiguous memory allocation techniques.
Worst-Fit Memory Allocation :
In this allocation technique, the process traverses the whole memory and always search
for the largest hole/partition, and then the process is placed in that hole/partition. It is a
slow process because it has to traverse the entire memory to search the largest hole.
Here is an example to understand Worst Fit-Allocation –
Program for Worst Fit algorithm in
Memory Management
Difficulty Level : Easy
Last Updated : 28 Jun, 2021
Prerequisite : Partition allocation methods
Worst Fit allocates a process to the partition which is largest sufficient among the freely
available partitions available in the main memory. If a large process comes at a later
stage, then memory will not have space to accommodate it.
Example:
Input : blockSize[] = {100, 500, 200, 300, 600};
processSize[] = {212, 417, 112, 426};
Output:
Process No. Process Size Block no.
1 212 5
2 417 2
3 112 5
4 426 Not Allocated
Recommended: Please try your approach on {IDE} first, before moving on to the
solution.
Implementation:
1- Input memory blocks and processes with sizes.
2- Initialize all memory blocks as free.
3- Start by picking each process and find the
maximum block size that can be assigned to
current process i.e., find max(bockSize[1],
blockSize[2],.....blockSize[n]) >
processSize[current], if found then assign
it to the current process.
5- If not then leave that process and keep checking
the further processes.
Below is implementation of above steps.
C++
Java
Python3
C#
Javascript
// Java implementation of worst - Fit algorithm
public class GFG
// Method to allocate memory to blocks as per worst fit
// algorithm
static void worstFit(int blockSize[], int m, int processSize[],
int n)
{
// Stores block id of the block allocated to a
// process
int allocation[] = new int[n];
// Initially no block is assigned to any process
for (int i = 0; i < allocation.length; i++)
allocation[i] = -1;
// pick each process and find suitable blocks
// according to its size ad assign to it
for (int i=0; i<n; i++)
{
// Find the best fit block for current process
int wstIdx = -1;
for (int j=0; j<m; j++)
{
if (blockSize[j] >= processSize[i])
{
if (wstIdx == -1)
wstIdx = j;
else if (blockSize[wstIdx] < blockSize[j])
wstIdx = j;
}
}
// If we could find a block for current process
if (wstIdx != -1)
{
// allocate block j to p[i] process
allocation[i] = wstIdx;
// Reduce available memory in this block.
blockSize[wstIdx] -= processSize[i];
}
}
System.out.println("\nProcess No.\tProcess Size\tBlock no.");
for (int i = 0; i < n; i++)
{
System.out.print(" " + (i+1) + "\t\t" + processSize[i] +
"\t\t");
if (allocation[i] != -1)
System.out.print(allocation[i] + 1);
else
System.out.print("Not Allocated");
System.out.println();
}
}
// Driver Method
public static void main(String[] args)
{
int blockSize[] = {100, 500, 200, 300, 600};
int processSize[] = {212, 417, 112, 426};
int m = blockSize.length;
int n = processSize.length;
worstFit(blockSize, m, processSize, n);
}
Output:
Process No. Process Size Block no.
1 212 5
2 417 2
3 112 5
4 426 Not Allocated
Here Process P1=30K is allocated with the Worst Fit-Allocation technique, so it traverses
the entire memory and selects memory size 400K which is the largest, and hence there is
an internal fragmentation of 370K which is very large and so many other processes can
also utilize this leftover space.
Advantages of Worst-Fit Allocation :
Since this process chooses the largest hole/partition, therefore there will be large internal
fragmentation. Now, this internal fragmentation will be quite big so that other small
processes can also be placed in that leftover partition.
Disadvantages of Worst-Fit Allocation :
It is a slow process because it traverses all the partitions in the memory and then selects
the largest partition among all the partitions, which is a time-consuming process.
// C++ implementation of worst - Fit algorithm
#include<bits/stdc++.h>
using namespace std;
// Function to allocate memory to blocks as per worst fit
// algorithm
void worstFit(int blockSize[], int m, int processSize[],
int n)
// Stores block id of the block allocated to a
// process
int allocation[n];
// Initially no block is assigned to any process
memset(allocation, -1, sizeof(allocation));
// pick each process and find suitable blocks
// according to its size ad assign to it
for (int i=0; i<n; i++)
{
// Find the best fit block for current process
int wstIdx = -1;
for (int j=0; j<m; j++)
{
if (blockSize[j] >= processSize[i])
{
if (wstIdx == -1)
wstIdx = j;
else if (blockSize[wstIdx] < blockSize[j])
wstIdx = j;
}
}
// If we could find a block for current process
if (wstIdx != -1)
{
// allocate block j to p[i] process
allocation[i] = wstIdx;
// Reduce available memory in this block.
blockSize[wstIdx] -= processSize[i];
}
}
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;
}
}
// Driver code
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 ;
