Best Fit Algorithm

The Best Fit Algorithm is a memory allocation strategy used in computer systems to efficiently utilize available memory resources. This algorithm aims to minimize the wastage of memory by allocating the smallest possible memory block that can accommodate the requested data. In the Best Fit Algorithm, the operating system searches for the smallest unused memory block that is equal to or larger than the requested size, and then allocates it to the process. By doing so, the algorithm ensures that the memory is allocated in a way that minimizes fragmentation, leading to more efficient use of memory resources in the system. In the implementation of the Best Fit Algorithm, a list or data structure is maintained to keep track of all the available memory blocks in the system. When a process requests memory allocation, the algorithm searches this list to find the smallest suitable memory block. Once the appropriate block is identified, the requested memory is allocated, and the remaining unused portion of the block (if any) is added back to the list of available memory. The Best Fit Algorithm has advantages over other memory allocation algorithms such as First Fit and Next Fit, as it reduces the overall fragmentation and waste of memory. However, it can be slower in comparison due to the time taken to search for the smallest suitable memory block.
package Others;

import java.util.ArrayList;

/**
 * @author Dekas Dimitrios
 */
public class BestFit {
    private static final int NO_ALLOCATION = -255; // if a process has been allocated in position -255,
                                                   // it means that it has not been actually allocated.

    /**
     * Method to find the maximum valued element of an array filled with positive integers.
     *
     * @param array: an array filled with positive integers.
     * @return the maximum valued element of the array.
     */
    private static int findMaxElement(int[] array) {
        int max = -1;
        for (int value : array) {
            if (value > max) {
                max = value;
            }
        }
        return max;
    }

    /**
     * Method to find the index of the memory block that is going to fit the given process based on the best fit algorithm.
     *
     * @param blocks: the array with the available memory blocks.
     * @param process: the size of the process.
     * @return the index of the block that fits, or -255 if no such block exists.
     */
    private static int findBestFit(int[] blockSizes, int processSize) {
        // Initialize minDiff with an unreachable value by a difference between a blockSize and the processSize.
        int minDiff = findMaxElement(blockSizes);
        int index = NO_ALLOCATION; // If there is no block that can fit the process, return NO_ALLOCATION as the result.
        for(int i=0 ; i < blockSizes.length ; i++) { // Find the most fitting memory block for the given process.
            if(blockSizes[i] - processSize < minDiff && blockSizes[i] - processSize >= 0) {
                minDiff = blockSizes[i] - processSize;
                index = i;
            }
        }
        return index;
    }

    /**
     * Method to allocate memory to blocks according to the best fit
     * algorithm. It should return an ArrayList of Integers, where the
     * index is the process ID (zero-indexed) and the value is the block
     * number (also zero-indexed).
     *
     * @param sizeOfBlocks: an int array that contains the sizes of the memory blocks available.
     * @param sizeOfProcesses: an int array that contains the sizes of the processes we need memory blocks for.
     * @return the ArrayList filled with Integers repressenting the memory allocation that took place.
     */
    static ArrayList<Integer> bestFit(int[] sizeOfBlocks, int[] sizeOfProcesses) {
        // The array list responsible for saving the memory allocations done by the best-fit algorithm
        ArrayList<Integer> memAlloc = new ArrayList<>();
        // Do this for every process
        for(int processSize : sizeOfProcesses) {
            int chosenBlockIdx = findBestFit(sizeOfBlocks, processSize); // Find the index of the memory block going to be used
            memAlloc.add(chosenBlockIdx); // Store the chosen block index in the memAlloc array list
            if(chosenBlockIdx != NO_ALLOCATION) { // Only if a block was chosen to store the process in it,
                sizeOfBlocks[chosenBlockIdx] -= processSize; // resize the block based on the process size
            }
        }
        return memAlloc;
    }

    /**
     * Method to print the memory allocated.
     *
     * @param memAllocation: an ArrayList of Integer representing the memory allocation done by the bestFit method.
     */
    public static void printMemoryAllocation(ArrayList<Integer> memAllocation) {
        System.out.println("Process No.\tBlock No.");
        System.out.println("===========\t=========");
        for (int i = 0; i < memAllocation.size(); i++) {
            System.out.print(" " + i + "\t\t");
            if (memAllocation.get(i) != NO_ALLOCATION)
                System.out.print(memAllocation.get(i));
            else
                System.out.print("Not Allocated");
            System.out.println();
        }
    }
}

LANGUAGE:

DARK MODE: