Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [61] branches/gridsim4.0-branch3
|
From: <mar...@us...> - 2007-09-18 04:17:23
|
Revision: 61
http://gridsim.svn.sourceforge.net/gridsim/?rev=61&view=rev
Author: marcos_dias
Date: 2007-09-17 21:17:27 -0700 (Mon, 17 Sep 2007)
Log Message:
-----------
SOME OPTIMISATIONS AND BUG FIXES:
+ gridlets now share entries in the availability profile. This reduces the number of entries in the profile, improves simulation speed and minimises the use of memory.
+ cancellation of gridlets. Gridlets can now be cancelled and the remaining part of the queue is compressed. The compression of the queue is described in an IEEE Transactions paper described in the header of the class. The compression avoids reschedule and is faster as the first time estimation is always respected as the gridlets are considered according to the order that they were put in the queue.
+ Some changes in the availability, GUI, and PE ranges related classes.
+ One example of cancellation has been included.
LIMITATIONS/KNOWN ISSUES:
+ AllocPolicy does not set the status of the Gridlet to CANCELED when it is sent to the user.
+ In fact, I do not know why the Gridlet is sent back to the user when it is cancelled.
+ TThe interface does not show the cancelled Gridlets properly YET. When ready, the cancelled Gridlets will appear in red right before they disappear from the panel.
Modified Paths:
--------------
branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExample01.java
branches/gridsim4.0-branch3/source/gridsim/ARPolicy.java
branches/gridsim4.0-branch3/source/gridsim/GridSim.java
branches/gridsim4.0-branch3/source/gridsim/PERangeList.java
branches/gridsim4.0-branch3/source/gridsim/ParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/SSGridlet.java
branches/gridsim4.0-branch3/source/gridsim/gui/AllocationAction.java
branches/gridsim4.0-branch3/source/gridsim/gui/GridSimVisualizer.java
branches/gridsim4.0-branch3/source/gridsim/gui/ResourceWindow.java
branches/gridsim4.0-branch3/source/gridsim/util/Workload.java
Added Paths:
-----------
branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleWithCancellation01.java
branches/gridsim4.0-branch3/examples/examples/workload/parallel/WorkloadWithCancellation.java
Modified: branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExample01.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExample01.java 2007-09-14 23:23:03 UTC (rev 60)
+++ branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExample01.java 2007-09-18 04:17:27 UTC (rev 61)
@@ -86,10 +86,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
Added: branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleWithCancellation01.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleWithCancellation01.java (rev 0)
+++ branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleWithCancellation01.java 2007-09-18 04:17:27 UTC (rev 61)
@@ -0,0 +1,173 @@
+
+package examples.workload.parallel;
+
+import gridsim.GridResource;
+import gridsim.GridSim;
+import gridsim.Machine;
+import gridsim.MachineList;
+import gridsim.ResourceCharacteristics;
+
+import java.util.ArrayList;
+import java.util.Calendar;
+import java.util.LinkedList;
+import java.util.Random;
+
+
+/**
+ * Test Driver class for this example
+ */
+public class TurboExampleWithCancellation01
+{
+ /**
+ * 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>();
+
+ //////////////////////////////////////////
+ // Initialise the GridSim package. It should be called
+ // before creating any entities. We can't run this example without
+ // initialising 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
+
+ // Initialise 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);
+ WorkloadWithCancellation workload = new WorkloadWithCancellation("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
+
+ ResourceCharacteristics resConfig = new ResourceCharacteristics(
+ arch, os, mList, ResourceCharacteristics.PARALLEL_SPACE_SHARED,
+ time_zone, cost);
+
+ //////////////////////////////////////////
+ // 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;
+ try {
+ gridRes = new GridResource(name, baud_rate, seed,
+ resConfig, peakLoad, offPeakLoad, holidayLoad, Weekends,
+ Holidays);
+ }
+ catch (Exception e) {
+ e.printStackTrace();
+ }
+
+ System.out.println("Creates one Grid resource with name = " + name);
+ return gridRes;
+ }
+} // end class
+
Added: branches/gridsim4.0-branch3/examples/examples/workload/parallel/WorkloadWithCancellation.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/workload/parallel/WorkloadWithCancellation.java (rev 0)
+++ branches/gridsim4.0-branch3/examples/examples/workload/parallel/WorkloadWithCancellation.java 2007-09-18 04:17:27 UTC (rev 61)
@@ -0,0 +1,250 @@
+/* Title: GridSim Toolkit
+ * Description: GridSim (Grid Simulation) Toolkit for Modeling and Simulation
+ * of Parallel and Distributed Systems such as Clusters and Grids
+ * Licence: GPL - http://www.gnu.org/copyleft/gpl.html
+ */
+
+package examples.workload.parallel;
+
+import eduni.simjava.Sim_event;
+import eduni.simjava.Sim_system;
+import gridsim.GridSimTags;
+import gridsim.Gridlet;
+import gridsim.IO_data;
+import gridsim.ParameterException;
+import gridsim.net.Link;
+import gridsim.util.Workload;
+
+import java.util.ArrayList;
+
+/**
+ * This class is an extended version of @link{Workload}. This class
+ * cancels some gridlets submitted.
+ *
+ * @author Marcos Dias de Assuncao
+ * @since GridSim Turbo Alpha 0.1
+ *
+ * @see Workload
+ */
+public class WorkloadWithCancellation extends Workload {
+ private final int NUM_GRIDLETS_BETWEEN_CANCELLATIONS = 50;
+ // value of 1, means that the cancellation will be sent
+ // at the gridlet's submission time + (gridlet duration * 1)
+ private final double TIME_CANCELLATION = 0.5;
+
+ /**
+ * Create a new @link{WorkloadWithCancellation} object <b>without</b> using
+ * the network extension. This means this entity directly sends Gridlets
+ * to a resource destination without going through a wired network. <br>
+ * <tt>NOTE:</tt>
+ * You can not use this constructor in an experiment that uses a wired
+ * network topology.
+ *
+ * @param name this entity name
+ * @param fileName the workload trace filename in one of the following
+ * format: <i>ASCII text, zip, gz.</i>
+ * @param resourceName the resource name
+ * @param rating the resource's PE rating
+ * @throws Exception This happens when creating this entity before
+ * initialising GridSim package or this entity name is
+ * <tt>null</tt> or empty
+ * @throws ParameterException This happens for the following conditions:
+ * <ul>
+ * <li>the entity name is null or empty
+ * <li>the workload trace file name is null or empty
+ * <li>the resource entity name is null or empty
+ * <li>the resource PE rating <= 0
+ * </ul>
+ * @pre name != null
+ * @pre fileName != null
+ * @pre resourceName != null
+ * @pre rating > 0
+ * @post $none
+ */
+ public WorkloadWithCancellation(String name, String fileName, String resourceName,
+ int rating) throws ParameterException, Exception {
+
+ super(name, fileName, resourceName, rating);
+ }
+
+ /**
+ * Create a new @link{WorkloadWithCancellation} object <b>with</b> the network extension.
+ * This means this entity directly sends Gridlets to a destination resource
+ * through a link. The link is automatically created by this constructor.
+ *
+ * @param name this entity name
+ * @param baudRate baud rate of this link (bits/s)
+ * @param propDelay Propagation delay of the Link in milliseconds
+ * @param MTU Maximum Transmission Unit of the Link in bytes.
+ * Packets which are larger than the MTU should be split
+ * up into MTU size units.
+ * For example, a 1024 byte packet trying to cross a 576
+ * byte MTU link should get split into 2 packets of 576
+ * bytes and 448 bytes.
+ * @param fileName the workload trace filename in one of the following
+ * format: <i>ASCII text, zip, gz.</i>
+ * @param resourceName the resource name
+ * @param rating the resource's PE rating
+ * @throws Exception This happens when creating this entity before
+ * initialising GridSim package or this entity name is
+ * <tt>null</tt> or empty
+ * @throws ParameterException This happens for the following conditions:
+ * <ul>
+ * <li>the entity name is null or empty
+ * <li> baudRate <= 0
+ * <li> propDelay <= 0
+ * <li> MTU <= 0
+ * <li>the workload trace file name is null or empty
+ * <li>the resource entity name is null or empty
+ * <li>the resource PE rating <= 0
+ * </ul>
+ * @pre name != null
+ * @pre baudRate > 0
+ * @pre propDelay > 0
+ * @pre MTU > 0
+ * @pre fileName != null
+ * @pre resourceName != null
+ * @pre rating > 0
+ * @post $none
+ */
+ public WorkloadWithCancellation(String name, double baudRate, double propDelay, int MTU,
+ String fileName, String resourceName, int rating)
+ throws ParameterException, Exception {
+
+ super( name, baudRate, propDelay, MTU, fileName, resourceName, rating );
+ }
+
+ /**
+ * Create a new Workload object <b>with</b> the network extension.
+ * This means this entity directly sends Gridlets to a destination resource
+ * through a link. The link is automatically created by this constructor.
+ *
+ * @param name this entity name
+ * @param link the link that will be used to connect this Workload
+ * to another entity or a Router.
+ * @param fileName the workload trace filename in one of the following
+ * format: <i>ASCII text, zip, gz.</i>
+ * @param resourceName the resource name
+ * @param rating the resource's PE rating
+ * @throws Exception This happens when creating this entity before
+ * initialising GridSim package or this entity name is
+ * <tt>null</tt> or empty
+ * @throws ParameterException This happens for the following conditions:
+ * <ul>
+ * <li>the entity name is null or empty
+ * <li>the link is empty
+ * <li>the workload trace file name is null or empty
+ * <li>the resource entity name is null or empty
+ * <li>the resource PE rating <= 0
+ * </ul>
+ * @pre name != null
+ * @pre link != null
+ * @pre fileName != null
+ * @pre resourceName != null
+ * @pre rating > 0
+ * @post $none
+ */
+ public WorkloadWithCancellation(String name, Link link, String fileName,
+ String resourceName, int rating)
+ throws ParameterException, Exception {
+
+ super(name, link, fileName, resourceName, rating);
+ }
+
+ //////////////////////// PRIVATE METHODS ///////////////////////
+
+ /**
+ * Collects Gridlets sent and stores them into a list.
+ * @pre $none
+ * @post $none
+ */
+ protected void collectGridlet() {
+ System.out.println(super.get_name() + ": Collecting Gridlets ...");
+ list_ = new ArrayList(gridletID_ + 1);
+
+ Object data = null;
+ Gridlet gl = null;
+
+ int counter = 1; // starts at 1, since gridletID_ starts at 1 too
+ Sim_event ev = new Sim_event();
+ while ( Sim_system.running() ) {
+
+ super.sim_get_next(ev); // get the next available event
+ data = ev.get_data(); // get the event's data
+
+ // handle ping request
+ if (ev.get_tag() == GridSimTags.INFOPKT_SUBMIT) {
+ processPingRequest(ev);
+ continue;
+ }
+
+ // get the Gridlet data
+ if (data != null && data instanceof Gridlet) {
+ gl = (Gridlet) data;
+
+ if(gl.getGridletStatus() == Gridlet.FAILED)
+ System.out.println("Gridlet failed");
+
+ if(gl.getGridletStatus() == Gridlet.CANCELED)
+ System.out.println("Gridlet cancelled");
+
+ list_.add(gl);
+ counter++;
+ }
+
+ // if all the Gridlets have been collected
+ if (counter == gridletID_) {
+ break;
+ }
+ }
+ }
+
+ /**
+ * Creates a Gridlet with the given information, then submit it to a
+ * resource
+ * @param id a Gridlet ID
+ * @param submitTime Gridlet's submit time
+ * @param runTime Gridlet's run time
+ * @param numProc number of processors
+ * @pre id >= 0
+ * @pre submitTime >= 0
+ * @pre runTime >= 0
+ * @pre numProc > 0
+ * @post $none
+ */
+ protected void submitGridlet(int id, long submitTime, int runTime, int numProc) {
+
+ // create the gridlet
+ int len = runTime * rating_; // calculate a job length for each PE
+ Gridlet gl = new Gridlet(id, len, size_, size_);
+ gl.setUserID( super.get_id() ); // set the owner ID
+ gl.setNumPE(numProc); // set the requested num of proc
+
+ // printing to inform user
+ if (gridletID_ == 1 || gridletID_ % INTERVAL == 0) {
+ System.out.println(super.get_name() + ": Submitting Gridlets to " +
+ resName_ + " ...");
+ }
+
+ // check the submit time
+ if (submitTime < 0) {
+ submitTime = 0;
+ }
+
+ gridletID_++; // increment the counter
+
+ // submit a gridlet to resource
+ super.send(super.output, submitTime, GridSimTags.GRIDLET_SUBMIT,
+ new IO_data(gl, gl.getGridletFileSize(), resID_) );
+
+ // check whether a cancellation has to be scheduled or not
+ int result = gridletID_ % NUM_GRIDLETS_BETWEEN_CANCELLATIONS;
+ if(result == 0) {
+ super.send(super.output, (submitTime + (TIME_CANCELLATION * runTime)), GridSimTags.GRIDLET_CANCEL,
+ new IO_data(gl, 0, resID_) );
+ gridletID_++;
+ }
+ }
+
+} // end class
+
Modified: branches/gridsim4.0-branch3/source/gridsim/ARPolicy.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/ARPolicy.java 2007-09-14 23:23:03 UTC (rev 60)
+++ branches/gridsim4.0-branch3/source/gridsim/ARPolicy.java 2007-09-18 04:17:27 UTC (rev 61)
@@ -488,9 +488,9 @@
}
/**
- * Gets the current time. Time calculates from simulation init time +
- * (GridSim.clock * MILLI_SEC). MILLI_SEC = 1000.
- * @return current time in seconds
+ * Gets the current time. Time is calculated from simulation init time +
+ * (GridSim.clock() * MILLI_SEC), where MILLI_SEC = 1000.
+ * @return current time in milliseconds
* @pre $none
* @post $result > 0
*/
Modified: branches/gridsim4.0-branch3/source/gridsim/GridSim.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/GridSim.java 2007-09-14 23:23:03 UTC (rev 60)
+++ branches/gridsim4.0-branch3/source/gridsim/GridSim.java 2007-09-18 04:17:27 UTC (rev 61)
@@ -449,7 +449,7 @@
/**
* Sets a <tt>GridInformationService</tt> (GIS) entity.
- * This method is useful is you write a different type of GIS entity.
+ * This method is useful when you want a different type of GIS entity.
* This method must be called before {@link #startGridSimulation()} method.
* @param gis a GIS object
* @return <tt>true</tt> if successful, <tt>false</tt> otherwise
@@ -459,7 +459,8 @@
*/
public static boolean setGIS(GridInformationService gis)
{
- if (gis == null) {
+ // ignore if an existing GIS object has already been created
+ if (gis == null || gis_ != null) {
return false;
}
Modified: branches/gridsim4.0-branch3/source/gridsim/PERangeList.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/PERangeList.java 2007-09-14 23:23:03 UTC (rev 60)
+++ branches/gridsim4.0-branch3/source/gridsim/PERangeList.java 2007-09-18 04:17:27 UTC (rev 61)
@@ -51,25 +51,28 @@
}
/**
- * Consolidate PE ranges: e.g. 3-5,5-8,10-20 => 3-8,10-20.
- * @pre assumes that the ranges are in order.
+ * Merges PE ranges: e.g. 3-5,5-8,10-20 => 3-8,10-20.
*/
- public void consolidatePERanges(){
- PERange currentRange;
- PERange nextRange;
+ public void mergePERanges() {
+ if(this.size() < 2) // there is nothing to be consolidated
+ return;
+
+ PERange currentRange;
+ PERange nextRange;
- sortRanges();
-
- for(int i=0 ; i<this.size()-1; i++) {
- currentRange = this.get(i);
- nextRange = this.get(i+1);
-
- if( currentRange.getEnd() == nextRange.getBeginning() ||
- (nextRange.getBeginning() - currentRange.getEnd()) == 1 ){
- currentRange.setEnd(nextRange.getEnd());
- this.remove(i+1);
- }
- }
+ sortRanges(); // sorts the ranges before
+ int index = 0;
+ while(index < super.size()-1){
+ currentRange = super.get(index);
+ nextRange = super.get(index+1);
+ if( (nextRange.getBeginning() - currentRange.getEnd()) == 1 ){
+ currentRange.setEnd(nextRange.getEnd());
+ super.remove(index+1);
+ }
+ else{
+ index++;
+ }
+ }
}
/**
@@ -89,7 +92,8 @@
* of the ranges
*/
public void sortRanges(){
- Collections.sort(this,comparator_);
+ if(super.size() > 1)
+ Collections.sort(this, comparator_);
}
/**
@@ -197,8 +201,13 @@
}
}
}
- rIntersec.consolidatePERanges();
- return rIntersec.size() == 0 ? null : rIntersec;
+
+ if( rIntersec.size() == 0)
+ return null;
+ else{
+ rIntersec.mergePERanges();
+ return rIntersec;
+ }
}
/**
@@ -285,14 +294,12 @@
return null;
}
- PERangeList query = lista;
- query.sortRanges();
+ PERangeList difference = lista.clone();
+ difference.mergePERanges();
PERangeList universe = listb;
universe.sortRanges();
-
- PERangeList difference = query.clone();
-
+
boolean finished = false;
while(!finished){
finished = true;
@@ -321,7 +328,7 @@
return null;
}
else{
- difference.consolidatePERanges();
+ difference.mergePERanges();
return difference;
}
}
@@ -453,7 +460,7 @@
return null;
}
else{
- universe.consolidatePERanges();
+ universe.mergePERanges();
return universe;
}
}
@@ -502,4 +509,22 @@
return begA.compareTo(begB);
}
}
+
+
+ // FOR DEBUGGING PURPOSES ONLY...
+ public static void main(String args[]){
+
+ PERange ra = new PERange(0, 10);
+ PERange rd = new PERange(31, 50);
+ PERange rb = new PERange(11, 20);
+ PERange rc = new PERange(21, 30);
+
+ PERangeList list = new PERangeList();
+ list.add(ra); list.add(rb);
+ list.add(rc); list.add(rd);
+
+ list.mergePERanges();
+
+ System.out.println("Consolidated# " + list);
+ }
}
Modified: branches/gridsim4.0-branch3/source/gridsim/ParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/ParallelSpaceShared.java 2007-09-14 23:23:03 UTC (rev 60)
+++ branches/gridsim4.0-branch3/source/gridsim/ParallelSpaceShared.java 2007-09-18 04:17:27 UTC (rev 61)
@@ -16,38 +16,48 @@
import java.util.ArrayList;
import java.util.Calendar;
+import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
+import java.util.Iterator;
import java.util.LinkedList;
/**
* @link{ParallelSpaceShared} class is an allocation policy for
* @link{GridResource} that behaves exactly like First Come First Serve (FCFS)
* with conservative backfilling. The policy is based on the conservative
- * backfilling algorithm described in:
+ * backfilling algorithm described in the following papers:
* <p>
* Dror G. Feitelson and Ahuva Mu'alem Weil, Utilization and Predictability
* in Scheduling the IBM SP2 with Backfilling, in Proceedings of the 12th
* International Parallel Processing Symposium on International
* Parallel Processing Symposium (IPPS 1998), pp. 542-546.
* <p>
+ * 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.
+ * <p>
* <b>LIMITATIONS:</b><br>
* <ul>
* <li> The list of machines comprising this resource must be homogeneous.
- * <li> Local load is not considered.
- * <li> Gridlets cannot be neither paused nor migrated.
+ * <li> Local load is not considered. If would like to simulate this, you have to
+ * model the local load as gridlets. It is more precise and faster.
+ * <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.AllocPolicy
+ * @see gridsim.PERange
+ * @see gridsim.PERangeList
*/
public class ParallelSpaceShared extends AllocPolicy {
- private LinkedList<SSGridlet> queuedGridlets_; // Queue of queued Gridlets
+ private LinkedList<SSGridlet> queuedGridlets_; // Queue of waiting Gridlets
private LinkedList<SSGridlet> runningGridlets_; // Queue of running Gridlets
private int numPE_; // The total number of PEs in the resource
private int ratingPE_; // The rating of one PE
@@ -56,8 +66,8 @@
// FOR DEBUGGING PURPOSES ONLY...
private ArrayList<AllocationListener> listeners_; // the listeners interested in this policy
- private boolean hasListener_;
- private double currentTime_;
+ private boolean hasListener_; // indicates whether there are listeners registered
+ private double lastActionTime_; // Keep the time of last relevant allocation action
/**
* Allocates a new @link{ParallelSpaceShared} object
@@ -87,7 +97,7 @@
queuedGridlets_ = new LinkedList<SSGridlet>();
availProfile_ = new AvailabilityProfile();
freePERanges_ = new PERangeList();
- currentTime_ = 0.0D;
+ lastActionTime_ = 0.0D;
numPE_ = 0;
ratingPE_ = 0;
listeners_ = null;
@@ -98,8 +108,7 @@
* Handles internal events that come to this entity.
*/
public void body(){
-
- // Gets the information on number of PEs and rating
+ // Gets the information on number of PEs and rating
// of one PE assuming that the machines are homogeneous
MachineList list = resource_.getMachineList();
int numMachine = list.size();
@@ -114,8 +123,7 @@
// a loop that is looking for internal events only
Sim_event ev = new Sim_event();
- while ( Sim_system.running() )
- {
+ while ( Sim_system.running() ) {
super.sim_get_next(ev);
// if the simulation finishes then exit the loop
@@ -126,7 +134,7 @@
// Internal Event if the event source is this entity
if (ev.get_src() == super.myId_) {
- updateSchedule();
+ updateSchedule();
}
}
@@ -145,15 +153,20 @@
* @param ack an acknowledgement, i.e. <tt>true</tt> if the user wants to know
* whether this operation is success or not, <tt>false</tt> otherwise.
*/
- public void gridletSubmit(Gridlet gridlet, boolean ack){
-
+ public void gridletSubmit(Gridlet gridlet, boolean ack) {
int reqPE = gridlet.getNumPE();
double currentTime = GridSim.clock();
+ lastActionTime_ = currentTime;
try{
// reject the Gridlet if it requires more PEs than the resource
// is able to provide
if(reqPE > numPE_){
+ 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 " + numPE_ + " PEs.");
gridlet.setGridletStatus(Gridlet.FAILED);
super.sendFinishGridlet(gridlet);
return;
@@ -164,57 +177,44 @@
": Exception on submission of a Gridlet");
}
- SSGridlet rgl = new SSGridlet(gridlet);
+ // Create a resource Gridlet
+ SSGridlet sgl = new SSGridlet(gridlet);
/////////////// FOR DEBUGGING PURPOSES ONLY ////////
if(GridSim.DEBUG_SIMULATION){
- if(hasListener_){
- AllocationAction action =
- new AllocationAction(AllocationAction.GRIDLET_ARRIVED, currentTime_);
- LinkedList<SSGridlet> list = new LinkedList<SSGridlet>();
- list.add(rgl);
- action.setSSGridlet(list);
- notifyListeners(action);
- }
+ LinkedList<SSGridlet> list = new LinkedList<SSGridlet>();
+ list.add(sgl);
+ notifyListeners(AllocationAction.GRIDLET_ARRIVED, true, lastActionTime_, list);
}
/////////////////////////////////////////////////////
-
// If there are no jobs in the queue list, then check if
- // there are enough PEs to process the job
+ // there are enough PEs to process the job immediately
boolean success = false;
int freePE = (freePERanges_ == null) ? 0 : freePERanges_.getNumPE();
if( reqPE <= freePE ){
- success = scheduleJobImmediately(rgl);
+ success = scheduleGridletImmediately(sgl);
}
// if the job could not be scheduled immediately, then
// find the anchor point where the job can be put
if(!success){
- findAnchorPoint(rgl);
+ findAnchorPoint(sgl);
+ // add this Gridlet into waiting list
+ queuedGridlets_.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
if(GridSim.DEBUG_SIMULATION){
- if(hasListener_){
- AllocationAction action =
- new AllocationAction(AllocationAction.GRIDLET_SCHEDULED, currentTime_);
- LinkedList<SSGridlet> list = new LinkedList<SSGridlet>();
- list.add(rgl);
- action.setSSGridlet(list);
- notifyListeners(action);
-
- if(GridSim.STEP_BY_STEP_SIMULATION){
- GridSim.pauseSimulation();
- }
- else if(GridSim.SLOW_MOTION_SIMULATION){
- GridSim.smallPause();
- }
- }
+ LinkedList<SSGridlet> list = new LinkedList<SSGridlet>();
+ list.add(sgl);
+ notifyListeners(AllocationAction.GRIDLET_SCHEDULED, true, lastActionTime_, list);
}
/////////////////////////////////////////////////////
@@ -226,7 +226,161 @@
);
}
}
+
+ /**
+ * Finds the status of a specified @link{Gridlet}.
+ * @param gridletId a Gridlet ID
+ * @param userId the user or owner's ID of this Gridlet
+ * @return the Gridlet status or <tt>-1</tt> if not found
+ * @see gridsim.Gridlet
+ * @pre gridletId > 0
+ * @pre userId > 0
+ * @post $none
+ */
+ public int gridletStatus(int gridletId,int userId){
+ SSGridlet sgl = null;
+
+ // Look for the Gridlet in the running queue
+ int index = findSSGridlet(runningGridlets_, gridletId, userId);
+ if (index >= 0) {
+ // Get the Gridlet from the execution list
+ sgl = runningGridlets_.get(index);
+ return sgl.getGridletStatus();
+ }
+
+ // Look for the gridlet in the waiting queue
+ index = findSSGridlet(queuedGridlets_, gridletId, userId);
+ if (index >= 0) {
+ // Get the Gridlet from the execution list
+ sgl = queuedGridlets_.get(index);
+ return sgl.getGridletStatus();
+ }
+
+ // if not found in all lists then report the Gridlet has not found
+ return -1;
+ }
+
+ /**
+ * 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, the availability
+ * profile is shifted forward. This process ensures that the Gridlets
+ * will not have an expected completion time worse than the one
+ * initially stipulated for the Gridlet. This process if known
+ * as the compression of the schedule. For more details please look
+ * at the references provided at the initial part of this documentation.<br>
+ * <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 both execution and paused list,
+ * then a <tt>null</tt> Gridlet will be send back to sender,
+ * i.e. the <tt>userId</tt>.
+ *
+ * <li> Once a Gridlet is cancelled, the availability profile is swept
+ * and Gridlets are moved forwards. The entries in the profile incurred
+ * by each Gridlet are updated and the new anchor for the Gridlet is found
+ * again. This process is repeated for each Gridlet. This guarantees that
+ * Gridlets will not have a time completion worse than those initially
+ * provided.
+ * </ul>
+ *
+ * @param gridletId a Gridlet ID
+ * @param userId the user or owner's ID of this Gridlet
+ * @pre gridletId > 0
+ * @pre userId > 0
+ * @post $none
+ */
+ public void gridletCancel(int gridletId, int userId){
+ double currentTime = GridSim.clock();
+ lastActionTime_ = currentTime; // set the time of the last allocation action
+ SSGridlet sgl = null; // stores the gridlet if found
+ boolean found = false;
+
+ // Look for the Gridlet in the running queue
+ int index = findSSGridlet(runningGridlets_, gridletId, userId);
+ if (index >= 0) {
+ found = true;
+
+ // Get the Gridlet from the execution list
+ sgl = runningGridlets_.get(index);
+
+ // if the Gridlet's finish time is smaller than the current
+ // time or the status is FINISHED, it means that the Gridlet
+ // has finished and will be 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.getGridletStatus() == Gridlet.SUCCESS ||
+ sgl.getGridletFinishTime() <= 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(index);
+ }
+ }
+
+ if(!found){
+ // Look for the gridlet in the waiting queue
+ index = findSSGridlet(queuedGridlets_, gridletId, userId);
+ if (index >= 0) {
+ found = true;
+
+ // Get the Gridlet from the waiting queue and
+ // remove from the queue before compressing the schedule
+ sgl = queuedGridlets_.remove(index);
+ }
+ }
+
+ // 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.resName_ + ".ParallelSpaceShared.gridletCancel():" +
+ " Cannot find Gridlet #" + gridletId + " for User #" + userId);
+ super.sendCancelGridlet(GridSimTags.GRIDLET_CANCEL, null, gridletId, userId);
+ return;
+ }
+ ////////////////////////// USED FOR DEBUGGING PURPOSES ONLY ///////////////////////
+
+ if(GridSim.DEBUG_SIMULATION){
+ // If a gridlet has been cancelled, then inform the listeners about it
+ LinkedList<SSGridlet> gridletsCancelled = new LinkedList<SSGridlet>();
+ gridletsCancelled.add(sgl);
+ this.notifyListeners(AllocationAction.GRIDLET_CANCELLED, true, lastActionTime_, gridletsCancelled);
+ }
+
+ ///////////////////////////////////////////////////////////////////////////////////
+
+ // compress the schedule, that is, moves the gridlets forwards
+ compressSchedule(sgl);
+
+ ////////////////////////// USED FOR DEBUGGING PURPOSES ONLY ///////////////////////
+
+ if(GridSim.DEBUG_SIMULATION){
+ // If a gridlet has been cancelled, then inform the listeners about it
+ this.notifyListeners(AllocationAction.SCHEDULE_CHANGED, true, lastActionTime_, null);
+ }
+
+ ///////////////////////////////////////////////////////////////////////////////////
+
+ // sends the Gridlet back to user
+ sgl.finalizeGridlet();
+ super.sendCancelGridlet(GridSimTags.GRIDLET_CANCEL, sgl.getGridlet(), gridletId, userId);
+ }
+
+ // -------------------- PRIVATE METHODS ----------------------------
+
/**
* Update the information about the jobs scheduled
* @param rgl the resource gridlet
@@ -235,48 +389,51 @@
int reqPE = sgl.getNumPE();
// calculate the execution time of the Gridlet
- double executionTime =
- forecastExecutionTime(ratingPE_, sgl.getRemainingGridletLength()) + 1;
+ double executionTime = forecastExecutionTime(ratingPE_, sgl.getRemainingGridletLength());
+ lastActionTime_ = GridSim.clock(); // keep the time of the last allocation action
- this.currentTime_ = GridSim.clock();
+ double startTime = -1; // keeps the potential start time of the gridlet
+ double finishTime = -1; // stores the gridlet's expected finish time
+ int anchorIndex = -1; // the anchor index, the entry in the profile where the gridlet will be placed
+ int tailIndex = -1; // insert index represents the position in the profile where
+ // the entry corresponding to the gridlet's finish time will be placed
+ ProfileEntry tailEntry = null; // a pointer to the last entry analysed while scanning the profile
+ ProfileEntry anchorEntry = null; // a pointer to the anchor entry
- double startTime = -1;
- double finishTime = -1;
- int anchorIndex = -1;
- int tailIndex = -1;
- ProfileEntry tailEntry = null;
- ProfileEntry anchorEntry = null;
-
- AvailabilityProfile clonedProfile = availProfile_.clone();
PERangeList intersectList = null;
-
- for(ProfileEntry entry : availProfile_){
+ int length = availProfile_.size();
+
+ Iterator<ProfileEntry> iterProfile = availProfile_.iterator();
+ while(iterProfile.hasNext()){
+ ProfileEntry entry = iterProfile.next();
anchorEntry = entry;
anchorIndex = availProfile_.indexOf(anchorEntry);
tailEntry = entry;
- startTime = entry.getTime();
- finishTime = startTime + executionTime;
+ startTime = entry.getTime(); // sets the start time as the time of the entry
+ finishTime = startTime + executionTime; // calculates when the finish time would be if
+ // the gridlet is put in this position
- if(entry.getNumPE() < reqPE) {
+ // scan the profile until an entry with enough PEs is found
+ if(entry.getNumPE() < reqPE) {
continue;
}
else {
+ // 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();
- int length = clonedProfile.size();
// Look for the intersection of available ranges from
// the anchor until the end of the profile or until
// the entries and further than the expected completion time
for(int i=anchorIndex+1; i<length; i++){
- ProfileEntry nextEntry = clonedProfile.get(i);
+ ProfileEntry nextEntry = availProfile_.get(i);
if(nextEntry.getTime() > finishTime){
break;
}
else{
- intersectList =
- PERangeList.intersection(intersectList, nextEntry.getPERanges());
-
+ intersectList = PERangeList.intersection(intersectList, nextEntry.getPERanges());
if(intersectList == null || intersectList.getNumPE() < reqPE){
break;
}
@@ -285,40 +442,52 @@
}
}
}
- // If a time slot with enough PEs has been found,
- // then stop the search
+ // If a time slot with enough PEs has been found, then stop the search
if(intersectList != null && intersectList.getNumPE() >= reqPE){
break;
}
}
}
+ // Increase the number of gridlets that rely on the anchor point to
+ // either mark their termination time or anchor
+ anchorEntry.increaseGridlet();
+
anchorIndex = availProfile_.indexOf(anchorEntry);
tailIndex = availProfile_.indexOf(tailEntry);
// Selects a range to be used by the Gridlet
PERangeList selected = selectPERangeList(reqPE, intersectList);
- // Creates a new entry to be added to the profile
- ProfileEntry newEntry = new ProfileEntry(finishTime);
- newEntry.setPERangeList(tailEntry.getPERanges().clone());
- availProfile_.add(tailIndex+1, newEntry);
+ // If the time of the last entry analysed is equals to the Gridlet
+ // expected finish time, then a new entry is not needed.
+ if(tailEntry.getTime() < finishTime){
+ // Creates a new entry to be added to the profile
+ ProfileEntry newEntry = new ProfileEntry(finishTime);
+ newEntry.setPERangeList(tailEntry.getPERanges().clone());
+ availProfile_.add(tailIndex+1, newEntry);
+ }
+ else{
+ // increase the number of gridlets that use this gridlet to
+ // mark their completion time
+ tailEntry.increaseGridlet();
+ }
// updates the entries between anchor and tail
for(int index=anchorIndex; index<=tailIndex; index++){
ProfileEntry entry = availProfile_.get(index);
+ if(entry.getTime() == finishTime){
+ break;
+ }
PERangeList updList = PERangeList.difference(entry.getPERanges(), selected);
entry.setPERangeList(updList);
}
- // add this Gridlet into execution list
- this.queuedGridlets_.add(sgl);
-
// Sets the list of ranges used by the gridlet
sgl.setPERangeList(selected);
// change Gridlet status
- sgl.setGridletStatus(Gridlet.QUEUED);
+ sgl.setGridletStatus(Gridlet.QUEUED);
sgl.setGridletPotentialStartTime(startTime);
sgl.setFinishTime(finishTime);
@@ -333,7 +502,7 @@
* @pre rgl != null
* @post $none
*/
- private boolean scheduleJobImmediately(SSGridlet sgl) {
+ private boolean scheduleGridletImmediately(SSGridlet sgl) {
int reqPE = sgl.getNumPE();
// calculate the execution time of the Gridlet
@@ -342,45 +511,51 @@
// calculates how much ahead to look into the availability profile
double currentTime = GridSim.clock() ;
- double finishTime = currentTime + executionTime;
+ double finishTime = currentTime + executionTime; // the Gridlet's expected finish time
+ lastActionTime_ = currentTime; // keep the time of the last allocation action
- this.currentTime_ = currentTime;
+ // freePERanges_ does not need to be clonned here as the
+ // PERangeList.intersection() method will create a new list of ranges
+ // with the intersection anyway
+ PERangeList intersectList = freePERanges_;
+ ProfileEntry closeGrlTail = null;
+ int insertIndex = -1; // this denotes where the new entry (if needed) will be added
- PERangeList intersectList = freePERanges_.clone();
- ProfileEntry closeGrlTail = null;
- int tailIndex = -1;
-
+ // scan the availability profile until the expected termination
+ // of the Gridlet to check whether enough resources will be available
+ // for the Gridlet. Stop the search if not enough resources are available
for(ProfileEntry entry : availProfile_){
double entryTime = entry.getTime();
if(entryTime < currentTime) {
continue;
}
- else if(entryTime >= finishTime) {
+ else if(entryTime > finishTime) {
break;
}
else{
closeGrlTail = entry;
- tailIndex = availProfile_.indexOf(entry);
+ insertIndex = availProfile_.indexOf(entry);
PERangeList listEntry = entry.getPERanges();
intersectList = PERangeList.intersection(listEntry, intersectList);
}
}
-
- tailIndex++;
-
- // if the number of PEs available over the time slot is smaller
+
+ // if the number of PEs available over the time slot is smaller
// than the number of PEs required, then the gridlet cannot be started
if(intersectList == null || intersectList.getNumPE() < reqPE){
return false;
}
- // Selects a list of ranges to be used by the Gridlet
+ // increment the index. That is, last entry before finish time + 1
+ insertIndex++;
+
+ // Select a list of ranges to be used by the Gridlet
PERangeList selected = selectPERangeList(reqPE, intersectList);
- if(selected.size() == 0){
+ if(selected.getNumPE() < reqPE){
return false;
}
-
- // add the information to the usageProfile
+
+ // Gathers the information should be added in the insertIndex
PERangeList listCloseGrlTail = null;
if(closeGrlTail == null){
listCloseGrlTail = freePERanges_.clone();
@@ -388,28 +563,45 @@
else{
listCloseGrlTail = closeGrlTail.getPERanges().clone();
}
-
+
+ // if the time of the entry at insertIndex - 1 is equals to
+ // the gridlet finish time, then a new entry in the profile
+ // is not needed. In this case, the entry at insertIndex - 1
+ // is updated to show that one more gridlet relies on the entry
+ // to represent its completion time. This reduces the number of
+ // entries in the availability profile
+ boolean addNewEntry = true;
+
// Updates entries in the profile
- for(int index=0; index<tailIndex; index++){
+ for(int index=0; index<insertIndex; index++){
ProfileEntry entry = availProfile_.get(index);
if(entry.getTime() < currentTime){
continue;
}
+ // if an entry whose time is equals to the gridlet's completion
+ // is found, then stop the update and sets addNewEntry to true
+ else if(entry.getTime() == finishTime){
+ entry.increaseGridlet();
+ addNewEntry = false;
+ break;
+ }
PERangeList uptList = PERangeList.difference(entry.getPERanges(), selected);
entry.setPERangeList(uptList);
}
-
- // subtracts the selected ranges from the free ranges
+
+ // subtracts the selected ranges from the free ranges
freePERanges_ = PERangeList.difference(freePERanges_, selected);
-
- // Creates a new entry to be added to the profile
- ProfileEntry newEntry = new ProfileEntry(finishTime);
- newEntry.setPERangeList(listCloseGrlTail);
- availProfile_.add(tailIndex, newEntry);
-
+ // If a new entry is required, then add it.
+ if(addNewEntry){
+ // Creates a new entry to be added to the profile
+ ProfileEntry newEntry = new ProfileEntry(finishTime);
+ newEntry.setPERangeList(listCloseGrlTail);
+ availProfile_.add(insertIndex, newEntry);
+ }
+
// add this Gridlet into execution list
- this.runningGridlets_.add(sgl);
+ runningGridlets_.add(sgl);
sgl.setGridletPotentialStartTime(currentTime);
sgl.setFinishTime(finishTime);
@@ -432,29 +624,30 @@
* availability profile.
*/
private void updateSchedule(){
+
double currentTime = GridSim.clock();
- this.currentTime_ = currentTime;
+ lastActionTime_ = currentTime;
// removes all Gridlets that have already completed from
// the queue of running Gridlets
PERangeList releasedRanges = new PERangeList();
- LinkedList<SSGridlet> completedGridlets = new LinkedList<SSGridlet>();
+ LinkedList<SSGridlet> grlsCompleted = new LinkedList<SSGridlet>();
for(SSGridlet gridlet : runningGridlets_){
- if(gridlet.getGridletFinishTime() <= currentTime &&
- gridlet.getGridletStatus() != Gridlet.SUCCESS &&
- gridlet.getGridletStatus() != Gridlet.FAILED){
+ // as gridlets are removed from running queue once they finish
+ // time is smaller than current time, then testing the time
+ // is enough. There's no need to check status
+ if(gridlet.getGridletFinishTime() <= currentTime) {
// Update the list of ranges released
releasedRanges.addAll(gridlet.getPERangeList().clone());
- completedGridlets.add(gridlet);
+ grlsCompleted.add(gridlet);
gridletFinish(gridlet, Gridlet.SUCCESS);
}
}
-// runningGridlets_.removeAll(grlToRemove);
-
- freePERanges_ = (freePERanges_ == null) ? new PERangeList() : freePERanges_.clone();
+
+ if(freePERanges_ == null)
+ freePERanges_ = new PERangeList();
freePERanges_.addAll(releasedRanges);
- freePERanges_.sortRanges();
- freePERanges_.consolidatePERanges();
+ freePERanges_.mergePERanges();
// Updates the usage profile
LinkedList<ProfileEntry> entToRemove = new LinkedList<ProfileEntry>();
@@ -471,13 +664,13 @@
// Start the execution of Gridlets that are queued and whose
// potential start execution time is smaller than current time
PERangeList allocatedRanges = new PERangeList();
- LinkedList<SSGridlet> grlToRemove = new LinkedList<SSGridlet>();
+ LinkedList<SSGridlet> grlsToStart = new LinkedList<SSGridlet>();
for(SSGridlet gridlet : queuedGridlets_){
if(gridlet.getGridletPotentialStartTime() <= currentTime){
// Update the list of ranges allocated
allocatedRanges.addAll(gridlet.getPERangeList());
runningGridlets_.add(gridlet);
- grlToRemove.add(gridlet);
+ grlsToStart.add(gridlet);
// change Gridlet status
gridlet.setGridletStatus(Gridlet.INEXEC);
@@ -485,28 +678,24 @@
super.sendInternalEvent(roundUpTime);
}
}
- queuedGridlets_.removeAll(grlToRemove);
- freePERanges_ = PERangeList.difference(freePERanges_.clone(), allocatedRanges);
+ queuedGridlets_.removeAll(grlsToStart);
+ freePERanges_ = PERangeList.difference(freePERanges_, allocatedRanges);
////////////////////////// USED FOR DEBUGGING PURPOSES ONLY ///////////////////////
if(GridSim.DEBUG_SIMULATION){
- if(hasListener_){
- AllocationAction action =
- new AllocationAction(AllocationAction.GRIDLET_COMPLETED, currentTime_);
- action.setSSGridlet(completedGridlets);
- notifyListeners(action);
-
- if(GridSim.STEP_BY_STEP_SIMULATION){
- GridSim.pauseSimulation();
- }
- else if(GridSim.SLOW_MOTION_SIMULATION){
- GridSim.smallPause();
- }
+ // If a gridlet has started execution or one has finished,
+ // then inform the listeners
+ if(grlsToStart.size() > 0 || grlsCompleted.size() > 0){
+ notifyListeners(AllocationAction.GRIDLET_COMPLETED, true, lastActionTime_, grlsCompleted);
}
}
-
+
///////////////////////////////////////////////////////////////////////////////////
+
+ // finally, remove the gridlets from the running queue
+ runningGridlets_.removeAll(grlsCompleted);
+
}
/**
@@ -516,7 +705,7 @@
* @param status the Gridlet status
*/
private void gridletFinish(SSGridlet sgl, int status) {
- // the order is important! Set the status first then finalize
+ // the order is important! Set the status first then finalise
// due to timing issues in SSGridlet class
sgl.setGridletStatus(status);
sgl.finalizeGridlet();
@@ -534,25 +723,25 @@
private PERangeList selectPERangeList(int reqPE, PERangeList freeList){
PERangeList selected = new PERangeList();
try{
- freeList.sortRanges();
+ freeList.sortRanges();
- for(PERange range: freeList){
- if(range.getNumPE() >= reqPE){
- int beginning = range.getBeginning();
- int end = beginning + reqPE - 1;
- selected.add(new PERange(beginning, end));
- break;
- }
- else{
- selected.add(range);
- reqPE -= range.getNumPE();
- }
- }
- }
+ for(PERange range: freeList){
+ if(range.getNumPE() >= reqPE){
+ int beginning = range.getBeginning();
+ int end = beginning + reqPE - 1;
+ selected.add(new PERange(beginning, end));
+ break;
+ }
+ else{
+ selected.add(range.clone());
+ reqPE -= range.getNumPE();
+ }
+ }
+ }
catch(NullPointerException ex){
ex.printStackTrace();
- System.out.println("selectPERangeList(): Exception. Number of PEs required = " + reqPE);
- System.out.println(availProfile_);
+ System.out.println("selectPERangeList(): Exception. Number of PEs required# " + reqPE +
+ "\n Profile# " + availProfile_);
}
return selected;
}
@@ -582,34 +771,223 @@
/**
* Notifies the listeners about the action performed
- * @param action the action performed
+ * @param allocationAction the action performed
+ * @param shouldPause indicates whether the simulation should be paused after
+ * notifying the listeners. <tt>true</tt> indicates that it should pause and
+ * <tt>false</tt> means that it should not.
+ * @param time the time when the action took place
+ * @param gridletList the list of gridlets to provide to the listeners
+ *
+ * @see AllocationAction#GRIDLET_ARRIVED
+ * @see AllocationAction#GRIDLET_SCHEDULED
+ * @see AllocationAction#GRIDLET_CANCELLED
+ * @see AllocationAction#GRIDLET_COMPLETED
+ * @see AllocationAction#SCHEDULE_CHANGED
*/
- private void notifyListeners(AllocationAction action){
- for(AllocationListener listener : listeners_){
- listener.allocationActionPerformed(action);
+ private void notifyListeners(int allocationAction, boolean shouldPause,
+ double time, LinkedList<SSGridlet> gridletList){
+
+ if(hasListener_){
+ AllocationAction action = new AllocationAction(allocationAction, time);
+
+ if(gridletList != null)
+ action.setSSGridlet(gridletList);
+
+ for(AllocationListener listener : listeners_){
+ listener.allocationActionPerformed(action);
+ }
+
+ if(shouldPause){
+ if(GridSim.STEP_BY_STEP_SIMULATION){
+ GridSim.pauseSimulation();
+ }
+ else if(GridSim.SLOW_MOTION_SIMULATION){
+ GridSim.smallPause();
+ }
+ }
}
}
/**
- * Finds the status of a specified @link{Gridlet}.
- * @param gridletId a Gridlet ID
- * @param userId the user or owner's ID of this Gridlet
- * @return the Gridlet status or <tt>-1</tt> if not found
- * @see gridsim.Gridlet
+ * Finds a Gridlet inside a given list. This method needs a combinati...
[truncated message content] |
