Question

Write Algoritm , code and output.

In Operating Systems ,

26. Implement a program to allocate memory by applying the following strategies.a

.FIRST FIT

b.BEST FIT

c.WORST FIT

Answer 1

(a) First Fit

Algorithm:

1- Input memory blocks with size and processes with size.
2- Initialize all memory blocks as free.
3- Start by picking each process and check if it can
   be assigned to current block. 
4- If size-of-process <= size-of-block if yes then 
   assign and check for next process.
5- If not then keep checking the further blocks.

code:

// C++ implementation of First - Fit algorithm
#include<bits/stdc++.h>
using namespace std;

// Function to allocate memory to
// blocks as per First fit algorithm
void firstFit(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++)
   {
       for (int j = 0; j < m; j++)
       {
           if (blockSize[j] >= processSize[i])
           {
               // allocate block j to p[i] process
               allocation[i] = j;

               // Reduce available memory in this block.
               blockSize[j] -= processSize[i];

               break;
           }
       }
   }

   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]);

   firstFit(blockSize, m, processSize, n);

   return 0 ;
}

Input : blockSize[]   = {100, 500, 200, 300, 600};
        processSize[] = {212, 417, 112, 426};

Output :

Process No.    Process Size    Block no.
   1            212              2
   2            417              5
   3            112              2
   4            426             Not Allocated

(b) Best Fit:

Algorithm:

1- Input memory blocks and processes with sizes.
2- Initialize all memory blocks as free.
3- Start by picking each process and find the
   minimum block size that can be assigned to
   current process i.e., find min(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.

Code:

// C++ implementation of Best - Fit algorithm
#include<bits/stdc++.h>
using namespace std;

// Function to allocate memory to blocks as per Best fit
// algorithm
void bestFit(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 bestIdx = -1;
       for (int j=0; j<m; j++)
       {
           if (blockSize[j] >= processSize[i])
           {
               if (bestIdx == -1)
                   bestIdx = j;
               else if (blockSize[bestIdx] > blockSize[j])
                   bestIdx = j;
           }
       }

       // If we could find a block for current process
       if (bestIdx != -1)
       {
           // allocate block j to p[i] process
           allocation[i] = bestIdx;

           // Reduce available memory in this block.
           blockSize[bestIdx] -= 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]);

   bestFit(blockSize, m, processSize, n);

   return 0 ;
}

Input : blockSize[]   = {100, 500, 200, 300, 600};
        processSize[] = {212, 417, 112, 426};

Output:

Process No.    Process Size    Block no.
 1               212             4
 2               417             2
 3               112             3
 4               426             5

(c) Worst Fit:

Algorithm:

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.

Code:

// 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 ;
}

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