4 Replies - 976 Views - Last Post: 22 March 2012 - 02:43 PM Rate Topic: -----

#1 dougyno1   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 06-May 11

Resource suggestions for homework

Posted 20 March 2012 - 02:25 PM

Hey all,

I have a homework task where we are required to build a program that implements the first fit and best fit algorithms (memory allocation) to place 5 incoming jobs of any size for example 56 (Kb) into memory blocks of a certain size and to place certain jobs on a waiting list. I found a good source code example already for first fit but nothing as yet for best fit. I would grately appreciate any recommendations of tutorials/source code etc for both algorithms and prefarably relating to the problem needed to be solved from anyone familiar with the topic.

Thanks very much!!

Is This A Good Question/Topic? 0
  • +

Replies To: Resource suggestions for homework

#2 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8379
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Resource suggestions for homework

Posted 20 March 2012 - 06:22 PM

May be a good exercide in C/C++ but in Java it is kind of completly useless
You won't store you jobs in contiguous bytes in memory, or it would be a completly tedious exercise that will never a match an actual problem in real life and that does not have any practical benefit. Actually it defeats Java philosophy where you would allocate Job object to store your task and really don't worry on how the memory is allocated.
Was This Post Helpful? 1
  • +
  • -

#3 blackcompe   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Re: Resource suggestions for homework

Posted 20 March 2012 - 08:54 PM

From what I've concluded, the only difference is that the best fit algorithm will place the object in the fullest bin that still has room, instead of placing it in the leftmost bin that has enough room. If you know the algorithm for first fit, then adapting it should be a piece of cake.
Was This Post Helpful? 1
  • +
  • -

#4 dougyno1   User is offline

  • D.I.C Head

Reputation: 0
  • View blog
  • Posts: 78
  • Joined: 06-May 11

Re: Resource suggestions for homework

Posted 22 March 2012 - 09:37 AM

Thanks guys for both of your comments,

It is just an exercise program to show how memory is allocated to job processes, the module is security and operating systems and we needed to show this in a java program.

I have already commpleted my first fit algorithm program, but am having having a little trouble after adapting it for best fit.

Here is the pseudo we were given in our brief:

Best-fit
1 Initialise memory_block(0) = 99999
2 Computer initial_memory_waste = memory_block(0) job_size
3 Inialise subscript = 0
4 Set counter to 1
5 Do while counter <= number of blocks in memory
If job_size > memory_size(counter)
counter = counter + 1
Else
memory_waste = memory_size(counter) job_size
If initial_memory_waste > memory_waste
subscript = counter
Initial_memory_waste = memory_wast
counter = counter + 1
End do
6 If subscript = 0
put job in waiting list
Else
load job into memory(subscript)
adjust free/busy memory lists
7 Fetch next job

here is the code I have adapted so far:


public class BF_Algorithm 

{
	double [] jobSize;
    double [] memorySize;
 
    // the number of memory blocks
    int blocks;
 
    // the number of jobs
    int jobs;
 
