C++ program for best fit algorithm

Hello there. Today we are going to see how to implement the best fit memory allocation algorithm in C++. This strategy distributes the process to the smallest available partition which is sufficient enough to fit in the process. There are other strategies also like first fit, next fit, etc., but the best fit algorithm helps in minimizing the wastage space, so we can accommodate more number of processes in each block. Now let’s move to the programming part.

C++: program for best fit algorithm

The program is very easy to understand if you know how the best fit strategy works. First, we will input the number of processes and blocks, and then their values. The calculation initially chooses the smallest block which is sufficient enough to satisfy the memory demand of each process. When we encounter a process that demands memory amount higher than the square size, we halt the algorithm. Let’s look at the code.

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
  int nb,np,temp,lowest=9999;
  int a1[20],a2[20],b[20],p[20];

  cout<<"Enter number of blocks ";
  cin>>nb;
  cout<<"Enter number of processes ";
  cin>>np;
  
  cout<<"Enter size of each block"<<endl;
  for(int i=1;i<=nb;i++)
    {
        cout<<"Block "<<i<<"-";
        cin>>b[i];
    }
  
  cout<<"\nEnter size of each process."<<endl;
  for(int i=1;i<=np;i++)
    {
        cout<<"Process "<<i<<"-";
        cin>>p[i];
    }
  
  for(int t=1;t<=np;t++)
  {
    for(int q=1;q<=nb;q++)
    {
      if(a1[q]!=1)
      {
        temp=b[q]-p[t];
        if(temp>=0)
          if(lowest>temp)
          {
            a2[t]=q;
            lowest=temp;
          }
      }
    }
    a1[a2[t]]=1;
    lowest=10000;
  }
  
  cout<<endl<<"Process number\tProcess size\tBlock number\tBlock size";
  for(int i=1;(i<=np and a2[i]!=0);i++)
  {
    cout<<endl<<i<<"\t\t"<<p[i]<<"\t\t"<<a2[i]<<"\t\t"<<b[a2[i]];
  }
  return 0;
}

Now, let’s look at the output.

Enter number of blocks 5
Enter number of processes 4
Enter size of each block
Block 1-90
Block 2-450
Block 3-180
Block 4-270
Block 5-540

Enter size of each process.
Process 1-200
Process 2-400
Process 3-100
Process 4-400

Process number  Process size    Block number    Block size
1               200             4               270
2               400             2               450
3               100             3               180
4               400             5               540
--------------------------------

As you can see, each process gets a block allotted to it in a memory-efficient way. That’s why processes with bigger requirements get bigger blocks allocated to them.

I hope you found this article useful. For further practice, you can try to implement other allocation strategies. That way, you will see which algorithm is best for any given scenario. That will enhance your grasp on the topic.

Also read: How to find the cube root of a number in C++

Leave a Reply