Skip to content

Added Best/First/Worst Fit algorithm implementation #1214

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Jan 26, 2020
Merged

Added Best/First/Worst Fit algorithm implementation #1214

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
79467b3
Added Best/First/Worst Fit algorithm implementation
DekasDimitrios Jan 26, 2020
d40464a
Change Done
DekasDimitrios Jan 26, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
89 changes: 89 additions & 0 deletions Others/BestFit.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,89 @@
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();
}
}
}
70 changes: 70 additions & 0 deletions Others/FirstFit.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,70 @@
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();
}
}
}
76 changes: 76 additions & 0 deletions Others/WorstFit.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,76 @@
package Others;

import java.util.ArrayList;

/**
* @author Dekas Dimitrios
*/
public class WorstFit {
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 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.
*/
static ArrayList<Integer> worstFit(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;
}

/**
* Method to print the memory allocated.
*
* @param memAllocation: an ArrayList of Integer representing the memory allocation done by the worstFit 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();
}
}
}