First Fit Algorithm
The First Fit Algorithm is a widely used heuristic method for solving the bin packing problem, which aims to efficiently allocate a set of items into the least number of bins possible. The bin packing problem has numerous practical applications, such as in loading trucks with packages, allocating tasks to servers, and even organizing items in a warehouse. The First Fit Algorithm is relatively simple and fast, making it an attractive option for tackling bin packing challenges. However, it is important to note that the First Fit Algorithm is not guaranteed to produce the optimal solution in all cases, as it is a heuristic approach.
In the First Fit Algorithm, items are processed sequentially, and each item is placed in the first available bin that has enough space left to accommodate it. To implement this algorithm, we start with an empty bin and iterate through the list of items. For each item, we check if it can fit into any of the already opened bins, and if so, we place it in the first bin where it fits. If no existing bin can accommodate the item, we open a new bin and place the item into it. This process continues until all items have been allocated to bins. Although this approach may not always result in the most efficient packing, it offers a good balance of simplicity and effectiveness for many real-world bin packing scenarios.
package Others;
import java.util.ArrayList;
/**
* @author Dekas Dimitrios
*/
public class FirstFit {
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 index of the memory block that is going to fit the given process based on the first 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 findFirstFit(int[] blockSizes, int processSize) {
for(int i=0 ; i < blockSizes.length ; i++) {
if(blockSizes[i] >= processSize) {
return i;
}
}
// If there is not a block that can fit the process, return -255 as the result
return NO_ALLOCATION;
}
/**
* Method to allocate memory to blocks according to the first 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> firstFit(int[] sizeOfBlocks, int[] sizeOfProcesses) {
// The array list responsible for saving the memory allocations done by the first-fit algorithm
ArrayList<Integer> memAlloc = new ArrayList<>();
// Do this for every process
for(int processSize : sizeOfProcesses) {
int chosenBlockIdx = findFirstFit(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 firstFit 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();
}
}
}
