Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [169] branches/gridsim4.0-branch3/source/gridsim
|
From: <mar...@us...> - 2008-04-11 00:58:19
|
Revision: 169
http://gridsim.svn.sourceforge.net/gridsim/?rev=169&view=rev
Author: marcos_dias
Date: 2008-04-10 17:58:22 -0700 (Thu, 10 Apr 2008)
Log Message:
-----------
Changes in the easy backfilling policy when it uses only one pivot. If we avoid creating a list of pivots the simulations are around 30% faster.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/GridResource.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/PERange.java
branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java
branches/gridsim4.0-branch3/source/gridsim/turbo/TResourceCharacteristics.java
Added Paths:
-----------
branches/gridsim4.0-branch3/source/gridsim/turbo/MAUIEBParallelSpaceShared.java
Modified: branches/gridsim4.0-branch3/source/gridsim/GridResource.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/GridResource.java 2008-04-09 01:48:26 UTC (rev 168)
+++ branches/gridsim4.0-branch3/source/gridsim/GridResource.java 2008-04-11 00:58:22 UTC (rev 169)
@@ -17,6 +17,7 @@
import gridsim.turbo.EBParallelSpaceShared;
import gridsim.turbo.CBParallelSpaceShared;
import gridsim.turbo.EBMultiplePartitions;
+import gridsim.turbo.MAUIEBParallelSpaceShared;
import gridsim.turbo.TResourceCharacteristics;
import gridsim.index.*;
@@ -643,6 +644,10 @@
policy_ = new EBParallelSpaceShared(super.get_name(), "EBParallelSpaceShared");
break;
+ case TResourceCharacteristics.MAUI_EB_PARALLEL_SPACE_SHARED:
+ policy_ = new MAUIEBParallelSpaceShared(super.get_name(), "MAUIEBParallelSpaceShared");
+ break;
+
case TResourceCharacteristics.AR_PARALLEL_SPACE_SHARED:
policy_ = new ARParallelSpaceShared(super.get_name(), "ARParallelSpaceShared");
break;
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-04-09 01:48:26 UTC (rev 168)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-04-11 00:58:22 UTC (rev 169)
@@ -1056,7 +1056,6 @@
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();
Iterator<AvailabilityProfileEntry> iterProfile = availProfile_.iterator();
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-04-09 01:48:26 UTC (rev 168)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-04-11 00:58:22 UTC (rev 169)
@@ -11,26 +11,19 @@
import gridsim.GridSim;
import gridsim.GridSimTags;
import gridsim.Gridlet;
-import gridsim.ParameterException;
import gridsim.gui.AllocationAction;
import java.util.Calendar;
import java.util.Collections;
import java.util.Iterator;
-import java.util.LinkedList;
/**
* <tt>EBParallelSpaceShared</tt> class is an allocation policy for
* <tt>GridResource</tt> that implements aggressive backfilling (EASY).
* The policy is based the aggressive backfilling algorithm described in the
- * following papers:
+ * following paper:
* <p>
* <ul>
- * <li> David B. Jackson, Quinn Snell and Mark J. Clement. Core Algorithms
- * of the Maui Scheduler, Revised Papers from the 7th International
- * Workshop on Job Scheduling Strategies for Parallel Processing
- * (JSSPP '01), Lecture Notes in Computer Science, pp. 87-102, London, UK.
- *
* <li>Ahuva W. Mu'alem and Dror G. Feitelson, Utilization, Predictability,
* Workloads, and User Runtime Estimates in Scheduling the IBM SP2
* with Backfilling. IEEE Transactions on Parallel and Distributed
@@ -38,14 +31,7 @@
* </ul>
* <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. The aggressive
- * backfilling implemented here is similar to that used by the MAUI scheduler.
- * That is, you can set the max number of pivot jobs will be considered during
- * backfilling. A job will be used to backfill if it does not delay the first
- * 'max number of pivots' in the queue. By default, only one pivot job is
- * used. You can set that by invoking {@link #setMaximumNumberOfPivots(int)}.
- * This scheduler will behave like conservative backfilling when the number
- * of pivots is very large.
+ * (PEs) that will be released when the running jobs complete.
* <p>
* <b>LIMITATIONS:</b><br>
* <ul>
@@ -71,15 +57,15 @@
public class EBParallelSpaceShared extends CBParallelSpaceShared {
- // Pivot jobs (i.e. the first n jobs in the queue)
- protected LinkedList<SSGridlet> pivotGridlets_;
+ // Pivot job (i.e. the first job in the queue)
+ protected SSGridlet pivot_;
- // Similarly to the aggressive backfilling in MAUI, the user
- // can specify how many pivots can be considered when scheduling a job.
- // That is, a job can be used to backfill if it does not delay the
- // first maxPivots_ jobs in the waiting queue. If this parameter is
- // very large, the policy will behave like conservative backfilling
- private int maxPivots_;
+ // the time when the first job in the waiting queue can start execution
+ private double shadowTime_;
+
+ // the list of PEs left unused when the first job in the waiting
+ // queue is scheduled
+ private PERangeList extraPEs_;
/**
* Allocates a new <tt>EBParallelSpaceShared</tt> object
@@ -105,68 +91,20 @@
String entityName) throws Exception{
super(resourceName, entityName);
// initialises local variables
- pivotGridlets_ = new LinkedList<SSGridlet>();
- maxPivots_ = 1; // default number of pivots is one
+ shadowTime_ = Double.MAX_VALUE;
+ extraPEs_ = null;
+ pivot_ = null;
}
/**
- * 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 maxNumPivots the maximum number of pivots used by this scheduler
- * @throws Exception This happens when one of the following scenarios occur:
- * <ul>
- * <li> Creating this entity before initialising GridSim package
- * <li> The entity name is <tt>null</tt> or empty
- * <li> The entity has <tt>zero</tt> number of PEs (Processing
- * Elements). <br>
- * No PEs, which means that the Gridlets cannot be processed.
- * A GridResource must contain one or more Machines.
- * A Machine must contain one or more PEs.
- * <li> The maximum number of pivots is <= 0.
- * </ul>
- *
- * @see gridsim.GridSim#init(int, Calendar, boolean,
- * String[], String[], String)
- */
- public EBParallelSpaceShared(String resourceName, String entityName,
- int maxNumPivots) throws Exception{
- this(resourceName, entityName);
- if(!setMaximumNumberOfPivots(maxNumPivots)) {
- throw new ParameterException("Maximum number of pivots should be > 0.");
- }
- }
-
- /**
* Handles internal events that come to this entity.
*/
public void body() {
super.body();
-
- // resets variables to default values
- pivotGridlets_.clear();
+ shadowTime_ = Double.MAX_VALUE;
+ extraPEs_ = null;
+ pivot_ = null;
}
-
- /**
- * Sets the maximum number of pivot jobs. Similarly to the aggressive
- * backfilling in MAUI, the system administrator can specify how many
- * pivots can be considered when scheduling a job. That is, a job can
- * be used to backfill if it does not delay the first maxPivots jobs
- * in the waiting queue. If this parameter is very large, the policy
- * will behave like conservative backfilling
- * @param maxPivots the maximum number of pivots
- * @return <tt>true</tt> if the number of pivots has been set;
- * <tt>false</tt> otherwise.
- */
- public boolean setMaximumNumberOfPivots(int maxPivots) {
- if(maxPivots < 1)
- return false;
-
- maxPivots_ = maxPivots;
- return true;
- }
/**
* Schedules/adds to the queue a new <tt>Gridlet</tt> received by the
@@ -292,8 +230,9 @@
// if start time has been set, then it means that gridlet is
// a pivot. So, we need to remove it from the pivot list
- if(sgl.getStartTime() > 0) {
- pivotGridlets_.remove(sgl);
+ if(sgl == pivot_) {
+ pivot_ = null;
+ shadowTime_ = Double.MAX_VALUE;
updateProfile = true;
}
}
@@ -398,11 +337,11 @@
protected boolean scheduleGridlet(SSGridlet sgl) {
// if there are enough pivots already, then just return
- if(pivotGridlets_.size() >= maxPivots_)
+ if(pivot_ != null)
return false;
- super.enqueueGridlet(sgl);
- pivotGridlets_.add(sgl);
+ enqueueGridlet(sgl);
+ pivot_ = sgl;
//------------------ FOR DEBUGGING PURPOSES ONLY ----------------
@@ -416,6 +355,41 @@
}
/**
+ * Enqueues a gridlet. That is, finds the anchor point, which is the point
+ * in the availability profile where there are enough processors to execute
+ * the Gridlet, and calculates the extra PEs and shadow time accordingly.
+ * @param sgl the resource gridlet
+ */
+ protected void enqueueGridlet(SSGridlet sgl){
+
+ // calculate the execution time of the Gridlet
+ double executionTime =
+ super.forecastExecutionTime(ratingPE_, sgl.getRemainingLength());
+
+ // check whether there are PEs available over the time interval requested
+ Object[] availObj = checkPERangesAvailability(sgl.getNumPE(), executionTime);
+
+ // the anchor index, the entry in the profile where the gridlet will be placed
+ int anchorIndex = (Integer)availObj[0];
+ PERangeList selected = (PERangeList)availObj[2];
+
+ // a pointer to the anchor entry
+ AvailabilityProfileEntry anchorEntry = availProfile_.get(anchorIndex);
+ double startTime = anchorEntry.getTime();
+ double finishTime = startTime + executionTime;
+ shadowTime_ = startTime;
+ extraPEs_ = PERangeList.difference(anchorEntry.getPERanges(), selected);
+
+ // Set the list of ranges used by the gridlet
+ sgl.setPERangeList(selected);
+
+ // change Gridlet status
+ sgl.setStatus(Gridlet.QUEUED);
+ sgl.setStartTime(startTime);
+ sgl.setActualFinishTime(finishTime);
+ }
+
+ /**
* 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
@@ -424,8 +398,8 @@
*/
protected void updateSchedule() {
int itemsFinished = 0;
+ int itemsStarted = 0;
double currentTime = GridSim.clock();
- int itemsStarted = 0;
itemsFinished = finishRunningGridlets(currentTime);
@@ -456,26 +430,34 @@
protected int backfillGridlets(double currentTime) {
int gridletStarted = 0;
- // checks the pivots first
- Iterator<SSGridlet> iter = pivotGridlets_.iterator();
- while(iter.hasNext()) {
- SSGridlet pivot = iter.next();
- if(pivot.getStartTime() <= currentTime) {
- gridletStarted++;
- queuedGridlets_.remove(pivot);
- runningGridlets_.add(pivot);
- // change Gridlet status
- pivot.setStatus(Gridlet.INEXEC);
- super.sendInternalEvent(pivot.getActualFinishTime()-currentTime,
+ // checks the pivot first
+ if(pivot_ != null && pivot_.getStartTime() <= currentTime) {
+ gridletStarted++;
+ queuedGridlets_.remove(pivot_); // pivots should be at the beginning
+ runningGridlets_.add(pivot_);
+
+ // a pointer to the last entry analysed
+ AvailabilityProfileEntry tailEntry =
+ availProfile_.getPrecedingEntry(pivot_.getActualFinishTime());
+
+ int tailIndex = tailEntry == null ? -1 : availProfile_.indexOf(tailEntry);
+
+ // allocate the ranges of PEs to the gridlet
+ allocateImmediatePERanges(tailIndex, pivot_.getPERangeList(),
+ currentTime, pivot_.getActualFinishTime());
+
+ // change Gridlet status
+ pivot_.setStatus(Gridlet.INEXEC);
+ super.sendInternalEvent(pivot_.getActualFinishTime()-currentTime,
UPDATE_SCHEDULE_TAG);
- iter.remove();
+ pivot_ = null;
+ shadowTime_ = Double.MAX_VALUE;
- //-------------- FOR DEBUGGING PURPOSES ONLY --------------
+ //-------------- FOR DEBUGGING PURPOSES ONLY --------------
- GridSim.notifyListeners(this.get_id(), AllocationAction.SCHEDULE_CHANGED, true);
+ GridSim.notifyListeners(this.get_id(), AllocationAction.SCHEDULE_CHANGED, true);
- //----------------------------------------------------------
- }
+ //----------------------------------------------------------
}
// order jobs according to the ordering heuristic provided.
@@ -484,12 +466,17 @@
Collections.sort(queuedGridlets_, super.jobOrderHeuristic_);
// Start the execution of Gridlets that are queued
- iter = queuedGridlets_.iterator();
+ Iterator<SSGridlet >iter = queuedGridlets_.iterator();
while (iter.hasNext()) {
+ // to prevent the policy from iterating the list unnecessarily
+ if(resource_.getNumFreePE() == 0 && pivot_ != null) {
+ break;
+ }
+
SSGridlet gridlet = iter.next();
if(gridlet.getStartTime() > 0)
continue;
-
+
boolean success = startGridlet(gridlet);
// if the job could not be scheduled immediately, then enqueue it
@@ -515,6 +502,98 @@
return gridletStarted;
}
+ /**
+ * Allocates a Gridlet into free PEs, sets the Gridlet status to INEXEC,
+ * updates the availability profile and the ranges currently available.
+ * @param sgl a SSGridlet object
+ * @return <tt>true</tt> if one of the two following conditions
+ * holds true:
+ * <ul>
+ * <li> There are currently free PE to process the Gridlet and the Gridlet
+ * WILL NOT execute beyond the <b>shadow time</b>. That is, it
+ * WILL NOT delay the first gridlet in the waiting queue.
+ * <li> There are currently free PE to process the Gridlet, the Gridlet
+ * WILL execute beyond the <b>shadow time</b> but WILL NOT use more
+ * PEs than those left as <b>extra nodes<b>. That is, nodes remaining
+ * idle when the first gridlet in the waiting queue starts.
+ * </ul>
+ * <br>
+ * The method returns <tt>false</tt> otherwise.
+ * @pre sgl != null
+ * @post $none
+ */
+ protected boolean startGridlet(SSGridlet sgl) {
+ int reqPE = sgl.getNumPE();
+
+ if(resource_.getNumFreePE() < reqPE) {
+ return false;
+ }
+
+ // 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
+ double finishTime = currentTime + executionTime;
+
+ PERangeList intersect = resource_.getFreePERanges();
+ if(finishTime > shadowTime_)
+ intersect = PERangeList.intersection(intersect, extraPEs_);
+
+ // the list of ranges of PEs selected for the gridlet
+ PERangeList selected = super.selectPERangeList(reqPE, intersect);
+ if(selected == null || selected.getNumPE() < reqPE) {
+ return false;
+ }
+
+ // tail index represents the position which corresponds to the closest
+ // entry to the gridlet's finish time OR an existing entry whose
+ // time is equals to the gridlet's or advance reservation's finish time
+ int tailIndex = -1;
+
+ // 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
+ allocateImmediatePERanges(tailIndex, selected, currentTime, finishTime);
+
+ if(finishTime > shadowTime_) {
+ extraPEs_ = PERangeList.difference(extraPEs_, selected);
+ }
+
+ // add this Gridlet into execution list
+ runningGridlets_.add(sgl);
+ sgl.setStartTime(currentTime);
+ sgl.setActualFinishTime(finishTime);
+
+ // change Gridlet status
+ sgl.setStatus(Gridlet.INEXEC);
+
+ // Sets the list of ranges used by the gridlet
+ sgl.setPERangeList(selected);
+
+ // 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;
+ }
+
// ------------------------- PRIVATE METHODS ----------------------------
/**
Added: branches/gridsim4.0-branch3/source/gridsim/turbo/MAUIEBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/MAUIEBParallelSpaceShared.java (rev 0)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/MAUIEBParallelSpaceShared.java 2008-04-11 00:58:22 UTC (rev 169)
@@ -0,0 +1,553 @@
+/*
+ * Title: GridSim Toolkit
+ * Description: GridSim (Grid Simulation) Toolkit for Modelling and Simulation
+ * of Parallel and Distributed Systems such as Clusters and Grids
+ * Licence: GPL - http://www.gnu.org/copyleft/gpl.html
+ *
+ */
+
+package gridsim.turbo;
+
+import gridsim.GridSim;
+import gridsim.GridSimTags;
+import gridsim.Gridlet;
+import gridsim.ParameterException;
+import gridsim.gui.AllocationAction;
+
+import java.util.Calendar;
+import java.util.Collections;
+import java.util.Iterator;
+import java.util.LinkedList;
+
+/**
+ * <tt>EBParallelSpaceShared</tt> class is an allocation policy for
+ * <tt>GridResource</tt> that implements aggressive backfilling (EASY).
+ * The policy is based the aggressive backfilling algorithm described in the
+ * following papers:
+ * <p>
+ * <ul>
+ * <li> David B. Jackson, Quinn Snell and Mark J. Clement. Core Algorithms
+ * of the Maui Scheduler, Revised Papers from the 7th International
+ * Workshop on Job Scheduling Strategies for Parallel Processing
+ * (JSSPP '01), Lecture Notes in Computer Science, pp. 87-102, London, UK.
+ *
+ * <li>Ahuva W. Mu'alem and Dror G. Feitelson, Utilization, Predictability,
+ * Workloads, and User Runtime Estimates in Scheduling the IBM SP2
+ * with Backfilling. IEEE Transactions on Parallel and Distributed
+ * Systems, 12:(6), pp. 529-543, 2001.
+ * </ul>
+ * <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. The aggressive
+ * backfilling implemented here is similar to that used by the MAUI scheduler.
+ * That is, you can set the max number of pivot jobs will be considered during
+ * backfilling. A job will be used to backfill if it does not delay the first
+ * 'max number of pivots' in the queue. By default, only one pivot job is
+ * used. You can set that by invoking {@link #setMaximumNumberOfPivots(int)}.
+ * This scheduler will behave like conservative backfilling when the number
+ * of pivots is very large.
+ * <p>
+ * <b>LIMITATIONS:</b><br>
+ * <ul>
+ * <li> The list of machines comprising this resource must be
+ * homogeneous.
+ * <li> Local load is not considered. If you would like to
+ * 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.
+ * </ul>
+ *
+ * @author Marcos Dias de Assuncao
+ * @since GridSim Turbo Alpha 0.1
+ *
+ * @see gridsim.GridSim
+ * @see gridsim.ResourceCharacteristics
+ * @see gridsim.turbo.TAllocPolicy
+ * @see gridsim.turbo.CBParallelSpaceShared
+ * @see gridsim.turbo.PERange
+ * @see gridsim.turbo.PERangeList
+ */
+
+public class MAUIEBParallelSpaceShared extends CBParallelSpaceShared {
+
+ // Pivot jobs (i.e. the first n jobs in the queue)
+ protected LinkedList<SSGridlet> pivotGridlets_;
+
+ // Similarly to the aggressive backfilling in MAUI, the user
+ // can specify how many pivots can be considered when scheduling a job.
+ // That is, a job can be used to backfill if it does not delay the
+ // first maxPivots_ jobs in the waiting queue. If this parameter is
+ // very large, the policy will behave like conservative backfilling
+ private int maxPivots_;
+
+ /**
+ * 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
+ * @throws Exception This happens when one of the following scenarios occur:
+ * <ul>
+ * <li> Creating this entity before initialising GridSim package
+ * <li> The entity name is <tt>null</tt> or empty
+ * <li> The entity has <tt>zero</tt> number of PEs (Processing
+ * Elements). <br>
+ * No PEs, which means that the Gridlets cannot be processed.
+ * A GridResource must contain one or more Machines.
+ * A Machine must contain one or more PEs.
+ * </ul>
+ *
+ * @see gridsim.GridSim#init(int, Calendar, boolean,
+ * String[], String[], String)
+ */
+ public MAUIEBParallelSpaceShared(String resourceName,
+ String entityName) throws Exception{
+ super(resourceName, entityName);
+ // initialises local variables
+ pivotGridlets_ = new LinkedList<SSGridlet>();
+ maxPivots_ = 1; // default number of pivots is one
+ }
+
+ /**
+ * 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 maxNumPivots the maximum number of pivots used by this scheduler
+ * @throws Exception This happens when one of the following scenarios occur:
+ * <ul>
+ * <li> Creating this entity before initialising GridSim package
+ * <li> The entity name is <tt>null</tt> or empty
+ * <li> The entity has <tt>zero</tt> number of PEs (Processing
+ * Elements). <br>
+ * No PEs, which means that the Gridlets cannot be processed.
+ * A GridResource must contain one or more Machines.
+ * A Machine must contain one or more PEs.
+ * <li> The maximum number of pivots is <= 0.
+ * </ul>
+ *
+ * @see gridsim.GridSim#init(int, Calendar, boolean,
+ * String[], String[], String)
+ */
+ public MAUIEBParallelSpaceShared(String resourceName, String entityName,
+ int maxNumPivots) throws Exception{
+ this(resourceName, entityName);
+ if(!setMaximumNumberOfPivots(maxNumPivots)) {
+ throw new ParameterException("Maximum number of pivots should be > 0.");
+ }
+ }
+
+ /**
+ * Handles internal events that come to this entity.
+ */
+ public void body() {
+ super.body();
+
+ // resets variables to default values
+ pivotGridlets_.clear();
+ }
+
+ /**
+ * Sets the maximum number of pivot jobs. Similarly to the aggressive
+ * backfilling in MAUI, the system administrator can specify how many
+ * pivots can be considered when scheduling a job. That is, a job can
+ * be used to backfill if it does not delay the first maxPivots jobs
+ * in the waiting queue. If this parameter is very large, the policy
+ * will behave like conservative backfilling
+ * @param maxPivots the maximum number of pivots
+ * @return <tt>true</tt> if the number of pivots has been set;
+ * <tt>false</tt> otherwise.
+ */
+ public boolean setMaximumNumberOfPivots(int maxPivots) {
+ if(maxPivots < 1)
+ return false;
+
+ maxPivots_ = maxPivots;
+ return true;
+ }
+
+ /**
+ * Schedules/adds to the queue a new <tt>Gridlet</tt> received by the
+ * <tt>GridResource</tt> entity.
+ * @param gridlet a Gridlet object to be executed
+ * @param ack an acknowledgement, i.e. <tt>true</tt> if the
+ * user wants to know whether this operation is successful
+ * or not, <tt>false</tt> otherwise.
+ */
+ public void gridletSubmit(Gridlet gridlet, boolean ack) {
+ int reqPE = gridlet.getNumPE();
+
+ try {
+ // reject the Gridlet if it requires more PEs than the resource
+ // is able to provide
+ if(reqPE > super.totalPE_){
+ String userName = GridSim.getEntityName( gridlet.getUserID() );
+ System.out.println(super.get_name() + ".gridletSubmit(): " +
+ " Gridlet #" + gridlet.getGridletID() + " from " +
+ userName + " user requires " + gridlet.getNumPE() + " PEs.");
+ System.out.println("--> The resource has only " +
+ super.totalPE_ + " PEs.");
+ gridlet.setGridletStatus(Gridlet.FAILED);
+ super.sendFinishGridlet(gridlet);
+ return;
+ }
+ }
+ catch(Exception ex) {
+ System.out.println(super.get_name() +
+ ": Exception on submission of a Gridlet");
+ }
+
+ // Create a resource Gridlet
+ SSGridlet sgl = new SSGridlet(gridlet);
+
+ //-------------- FOR DEBUGGING PURPOSES ONLY --------------
+
+ GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_ARRIVED, true, sgl);
+
+ //----------------------------------------------------------
+
+ sgl.setStatus(Gridlet.QUEUED);
+ queuedGridlets_.add(sgl);
+ backfillGridlets(GridSim.clock());
+
+ // sends back an ack if required
+ if (ack == true) {
+ super.sendAck(GridSimTags.GRIDLET_SUBMIT_ACK, true,
+ gridlet.getGridletID(), gridlet.getUserID()
+ );
+ }
+ }
+
+ /**
+ * Cancels a Gridlet running or in the waiting queue.
+ * This method will search the running and waiting queues.
+ * The User ID is important as many users might have the same
+ * Gridlet ID in the lists. If a Gridlet is cancelled and the gridlet was
+ * either running or was a pivot, then the availability profile is updated.
+ * After that, the backfilling algorithm is called to check which
+ * gridlets can be started or scheduled.
+ * <b>NOTE:</b>
+ * <ul>
+ * <li> Before cancelling a Gridlet, this method updates when
+ * the expected completion time of the Gridlet is. If the
+ * completion time is smaller than the current time, then
+ * the Gridlet is considered to be <tt>finished</tt>.
+ * Therefore the Gridlet cannot be cancelled.
+ *
+ * <li> Once a Gridlet has been cancelled, it cannot be resumed
+ * to execute again since this method will pass the Gridlet
+ * back to sender, i.e. the <tt>userId</tt>.
+ *
+ * <li> If a Gridlet cannot be found in either execution and
+ * waiting lists, then a <tt>null</tt> Gridlet will be send back
+ * to sender, i.e. the <tt>userId</tt>.
+ * </ul>
+ * @param gridletId a Gridlet ID
+ * @param userId the user or owner's ID of this Gridlet
+ * @pre gridletId > 0
+ * @pre userId > 0
+ */
+ public void gridletCancel(int gridletId, int userId) {
+ double currentTime = GridSim.clock();
+
+ // stores the gridlet if found
+ SSGridlet sgl = null;
+ boolean found = false;
+ boolean updateProfile = false;
+
+ // Look for the Gridlet in the running queue
+ sgl = findSSGridlet(runningGridlets_, gridletId, userId);
+ if (sgl != null) {
+ found = true;
+
+ // if the Gridlet's finish time is smaller than the current
+ // time or the status is FINISHED, it means that the Gridlet
+ // has finished, but has not been removed from the running
+ // queue yet. It will probably be done shortly,
+ // so just send a null to the user.
+ if(sgl.getStatus() == Gridlet.SUCCESS ||
+ sgl.getActualFinishTime() <= currentTime){
+ super.sendCancelGridlet(GridSimTags.GRIDLET_CANCEL,
+ null, gridletId, userId);
+ return; // return as it is impossible to cancel the Gridlet
+ }
+ else{
+ // remove from the queue before compressing the schedule
+ runningGridlets_.remove(sgl);
+ updateProfile = true;
+ }
+ }
+
+ if(!found) {
+ // Look for the gridlet in the waiting queue
+ sgl = findSSGridlet(queuedGridlets_, gridletId, userId);
+ if (sgl != null) {
+ found = true;
+
+ // Get the Gridlet from the waiting queue and
+ // remove from the queue before compressing the schedule
+ queuedGridlets_.remove(sgl);
+
+ // if start time has been set, then it means that gridlet is
+ // a pivot. So, we need to remove it from the pivot list
+ if(sgl.getStartTime() > 0) {
+ pivotGridlets_.remove(sgl);
+ updateProfile = true;
+ }
+ }
+ }
+
+ // If the Gridlet could not be found in neither queue, then send a null
+ // Gridlet to the user and return because there is no need to
+ // compress the schedule
+ if(!found) {
+ System.out.println(super.get_name() + ".gridletCancel():" +
+ " Cannot find Gridlet #" + gridletId + " for User #" + userId);
+ super.sendCancelGridlet(GridSimTags.GRIDLET_CANCEL,
+ null, gridletId, userId);
+ return;
+ }
+
+ // check whether the Gridlet is running
+ boolean isRunning = sgl.getStatus() == Gridlet.INEXEC;
+ sgl.setStatus(Gridlet.CANCELED);
+
+ //----------------- USED FOR DEBUGGING PURPOSES ONLY -------------------
+
+ // If a gridlet has been cancelled, then inform the listeners
+ GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_CANCELLED, true, sgl);
+
+ //----------------------------------------------------------------------
+
+ // remove/update entries of the gridlet in the profile
+ if(updateProfile) {
+ removeGridlet(isRunning, sgl);
+ backfillGridlets(currentTime);
+
+ //------------------- USED FOR DEBUGGING PURPOSES ONLY -----------------
+
+ // Inform the listeners about the new schedule
+ GridSim.notifyListeners(this.get_id(), AllocationAction.SCHEDULE_CHANGED, true);
+
+ //----------------------------------------------------------------------
+ }
+
+ // sends the Gridlet back to user
+ sgl.finalizeGridlet();
+ super.sendCancelGridlet(GridSimTags.GRIDLET_CANCEL,
+ sgl.getGridlet(), gridletId, userId);
+ }
+
+ /**
+ * Pauses a <tt>Gridlet</tt> only if it is currently executing.
+ * <b>NOTE: This operation is not supported. </b>
+ * @param gridletId a Gridlet ID
+ * @param userId the user or owner's ID of this Gridlet
+ * @param ack an acknowledgement, i.e. <tt>true</tt> if wanted to know
+ * whether this operation is success or not, <tt>false</tt>
+ * otherwise.
+ */
+ public void gridletPause(int gridletId, int userId, boolean ack){
+ System.out.println(super.get_name() +
+ ".gridletMove(): not supported at the moment.");
+ }
+
+ /**
+ * Moves a Gridlet from this GridResource entity to a different one.
+ * <b>NOTE: This operation is not supported. </b>
+ * @param gridletId a Gridlet ID
+ * @param userId the user or owner's ID of this Gridlet
+ * @param destId a new destination GridResource ID for this Gridlet
+ * @param ack an acknowledgement, i.e. <tt>true</tt> if wanted to know
+ * whether this operation is success or not, <tt>false</tt>
+ * otherwise
+ */
+ public void gridletMove(int gridletId, int userId, int destId, boolean ack){
+ System.out.println(super.get_name() +
+ ".gridletPause(): not supported at the moment.");
+ }
+
+ /**
+ * Resumes a Gridlet only in the paused list.
+ * <b>NOTE: This operation is not supported. </b>
+ * @param gridletId a Gridlet ID
+ * @param userId the user or owner's ID of this Gridlet
+ * @param ack an acknowledgement, i.e. <tt>true</tt> if wanted to know
+ * whether this operation is success or not, <tt>false</tt>
+ * otherwise
+ */
+ public void gridletResume(int gridletId, int userId, boolean ack){
+ System.out.println(super.get_name() +
+ ".gridletResume(): not supported at the moment.");
+ }
+
+ // -------------------- PROTECTED METHODS ----------------------------
+
+ /**
+ * 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.
+ */
+ protected boolean scheduleGridlet(SSGridlet sgl) {
+
+ // if there are enough pivots already, then just return
+ if(pivotGridlets_.size() >= maxPivots_)
+ return false;
+
+ super.enqueueGridlet(sgl);
+ pivotGridlets_.add(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);
+
+ //---------------------------------------------------------------
+
+ return true;
+ }
+
+ /**
+ * 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.
+ */
+ protected void updateSchedule() {
+ int itemsFinished = 0;
+ double currentTime = GridSim.clock();
+ int itemsStarted = 0;
+
+ itemsFinished = finishRunningGridlets(currentTime);
+
+ // remove past entries from the availability profile
+ AvailabilityProfileEntry currentStatus =
+ availProfile_.removePastEntries(currentTime);
+ if(currentStatus != null) {
+ resource_.resetFreePERanges(currentStatus.getPERanges());
+ }
+
+ itemsStarted = backfillGridlets(currentTime);
+
+ //---------------- USED FOR DEBUGGING PURPOSES ONLY --------------------
+
+ // 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 backfills/starts gridlets that are in the queue
+ * @param currentTime the current simulation time
+ * @return the number of gridlets started
+ */
+ protected int backfillGridlets(double currentTime) {
+ int gridletStarted = 0;
+
+ // checks the pivots first
+ Iterator<SSGridlet> iter = pivotGridlets_.iterator();
+ while(iter.hasNext()) {
+ SSGridlet pivot = iter.next();
+ if(pivot.getStartTime() <= currentTime) {
+ gridletStarted++;
+ queuedGridlets_.remove(pivot); // pivots should be at the beginning
+ runningGridlets_.add(pivot);
+ // change Gridlet status
+ pivot.setStatus(Gridlet.INEXEC);
+ super.sendInternalEvent(pivot.getActualFinishTime()-currentTime,
+ UPDATE_SCHEDULE_TAG);
+ iter.remove();
+
+ //-------------- FOR DEBUGGING PURPOSES ONLY --------------
+
+ GridSim.notifyListeners(this.get_id(), AllocationAction.SCHEDULE_CHANGED, true);
+
+ //----------------------------------------------------------
+ }
+ }
+
+ // order jobs according to the ordering heuristic provided.
+ // That is, if one was provided by the user.
+ if(super.jobOrderHeuristic_ != null)
+ Collections.sort(queuedGridlets_, super.jobOrderHeuristic_);
+
+ // Start the execution of Gridlets that are queued
+ iter = queuedGridlets_.iterator();
+ while (iter.hasNext()) {
+ SSGridlet gridlet = iter.next();
+ if(gridlet.getStartTime() > 0)
+ continue;
+
+ boolean success = startGridlet(gridlet);
+
+ // if the job could not be scheduled immediately, then enqueue it
+ if(success) {
+ iter.remove();
+ gridletStarted++;
+ }
+ else {
+ success = scheduleGridlet(gridlet);
+ }
+
+ // Inform visualiser that the gridlet was either started or scheduled
+ if(success) {
+ //-------------- FOR DEBUGGING PURPOSES ONLY --------------
+
+ GridSim.notifyListeners(this.get_id(),
+ AllocationAction.ITEM_SCHEDULED, true, gridlet);
+
+ //----------------------------------------------------------
+ }
+ }
+
+ return gridletStarted;
+ }
+
+ /**
+ * Allocates a Gridlet into free PEs, sets the Gridlet status to INEXEC,
+ * updates the availability profile and the ranges currently available
+ * @param sgl a SSGridlet object
+ * @return <tt>true</tt> if there is are free PE to process this Gridlet,
+ * <tt>false</tt> otherwise
+ * @pre sgl != null
+ * @post $none
+ */
+ protected boolean startGridlet(SSGridlet sgl) {
+ int reqPE = sgl.getNumPE();
+ // Just to make the easy backfilling faster and avoid checking the
+ // availability profile unnecessarily
+ if(resource_.getNumFreePE() < reqPE)
+ return false;
+
+ return super.startGridlet(sgl);
+ }
+
+ // ------------------------- PRIVATE METHODS ----------------------------
+
+ /**
+ * This method removes/updates all the entries of a gridlet from the profile
+ * and updates the ranges of current free PEs if the gridlet was in execution.
+ * @param wasRunning <tt>true</tt> if the gridlet was running;
+ * <tt>false</tt> otherwise.
+ * @param gridlet the Gridlet to be removed
+ */
+ private void removeGridlet(boolean wasRunning, SSGridlet gridlet) {
+ if(!gridlet.hasReserved()) {
+
+ // removes the gridlet from the profile
+ updateEntriesAtProfile(wasRunning, gridlet);
+ }
+ }
+}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/PERange.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/PERange.java 2008-04-09 01:48:26 UTC (rev 168)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/PERange.java 2008-04-11 00:58:22 UTC (rev 169)
@@ -67,14 +67,6 @@
}
/**
- * Increases the end of the range
- * @return returns the new value of the range
- */
- public int increaseEnd(){
- return ++end_;
- }
-
- /**
* Returns the number of PEs in this range
* @return the number of PEs
*/
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java 2008-04-09 01:48:26 UTC (rev 168)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java 2008-04-11 00:58:22 UTC (rev 169)
@@ -46,7 +46,7 @@
// the finish time of the Gridlet
private double actualFinishTime_;
- // estimation of Gridlet finished time
+ // estimation of Gridlet finished time
private double expectedFinishTime_;
// num PE needed to execute this Gridlet
@@ -448,7 +448,7 @@
expectedFinishTime_ = time;
}
- /**
+ /**
* Gets the Gridlet's finish time
* @return finish time of a gridlet or <tt>-1.0</tt> if
* it cannot finish in this hourly slot
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/TResourceCharacteristics.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/TResourceCharacteristics.java 2008-04-09 01:48:26 UTC (rev 168)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/TResourceCharacteristics.java 2008-04-11 00:58:22 UTC (rev 169)
@@ -47,24 +47,29 @@
public static final int EB_PARALLEL_SPACE_SHARED = 11;
/** Parallel spaced-shared system using First Come First Serve (FCFS)
+ * algorithm and aggressive backfilling (EASY) with configurable number of
+ * pivots */
+ public static final int MAUI_EB_PARALLEL_SPACE_SHARED = 12;
+
+ /** Parallel spaced-shared system using First Come First Serve (FCFS)
* algorithm, conservative backfilling and supporting advance reservations */
- public static final int AR_PARALLEL_SPACE_SHARED = 12;
+ public static final int AR_PARALLEL_SPACE_SHARED = 13;
/** Parallel spaced-shared system using multiple
* partitions and aggressive (EASY) backfilling */
- public static final int EB_MULTI_PARTITIONS = 13;
+ public static final int EB_MULTI_PARTITIONS = 14;
/** Parallel spaced-shared system using multiple
* partitions and conservative backfilling */
- public static final int CB_MULTI_PARTITIONS = 14;
+ public static final int CB_MULTI_PARTITIONS = 15;
/** Parallel spaced-shared system using multiple
* partitions, conservative backfilling and advance reservations */
- public static final int ARCB_MULTI_PARTITIONS = 15;
+ public static final int ARCB_MULTI_PARTITIONS = 16;
/** Parallel spaced-shared system using multiple
* partitions, aggressive (EASY) backfilling and advance reservations */
- public static final int AREB_MULTI_PARTITIONS = 16;
+ public static final int AREB_MULTI_PARTITIONS = 17;
/**
* Allocates a new {@link TResourceCharacteristics} object.
@@ -171,6 +176,7 @@
// Assuming all PEs in all Machine have same rating.
case TResourceCharacteristics.CB_PARALLEL_SPACE_SHARED:
case TResourceCharacteristics.EB_PARALLEL_SPACE_SHARED:
+ case TResourceCharacteristics.MAUI_EB_PARALLEL_SPACE_SHARED:
case TResourceCharacteristics.AR_PARALLEL_SPACE_SHARED:
case TResourceCharacteristics.EB_MULTI_PARTITIONS:
case TResourceCharacteristics.CB_MULTI_PARTITIONS:
@@ -290,6 +296,10 @@
policyName = "EB_PARALLEL_SPACE_SHARED";
break;
+ case TResourceCharacteristics.MAUI_EB_PARALLEL_SPACE_SHARED:
+ policyName = "MAUI_EB_PARALLEL_SPACE_SHARED";
+ break;
+
case TResourceCharacteristics.AR_PARALLEL_SPACE_SHARED:
policyName = "AR_PARALLEL_SPACE_SHARED";
break;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
