Best Fit Algorithm Program In C

April 1, 2022

Best Fit Algorithm Program in C

Memory allocation is one of the important tasks of the operating system. As the different processes need the CPU processing time, they also need a certain amount of memory. This memory is allocated to different processes according to their demand.

What is memory allocation

The three most common types of memory allocation schemes are

What is Best Fit

In the case of the best fit memory allocation scheme for process p1, the operating system searches for –

The empty memory block that can accommodate process P1
The memory wastage is minimum after allocating the process p1 out of all blocks.

This scheme is considered the best approach as it results in the most optimised memory allocation. However, finding the best fit memory allocation may be time-consuming.

Read Also – Best Fit program in C++

Methods discussed

We will look at two methods for the coding of the Best Fit algorithm.

Method 1 – Only Single Process allowed to occupy any block space
Method 2 – Multiple Processes allowed to share fragmented block space

Method 1 (Processes not Allowed sharing BlockSpace)

Let us have a look at the code below –

Run

#include <stdio.h>

void implimentBestFit(int blockSize[], int blocks, int processSize[], int proccesses)
{
    // This will store the block id of the allocated block to a process
    int allocation[proccesses];
    int occupied[blocks];
    
    // initially assigning -1 to all allocation indexes
    // means nothing is allocated currently
    for(int i = 0; i < proccesses; i++){
        allocation[i] = -1;
    }
    
    for(int i = 0; i < blocks; i++){
        occupied[i] = 0;
    }
 
    // pick each process and find suitable blocks
    // according to its size ad assign to it
    for (int i = 0; i < proccesses; i++)
    {
        
        int indexPlaced = -1;
        for (int j = 0; j < blocks; j++) { 
            if (blockSize[j] >= processSize[i] && !occupied[j])
            {
                // place it at the first block fit to accomodate process
                if (indexPlaced == -1)
                    indexPlaced = j;
                    
                // if any future block is smalller than the current block where
                // process is placed, change the block and thus indexPlaced
		// this reduces the wastage thus best fit
                else if (blockSize[j] < blockSize[indexPlaced])
                    indexPlaced = j;
            }
        }
 
        // If we were successfully able to find block for the process
        if (indexPlaced != -1)
        {
            // allocate this block j to process p[i]
            allocation[i] = indexPlaced;
            
            // make the status of the block as occupied
            occupied[indexPlaced] = 1;
        }
    }
 
    printf("\nProcess No.\tProcess Size\tBlock no.\n");
    for (int i = 0; i < proccesses; i++)
    {
        printf("%d \t\t\t %d \t\t\t", i+1, processSize[i]);
        if (allocation[i] != -1)
            printf("%d\n",allocation[i] + 1);
        else
            printf("Not Allocated\n");
    }
}
 
// Driver code
int main()
{
    int blockSize[] = {100, 50, 30, 120, 35};
    int processSize[] = {40, 10, 30, 60};
    int blocks = sizeof(blockSize)/sizeof(blockSize[0]);
    int proccesses = sizeof(processSize)/sizeof(processSize[0]);
 
    implimentBestFit(blockSize, blocks, processSize, proccesses);
 
    return 0 ;
}

Output

Process No.	Process Size	Block no.
1 		10 		2
2 		30 		1
3 		60 		4
4 		30 		4

Method 2 (Processes Allowed sharing BlockSpace)

Let us have a look at the code below –

Run

// C Program for Worst Fit
#include <stdio.h>

void implimentBestFit(int blockSize[], int blocks, int processSize[], int processes)
{
    // This will store the block id of the allocated block to a process
    int allocation[processes];
    
    // initially assigning -1 to all allocation indexes
    // means nothing is allocated currently
    for(int i = 0; i < processes; i++){
        allocation[i] = -1;
    }
 
    // pick each process and find suitable blocks
    // according to its size ad assign to it
    for (int i=0; i < processes; i++)
    {
        
        int indexPlaced = -1;
        for (int j=0; j < blocks; j++) 
        { 
            if (blockSize[j] >= processSize[i])
            {
                // place it at the first block fit to accomodate process
                if (indexPlaced == -1)
                    indexPlaced = j;
                    
                // if any future block is better that is 
                // any future block with smaller size encountered
                // that can accomodate the given process
                else if (blockSize[j] < blockSize[indexPlaced])
                    indexPlaced = j;
            }
        }
 
        // If we were successfully able to find block for the process
        if (indexPlaced != -1)
        {
            // allocate this block j to process p[i]
            allocation[i] = indexPlaced;
 
            // Reduce available memory for the block
            blockSize[indexPlaced] -= processSize[i];
        }
    }
 
    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 (allocation[i] != -1)
            printf("%d\n",allocation[i] + 1);
        else
            printf("Not Allocated\n");
    }
}
 
// Driver code
int main()
{
    int blockSize[] = {50, 20, 100, 90};
    int processSize[] = {10, 30, 60, 30};
    int blocks = sizeof(blockSize)/sizeof(blockSize[0]);
    int processes = sizeof(processSize)/sizeof(processSize[0]);
 
    implimentBestFit(blockSize, blocks, processSize, processes);
 
    return 0 ;
}

Output

Lets have a look at the code below –

Process No.	Process Size	Block no.
1 		10 		2
2 		30 		1
3 		60 		4
4 		80 		3

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

Best Fit Algorithm Program In C