Tutorialspoint.dev

Program for Worst Fit algorithm in Memory Management

Prerequisite : Partition allocation methods

Worst Fit allocates a process to the partition which is largest sufficient among the freely available partitions available in the main memory. If a large process comes at a later stage, then memory will not have space to accommodate it.

Example:



Input : blockSize[]   = {100, 500, 200, 300, 600};
        processSize[] = {212, 417, 112, 426};
Output:
Process No.    Process Size    Block no.
   1        212        5
   2        417        2
   3        112        5
   4        426        Not Allocated

first-fit

Implementation:
1- Input memory blocks and processes with sizes.
2- Initialize all memory blocks as free.
3- Start by picking each process and find the
   maximum block size that can be assigned to
   current process i.e., find max(bockSize[1], 
   blockSize[2],.....blockSize[n]) > 
   processSize[current], if found then assign 
   it to the current process.
5- If not then leave that process and keep checking
   the further processes.

Below is implementation of above steps.

C++

// C++ implementation of worst - Fit algorithm
#include<bits/stdc++.h>
using namespace std;
  
// Function to allocate memory to blocks as per worst fit
// algorithm
void worstFit(int blockSize[], int m, int processSize[], 
                                                 int n)
{
    // Stores block id of the block allocated to a
    // process
    int allocation[n];
  
    // Initially no block is assigned to any process
    memset(allocation, -1, sizeof(allocation));
  
    // pick each process and find suitable blocks
    // according to its size ad assign to it
    for (int i=0; i<n; i++)
    {
        // Find the best fit block for current process
        int wstIdx = -1;
        for (int j=0; j<m; j++)
        {
            if (blockSize[j] >= processSize[i])
            {
                if (wstIdx == -1)
                    wstIdx = j;
                else if (blockSize[wstIdx] < blockSize[j])
                    wstIdx = j;
            }
        }
  
        // If we could find a block for current process
        if (wstIdx != -1)
        {
            // allocate block j to p[i] process
            allocation[i] = wstIdx;
  
            // Reduce available memory in this block.
            blockSize[wstIdx] -= processSize[i];
        }
    }
  
    cout << " Process No. Process Size Block no. ";
    for (int i = 0; i < n; i++)
    {
        cout << "   " << i+1 << " " << processSize[i] << " ";
        if (allocation[i] != -1)
            cout << allocation[i] + 1;
        else
            cout << "Not Allocated";
        cout << endl;
    }
}
  
// Driver code
int main()
{
    int blockSize[] = {100, 500, 200, 300, 600};
    int processSize[] = {212, 417, 112, 426};
    int m = sizeof(blockSize)/sizeof(blockSize[0]);
    int n = sizeof(processSize)/sizeof(processSize[0]);
  
    worstFit(blockSize, m, processSize, n);
  
    return 0 ;
}

Java

// Java implementation of worst - Fit algorithm
  
public class GFG 
{
    // Method to allocate memory to blocks as per worst fit
    // algorithm
    static void worstFit(int blockSize[], int m, int processSize[], 
                                                     int n)
    {
        // Stores block id of the block allocated to a
        // process
        int allocation[] = new int[n];
       
        // Initially no block is assigned to any process
        for (int i = 0; i < allocation.length; i++)
            allocation[i] = -1;
       
        // pick each process and find suitable blocks
        // according to its size ad assign to it
        for (int i=0; i<n; i++)
        {
            // Find the best fit block for current process
            int wstIdx = -1;
            for (int j=0; j<m; j++)
            {
                if (blockSize[j] >= processSize[i])
                {
                    if (wstIdx == -1)
                        wstIdx = j;
                    else if (blockSize[wstIdx] < blockSize[j])
                        wstIdx = j;
                }
            }
       
            // If we could find a block for current process
            if (wstIdx != -1)
            {
                // allocate block j to p[i] process
                allocation[i] = wstIdx;
       
                // Reduce available memory in this block.
                blockSize[wstIdx] -= processSize[i];
            }
        }
       
        System.out.println(" Process No. Process Size Block no.");
        for (int i = 0; i < n; i++)
        {
            System.out.print("   " + (i+1) + " " + processSize[i] + " ");
            if (allocation[i] != -1)
                System.out.print(allocation[i] + 1);
            else
                System.out.print("Not Allocated");
            System.out.println();
        }
    }
      
    // Driver Method
    public static void main(String[] args)
    {
         int blockSize[] = {100, 500, 200, 300, 600};
         int processSize[] = {212, 417, 112, 426};
         int m = blockSize.length;
         int n = processSize.length;
           
         worstFit(blockSize, m, processSize, n);
    }
}

Python3

# Python3 implementation of worst - Fit algorithm 
  
# Function to allocate memory to blocks as 
# per worst fit algorithm 
def worstFit(blockSize, m, processSize, n):
      
    # Stores block id of the block 
    # allocated to a process 
      
    # Initially no block is assigned 
    # to any process 
    allocation = [-1] * n
      
    # pick each process and find suitable blocks 
    # according to its size ad assign to it 
    for i in range(n):
          
        # Find the best fit block for 
        # current process 
        wstIdx = -1
        for j in range(m):
            if blockSize[j] >= processSize[i]:
                if wstIdx == -1
                    wstIdx =
                elif blockSize[wstIdx] < blockSize[j]: 
                    wstIdx = j
  
        # If we could find a block for 
        # current process 
        if wstIdx != -1:
              
            # allocate block j to p[i] process 
            allocation[i] = wstIdx 
  
            # Reduce available memory in this block. 
            blockSize[wstIdx] -= processSize[i]
  
    print("Process No. Process Size Block no.")
    for i in range(n):
        print(i + 1, "       "
              processSize[i], end = "    "
        if allocation[i] != -1:
            print(allocation[i] + 1
        else:
            print("Not Allocated")
  
# Driver code 
if __name__ == '__main__':
    blockSize = [100, 500, 200, 300, 600
    processSize = [212, 417, 112, 426
    m = len(blockSize) 
    n = len(processSize) 
  
    worstFit(blockSize, m, processSize, n)
  
# This code is contributed by PranchalK


Output:

Process No.    Process Size    Block no.
   1        212        5
   2        417        2
   3        112        5
   4        426        Not Allocated

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter