2012-11-05 21:04:21 -05:00
|
|
|
/*
|
2012-11-14 23:54:24 -05:00
|
|
|
* Best Fit Algorithm by David Weber
|
|
|
|
* ITCS 3146
|
|
|
|
* 11/9/2012
|
2012-11-05 21:04:21 -05:00
|
|
|
*/
|
|
|
|
|
2012-11-17 05:07:03 -05:00
|
|
|
import java.lang.reflect.Method;
|
2012-11-20 22:03:08 -05:00
|
|
|
import java.util.*;
|
2012-11-14 23:54:24 -05:00
|
|
|
|
|
|
|
public class BestFitAlgorithm implements baseAlgorithm{
|
|
|
|
|
2012-11-24 04:29:34 -05:00
|
|
|
private int memoryBlock[];
|
2012-11-17 05:07:03 -05:00
|
|
|
private Job[] jobArray = new Job[memoryManagement.JOBAMOUNT+10];
|
2012-11-24 04:29:34 -05:00
|
|
|
ArrayList<Integer> indices;
|
|
|
|
ArrayList<Integer> blocks;
|
2012-11-20 22:03:08 -05:00
|
|
|
int memoryLocation;
|
|
|
|
int bestSize; //The most suitable block size for the job
|
|
|
|
int bestSizeIndex; //The most suitable block size starting index for the job
|
|
|
|
|
2012-11-14 23:54:24 -05:00
|
|
|
public BestFitAlgorithm(int memorySize)
|
|
|
|
{
|
|
|
|
//Initialize memory block to whatever the size is
|
|
|
|
memoryBlock = new int[memorySize];
|
2012-11-24 04:29:34 -05:00
|
|
|
blocks = new ArrayList(); //Dynamically resizable array list for allocation candidates (interleaved with index and memory size);
|
|
|
|
indices = new ArrayList(); //Dynamically resizable array list for allocation candidates (interleaved with index and memory size);
|
2012-11-14 23:54:24 -05:00
|
|
|
}
|
|
|
|
|
2012-11-20 22:03:08 -05:00
|
|
|
public int getBestIndex(int jobSize)
|
2012-11-14 23:54:24 -05:00
|
|
|
{
|
2012-11-20 22:03:08 -05:00
|
|
|
memoryLocation = 0;
|
2012-11-14 23:54:24 -05:00
|
|
|
|
2012-11-20 22:03:08 -05:00
|
|
|
indices.clear();
|
|
|
|
blocks.clear();
|
2012-11-24 04:29:34 -05:00
|
|
|
synchronized(memoryBlock)
|
2012-11-20 22:03:08 -05:00
|
|
|
{
|
2012-11-24 04:29:34 -05:00
|
|
|
while (memoryLocation < this.memoryBlock.length)
|
2012-11-14 23:54:24 -05:00
|
|
|
{
|
2012-11-24 04:29:34 -05:00
|
|
|
if (memoryBlock[memoryLocation] != 0){
|
|
|
|
memoryLocation++;
|
|
|
|
continue;
|
|
|
|
}
|
|
|
|
|
|
|
|
int beginningLoc = memoryLocation;
|
|
|
|
int free = 0;
|
2012-11-20 22:03:08 -05:00
|
|
|
|
2012-11-24 04:29:34 -05:00
|
|
|
while (memoryLocation < this.memoryBlock.length && memoryBlock[memoryLocation] == 0)
|
|
|
|
{
|
|
|
|
memoryLocation++;
|
|
|
|
free++;
|
|
|
|
}
|
|
|
|
|
|
|
|
if (free >= jobSize){
|
|
|
|
//System.out.println("Found a block of size " + free + " at " + beginningLoc);
|
|
|
|
blocks.add(free);
|
|
|
|
indices.add(beginningLoc);
|
|
|
|
}
|
2012-11-20 22:03:08 -05:00
|
|
|
}
|
|
|
|
}
|
2012-11-27 16:31:41 -05:00
|
|
|
//System.out.println("Size of indices array: " + indices.size());
|
|
|
|
//System.out.println("Size of sizes array: " + blocks.size());
|
2012-11-20 22:03:08 -05:00
|
|
|
|
|
|
|
for(int i = 0; i < blocks.size(); i++)
|
|
|
|
{
|
2012-11-27 16:31:41 -05:00
|
|
|
//System.out.println("Index: " + indices.get(i));
|
|
|
|
//System.out.println("Size: " + blocks.get(i));
|
2012-11-20 22:03:08 -05:00
|
|
|
}
|
2012-11-27 17:36:40 -05:00
|
|
|
int bSize = 1;
|
2012-11-20 22:03:08 -05:00
|
|
|
int bestIndex = -1;
|
2012-11-27 18:04:07 -05:00
|
|
|
|
2012-11-27 17:36:40 -05:00
|
|
|
if(!blocks.isEmpty())
|
|
|
|
{
|
|
|
|
bSize = blocks.get(0).intValue();
|
|
|
|
}
|
2012-11-20 22:03:08 -05:00
|
|
|
|
|
|
|
//GET BEST INDEX
|
|
|
|
for(int i = 0; i < blocks.size(); i++)
|
|
|
|
{
|
|
|
|
//BEST CASE
|
|
|
|
if(blocks.get(i).intValue() == jobSize)
|
2012-11-17 05:07:03 -05:00
|
|
|
{
|
2012-11-20 22:03:08 -05:00
|
|
|
//Best possible fit. You're done.
|
|
|
|
//System.out.println("Best Case");
|
|
|
|
bestIndex = indices.get(i).intValue();
|
2012-11-17 05:07:03 -05:00
|
|
|
}
|
2012-11-20 22:03:08 -05:00
|
|
|
else if((blocks.get(i).intValue() <= bSize && blocks.get(i).intValue() >= jobSize) || blocks.get(i).intValue() > -1)
|
2012-11-14 23:54:24 -05:00
|
|
|
{
|
2012-11-20 22:03:08 -05:00
|
|
|
bestIndex = indices.get(i).intValue();
|
2012-11-14 23:54:24 -05:00
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2012-11-20 22:03:08 -05:00
|
|
|
//System.out.println("bestIndex: " + bestIndex);
|
|
|
|
//System.out.println("bSize: " + bSize);
|
2012-11-27 16:31:41 -05:00
|
|
|
|
2012-11-20 22:03:08 -05:00
|
|
|
return bestIndex;
|
2012-11-14 23:54:24 -05:00
|
|
|
}
|
|
|
|
|
|
|
|
@Override
|
|
|
|
public void allocate(int jobID, int jobSize, int jobTime)
|
2012-11-20 22:03:08 -05:00
|
|
|
{
|
2012-11-17 05:07:03 -05:00
|
|
|
try
|
2012-11-14 23:54:24 -05:00
|
|
|
{
|
2012-11-17 05:07:03 -05:00
|
|
|
Method deallocateMethod = this.getClass().getMethod("deallocate", new Class[]{int.class, int.class});
|
2012-11-20 22:03:08 -05:00
|
|
|
|
|
|
|
bestSizeIndex = this.getBestIndex(jobSize);
|
|
|
|
|
2012-11-27 17:36:40 -05:00
|
|
|
if(bestSizeIndex == -1)
|
2012-11-14 23:54:24 -05:00
|
|
|
{
|
2012-11-27 17:36:40 -05:00
|
|
|
while(bestSizeIndex == -1)
|
|
|
|
{
|
|
|
|
//Compact and try again
|
|
|
|
//System.out.println("Compacting memory...");
|
|
|
|
this.compact();
|
|
|
|
bestSizeIndex = this.getBestIndex(jobSize);
|
|
|
|
}
|
2012-11-14 23:54:24 -05:00
|
|
|
}
|
2012-11-20 22:03:08 -05:00
|
|
|
|
2012-11-27 17:36:40 -05:00
|
|
|
if(jobSize > memoryBlock.length)
|
2012-11-17 02:24:16 -05:00
|
|
|
{
|
2012-11-27 17:36:40 -05:00
|
|
|
//System.out.println("Job is too large for current memory size");
|
2012-11-17 02:24:16 -05:00
|
|
|
}
|
2012-11-27 17:36:40 -05:00
|
|
|
|
|
|
|
|
|
|
|
if(bestSizeIndex != -1)
|
2012-11-17 05:07:03 -05:00
|
|
|
{
|
2012-11-27 18:04:07 -05:00
|
|
|
//System.out.println("The size of the job is: " + jobSize);
|
|
|
|
//System.out.println("The best size index is: " + bestSizeIndex);
|
2012-11-20 22:03:08 -05:00
|
|
|
|
|
|
|
synchronized(memoryBlock)
|
2012-11-17 05:07:03 -05:00
|
|
|
{
|
2012-11-20 22:03:08 -05:00
|
|
|
for(int i = bestSizeIndex; i < jobSize + bestSizeIndex; i++)
|
|
|
|
{
|
2012-11-27 16:31:41 -05:00
|
|
|
//System.out.println("Writing jobID: " + jobID + " to position " + i + " in memory block!");
|
2012-11-20 22:03:08 -05:00
|
|
|
this.memoryBlock[i] = jobID;
|
|
|
|
}
|
2012-11-17 05:07:03 -05:00
|
|
|
}
|
2012-11-20 22:03:08 -05:00
|
|
|
|
2012-11-27 16:31:41 -05:00
|
|
|
//System.out.println("Successfully allocated! Starting job...");
|
2012-11-17 05:07:03 -05:00
|
|
|
|
2012-11-27 18:04:07 -05:00
|
|
|
//System.out.println("Job time: " + jobTime);
|
2012-11-27 17:36:40 -05:00
|
|
|
|
|
|
|
Job newJob = new Job(jobTime, jobID, jobSize, bestSizeIndex, deallocateMethod, this);
|
2012-11-20 22:03:08 -05:00
|
|
|
|
|
|
|
jobArray[jobID] = newJob;
|
|
|
|
|
|
|
|
newJob.start();
|
2012-11-17 05:07:03 -05:00
|
|
|
|
2012-11-27 16:31:41 -05:00
|
|
|
//System.out.println("Job started!");
|
2012-11-17 05:07:03 -05:00
|
|
|
}
|
|
|
|
}
|
|
|
|
catch (Exception e)
|
|
|
|
{
|
2012-11-27 17:36:40 -05:00
|
|
|
e.printStackTrace();
|
|
|
|
System.exit(-1);
|
2012-11-14 23:54:24 -05:00
|
|
|
}
|
|
|
|
}
|
2012-11-20 22:03:08 -05:00
|
|
|
/*
|
|
|
|
* This method gathers all occupied memory and stores it contiguously in an array list of blocks.
|
|
|
|
* After that, it rewrites the memoryBlock array by writing the memory in contiguous order, and then
|
|
|
|
* filling in the rest of the memory with 0's
|
|
|
|
*/
|
2012-11-14 23:54:24 -05:00
|
|
|
public void compact()
|
|
|
|
{
|
2012-11-24 04:29:34 -05:00
|
|
|
ArrayList<Integer> takenBlocks = new ArrayList();
|
2012-11-20 22:03:08 -05:00
|
|
|
|
|
|
|
memoryLocation = 0;
|
|
|
|
|
|
|
|
//Gather allocated memory
|
|
|
|
while(memoryLocation < this.memoryBlock.length && memoryBlock[memoryLocation] != 0)
|
|
|
|
{
|
|
|
|
takenBlocks.add(memoryBlock[memoryLocation]);
|
|
|
|
memoryLocation++;
|
|
|
|
}
|
|
|
|
|
|
|
|
for(int i = 0; i < takenBlocks.size(); i++)
|
|
|
|
{
|
2012-11-24 04:29:34 -05:00
|
|
|
|
|
|
|
synchronized(memoryBlock)
|
|
|
|
{
|
|
|
|
this.memoryBlock[i] = takenBlocks.get(i).intValue();
|
|
|
|
}
|
2012-11-20 22:03:08 -05:00
|
|
|
}
|
|
|
|
|
|
|
|
for(int i = takenBlocks.size(); i < this.memoryBlock.length; i++)
|
|
|
|
{
|
2012-11-24 04:29:34 -05:00
|
|
|
synchronized(memoryBlock)
|
|
|
|
{
|
|
|
|
this.memoryBlock[i] = 0;
|
|
|
|
}
|
2012-11-20 22:03:08 -05:00
|
|
|
}
|
|
|
|
|
|
|
|
/*System.out.println("Successfully compacted!");
|
|
|
|
|
|
|
|
if(takenBlocks.isEmpty())
|
|
|
|
{
|
|
|
|
System.out.println("Cannot compact!");
|
|
|
|
}
|
|
|
|
*/
|
2012-11-14 23:54:24 -05:00
|
|
|
}
|
|
|
|
|
|
|
|
@Override
|
|
|
|
public void deallocate(int jobSize, int beginningLocation)
|
2012-11-05 21:08:12 -05:00
|
|
|
{
|
2012-11-24 04:29:34 -05:00
|
|
|
synchronized(memoryBlock)
|
2012-11-14 23:54:24 -05:00
|
|
|
{
|
2012-11-27 16:31:41 -05:00
|
|
|
for(int i = beginningLocation; i < jobSize + beginningLocation; i++)
|
2012-11-24 04:29:34 -05:00
|
|
|
{
|
2012-11-27 16:31:41 -05:00
|
|
|
memoryBlock[i] = 0;
|
2012-11-24 04:29:34 -05:00
|
|
|
}
|
2012-11-14 23:54:24 -05:00
|
|
|
}
|
2012-11-05 21:08:12 -05:00
|
|
|
}
|
2012-11-14 23:54:24 -05:00
|
|
|
|
2012-11-05 21:04:21 -05:00
|
|
|
}
|