First fit in C

April 1, 2022

First Fit in C

The operating system uses different memory management schemes to optimize resource allocation. The responsibility of these schemes is to allocate memory chunks based on the demand by the operating system. The three most commonly used allocation schemes are first to fit, best fit, and worst fit.

First Fit

The operating system uses different memory management schemes to optimize resource allocation.

The responsibility of these schemes is to allocate memory chunks based on the demand by the operating system. The three most commonly used allocation schemes are

The first fit memory allocation scheme checks the empty memory block in a sequential manner. This means that the memory block found empty at the first attempt is checked for size.

If the size is not less than the required size, it is allocated. One of the biggest issues in this memory allocation scheme is, when a process is allocated to a comparatively larger space than needed, it creates huge chunks of memory space.

Read Also – First Fit algorithm in C++

Methods discussed

We will look at two different methods –

  • Method 1 – Blocks allowed to keep just one single process
  • Method 2 – Blocks are allowed to keep multiple processes if partitioned fragmentation is big enough for new processes

Method 1 (Only Single Processes Allowed in Blocks)

Run 
#include <stdio.h>

void implimentFirstFit(int blockSize[], int blocks, int processSize[], int processes)
{
    // This will store the block id of the allocated block to a process
    int allocate[processes];
    int occupied[blocks];

    // initially assigning -1 to all allocation indexes
    // means nothing is allocated currently
    for(int i = 0; i < processes; i++)
	{
		allocate[i] = -1;
	}
	
	for(int i = 0; i < blocks; i++){
        occupied[i] = 0;
    }
	
    // take each process one by one and find
    // first block that can accomodate it
    for (int i = 0; i < processes; i++)
    {
        for (int j = 0; j < blocks; j++) 
        { 
        if (!occupied[j] && blockSize[j] >= processSize[i])
            {
                // allocate block j to p[i] process
                allocate[i] = j;
                occupied[j] = 1;
 
                break;
            }
        }
    }

    printf("\nProcess No.\tProcess Size\tBlock no.\n");
    for (int i = 0; i < processes; i++)
    {
        printf("%d \t\t\t %d \t\t\t", i+1, processSize[i]);
        if (allocate[i] != -1)
            printf("%d\n",allocate[i] + 1);
        else
            printf("Not Allocated\n");
    }
}

void main()
{
    int blockSize[] = {30, 5, 10};
    int processSize[] = {10, 6, 9};
    int m = sizeof(blockSize)/sizeof(blockSize[0]);
    int n = sizeof(processSize)/sizeof(processSize[0]);
    
    implimentFirstFit(blockSize, m, processSize, n);
}

Output

Process No.	Process Size	Block no.
1 		10 		1
2 		6 		3
3 		9 		Not Allocated

Method 2 (Multiple Processes Allowed)

Run 
#include <stdio.h>

void implimentFirstFit(int blockSize[], int blocks, int processSize[], int processes)
{
    // This will store the block id of the allocated block to a process
    int allocate[processes];
    
    // initially assigning -1 to all allocation indexes
    // means nothing is allocated currently
    for(int i = 0; i < processes; i++)
    {
		allocate[i] = -1;
    }
	
    // take each process one by one and find
    // first block that can accomodate it
    for (int i = 0; i < processes; i++)
    {
        for (int j = 0; j < blocks; j++) { 
            if (blockSize[j] >= processSize[i])
            {
                // allocate block j to p[i] process
                allocate[i] = j;
 
                // Reduce size of block j as it has accomodated p[i]
                blockSize[j] -= processSize[i];
 
                break;
            }
        }
    }

    printf("\nProcess No.\tProcess Size\tBlock no.\n");
    for (int i = 0; i < processes; i++)
    {
        printf("%d \t\t\t %d \t\t\t", i+1, processSize[i]);
        if (allocate[i] != -1)
            printf("%d\n",allocate[i] + 1);
        else
            printf("Not Allocated\n");
    }
}

void main()
{
    int blockSize[] = {30, 5, 10};
    int processSize[] = {10, 6, 9};
    int m = sizeof(blockSize)/sizeof(blockSize[0]);
    int n = sizeof(processSize)/sizeof(processSize[0]);
    
    implimentFirstFit(blockSize, m, processSize, n);
}

Output

Process No.   Process Size   Block no.
1             10             1
2             6              1
3             9              1
Operating systems Memory

      Read More

  1. Memory Management Introduction
  2. Partition Allocation Method
    1. First Fit in OS
      1. Program in C | C++ | Java | Python
    2. Best fit
      1. Program in C | C++ | Java | Python
    3. Worst fit
      1. Program in C | C++ | Java | Python
    4. Next fit
      1. Program in C | C++ | Java | Python
    5. First fit best fit worst fit in OS Example
  3. Buddy- System Allocator
  4. Paging
    1. Types of Paging
  5. Fragmentation
    1. internal fragmentation
    2. external fragmentation
    3. internal fragmentation vs external fragmentation
  6. Mapping Virtual address to Physical Address.
  7. Virtual Memory 
  8. Demand Paging
  9. Implementation of Demand paging and page fault
  10. Segmentation
  11. Page Replacement Algorithms
    1. LRU
    2. FIFO
    3. Optimal Page Replacement algorithm
  12. Thrashing
  13. Belady’s Anomaly
  14. Static vs Dynamic Loading
  15. Static vs Dynamic Linking
  16. Swapping
  17. Translational Look Aside Buffer
  18. Process Address Space
  19. Difference between Segmentation and Paging
Go to Operating System Tutorials Main Page