Worst Fit Algorithm Program In C

June 29, 2023

Worst Fit Algorithm Program in C

 On this page, we will learn Worst Fit algorithm in C. How it works and programs in C

Worst Fit

Why Memory Allocation Algorithm?

The processes need empty memory slots during processing time.

This memory is allocated to the processes by the operating system based on various algorithms like

  1. First Fit
  2. Best Fit
  3. Worst Fit
  4. Next Fit

OS  decides it depends on the free memory and the demanded memory by the process in execution and algorithm used.

Please read more about Worst Fit Algorithm here first.

In the case of the worst fit when accommodating a process P1, the operating system searches for –

  • Memory block that can fit the process
  • Leaves the highest wasted(empty) space after P1 is placed in block
Worst Fit Allocation in OS

Methods discussed

We will look at two methods –

  • Method 1: Block allowed to keep just one single process, even though fragmented space is large enough to accommodate other processes
  • Method 2: Block allowed to keep multiple processes, if fragmented space is large enough to accommodate other processes

Method 1 (Block allowed to keep one Process)

Run 
#include <stdio.h>

void implimentWorstFit(int blockSize[], int blocks, int processSize[], int processes)
{
    // This will store the block id of the allocated block to a process
    int allocation[processes];
    int occupied[blocks];
    
    // initially assigning -1 to all allocation indexes
    // means nothing is allocated currently
    for(int i = 0; i < processes; 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 < processes; i++)
    {
	int indexPlaced = -1;
	for(int j = 0; j < blocks; j++)
	{
	    // if not occupied and block size is large enough
	    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 larger than the current block where
                // process is placed, change the block and thus indexPlaced
                else if (blockSize[indexPlaced] < blockSize[j])
                    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;
 
            // 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[] = {100, 50, 30, 120, 35};
    int processSize[] = {40, 10, 30, 60};
    int blocks = sizeof(blockSize)/sizeof(blockSize[0]);
    int processes = sizeof(processSize)/sizeof(processSize[0]);
 
    implimentWorstFit(blockSize, blocks, processSize, processes);
 
    return 0;
}

Output

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

Method 2 (Block Allowed to keep multiple Processes)

In this case, one block is allowed to keep multiple processes if fragmented space is large enough to accommodate the newer processes.
Run 
// C Program for Worst Fit
#include <stdio.h>

void implimentWorstFit(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 larger than the current block where
                // process is placed, change the block and thus indexPlaced
                else if (blockSize[indexPlaced] < blockSize[j])
                    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[] = {5, 4, 3, 6, 7};
    int processSize[] = {1, 3, 5, 3};
    int blocks = sizeof(blockSize)/sizeof(blockSize[0]);
    int processes = sizeof(processSize)/sizeof(processSize[0]);
 
    implimentWorstFit(blockSize, blocks, processSize, processes);
 
    return 0 ;
}

Output

Process No.	Process Size	Block no.
1 		1 		5
2 		3 		4
3 		5 		5
4 		3 		1
[table id=676 /]
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