    int theCounter;
    int jobIndex;
    int jobInQueue;
    double memoryWaste;
    double initialWaste;
    int subScript = 0;
 
public void setJobs(double job1, double job2, double job3, double job4, double job5)
{
    jobSize = new double[5];
     // jobs
    jobSize[0] = job1;  // job 1
    jobSize[1] = job2;  // job 2
    jobSize[2] = job3;  // job 3
    jobSize[3] = job4;  // job 4
    jobSize[4] = job5;  // job 5
    jobs = jobSize.length;
}
public void setMemory(double memory1, double memory2, double memory3, double memory4, double memory5)
{
     memorySize = new double[5];
    //available memory blocks
    memorySize[0] = memory1;  // memory block 1
    memorySize[1] = memory2;  // memory block 2
    memorySize[2] = memory3;  // memory block 3
    memorySize[3] = memory4;  // memory block 4
    memorySize[4] = memory5;  // memory block 5
    blocks = memorySize.length;
}
 
public void bestFit(int countr, int jobIndex)
{
	
   
	theCounter = countr;
 
do {
            if (jobSize[jobIndex] > memorySize[theCounter-1])
        {  
            theCounter += 1;
        }
        else
        { 
        
        	memoryWaste = memorySize[theCounter] - (jobSize[0] + jobSize[1] + jobSize[2] + jobSize[3] + jobSize[4]);
        	
        }
            if (initialWaste > memoryWaste)
            {
            	subScript = theCounter;
            	initialWaste = memoryWaste;
            	theCounter += 1;
            }
            
 
  }   while (theCounter <= blocks && jobIndex < jobs);
 
if (subScript == 0)
{
  jobInQueue = jobIndex;
  if (jobInQueue < jobs) {
  System.out.println("Job " + (jobInQueue+1) + " of size " + jobSize[jobInQueue] + " is sent to waiting queue!" + "\n");
  }
} else
{
	System.out.println("Job " + (jobIndex+1) + " of size "  + jobSize[jobIndex] + " has been loaded into memory block:" + subScript + "\n");
    memorySize[theCounter-1] = (memorySize[theCounter-1]-jobSize[jobIndex]);
    System.out.println("The size of memory block " + theCounter + " is now " + memorySize[theCounter-1] + "\n");
    
    theCounter = 1;
    jobIndex += 1;
}
}

public double initialcomputerWaste()
{
	double answer;
	double memoryBlock0 = 99999;
	answer = memoryBlock0 - (jobSize[0] + jobSize[1] + jobSize[2] + jobSize[3] + jobSize[4]);
	answer = initialWaste;
	return answer;
}

public void showData() {

System.out.println("Available memory blocks are: (" + memorySize[0] + "), (" + memorySize[1] + "),(" + memorySize[2] + "), (" + memorySize[3] + "), (" + memorySize[4] + ")" + "\n");
System.out.println("And jobs to allocate are: (" + jobSize[0] + "), (" + jobSize[1] + "),(" + jobSize[2] + "), (" + jobSize[3] + "), (" + jobSize[4] + ")" + "\n");

}
 
public static void main(String [] args) 
{

  BF_Algorithm ob = new BF_Algorithm();
  ob.setJobs(64,80,10,5,18); // set new jobs, change these values if you want
  ob.setMemory(99,70,20,20,35); // set memory blocks, change these values if you want
  ob.showData(); // display detail of available memory blocks and jobs to allocate 
  ob.bestFit(1,0);
  System.out.println("Initial computer waste is: " + ob.initialcomputerWaste());
  
  
  if (ob.jobInQueue < ob.jobs) {
      ob.bestFit(1,(ob.jobInQueue+1));
    }
  }
}



and the output is attached

is there any suggestions on what is wrong with the program??
Was This Post Helpful? 0
  • +
  • -

#5 blackcompe   User is offline

  • D.I.C Lover
  • member icon

Reputation: 1159
  • View blog
  • Posts: 2,547
  • Joined: 05-May 05

Re: Resource suggestions for homework

Posted 22 March 2012 - 02:43 PM

It looks like you've completely neglected to implement steps 1-4 in the algorithm. In your code you immediately start at the do/while loop, which is step 5 of the psuedocode. Ok... I see you have a method initialComputerWaste, but that really shouldn't be extracted. You can see that I actually had to look for it. I sort of stumbled upon it. At the very least, you could have called it from the bestFit method. That's apart of the algorithm and therefore should be in the method. Everything dealing with the best fit algorithm ought to be the method. It's not a long algorithm. If anything you can extract code into methods later.

memoryWaste = memorySize[theCounter] - (jobSize[0] + jobSize[1] + jobSize[2] + jobSize[3] + jobSize[4]);



That's wrong. You're supposed to take the remaining capacity of the bin and subtract from it the size of the job we're scheduling. That's definitely going to throw off your results. Your psuedocode also agrees.

memory_waste = memory_size(counter) – job_size


This post has been edited by blackcompe: 22 March 2012 - 02:51 PM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1