First Fit program in C++

March 27, 2022

First Fit Program in C++

Memory management schemes in an operating system are used to allocate memory during the processing time. These schemes allocate memory chunks to the processes based on different criteria. The three most commonly used schemes are first fit, best fit, and worst fit.

How first fit works?

Whenever a process (p1) comes with memory allocation request the following happens –

OS sequentially searches available memory blocks from the first index
Assigns the first memory block large enough to accommodate process

Whenever a new process P2 comes, it does the same thing. Search from the first index again.

Read Also – First Fit algorithm in JAVA

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 allowed to keep multiple processes, if partitioned fragmentation big enough for new processes

Method 1 Code

Run

// Only Single Processes Allowed in Blocks
#include<bits/stdc++.h>
using namespace std;

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
    memset(allocate, -1, sizeof(allocate));
	
	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++)
    {
        cout << i + 1 << "\t\t\t" << processSize[i] << "\t\t\t";
        if (allocate[i] != -1)
            cout << allocate[i] + 1 << endl;
        else
            cout << "Not Allocated" << endl;
    }
}

int main()
{
    int blockSize[] = {100, 50, 30, 120, 35};
    int processSize[] = {20, 60, 70, 40};
    int m = sizeof(blockSize)/sizeof(blockSize[0]);
    int n = sizeof(processSize)/sizeof(processSize[0]);
    
    implimentFirstFit(blockSize, m, processSize, n);
    
    return 0;
}

Output

Process No.	Process Size	Block no.
1		20		1
2		60		4
3		70		Not Allocated
4		40		2

Method 2 Code

In this multiple processes can share the same block if space is available for the newer process.

Run

// Multiple Processes Allowed
#include<bits/stdc++.h>
using namespace std;

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
    memset(allocate, -1, sizeof(allocate));
	
    // 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++)
    {
        cout << i + 1 << "\t\t\t" << processSize[i] << "\t\t\t";
        if (allocate[i] != -1)
            cout << allocate[i] + 1 << endl;
        else
            cout << "Not Allocated" << endl;
    }
}

int main()
{
    int blockSize[] = {100, 50, 30, 120, 35};
    int processSize[] = {20, 60, 70, 40};
    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		20		1
2		60		1
3		70		4
4		40		2

Memory Management Introduction
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
Buddy- System Allocator
Paging
1. Types of Paging
Fragmentation
Mapping Virtual address to Physical Address.
Virtual Memory
Demand Paging
Implementation of Demand paging and page fault
Segmentation
Page Replacement Algorithms
Thrashing
Belady’s Anomaly
Static vs Dynamic Loading
Static vs Dynamic Linking
Swapping
Translational Look Aside Buffer
Process Address Space
Difference between Segmentation and Paging

First Fit program in C++