d

```
package com.thealgorithms.others;
/**
* @author Alexandros Lemonaris
*/
import java.util.ArrayList;
public abstract class MemoryManagementAlgorithms {
/**
* Method to allocate memory to blocks according to CPU algorithms.
* Use of inheritance to avoid repeated code.
* Abstract method since it is implemented different for each 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.
*/
public abstract ArrayList<Integer> fitProcess(int[] sizeOfBlocks, int[] sizeOfProcesses);
/**
* A constant value used to indicate that an allocation has not been made.
* This value is used as a sentinel value to represent that no allocation has been made
* when allocating space in an array or other data structure.
* The value is -255 and is marked as protected and final to ensure that it cannot be modified
* from outside the class and that its value remains consistent throughout the program
* execution.
*
* @author: Ishan Makadia (github.com/intrepid-ishan)
* @version: April 06, 2023
*/
protected static final int NO_ALLOCATION = -255;
}
/**
* @author Dekas Dimitrios
*/
class BestFitCPU extends MemoryManagementAlgorithms {
/**
* 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.
*/
public ArrayList<Integer> fitProcess(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;
}
}
/**
* @author Dekas Dimitrios
*/
class WorstFitCPU extends MemoryManagementAlgorithms {
/**
* Method to find the index of the memory block that is going to fit the
* given process based on the worst 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 findWorstFit(int[] blockSizes, int processSize) {
int max = -1;
int index = -1;
for (int i = 0; i < blockSizes.length; i++) { // Find the index of the biggest memory block available.
if (blockSizes[i] > max) {
max = blockSizes[i];
index = i;
}
}
// If the biggest memory block cannot fit the process, return -255 as the result
if (processSize > blockSizes[index]) {
return NO_ALLOCATION;
}
return index;
}
/**
* Method to allocate memory to blocks according to the worst 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.
*/
public ArrayList<Integer> fitProcess(int[] sizeOfBlocks, int[] sizeOfProcesses) {
// The array list responsible for saving the memory allocations done by the worst-fit
// algorithm
ArrayList<Integer> memAlloc = new ArrayList<>();
// Do this for every process
for (int processSize : sizeOfProcesses) {
int chosenBlockIdx = findWorstFit(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;
}
}
/**
* @author Dekas Dimitrios
*/
class FirstFitCPU extends MemoryManagementAlgorithms {
/**
* 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.
*/
public ArrayList<Integer> fitProcess(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;
}
}
/**
* @author Alexandros Lemonaris
*/
class NextFit extends MemoryManagementAlgorithms {
private int counter = 0; // variable that keeps the position of the last registration into the memory
/**
* Method to find the index of the memory block that is going to fit the
* given process based on the next fit algorithm. In the case of next fit,
* if the search is interrupted in between, the new search is carried out from the last
* location.
*
* @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 int findNextFit(int[] blockSizes, int processSize) {
for (int i = 0; i < blockSizes.length; i++) {
if (counter + i >= blockSizes.length) {
counter = -i; // starts from the start of the array
}
if (blockSizes[i + counter] >= processSize) {
counter += i;
return counter;
}
}
// If there is not a block that can fit the process, return -255 as the result
counter += blockSizes.length; // counter keeps its last value
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.
*/
public ArrayList<Integer> fitProcess(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 = findNextFit(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;
}
}
```