Scribd Logo
Upload

Welcome to Scribd!

  • 140 views

    Worst Fit Algorithm

    Uploaded by

    Magarsa Bedasa
    1) Worst-fit memory allocation is a technique where processes are allocated to the largest free memory partition that is sufficient to hold them. This leads to large internal fragmentation but allows other smaller processes to potentially fit in the leftover space. 2) It is slow since it must traverse all memory partitions to find the largest free one for each process. 3) An example allocates processes of sizes 212, 417, 112, 426 to partitions of sizes 100, 500, 200, 300, 600 using a worst-fit algorithm, leaving the 426 process unallocated.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Worst Fit Algorithm

    Uploaded by

    Magarsa Bedasa
    140 views12 pages
    1) Worst-fit memory allocation is a technique where processes are allocated to the largest free memory partition that is sufficient to hold them. This leads to large internal fragmentation but allows other smaller processes to potentially fit in the leftover space. 2) It is slow since it must traverse all memory partitions to find the largest free one for each process. 3) An example allocates processes of sizes 212, 417, 112, 426 to partitions of sizes 100, 500, 200, 300, 600 using a worst-fit algorithm, leaving the 426 process unallocated.

    Original Title

    Worst fit algorithm

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1) Worst-fit memory allocation is a technique where processes are allocated to the largest free memory partition that is sufficient to hold them. This leads to large internal fragmentation but allows other smaller processes to potentially fit in the leftover space. 2) It is slow since it must traverse all memory partitions to find the largest free one for each process. 3) An example allocates processes of sizes 212, 417, 112, 426 to partitions of sizes 100, 500, 200, 300, 600 using a worst-fit algorithm, leaving the 426 process unallocated.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    140 views12 pages

    Worst Fit Algorithm

    Uploaded by

    Magarsa Bedasa
    1) Worst-fit memory allocation is a technique where processes are allocated to the largest free memory partition that is sufficient to hold them. This leads to large internal fragmentation but allows other smaller processes to potentially fit in the leftover space. 2) It is slow since it must traverse all memory partitions to find the largest free one for each process. 3) An example allocates processes of sizes 212, 417, 112, 426 to partitions of sizes 100, 500, 200, 300, 600 using a worst-fit algorithm, leaving the 426 process unallocated.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    You are on page 1of 12

    Worst-Fit Allocation in Operating

    Systems
     Last Updated : 03 Feb, 2021

    For both fixed and dynamic memory allocation schemes, the operating system must keep
    a list of each memory location noting which are free and which are busy. Then as new
    jobs come into the system, the free partitions must be allocated. 
    These partitions may be allocated in 4 ways: 
    1. First-Fit Memory Allocation
    2. Best-Fit Memory Allocation
    3. Worst-Fit Memory Allocation
    4. Next-Fit Memory Allocation
    These are Contiguous memory allocation techniques. 
    Worst-Fit Memory Allocation : 
    In this allocation technique, the process traverses the whole memory and always search
    for the largest hole/partition, and then the process is placed in that hole/partition. It is a
    slow process because it has to traverse the entire memory to search the largest hole. 
    Here is an example to understand Worst Fit-Allocation – 
    Program for Worst Fit algorithm in
    Memory Management
     Difficulty Level : Easy
     Last Updated : 28 Jun, 2021

    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
     
     
    Recommended: Please try your approach on {IDE} first, before moving on to the
    solution.
    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++
     Java
     Python3
     C#
     Javascript

    // 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("\nProcess No.\tProcess Size\tBlock no.");

            for (int i = 0; i < n; i++)

            {

                System.out.print("   " + (i+1) + "\t\t" + processSize[i] +


    "\t\t");

                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);

        }

    Output: 
    Process No. Process Size Block no.
    1 212 5
    2 417 2
    3 112 5
    4 426 Not Allocated
    Here Process P1=30K is allocated with the Worst Fit-Allocation technique, so it traverses
    the entire memory and selects memory size 400K which is the largest, and hence there is
    an internal fragmentation of 370K which is very large and so many other processes can
    also utilize this leftover space. 
    Advantages of Worst-Fit Allocation : 
    Since this process chooses the largest hole/partition, therefore there will be large internal
    fragmentation. Now, this internal fragmentation will be quite big so that other small
    processes can also be placed in that leftover partition. 
    Disadvantages of Worst-Fit Allocation : 
    It is a slow process because it traverses all the partitions in the memory and then selects
    the largest partition among all the partitions, which is a time-consuming process.

    // 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 << "\nProcess No.\tProcess Size\tBlock no.\n";

        for (int i = 0; i < n; i++)

        {

            cout << "   " << i+1 << "\t\t" << processSize[i] << "\t\t";

            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 ;

    You might also like