Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [102] branches/gridsim4.0-branch3
|
From: <mar...@us...> - 2008-02-14 12:00:17
|
Revision: 102
http://gridsim.svn.sourceforge.net/gridsim/?rev=102&view=rev
Author: marcos_dias
Date: 2008-02-14 04:00:22 -0800 (Thu, 14 Feb 2008)
Log Message:
-----------
This update includes a bug fix in the easy backfilling policy and a preliminary version of a multiple queue backfilling policy.
Modified Paths:
--------------
branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleEasy01.java
branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues01.java
branches/gridsim4.0-branch3/source/gridsim/GridResource.java
branches/gridsim4.0-branch3/source/gridsim/gui/ResourceWindow.java
branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java
branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/MultipleEasyBackfillingQueues.java
branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java
branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java
branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java
branches/gridsim4.0-branch3/source/gridsim/turbo/TResourceCharacteristics.java
Added Paths:
-----------
branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues02.java
branches/gridsim4.0-branch3/source/gridsim/turbo/QueuePredicate.java
Modified: branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleEasy01.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleEasy01.java 2008-02-12 05:46:26 UTC (rev 101)
+++ branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleEasy01.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -85,10 +85,10 @@
//////////////////////////////////////////
// Starts the simulation in debug mode
- GridSim.startGridSimulation(true);
+// GridSim.startGridSimulation(true);
// Start the simulation in normal mode
-// GridSim.startGridSimulation();
+ GridSim.startGridSimulation();
//////////////////////////////////////////
// Final step: Prints the Gridlets when simulation is over
Modified: branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues01.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues01.java 2008-02-12 05:46:26 UTC (rev 101)
+++ branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues01.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -1,10 +1,14 @@
package examples.workload.parallel;
+import gridsim.AllocPolicy;
import gridsim.GridResource;
import gridsim.GridSim;
import gridsim.Machine;
import gridsim.MachineList;
+import gridsim.ResourceCalendar;
+import gridsim.ResourceCharacteristics;
+import gridsim.turbo.MultipleEasyBackfillingQueues;
import gridsim.turbo.TResourceCharacteristics;
import gridsim.util.Workload;
@@ -85,10 +89,10 @@
//////////////////////////////////////////
// Starts the simulation in debug mode
- GridSim.startGridSimulation(true);
+// GridSim.startGridSimulation(true);
// Start the simulation in normal mode
-// GridSim.startGridSimulation();
+ GridSim.startGridSimulation();
//////////////////////////////////////////
// Final step: Prints the Gridlets when simulation is over
@@ -143,6 +147,13 @@
TResourceCharacteristics resConfig = new TResourceCharacteristics(
arch, os, mList, TResourceCharacteristics.EB_PARALLEL_SPACE_SHARED,
time_zone, cost);
+
+ MultipleEasyBackfillingQueues policy = null;
+ try {
+ policy = new MultipleEasyBackfillingQueues(name, "Policy", 1);
+ } catch (Exception e1) {
+ e1.printStackTrace();
+ }
//////////////////////////////////////////
// 6. Finally, we need to create a GridResource object.
@@ -160,10 +171,14 @@
// incorporates holidays. However, no holidays are set in this example
LinkedList holidays = new LinkedList();
GridResource gridRes = null;
+
+ ResourceCalendar resCalendar = new ResourceCalendar(time_zone,
+ peakLoad, offPeakLoad, holidayLoad, weekends,
+ holidays, seed);
+
try {
- gridRes = new GridResource(name, baud_rate, seed,
- resConfig, peakLoad, offPeakLoad, holidayLoad, weekends,
- holidays);
+ gridRes = new GridResource(name, baud_rate, resConfig,
+ resCalendar, policy);
}
catch (Exception e) {
e.printStackTrace();
Added: branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues02.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues02.java (rev 0)
+++ branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues02.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -0,0 +1,247 @@
+
+package examples.workload.parallel;
+
+import gridsim.GridResource;
+import gridsim.GridSim;
+import gridsim.Machine;
+import gridsim.MachineList;
+import gridsim.ResourceCalendar;
+import gridsim.turbo.MultipleEasyBackfillingQueues;
+import gridsim.turbo.QueuePredicate;
+import gridsim.turbo.SSGridlet;
+import gridsim.turbo.TResourceCharacteristics;
+import gridsim.util.Workload;
+
+import java.util.ArrayList;
+import java.util.Calendar;
+import java.util.LinkedList;
+import java.util.Random;
+
+
+/**
+ * Test Driver class for this example
+ */
+public class TurboExampleMultiEBQueues02
+{
+ /**
+ * Creates main() to run this example
+ */
+ public static void main(String[] args)
+ {
+ long startTime = System.currentTimeMillis();
+ if(args.length == 0){
+ System.out.println("Please provide the location of the workload file!");
+ System.exit(1);
+ }
+
+ try {
+
+ //////////////////////////////////////////
+ // Get the workload to be used The format should be:
+ // ASCII text, gzip or zip.
+
+ String fileName = args[0];
+ // /Users/marcosd/Documents/workspace/intergrid/workloads/sdsc_blue_2000_400.swf
+
+ ArrayList<GridResource> resources = new ArrayList<GridResource>();
+
+ //////////////////////////////////////////
+ // Initialize the GridSim package. It should be called
+ // before creating any entities. We can't run this example without
+ // initializing GridSim first. We will get run-time exception
+ // error.
+
+ // number of grid user entities + any Workload entities.
+ int num_user = 1;
+ Calendar calendar = Calendar.getInstance();
+ boolean trace_flag = false; // mean trace GridSim events
+
+ // Initialize the GridSim package without any statistical
+ // functionalities. Hence, no GridSim_stat.txt file is created.
+ System.out.println("Initializing GridSim package");
+ GridSim.init(num_user, calendar, trace_flag);
+
+ //////////////////////////////////////////
+ // Creates one or more GridResource entities
+ int totalResource = 1; // total number of Grid resources
+ int rating = 377; // rating of each PE in MIPS
+ int totalPE = 9; // total number of PEs for each Machine
+ int totalMachine = 128; // total number of Machines
+ int i = 0;
+
+ String[] resArray = new String[totalResource];
+ for (i = 0; i < totalResource; i++) {
+ String resName = "Res_" + i;
+ GridResource resource = createGridResource(resName, rating, totalMachine, totalPE);
+ resources.add(resource);
+
+ // add a resource name into an array
+ resArray[i] = resName;
+ }
+
+ //////////////////////////////////////////
+ // Creates one Workload trace entity.
+
+ int resID = 0;
+ Random r = new Random();
+ resID = r.nextInt(totalResource);
+ Workload workload = new Workload("Load_1", fileName, resArray[resID], rating);
+
+ //////////////////////////////////////////
+ // Starts the simulation in debug mode
+ GridSim.startGridSimulation(true);
+
+ // Start the simulation in normal mode
+// GridSim.startGridSimulation();
+
+ //////////////////////////////////////////
+ // Final step: Prints the Gridlets when simulation is over
+ long finishTime = System.currentTimeMillis();
+ System.out.println("The simulation took " + (finishTime - startTime) + " milliseconds");
+
+ // prints the Gridlets inside a Workload entity
+ // workload.printGridletList(trace_flag);
+ }
+ catch (Exception e) {
+ e.printStackTrace();
+ }
+ }
+
+ /**
+ * Creates one Grid resource. A Grid resource contains one or more
+ * Machines. Similarly, a Machine contains one or more PEs (Processing
+ * Elements or CPUs).
+ * @param name a Grid Resource name
+ * @param peRating rating of each PE
+ * @param totalMachine total number of Machines
+ * @param totalPE total number of PEs for each Machine
+ */
+ private static GridResource createGridResource(String name, int peRating,
+ int totalMachine, int totalPE)
+ {
+
+ //////////////////////////////////////////
+ // Here are the steps needed to create a Grid resource:
+ // 1. We need to create an object of MachineList to store one or more
+ // Machines
+ MachineList mList = new MachineList();
+
+ for (int i = 0; i < totalMachine; i++)
+ {
+ //////////////////////////////////////////
+ // 4. Create one Machine with its id and list of PEs or CPUs
+ mList.add( new Machine(i, totalPE, peRating) );
+ }
+
+ //////////////////////////////////////////
+ // 5. Create a ResourceCharacteristics object that stores the
+ // properties of a Grid resource: architecture, OS, list of
+ // Machines, allocation policy: time- or space-shared, time zone
+ // and its price (G$/PE time unit).
+ String arch = "Sun Ultra"; // system architecture
+ String os = "Solaris"; // operating system
+ double time_zone = 0.0; // time zone this resource located
+ double cost = 3.0; // the cost of using this resource
+
+ // this resource will use an aggressive backfilling policy (EASY)
+ TResourceCharacteristics resConfig = new TResourceCharacteristics(
+ arch, os, mList, TResourceCharacteristics.EB_PARALLEL_SPACE_SHARED,
+ time_zone, cost);
+
+ MultipleEasyBackfillingQueues policy = null;
+ try {
+ policy = new MultipleEasyBackfillingQueues(name, "Policy", 2);
+ } catch (Exception e1) {
+ e1.printStackTrace();
+ }
+
+ // creates two partitions, one for small jobs and another for long jobs
+ // assign the same number of PEs to both
+ QueuePredicateExample pred1 = new QueuePredicateExample(0, 10000, peRating);
+ QueuePredicateExample pred2 = new QueuePredicateExample(10000, Integer.MAX_VALUE, peRating);
+
+ policy.createQueue(0, resConfig.getNumPE() / 2, pred1);
+ policy.createQueue(1, resConfig.getNumPE() / 2, pred2);
+
+ //////////////////////////////////////////
+ // 6. Finally, we need to create a GridResource object.
+ double baud_rate = 10000.0; // communication speed
+ long seed = 11L*13*17*19*23+1;
+ double peakLoad = 0.0; // the resource load during peak hour
+ double offPeakLoad = 0.0; // the resource load during off-peak hr
+ double holidayLoad = 0.0; // the resource load during holiday
+
+ // incorporates weekends so the grid resource is on 7 days a week
+ LinkedList weekends = new LinkedList();
+ weekends.add(new Integer(Calendar.SATURDAY));
+ weekends.add(new Integer(Calendar.SUNDAY));
+
+ // incorporates holidays. However, no holidays are set in this example
+ LinkedList holidays = new LinkedList();
+ GridResource gridRes = null;
+
+ ResourceCalendar resCalendar = new ResourceCalendar(time_zone,
+ peakLoad, offPeakLoad, holidayLoad, weekends,
+ holidays, seed);
+
+ try {
+ gridRes = new GridResource(name, baud_rate, resConfig,
+ resCalendar, policy);
+ }
+ catch (Exception e) {
+ e.printStackTrace();
+ }
+
+ System.out.println("Creates one Grid resource with name = " + name);
+ return gridRes;
+ }
+} // end class
+
+class QueuePredicateExample implements QueuePredicate {
+ int minRuntime_;
+ int maxRuntime_;
+ int resRating_;
+
+ /*
+ * Default constructor
+ */
+ public QueuePredicateExample(int minRuntime,
+ int maxRuntime, int rating) {
+ this.minRuntime_ = minRuntime;
+ this.maxRuntime_ = maxRuntime;
+ this.resRating_ = rating;
+ }
+
+ /*
+ * (non-Javadoc)
+ * @see gridsim.turbo.QueuePredicate#match(gridsim.turbo.SSGridlet)
+ */
+ public boolean match(SSGridlet gridlet) {
+ double runtime = forecastExecutionTime(gridlet);
+ if(runtime < minRuntime_ || runtime >= maxRuntime_)
+ return false;
+
+ return true;
+ }
+
+ /*
+ * Forecast execution time of a Gridlet.
+ * <tt>execution time = length / available rating</tt>
+ * @param gridlet the gridlet to be considered
+ * @return Gridlet's execution time.
+ */
+ private double forecastExecutionTime(SSGridlet gridlet) {
+ double executionTime = (gridlet.getLength() / resRating_);
+
+ // This is as a safeguard since the finish time can be extremely
+ // small close to 0.0, such as 4.5474735088646414E-14. Hence causing
+ // some Gridlets never to be finished and consequently hang the program
+ if (executionTime < 1.0) {
+ executionTime = 1.0;
+ }
+ return executionTime;
+ }
+}
+
+
+
Modified: branches/gridsim4.0-branch3/source/gridsim/GridResource.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/GridResource.java 2008-02-12 05:46:26 UTC (rev 101)
+++ branches/gridsim4.0-branch3/source/gridsim/GridResource.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -14,7 +14,6 @@
import gridsim.turbo.EBParallelSpaceShared;
import gridsim.turbo.CBParallelSpaceShared;
import gridsim.turbo.MultipleEasyBackfillingQueues;
-import gridsim.turbo.TAllocPolicy;
import gridsim.turbo.TResourceCharacteristics;
import gridsim.index.*;
@@ -646,10 +645,11 @@
case TResourceCharacteristics.AR_PARALLEL_SPACE_SHARED:
policy_ = new ARParallelSpaceShared(super.get_name(), "ARParallelSpaceShared");
break;
-
+
+ // creates the scheduler with only one queue
case TResourceCharacteristics.MULTIPLE_EASY_BACKFILLING_QUEUES:
policy_ = new MultipleEasyBackfillingQueues(super.get_name(),
- "MultipleEasyBackfillingQueues");
+ "MultipleEasyBackfillingQueues", 1);
break;
default:
Modified: branches/gridsim4.0-branch3/source/gridsim/gui/ResourceWindow.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/gui/ResourceWindow.java 2008-02-12 05:46:26 UTC (rev 101)
+++ branches/gridsim4.0-branch3/source/gridsim/gui/ResourceWindow.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -694,7 +694,7 @@
for(int i=0; i<size; i++) {
ScheduleItem item = (ScheduleItem)scheduledItems_.get(i);
- if(item == null)
+ if(item == null || item.getStartTime() < 0)
continue;
int itemId = item.getID();
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java 2008-02-12 05:46:26 UTC (rev 101)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -70,19 +70,25 @@
* entries whose date is smaller or equals to refTime will
* be removed.
* @param refTime the reference time to be used for entry removal.
+ * @return the last entry removed or <tt>null</tt> if no entry
+ * has been removed.
*/
- public void removePastEntries(double refTime) {
+ public AvailabilityProfileEntry removePastEntries(double refTime) {
+ AvailabilityProfileEntry lastRemoved = null;
// Update the availability profile
Iterator<AvailabilityProfileEntry> iterProfile = super.iterator();
while(iterProfile.hasNext()) {
AvailabilityProfileEntry entry = iterProfile.next();
if(entry.getTime() <= refTime){
+ lastRemoved = entry;
iterProfile.remove();
}
else{
break;
}
}
+
+ return lastRemoved;
}
/**
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-02-12 05:46:26 UTC (rev 101)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -239,7 +239,7 @@
// If there are no jobs in the queue list, then check if
// there are enough PEs to process the job immediately
boolean success = false;
- int freePE = super.resource_.getNumFreePE();
+ int freePE = resource_.getNumFreePE();
if( reqPE <= freePE ){
success = startGridlet(sgl);
@@ -908,7 +908,6 @@
break;
}
else {
- // Sep. 29, 2007 - Changed by Marcos
// if the finish time is equals to the entry time, so there
// is no need to check the intersection
if(entryTime < finishTime) {
@@ -1116,7 +1115,7 @@
* start time or the place where the new anchor (if needed) will be placed
* @param tailIndex the index of the entry closest to the finish time but
* whose time is smaller or equals to the finish time
- * @param selected the lsit of PE ranges selected
+ * @param selected the list of PE ranges selected
* @param startTime the start time of the Gridlet
* @param finishTime the finish time of the Gridlet
*/
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-02-12 05:46:26 UTC (rev 101)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -37,8 +37,7 @@
* with Backfilling. IEEE Transactions on Parallel and Distributed
* Systems, 12:(6), pp. 529-543, 2001.
* </ul>
- *
- * This policy maintains an availability profile. The availability
+ * <br> This policy maintains an availability profile. The availability
* profile contains information about the ranges of processing elements
* (PEs) that will be released when the running jobs complete.
* In addition, the policy maintains the list of extra nodes, that is, the nodes
@@ -54,9 +53,7 @@
* simulate this, you have to model the local load as gridlets.
* It is more precise and faster. To do so, please check
* {@link Lublin99Workload}.
- * <li> Gridlets cannot be paused nor migrated. This could be
- * easily done, but due to time constraints, I could not
- * implement these features.
+ * <li> Gridlets cannot be paused nor migrated.
* </ul>
*
* @author Marcos Dias de Assuncao
@@ -71,10 +68,12 @@
*/
public class EBParallelSpaceShared extends TAllocPolicy {
-
// Queue of waiting Gridlets
protected LinkedList<SSGridlet> queuedGridlets_;
+ // Pivot job (i.e. the first job in the queue)
+ private SSGridlet pivot_;
+
// Queue of running Gridlets
protected LinkedList<SSGridlet> runningGridlets_;
@@ -97,9 +96,6 @@
// queue is scheduled
private PERangeList extraPEs_;
- // used only to set the extraPEs_ back to the default value
- private PERangeList allPEs_;
-
// a tag to indicate that a gridlet has finished
private static final int UPDATE_SCHEDULE_TAG = 10;
@@ -133,7 +129,9 @@
availProfile_ = new AvailabilityProfile();
lastScheduleUpdate_ = 0.0D;
shadowTime_ = Double.MAX_VALUE;
+ extraPEs_ = null;
ratingPE_ = 0;
+ pivot_ = null;
}
/**
@@ -148,10 +146,6 @@
// of one PE assuming that the machines are homogeneous
ratingPE_ = resource_.getMIPSRatingOfOnePE();
- // the extra PEs to start are the same that are free
- extraPEs_ = resource_.getFreePERanges().clone();
- allPEs_ = extraPEs_.clone();
-
// a loop that is looking for internal events only
Sim_event ev = new Sim_event();
while ( Sim_system.running() ) {
@@ -180,10 +174,8 @@
availProfile_.clear();
lastScheduleUpdate_ = 0.0D;
shadowTime_ = Double.MAX_VALUE;
- ratingPE_ = 0;
+ extraPEs_ = null;
resource_.resetFreePERanges();
- extraPEs_ = resource_.getFreePERanges().clone();
- allPEs_ = extraPEs_.clone();
}
/**
@@ -233,21 +225,13 @@
if( reqPE <= freePE ) {
success = startGridlet(sgl);
-
- //------------------ FOR DEBUGGING PURPOSES ONLY ----------------
-
- // Notifies the listeners that a Gridlet has been either scheduled
- // to run immediately or put in the waiting queue
- GridSim.notifyListeners(this.get_id(),
- AllocationAction.ITEM_SCHEDULED, true, sgl);
-
- //---------------------------------------------------------------
}
// if the job could not be scheduled immediately, then
// it has to be put in the waiting queue
if(!success) {
- enqueueGridlet(sgl);
+ scheduleGridlet(sgl);
+ queuedGridlets_.add(sgl);
}
// sends back an ack if required
@@ -396,8 +380,7 @@
private boolean startGridlet(SSGridlet sgl) {
int reqPE = sgl.getNumPE();
- if(resource_.getFreePERanges() == null ||
- resource_.getFreePERanges().getNumPE() < reqPE) {
+ if(resource_.getNumFreePE() < reqPE) {
return false;
}
@@ -419,72 +402,23 @@
// time is equals to the gridlet's or advance reservation's finish time
int tailIndex = -1;
- // if there are no jobs in the queue or in execution
- if(availProfile_.size() == 0 && shadowTime_ == Double.MAX_VALUE) {
- selected = super.selectPERangeList(reqPE, resource_.getFreePERanges());
- }
- else {
- // a pointer to the last entry analysed
- AvailabilityProfileEntry tailEntry = null;
-
- // the list of selected ranges
- PERangeList intersectList = null;
-
- // For immediate gridlets the start point
- // is the current list of PEs available
- intersectList = resource_.getFreePERanges().clone();
-
- // scan the availability profile until the expected termination
- // of the Gridlet to check whether enough PEs will be available
- // for the Gridlet. Stop the search if not enough PEs are available
- for(AvailabilityProfileEntry entry : availProfile_) {
- double entryTime = entry.getTime();
- if(entryTime < currentTime) {
- continue;
- }
- else if(entryTime > finishTime) {
- break;
- }
- else {
- tailEntry = entry;
- // if the finish time is equals to the entry time, so there
- // is no need to check the intersection
- if(entryTime < finishTime) {
- PERangeList listEntry = entry.getPERanges();
- intersectList = PERangeList.intersection(listEntry, intersectList);
- if(intersectList == null || intersectList.getNumPE() < reqPE)
- break;
- }
- }
- tailIndex = availProfile_.indexOf(tailEntry);
- }
+ PERangeList intersect = resource_.getFreePERanges();
+
+ if(finishTime > shadowTime_)
+ intersect = PERangeList.intersection(intersect, extraPEs_);
+
+ selected = super.selectPERangeList(reqPE, intersect);
+ if(selected == null || selected.getNumPE() < reqPE)
+ return false;
- // return false if the number of PEs available over the required
- // time interval is smaller than what the Gridlet requires
- if(intersectList == null || intersectList.getNumPE() < reqPE) {
- return false;
- }
- else {
- // the job has to finish before the shadow time or has
- // to use less PEs than the extra nodes
- if(finishTime < shadowTime_) {
- selected = super.selectPERangeList(reqPE, intersectList);
- }
- else {
- intersectList = PERangeList.intersection(intersectList, extraPEs_);
- if(intersectList == null || intersectList.getNumPE() < reqPE) {
- return false;
- }
- else {
- selected = super.selectPERangeList(reqPE, intersectList);
- extraPEs_ = PERangeList.difference(extraPEs_, selected);
- }
- }
- }
- }
+ // a pointer to the last entry analysed
+ AvailabilityProfileEntry tailEntry =
+ availProfile_.getPrecedingEntry(finishTime);
+
+ tailIndex = tailEntry == null ? -1 : availProfile_.indexOf(tailEntry);
// allocate the ranges of PEs to the gridlet
- allocatePERanges(tailIndex, selected, currentTime, finishTime);
+ allocatePERanges(tailIndex, selected, finishTime);
// add this Gridlet into execution list
runningGridlets_.add(sgl);
@@ -500,29 +434,36 @@
// then send this event to itself to update the queues after
// this gridlet's completion time
super.sendInternalEvent(executionTime, UPDATE_SCHEDULE_TAG);
+
+ //------------------ FOR DEBUGGING PURPOSES ONLY ----------------
+
+ // Notifies the listeners that a Gridlet has been either scheduled
+ // to run immediately or put in the waiting queue
+ GridSim.notifyListeners(this.get_id(),
+ AllocationAction.ITEM_SCHEDULED, true, sgl);
+
+ //---------------------------------------------------------------
+
return true;
}
/**
- * Enqueues a gridlet. That is, put the gridlet into the
- * queue of waiting gridlets. If the gridlet is the first into the queue,
- * then updates the extra nodes and the shadow time. The shadow time will
+ * Tries to schedule a gridlet. That is, make the gridlet the pivot,
+ * or the first gridlet in the queue. If that is not possible, then return
+ * false. If the gridlet is the first into the queue, then updates the
+ * pivot, extra nodes and the shadow time. The shadow time will
* be the start time of the gridlet whereas the extra PEs will be the
* PEs left unused when the gridlet starts execution.
* @param sgl the resource gridlet
+ * @return <tt>true</tt> if scheduled; <tt>false</tt> otherwise.
*/
- private void enqueueGridlet(SSGridlet sgl) {
+ private boolean scheduleGridlet(SSGridlet sgl) {
int reqPE = sgl.getNumPE();
// if there are gridlets waiting execution already, then simply
// insert this gridlet into the queue and return
- if(queuedGridlets_.size() > 0) {
- queuedGridlets_.add(sgl);
- return;
- }
-
- // otherwise, just add the gridlet in the queue and continue
- queuedGridlets_.add(sgl);
+ if(pivot_ != null)
+ return false;
// calculate the execution time of the Gridlet
double executionTime =
@@ -553,6 +494,7 @@
sgl.setStatus(Gridlet.QUEUED);
sgl.setStartTime(startTime);
sgl.setFinishTime(finishTime);
+ pivot_ = sgl;
//------------------ FOR DEBUGGING PURPOSES ONLY ----------------
@@ -561,6 +503,8 @@
GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_SCHEDULED, true, sgl);
//---------------------------------------------------------------
+
+ return true;
}
/**
@@ -568,13 +512,13 @@
* availability profile accordingly
* @param tailIndex the index of the entry closest to the finish time but
* whose time is smaller or equals to the finish time
- * @param selected the list of PE ranges selected
- * @param startTime the start time of the Gridlet
+ * @param selected the list of PE ranges selected
* @param finishTime the finish time of the Gridlet
*/
private void allocatePERanges(int tailIndex,
- PERangeList selected, double startTime, double finishTime) {
+ PERangeList selected, double finishTime) {
+ double startTime = GridSim.clock();
AvailabilityProfileEntry newEntryAfterTail = null;
// if the time of the entry at (tailIndex) is equals to
@@ -616,7 +560,7 @@
// Update entries of the profile
for(int index=0; index<=updTo; index++) {
AvailabilityProfileEntry entry = availProfile_.get(index);
- if(entry.getTime() < startTime){
+ if(entry.getTime() < startTime) {
continue;
}
PERangeList uptList =
@@ -630,6 +574,10 @@
// subtract the selected ranges from the currently free ranges
resource_.setPEsBusy(selected);
+
+ if(finishTime > shadowTime_)
+ extraPEs_ = PERangeList.difference(extraPEs_, selected);
+
}
/**
@@ -642,102 +590,41 @@
* array[1] the list of PE ranges available at that time<br>
*/
private Object[] findStartTime(int reqPE, double duration) {
-
- // the anchor index, the entry in the profile where
- // the gridlet will be placed OR the closest entry to the
- // point where the anchor of the advance reservation will be placed
- int anchorIndex = -1;
-
- // a pointer to the anchor entry (described above)
- AvailabilityProfileEntry anchorEntry = null;
-
- // the list of selected ranges
- PERangeList intersectList = null;
-
- double potStartTime = -1; // keep the potential start time of the gridlet
- double potFinishTime = -1; // store the gridlet's expected finish time
-
- intersectList = null;
- int length = availProfile_.size();
+ PERangeList availRanges = null; // list of ranges available for the job
+ double startTime = -1; // the job's potential start time
Iterator<AvailabilityProfileEntry> iterProfile = availProfile_.iterator();
while(iterProfile.hasNext()) {
-
- AvailabilityProfileEntry entry = iterProfile.next();
+ AvailabilityProfileEntry entry = iterProfile.next();
// scan the profile until an entry with enough PEs is found
if(entry.getNumPE() < reqPE) {
continue;
}
else {
-
- anchorEntry = entry;
- anchorIndex = availProfile_.indexOf(anchorEntry);
-
- // sets the start time as the time of the entry
- potStartTime = entry.getTime();
- // calculates when the finish time will be if
- // the gridlet is put at this position
- potFinishTime = potStartTime + duration;
-
- // if an entry with enough PEs is found, then scan the profile
- // from that point onwards analysing the intersection of
- // the ranges available in the entries until the
- // gridlet expected completion time
- intersectList = entry.getPERanges().clone();
-
- // Look for the intersection of available ranges from
- // the anchor until the end of the profile or until
- // the entries are further than the expected completion time
- for(int i=anchorIndex+1; i<length; i++){
- AvailabilityProfileEntry nextEntry = availProfile_.get(i);
- if(nextEntry.getTime() > potFinishTime){
- break;
- }
- else {
- // if the finish time is equals to the entry time, so there
- // is no need to check the intersection
- if(nextEntry.getTime() < potFinishTime) {
- intersectList = PERangeList.intersection(intersectList,
- nextEntry.getPERanges());
- if(intersectList == null || intersectList.getNumPE() < reqPE) {
- break;
- }
- }
- }
- }
- // If a time slot with enough PEs has been found, then stop the search
- if(intersectList != null && intersectList.getNumPE() >= reqPE) {
- break;
- }
+ // sets the start time as the time of the entry
+ startTime = entry.getTime();
+ availRanges = entry.getPERanges().clone();
+ break;
}
}
// creates the array with the result
Object[] result = new Object[3];
- result[0] = new Double(anchorEntry.getTime());
- result[1] = intersectList;
+ result[0] = new Double(startTime);
+ result[1] = availRanges;
return result;
}
- /**
- * This method is called to update the schedule. It removes completed
- * gridlets and return them to the users and verifies whether the first gridlet
- * in the waiting queue can be started. If it cannot be started, them
- * tries to backfill with jobs waiting in the queue. The method also
- * removes old entries from the availability profile.
+ /**
+ * This method finalises the gridlets in execution whose time
+ * is smaller or equals to the current simulation time.
+ * @param currentTime the current simulation time
+ * @return the number of gridlets completed
*/
- private void updateSchedule(){
+ protected int finishRunningGridlets(double currentTime) {
+ int itemsFinished = 0;
- double currentTime = GridSim.clock();
- int gridletFinished = 0;
- int gridletStarted = 0;
-
- // removes all Gridlets that have already completed from
- // the queue of running Gridlets
- PERangeList releasedRanges = new PERangeList();
- LinkedList<SSGridlet> grlsCompleted = new LinkedList<SSGridlet>();
-
// iterates the list to check what has finished
Iterator<SSGridlet> iter = runningGridlets_.iterator();
while (iter.hasNext()) {
@@ -747,92 +634,86 @@
// is enough. There's no need to check status
if(gridlet.getFinishTime() <= currentTime) {
// Update the list of ranges released
- releasedRanges.addAll(gridlet.getPERangeList().clone());
- grlsCompleted.add(gridlet);
gridletFinish(gridlet, Gridlet.SUCCESS);
iter.remove();
- gridletFinished++;
- }
- }
+ itemsFinished++;
+ }
+ }
+ return itemsFinished;
+ }
+
+ /**
+ * This method is called to update the schedule. It removes completed
+ * gridlets and return them to the users and verifies whether the first gridlet
+ * in the waiting queue can be started. If it cannot be started, them
+ * tries to backfill with jobs waiting in the queue. The method also
+ * removes old entries from the availability profile.
+ */
+ private void updateSchedule() {
+ int itemsFinished = 0;
+ double currentTime = GridSim.clock();
+ int itemsStarted = 0;
- // returns ranges of PEs to the list of PEs available
- resource_.setPEsAvailable(releasedRanges);
+ itemsFinished = finishRunningGridlets(currentTime);
- // Updates the availability profile
- Iterator<AvailabilityProfileEntry> iterProfile = availProfile_.iterator();
- while(iterProfile.hasNext()) {
- AvailabilityProfileEntry entry = iterProfile.next();
- if(entry.getTime() <= currentTime){
- iterProfile.remove();
- }
+ // remove past entries from the availability profile
+ AvailabilityProfileEntry currentStatus = availProfile_.removePastEntries(currentTime);
+ if(currentStatus != null) {
+ resource_.resetFreePERanges(currentStatus.getPERanges());
}
+
+ itemsStarted = startQueuedGridlets(currentTime);
- // if at least a gridlet has finished, then we should iterate the
- // waiting queue. We need to try to start the first gridlet in the queue.
- // If it cannot be started, then we should backfill with the remaining
- // gridlets in the queue.
- if(gridletFinished > 0) {
- if(queuedGridlets_.size() > 0) {
-
- // This is a tricky approach. We decided to clone the waiting
- // queue, try to start the first job, and then enqueue all
- // jobs again, including the first job if it cannot be started
- LinkedList<SSGridlet> clonedQueue =
- (LinkedList<SSGridlet>)queuedGridlets_.clone();
- queuedGridlets_.clear();
-
- //TODO: To think a better way to do this. But the idea is to
- // try to start first job, then enqueue all the other jobs again.
- // If the first job cannot be started, then try to start the other
- // jobs (ie. backfill) or enqueue them again
- SSGridlet gridlet = clonedQueue.getFirst();
- clonedQueue.removeFirst();
-
- if(gridlet.getStartTime() <= currentTime) {
- // if the gridlet can be started, then the extra nodes
- // and the shadow time will be set back to the default values
- // and will be changed when the next gridlet in the waiting queue
- // is scheduled.
- extraPEs_ = allPEs_.clone();
- shadowTime_ = Double.MAX_VALUE;
- if (!startGridlet(gridlet)) {
- // NOTE that it should NOT happen,
- // but if it does, enqueue the job
- enqueueGridlet(gridlet);
- }
- }
- else {
- // if the first job cannot be started, then put it back into
- // the queue and backfill with other jobs. That is, try to
- // start the other jobs.
- queuedGridlets_.add(gridlet);
- iter = clonedQueue.iterator();
- while(iter.hasNext()) {
- gridlet = iter.next();
- if(startGridlet(gridlet))
- iter.remove();
- }
- }
-
- // Add the jobs still remaining back into the waiting queue
- iter = clonedQueue.iterator();
- while(iter.hasNext()) {
- gridlet = iter.next();
- enqueueGridlet(gridlet);
- }
- }
-
- //---------------- USED FOR DEBUGGING PURPOSES ONLY --------------------
+ //---------------- USED FOR DEBUGGING PURPOSES ONLY --------------------
- // If a gridlet has started execution or one has finished,
- // then inform the listeners
- if(gridletStarted > 0 || gridletFinished > 0){
- GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_COMPLETED,
- true, grlsCompleted);
- }
+ // If a gridlet has started execution or one has finished,
+ // then inform the listeners
+ if(itemsStarted > 0 || itemsFinished > 0) {
+ GridSim.notifyListeners(this.get_id(),
+ AllocationAction.SCHEDULE_CHANGED, true);
+ }
- //----------------------------------------------------------------------
+ //----------------------------------------------------------------------
+ }
+
+ /**
+ * This method starts gridlets that are in the queue and
+ * whose start time is smaller than the reference time and updates
+ * the availability accordingly
+ * @param currentTime the current simulation time
+ * @return the number of gridlets started
+ */
+ protected int startQueuedGridlets(double currentTime) {
+ int gridletStarted = 0;
+
+ // first checks the pivot first
+ if(pivot_ != null) {
+ if(pivot_.getStartTime() <= currentTime) {
+ shadowTime_ = Double.MAX_VALUE;
+ startGridlet(pivot_);
+ gridletStarted++;
+ queuedGridlets_.remove(pivot_);
+ pivot_ = null;
+ }
}
+
+ // Start the execution of Gridlets that are queued
+ Iterator<SSGridlet> iter = queuedGridlets_.iterator();
+ while (iter.hasNext()) {
+ SSGridlet gridlet = iter.next();
+ boolean success = startGridlet(gridlet);
+
+ // if the job could not be scheduled immediately, then enqueue it
+ if(success) {
+ iter.remove();
+ gridletStarted++;
+ }
+ else if (pivot_ == null) { // if there is not a pivot already
+ scheduleGridlet(gridlet);
+ }
+ }
+
+ return gridletStarted;
}
/**
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/MultipleEasyBackfillingQueues.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/MultipleEasyBackfillingQueues.java 2008-02-12 05:46:26 UTC (rev 101)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/MultipleEasyBackfillingQueues.java 2008-02-14 12:00:22 UTC (rev 102)
@@ -13,10 +13,12 @@
import gridsim.GridSim;
import gridsim.GridSimTags;
import gridsim.Gridlet;
+import gridsim.ParameterException;
import gridsim.gui.AllocationAction;
import java.util.ArrayList;
import java.util.Calendar;
+import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
@@ -37,17 +39,23 @@
public class MultipleEasyBackfillingQueues extends TAllocPolicy {
// Queue of running Gridlets
- protected LinkedList<SSGridlet> runningGridlets_;
+ protected LinkedList<MQGridlet> runningGridlets_;
+
+ // Queue of Gridlets waiting in this queue
+ protected LinkedList<MQGridlet> queuedGridlets_;
- // The queues used by this scheduler
- protected ArrayList<EasyBackfillingQueue> queues_;
-
// The rating of one PE
protected int ratingPE_;
// the resource characteristics object to be used
- protected TResourceCharacteristics resource_;
+ protected TResourceCharacteristics resource_;
+ // The availability profile
+ protected Profile profile_;
+
+ // the number of queues in this scheduler
+ private int numQueues_;
+
// the last time when the schedule updated was called
private double lastScheduleUpdate_;
@@ -56,13 +64,14 @@
// a constant that denotes an unknown value
private static final int UNKNOWN = -1;
-
+
/**
* Allocates a new <tt>EBParallelSpaceShared</tt> object
*
* @param resourceName the <tt>GridResource</tt> entity name that will
* contain this allocation policy
* @param entityName this object entity name
+ * @param numQueues The number of queues in the scheduler
* @throws Exception This happens when one of the following scenarios occur:
* <ul>
* <li> Creating this entity before initialising GridSim package
@@ -78,14 +87,30 @@
* String[], String[], String)
*/
public MultipleEasyBackfillingQueues(String resourceName,
- String entityName) throws Exception{
+ String entityName, int numQueues) throws Exception {
super(resourceName, entityName);
+ // makes sure that the scheduler has at least one queue
+ if(numQueues <= 0) {
+ throw new ParameterException("Number of queues" +
+ "should be larger than 1");
+ }
+
// initialises local data structure
- runningGridlets_ = new LinkedList<SSGridlet>();
+ runningGridlets_ = new LinkedList<MQGridlet>();
+ queuedGridlets_ = new LinkedList<MQGridlet>();
+ numQueues_ = numQueues;
+ profile_ = new Profile();
lastScheduleUpdate_ = 0.0D;
ratingPE_ = 0;
}
+
+
+ public boolean createQueue(int queueId, int numPE, QueuePredicate predicate) {
+ EasyBackFillingQueue queue = new EasyBackFillingQueue(queueId, numPE, predicate);
+ profile_.addQueue(queue);
+ return true;
+ }
/**
* Handles internal events that come to this entity.
@@ -99,6 +124,51 @@
// of one PE assuming that the machines are homogeneous
ratingPE_ = resource_.getMIPSRatingOfOnePE();
+ if(numQueues_ > 1 && profile_.getNumberOfQueues() != numQueues_) {
+ System.out.println(super.get_name() + ".body(): The scheduler" +
+ " is expected to have " + numQueues_ + " queues. However," +
+ " only " + profile_.getNumberOfQueues() + " have been defined");
+ return;
+ }
+
+ //TODO: To validate the processing elements assigned to the queues
+
+ // if the user has not specified the queues and the scheduler is
+ // expected to have only one queue, then creates the queue and
+ // includes it in the list.
+ if(profile_.getNumberOfQueues() == 0 && numQueues_ == 1) {
+ // creates the accept all predicate
+ QueuePredicate predicate = new QueuePredicate() {
+ public boolean match(SSGridlet gridlet) {
+ return true;
+ }
+ };
+
+ EasyBackFillingQueue queue =
+ new EasyBackFillingQueue(0, resource_.getNumPE(), predicate);
+ queue.idlePERanges_ = resource_.getFreePERanges().clone();
+ profile_.addQueue(queue);
+ }
+ // assigns the PEs to the queues
+ else {
+ int allocPE = 0;
+ PERangeList freeRanges = resource_.getFreePERanges().clone();
+ for(EasyBackFillingQueue queue : profile_.queues_.values()) {
+ allocPE += queue.initialNumPEs_;
+
+ if(allocPE > resource_.getNumPE()) {
+ System.out.println(super.get_name() + ".body(): The scheduler" +
+ " cannot allocate PEs to all queues because there are not" +
+ " anough PEs");
+ return;
+ }
+
+ PERangeList selected = super.selectPERangeList(queue.initialNumPEs_, freeRanges);
+ queue.idlePERanges_ = selected;
+ freeRanges = PERangeList.difference(freeRanges, selected);
+ }
+ }
+
// a loop that is looking for internal events only
Sim_event ev = new Sim_event();
while ( Sim_system.running() ) {
@@ -160,12 +230,63 @@
}
// Create a resource Gridlet
- SSGridlet sgl = new SSGridlet(gridlet);
+ MQGridlet sgl = new MQGridlet(gridlet);
//-------------- FOR DEBUGGING PURPOSES ONLY --------------
- GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_ARRIVED, true, sgl);
+ GridSim.notifyListeners(this.get_id(),
+ AllocationAction.ITEM_ARRIVED, true, sgl);
+
+ //----------------------------------------------------------
+
+ // the id of the queue where the job can be scheduled
+ int queueId = profile_.getCorrespondingQueue(sgl);
+
+ // if no queue can handle the gridlet, then reject it
+ if(queueId == UNKNOWN) {
+ String userName = GridSim.getEntityName( gridlet.getUserID() );
+ System.out.println(super.get_name() + ".gridletSubmit(): " +
+ " Gridlet #" + gridlet.getGridletID() + " from " +
+ userName + " cannot be handled by any queue in this resource.");
+ try {
+ gridlet.setGridletStatus(Gridlet.FAILED);
+ } catch (Exception ex) {
+ System.out.println(super.get_name() +
+ ": Exception on submission of a Gridlet");
+ }
+ super.sendFinishGridlet(gridlet);
+ return;
+ }
+
+ sgl.setQueueID(queueId);
+
+ // If there are no jobs in the queue list, then check if
+ // there are enough PEs to process the job immediately
+ boolean success = startGridlet(sgl);
+ // if the job could not be scheduled immediately, then enqueue it
+ if(!success) {
+ scheduleGridlet(sgl);
+ queuedGridlets_.add(sgl);
+ }
+
+// System.out.println("\nFree Ranges=" + profile_.getIdlePEsPerQueue());
+// System.out.println(profile_);
+
+ //------------------ FOR DEBUGGING PURPOSES ONLY ----------------
+
+ // Notifies the listeners that a Gridlet has been either scheduled
+ // to run immediately or put in the waiting queue
+ GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_SCHEDULED, true, sgl);
+
+ //---------------------------------------------------------------
+
+ // sends back an ack if required
+ if (ack == true) {
+ super.sendAck(GridSimTags.GRIDLET_SUBMIT_ACK, true,
+ gridlet.getGridletID(), gridlet.getUserID()
+ );
+ }
}
/**
@@ -239,8 +360,222 @@
}
// -------------------- PRIVATE METHODS ----------------------------
+
+ /**
+ *
+ */
+ private boolean startGridlet(MQGridlet sgl) {
+
+ int reqPE = sgl.getNumPE();
+ if(reqPE > resource_.getNumFreePE())
+ return false;
+
+ boolean success = false; // to test various conditions
+ int queueId = sgl.getQueueID();
+
+ // calculate the execution time of the Gridlet
+ double executionTime =
+ super.forecastExecutionTime(ratingPE_, sgl.getRemainingLength());
+ // calculates how much ahead to look into the availability profile
+ double currentTime = GridSim.clock() ;
+
+ // the Gridlet's expected finish time if it starts now
+ double finishTime = currentTime + executionTime;
+
+ PERangeList ranges =
+ profile_.getImmediateAvailability(queueId, executionTime);
+
+ // if the above method returns null, it means that there are not enough
+ // PEs to serve the reservation or Gridlet
+ if(ranges.getNumPE() >= reqPE) {
+ ranges = super.selectPERangeList(reqPE, ranges);
+ profile_.allocateImmediateRanges(queueId, finishTime, ranges);
+ success = true;
+ }
+
+ // If the queue to which the gridlet is assigned does not have the
+ // required PEs, then try to borrow the additional PEs from other queues.
+ if(!success) {
+ PERangeList overallAvailPEs =
+ profile_.getImmediateAvailability(executionTime);
+
+ // additional PEs required
+ int addRequired = reqPE - ranges.getNumPE();
+
+ PERangeList addRanges =
+ PERangeList.difference(overallAvailPEs, ranges);
+
+ if(addRanges != null && addRanges.getNumPE() >= addRequired) {
+ // subtracts the ranges already obtained from the gridlet's queue
+
+// System.out.println("\nRanges to Add to queue " + queueId +" = " +
+// addRanges + "\noverall = " + overallAvailPEs +
+// "\n overall num available = " + overallAvailPEs.getNumPE() +
+// "\n free PEs = " + resource_.getNumFreePE() +
+// "\n free PEs profile = " + profile_.getNumFreePEs() +
+// "\n PEs from the queue = " + ranges.getNumPE() +
+// "\n req PEs = " + reqPE);
+
+ // borrows the ranges from the queues and adds it into the
+ // specified queue
+ addRanges = super.selectPERangeList(addRequired, addRanges);
+ profile_.transferPEs(queueId, addRanges, currentTime, finishTime);
+
+ // allocate the ranges to the job
+ ranges.addAll(addRanges);
+ profile_.allocateImmediateRanges(queueId, finishTime, ranges);
+ success = true;
+ }
+ }
+
+ if(!success)
+ return false;
+
+ // sets the PEs to busy at resource class. This is just to provide
+ // information to other classes that may query it
+ resource_.setPEsBusy(ranges);
+
+ // add this Gridlet into execution list
+ runningGridlets_.add(sgl);
+ sgl.setStartTime(currentTime);
+ sgl.setFinishTime(finishTime);
+
+ // change Gridlet status
+ sgl.setStatus(Gridlet.INEXEC);
+
+ // Sets the list of ranges used by the gridlet
+ sgl.setPERangeList(ranges);
+
+ // then send this event to itself to update the queues after
+ // this gridlet's completion time
+ super.sendInternalEvent(executionTime, UPDATE_SCHEDULE_TAG);
+
+ //------------------ FOR DEBUGGING PURPOSES ONLY ----------------
+
+ // Notifies the listeners that a Gridlet has been either scheduled
+ // to run immediately or put in the waiting queue
+ GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_SCHEDULED, true, sgl);
+
+ //---------------------------------------------------------------
+ return true;
+ }
+
/**
+ * @param sgl the resource gridlet
+ */
+ private boolean scheduleGridlet(MQGridlet sgl) {
+ int reqPE = sgl.getNumPE();
+ int queueId = sgl.getQueueID();
+
+ EasyBackFillingQueue queue = profile_.getQueue(queueId);
+
+ // if queue has a pivot already, then just add
+ // the job to the waiting queue
+ if(queue.pivot_ != null) {
+ return false;
+ }
+
+ PERangeList ranges = null;
+
+ // calculate the execution time of the Gridlet
+ double executionTime =
+ super.forecastExecutionTime(ratingPE_, sgl.getRemainingLength());
+
+ double startTime = -1; // keep the potential start time of the gridlet
+ double finishTime = -1; // store the gridlet's expected finish time
+
+ // check whether there are PEs available over the time interval requested
+ Object[] availObjQueue =
+ profile_.checkPERangesAvailability(queueId, reqPE, executionTime);
+
+ Object[] availObj =
+ profile_.checkPERangesAvailability(reqPE, executionTime);
+
+ int anchor;
+ double startTimeQueue;
+ if (availObjQueue == null)
+ startTimeQueue = Double.MAX_VALUE;
+ else {
+ anchor = (Integer)availObjQueue[0];
+ startTimeQueue=profile_.get(anchor).getTime();
+ }
+
+// System.out.println(profile_);
+
+ anchor = (Integer)availObj[0];
+ double startTimeAll = profile_.get(anchor).getTime();
+
+ if(startTimeQueue <= startTimeAll) {
+ ranges = (PERangeList)availObjQueue[2];
+ ranges = super.selectPERangeList(reqPE, ranges);
+
+ int anchorIndex = (Integer)availObjQueue[0];
+ int tailIndex = (Integer)availObjQueue[1];
+
+ startTime = startTimeQueue;
+ finishTime = startTime + executionTime;
+
+ profile_.allocatePERanges(queueId, anchorIndex, tailIndex,
+ ranges, startTime, finishTime);
+ }
+ // If the queue to which the gridlet is assigned does not have the
+ // required PEs, then try to borrow the additional PEs from other queues.
+ else {
+ PERangeList addRanges = (PERangeList)availObj[2];
+
+ // the anchor index, the entry in the profile where the gridlet will be placed
+ int anchorIndex = (Integer)availObj[0];
+ // insert index represents the position after which the entry
+ // corresponding to the gridlet's finish time will be placed
+ int tailIndex = (Integer)availObj[1];
+
+ // a pointer to the anchor entry
+ startTime = startTimeAll;
+ finishTime = startTime + executionTime;
+
+ availObjQueue = profile_.checkPERangesAvailability(queueId,
+ startTime, executionTime);
+
+ ranges = availObjQueue == null ? new PERangeList() : (PERangeList)availObjQueue[2];
+ addRanges = availObjQueue == null ? addRanges : PERangeList.difference(addRanges, ranges);
+ addRanges = super.selectPERangeList(reqPE - ranges.getNumPE(), addRanges);
+
+// System.out.println("\nRanges to transfer to queue " + queueId +" = " +
+// addRanges + " from " + startTime + " to " + finishTime);
+
+ // borrows the ranges from the queues and adds it into the
+ // specified queue
+ profile_.transferPEs(queueId, addRanges, startTime, finishTime);
+
+ // finally allocate the ranges to the gridlet
+ ranges.addAll(addRanges);
+ profile_.allocatePERanges(queueId, anchorIndex, tailIndex,
+ ranges, startTime, finishTime);
+ }
+
+ queue.pivot_ = sgl;
+
+ // Set the list of ranges used by the gridlet
+ sgl.setPERangeList(ranges);
+
+ // change Gridlet status
+ sgl.setStatus(Gridlet.QUEUED);
+ sgl.setStartTime(startTime);
+ sgl.setFinishTime(finishTime);
+
+ //------------------ FOR DEBUGGING PURPOSES ONLY ----------------
+
+ // Notifies the listeners that a Gridlet has been either scheduled
+ // to run immediately or put in the waiting queue
+ GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_SCHEDULED, true, sgl);
+
+ //---------------------------------------------------------------
+
+ return true;
+ }
+
+ /**
* Process and event sent to this entity
* @param ev the event to be handled
*/
@@ -273,39 +608,109 @@
* tries to backfill with jobs waiting in the queue. The method also
* removes old entries from the availability profile.
*/
- private void updateSchedule(){
-
+ private void updateSchedule() {
- }
+ int itemsFinished = 0;
+ double currentTime = GridSim.clock();
+ int itemsStarted = 0;
- static class EasyBackfillingQueue {
+ itemsFinished = finishRunningGridlets(currentTime);
- int queueId_ = UNKNOWN;
+ // remove past entries from the availability profile
+ ProfileEntry currentStatus = profile_.removePastEntries(currentTime);
+ if(currentStatus != null) {
+ profile_.setCurrentStatus(currentStatus);
+ resource_.resetFreePERanges(currentStatus.getPERanges());
+ }
- // initial number of PEs assigned to this queue
- int initialNumPE_ = 0;
-
- // Queue of Gridlets waiting in this queue
- LinkedList<SSGridlet> queuedGridlets_;
-
- // the time when the first job in the waiting queue can
- // start its execution
- double shadowTime_ = ...
[truncated message content] |
