first_fit.c

/* C implementation of First Fit algorithm
   in memory management. The First Fit algorithm
   is a memory allocation algorithm used by operating
   systems. It is used to allocate memory blocks to
   processes as they are requested. The process is
   given access to the first block of memory that is
   sufficiently large to accomodate the required
   amount of memory.

   The algorithm works as follows: many fixed-size
   blocks make up the memory. The technique looks for
   the first memory block that is big enough to hold
   the required memory when a process requests it.
   The block is then split into two pieces if it
   exceeds the memory request. The first portion
   is alloted to the process, while the second is
   returned to the pool of memory that is readily
   available. If no suitable block is found, the
   process is put on a waiting list until a block
   becomes available. When a process releases memory,
   the algorithm merges adjacent free blocks to form
   larger blocks. Time complexity is O(n*m) when n is
   the number of processes and m is the numner of
   memory blocks. The outer for loop runs for n
   times and the inner for loop runs for m times.
   Space complexity is O(n( where n is again 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). */
   

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