Program for First Fit algorithm in Memory Management

Prerequisite : Partition Allocation Methods
In the first fit, the partition is allocated which is first sufficient from the top of Main Memory.
Example : 

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

• Its advantage is that it is the fastest search as it searches only the first block i.e. enough to assign a process.
• It may have problems of not allowing processes to take space even if it was possible to allocate. Consider the above example, process number 4 (of size 426) does not get memory. However it was possible to allocate memory if we had allocated using best fit allocation [block number 4 (of size 300) to process 1, block number 2 to process 2, block number 3 to process 3 and block number 5 to process 4].

Implementation:
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.

Below is an implementation of above steps.
 

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

// C implementation of First - Fit algorithm #include<stdio.h> // Function to allocate memory to // blocks as per First fit algorithm void firstFit(int blockSize[], int m, int processSize[], int n) {  int i, j;  // Stores block id of the  // block allocated to a process  int allocation[n];  // Initially no block is assigned to any process  for(i = 0; i < n; i++)  {  allocation[i] = -1;  }    // pick each process and find suitable blocks  // according to its size ad assign to it  for (i = 0; i < n; i++) //here, n -> number of processes  {  for (j = 0; j < m; j++) //here, m -> number of blocks  {  if (blockSize[j] >= processSize[i])  {  // allocating block j to the ith process  allocation[i] = j;  // Reduce available memory in this block.  blockSize[j] -= processSize[i];  break; //go to the next process in the queue  }  }  }  printf("\nProcess No.\tProcess Size\tBlock no.\n");  for (int i = 0; i < n; i++)  {  printf(" %i\t\t\t", i+1);  printf("%i\t\t\t\t", processSize[i]);  if (allocation[i] != -1)  printf("%i", allocation[i] + 1);  else  printf("Not Allocated");  printf("\n");  } } // Driver code int main() {  int m; //number of blocks in the memory  int n; //number of processes in the input queue  int blockSize[] = {100, 500, 200, 300, 600};  int processSize[] = {212, 417, 112, 426};  m = sizeof(blockSize) / sizeof(blockSize[0]);  n = sizeof(processSize) / sizeof(processSize[0]);  firstFit(blockSize, m, processSize, n);  return 0 ; } 

// Java implementation of First - Fit algorithm // Java implementation of First - Fit algorithm class GFG  {  // Method to allocate memory to   // blocks as per First fit algorithm  static void firstFit(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++)  {  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;  }  }  }    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 Code  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;    firstFit(blockSize, m, processSize, n);  } } 

# Python3 implementation of First-Fit algorithm  # Function to allocate memory to  # blocks as per First fit algorithm  def firstFit(blockSize, m, processSize, n): # Stores block id of the  # block allocated to a process  allocation = [-1] * n # Initially no block is assigned to any process # pick each process and find suitable blocks  # according to its size ad assign to it  for i in range(n): for j in range(m): 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 print(" Process No. Process Size Block no.") for i in range(n): print(" ", i + 1, " ", processSize[i], " ", end = " ") if allocation[i] != -1: print(allocation[i] + 1) else: print("Not Allocated") # Driver code  if __name__ == '__main__': blockSize = [100, 500, 200, 300, 600] processSize = [212, 417, 112, 426] m = len(blockSize) n = len(processSize) firstFit(blockSize, m, processSize, n) # This code is contributed by PranchalK 

// C# implementation of First - Fit algorithm using System; class GFG  {  // Method to allocate memory to   // blocks as per First fit algorithm  static void firstFit(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++)  {  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;  }  }  }    Console.WriteLine("\nProcess No.\tProcess Size\tBlock no.");  for (int i = 0; i < n; i++)  {  Console.Write(" " + (i+1) + "\t\t" +   processSize[i] + "\t\t");  if (allocation[i] != -1)  Console.Write(allocation[i] + 1);  else  Console.Write("Not Allocated");  Console.WriteLine();  }  }    // Driver Code  public static void Main()  {  int []blockSize = {100, 500, 200, 300, 600};  int []processSize = {212, 417, 112, 426};  int m = blockSize.Length;  int n = processSize.Length;    firstFit(blockSize, m, processSize, n);  } } // This code is contributed by nitin mittal. 

// Javascript implementation <script> const firstFit = (blockSize,m,processSize,n) => {  // Stores block id of the   // block allocated to a process  const allocation = [];    // Initially no block is assigned to any process  for (let 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 (let i = 0; i < n; i++)  {  for (let 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;  }  }  }    document.write("\nProcess No.\tProcess Size\tBlock no.");  for (let i = 0; i < n; i++)  {  let s = "Not Allocated"  if (allocation[i] > -1)  document.write(" " + (i+1) + "\t\t\t\t" +   processSize[i] + "\t\t\t\t"+ (allocation[i] + 1));  else  document.write(" " + (i+1) + "\t\t\t\t" +   processSize[i] + "\t\t\t\tNot Allocated");    }  }      const blockSize = [100, 500, 200, 300, 600];  const processSize = [212, 417, 112, 426];  let m = blockSize.length;  let n = processSize.length;    firstFit(blockSize, m, processSize, n); // This code is contributed by ashishsingh13122000. </script> 

Output : 
 

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

Time complexity of First Fit algorithm is O(n*m), where n is the number of processes and m is the number of memory blocks. The outer for loop runs for n times and the inner for loop runs for m times.
Auxiliary Space of First Fit algorithm is O(n), where n is the number of processes. The allocation array is used to store the block number allocated to the process, which takes a space of O(n).