Best Fit Algorithm in C and C++

Here you will learn about best fit algorithm in C and C++ with program example.

Memory Management is one of the services provided by OS which is needed for Optimized memory usage of the available memory in a Computer System.

For this purpose OS uses 3 methods:-

1. First Fit
2. Best Fit
3. Worst Fit

In this section we will talk about Best Fit Memory Management Scheme.

What is Best Fit Memory Management Scheme?

Best fit uses the best memory block based on the Process memory request. In best fit implementation the algorithm first selects the smallest block which can adequately fulfill the memory request by the respective process.

Because of this memory is utilized optimally but as it compares the blocks with the requested memory size it increases the time requirement and hence slower than other methods. It suffers from Internal Fragmentation which simply means that the memory block size is greater than the memory requested by the process, then the free space gets wasted.

Once we encounter a process that requests a memory which is higher than block size we stop the algorithm.

Best Fit Algorithm

1. Get no. of Processes and no. of blocks.
2. After that get the size of each block and process requests.
3. Then select the best memory block that can be allocated using the above definition.
4. Display the processes with the blocks that are allocated to a respective process.
5. Value of Fragmentation is optional to display to keep track of wasted memory.
6. Stop.

Program for Best Fit Algorithm in C

#include<stdio.h>

void main()
{
	int fragment[20],b[20],p[20],i,j,nb,np,temp,lowest=9999;
	static int barray[20],parray[20];
	
	printf("\n\t\t\tMemory Management Scheme - Best Fit");
	printf("\nEnter the number of blocks:");
	scanf("%d",&nb);
	printf("Enter the number of processes:");
	scanf("%d",&np);
	
	printf("\nEnter the size of the blocks:-\n");
	for(i=1;i<=nb;i++)
    {
		printf("Block no.%d:",i);
        scanf("%d",&b[i]);
    }
	
	printf("\nEnter the size of the processes :-\n");
	for(i=1;i<=np;i++)
    {
        printf("Process no.%d:",i);
        scanf("%d",&p[i]);
    }
	
	for(i=1;i<=np;i++)
	{
		for(j=1;j<=nb;j++)
		{
			if(barray[j]!=1)
			{
				temp=b[j]-p[i];
				if(temp>=0)
					if(lowest>temp)
					{
						parray[i]=j;
						lowest=temp;
					}
			}
		}
		
		fragment[i]=lowest;
		barray[parray[i]]=1;
		lowest=10000;
	}
	
	printf("\nProcess_no\tProcess_size\tBlock_no\tBlock_size\tFragment");
	for(i=1;i<=np && parray[i]!=0;i++)
		printf("\n%d\t\t%d\t\t%d\t\t%d\t\t%d",i,p[i],parray[i],b[parray[i]],fragment[i]);
}

Program for Best Fit Algorithm in C++

#include<iostream>

using namespace std;

int main()
{
	int fragment[20],b[20],p[20],i,j,nb,np,temp,lowest=9999;
	static int barray[20],parray[20];
	cout<<"\n\t\t\tMemory Management Scheme - Best Fit";
	cout<<"\nEnter the number of blocks:";
	cin>>nb;
	cout<<"Enter the number of processes:";
	cin>>np;
	
	cout<<"\nEnter the size of the blocks:-\n";
	for(i=1;i<=nb;i++)
    {
        cout<<"Block no."<<i<<":";
        cin>>b[i];
    }
	
	cout<<"\nEnter the size of the processes :-\n";
	for(i=1;i<=np;i++)
    {
        cout<<"Process no. "<<i<<":";
        cin>>p[i];
    }
	
	for(i=1;i<=np;i++)
	{
		for(j=1;j<=nb;j++)
		{
			if(barray[j]!=1)
			{
				temp=b[j]-p[i];
				if(temp>=0)
					if(lowest>temp)
					{
						parray[i]=j;
						lowest=temp;
					}
			}
		}
		
		fragment[i]=lowest;
		barray[parray[i]]=1;
		lowest=10000;
	}
	
	cout<<"\nProcess_no\tProcess_size\tBlock_no\tBlock_size\tFragment";
	for(i=1;i<=np && parray[i]!=0;i++)
		cout<<"\n"<<i<<"\t\t"<<p[i]<<"\t\t"<<parray[i]<<"\t\t"<<b[parray[i]]<<"\t\t"<<fragment[i];
	
	return 0;
}

Output

Comment below if you have any doubts related to above best fit algorithm in C and C++.