Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [62] branches/gridsim4.0-branch3/source/gridsim/ ParallelSpaceShared.java
|
From: <mar...@us...> - 2007-09-19 01:32:25
|
Revision: 62
http://gridsim.svn.sourceforge.net/gridsim/?rev=62&view=rev
Author: marcos_dias
Date: 2007-09-18 18:32:28 -0700 (Tue, 18 Sep 2007)
Log Message:
-----------
Small changes in comments have been made to make it easier to understand the resource allocation policy.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/ParallelSpaceShared.java
Modified: branches/gridsim4.0-branch3/source/gridsim/ParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/ParallelSpaceShared.java 2007-09-18 04:17:27 UTC (rev 61)
+++ branches/gridsim4.0-branch3/source/gridsim/ParallelSpaceShared.java 2007-09-19 01:32:28 UTC (rev 62)
@@ -12,13 +12,10 @@
import eduni.simjava.Sim_system;
import gridsim.gui.AllocationAction;
import gridsim.gui.AllocationListener;
-//import examples.workload.parallel.Visualizer;
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;
@@ -40,7 +37,7 @@
* <b>LIMITATIONS:</b><br>
* <ul>
* <li> The list of machines comprising this resource must be homogeneous.
- * <li> Local load is not considered. If would like to simulate this, you have to
+ * <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.
* <li> Gridlets cannot be paused nor migrated.
* </ul>
@@ -57,17 +54,17 @@
public class ParallelSpaceShared extends AllocPolicy {
- 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
- private AvailabilityProfile availProfile_; // a list containing the availability of PEs
- private PERangeList freePERanges_; // the ranges of available PEs
+ 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
+ private AvailabilityProfile availProfile_; // a list containing the availability of PEs
+ private PERangeList freePERanges_; // the ranges of currently available PEs
- // FOR DEBUGGING PURPOSES ONLY...
- private ArrayList<AllocationListener> listeners_; // the listeners interested in this policy
- private boolean hasListener_; // indicates whether there are listeners registered
- private double lastActionTime_; // Keep the time of last relevant allocation action
+ // FOR DEBUGGING PURPOSES ONLY
+ private ArrayList<AllocationListener> listeners_; // the listeners interested in this policy
+ private boolean hasListener_; // indicates whether there are listeners registered
+ private double lastActionTime_; // Keep the time of the last allocation action
/**
* Allocates a new @link{ParallelSpaceShared} object
@@ -83,7 +80,6 @@
* 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 machines that are part of this resource are not homogeneous.
* </ul>
* @see gridsim.GridSim#init(int, Calendar, boolean,
* String[], String[], String)
@@ -149,9 +145,9 @@
/**
* Schedules a new @link{Gridlet} received by the GridResource entity.
- * @param gridletl a Gridlet object to be executed
+ * @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 success or not, <tt>false</tt> otherwise.
+ * whether this operation is successful or not, <tt>false</tt> otherwise.
*/
public void gridletSubmit(Gridlet gridlet, boolean ack) {
int reqPE = gridlet.getNumPE();
@@ -265,7 +261,7 @@
* 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
+ * profile is shifted forwards. 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
@@ -281,11 +277,11 @@
* 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,
+ * <li> If a Gridlet cannot be found in either 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
+ * <li> Once a Gridlet is cancelled, the availability profile is scanned
* 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
@@ -315,8 +311,8 @@
// 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,
+ // 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.getGridletStatus() == Gridlet.SUCCESS ||
sgl.getGridletFinishTime() <= currentTime){
@@ -368,7 +364,7 @@
////////////////////////// USED FOR DEBUGGING PURPOSES ONLY ///////////////////////
if(GridSim.DEBUG_SIMULATION){
- // If a gridlet has been cancelled, then inform the listeners about it
+ // Inform the listeners about the new schedule
this.notifyListeners(AllocationAction.SCHEDULE_CHANGED, true, lastActionTime_, null);
}
@@ -383,7 +379,7 @@
/**
* Update the information about the jobs scheduled
- * @param rgl the resource gridlet
+ * @param sgl the resource gridlet
*/
private void findAnchorPoint(SSGridlet sgl){
int reqPE = sgl.getNumPE();
@@ -392,11 +388,12 @@
double executionTime = forecastExecutionTime(ratingPE_, sgl.getRemainingGridletLength());
lastActionTime_ = GridSim.clock(); // keep the time of the last allocation action
- 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
+ double startTime = -1; // keep the potential start time of the gridlet
+ double finishTime = -1; // store 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 after which 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
@@ -411,8 +408,8 @@
tailEntry = entry;
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
+ finishTime = startTime + executionTime; // calculates when the finish time will be if
+ // the gridlet is put at this position
// scan the profile until an entry with enough PEs is found
if(entry.getNumPE() < reqPE) {
@@ -426,7 +423,7 @@
// 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
+ // the entries are further than the expected completion time
for(int i=anchorIndex+1; i<length; i++){
ProfileEntry nextEntry = availProfile_.get(i);
if(nextEntry.getTime() > finishTime){
@@ -450,17 +447,17 @@
}
// Increase the number of gridlets that rely on the anchor point to
- // either mark their termination time or anchor
+ // either mark their termination time or start time
anchorEntry.increaseGridlet();
anchorIndex = availProfile_.indexOf(anchorEntry);
tailIndex = availProfile_.indexOf(tailEntry);
- // Selects a range to be used by the Gridlet
+ // Selects a list of ranges to be used by the Gridlet
PERangeList selected = selectPERangeList(reqPE, intersectList);
- // If the time of the last entry analysed is equals to the Gridlet
- // expected finish time, then a new entry is not needed.
+ // If the time of the last entry analysed is smaller than the Gridlet
+ // expected finish time, then a new entry is needed.
if(tailEntry.getTime() < finishTime){
// Creates a new entry to be added to the profile
ProfileEntry newEntry = new ProfileEntry(finishTime);
@@ -473,7 +470,7 @@
tailEntry.increaseGridlet();
}
- // updates the entries between anchor and tail
+ // update the entries from anchor to (tail OR tail-1)
for(int index=anchorIndex; index<=tailIndex; index++){
ProfileEntry entry = availProfile_.get(index);
if(entry.getTime() == finishTime){
@@ -483,23 +480,22 @@
entry.setPERangeList(updList);
}
- // Sets the list of ranges used by the gridlet
+ // Set the list of ranges used by the gridlet
sgl.setPERangeList(selected);
// change Gridlet status
sgl.setGridletStatus(Gridlet.QUEUED);
-
sgl.setGridletPotentialStartTime(startTime);
sgl.setFinishTime(finishTime);
}
/**
- * Allocates a Gridlet into free PEs and sets the Gridlet status into
- * INEXEC and PE status into busy afterwards
- * @param sgl a ResGridlet object
- * @return <tt>true</tt> if there is an empty PE to process this Gridlet,
+ * 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 rgl != null
+ * @pre sgl != null
* @post $none
*/
private boolean scheduleGridletImmediately(SSGridlet sgl) {
@@ -515,15 +511,15 @@
lastActionTime_ = currentTime; // keep the time of the last allocation action
// 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.intersection() and selectPERangeList() methods 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
// 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
+ // of the Gridlet to check whether enough PEs will be available
+ // for the Gridlet. Stop the search if not enough PEs are available
for(ProfileEntry entry : availProfile_){
double entryTime = entry.getTime();
if(entryTime < currentTime) {
@@ -546,7 +542,7 @@
return false;
}
- // increment the index. That is, last entry before finish time + 1
+ // increment the index. That is, (last entry before finish time + 1)
insertIndex++;
// Select a list of ranges to be used by the Gridlet
@@ -555,7 +551,7 @@
return false;
}
- // Gathers the information should be added in the insertIndex
+ // Gathers the information that must be added at insertIndex
PERangeList listCloseGrlTail = null;
if(closeGrlTail == null){
listCloseGrlTail = freePERanges_.clone();
@@ -564,15 +560,15 @@
listCloseGrlTail = closeGrlTail.getPERanges().clone();
}
- // if the time of the entry at insertIndex - 1 is equals to
+ // 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 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
+ // Update entries in the profile
for(int index=0; index<insertIndex; index++){
ProfileEntry entry = availProfile_.get(index);
if(entry.getTime() < currentTime){
@@ -589,10 +585,10 @@
entry.setPERangeList(uptList);
}
- // subtracts the selected ranges from the free ranges
+ // subtract the selected ranges from the currently free ranges
freePERanges_ = PERangeList.difference(freePERanges_, selected);
- // If a new entry is required, then add it.
+ // If a new entry is required, then add it to the profile
if(addNewEntry){
// Creates a new entry to be added to the profile
ProfileEntry newEntry = new ProfileEntry(finishTime);
@@ -611,24 +607,25 @@
// Sets the list of ranges used by the gridlet
sgl.setPERangeList(selected);
- // then send this into itself
+ // then send this event to itself to update the queues after
+ // this gridlet's completion time
int roundUpTime = (int)(executionTime + 1);
super.sendInternalEvent(roundUpTime);
return true;
}
/**
- * This method is called to update the schedule. It verifies
- * whether there are gridlets in the waiting list that should
- * start execution. It also removes old entries from the
- * availability profile.
+ * This method is called to update the schedule. It removes completed
+ * gridlets and return them to the users and verifies whether there are
+ * gridlets in the waiting list that should start execution. It also
+ * removes old entries from the availability profile.
*/
private void updateSchedule(){
double currentTime = GridSim.clock();
lastActionTime_ = currentTime;
- // removes all Gridlets that have already completed from
+ // remove all Gridlets that have already completed from
// the queue of running Gridlets
PERangeList releasedRanges = new PERangeList();
LinkedList<SSGridlet> grlsCompleted = new LinkedList<SSGridlet>();
@@ -644,12 +641,12 @@
}
}
- if(freePERanges_ == null)
+ if(freePERanges_ == null) // freePERanges_ can be null if all ranges are busy
freePERanges_ = new PERangeList();
freePERanges_.addAll(releasedRanges);
freePERanges_.mergePERanges();
- // Updates the usage profile
+ // Update the availability profile
LinkedList<ProfileEntry> entToRemove = new LinkedList<ProfileEntry>();
for(ProfileEntry entry : availProfile_){
if(entry.getTime() <= currentTime){
@@ -713,8 +710,8 @@
}
/**
- * Selects a range to be used by a Gridlet based on
- * the list of free ranges.
+ * Selects a range to be used by a Gridlet out of the list
+ * of free ranges provided.
* @param reqPE the number of PEs required.
* @param rangeList the list of free ranges.
* @return the range to be allocated or <tt>null</tt> if no
@@ -853,7 +850,7 @@
* a the given Gridlet.
* @param wasRunning indicates whether the gridlet was running.
* <tt>true</tt> indicates that it was running and <tt>false</tt> otherwise.
- * @param sgl the Gridlet whose entries have to be removed and updated
+ * @param sgl the Gridlet whose entries have to be removed or updated
*/
private void updateGridletEntriesAtProfile(boolean wasRunning, SSGridlet sgl){
@@ -869,9 +866,10 @@
// if the Gridlet was running, then update the range of PEs currently
// available and set the reference time as current simulation time
if(wasRunning) {
- // returns the ranges to the list of free ranges
- // sorts it, and consolidates the ranges to avoid fragments
- // As freePERanges_, make sure that it is not null before adds the ranges back to it
+ // returns the ranges to the list of free ranges and consolidates
+ // the ranges to avoid fragments. As freePERanges_ can be null if
+ // all ranges are busy, make sure that it is not null before adding
+ // the ranges back to it
if(freePERanges_ == null)
freePERanges_ = new PERangeList();
@@ -903,6 +901,9 @@
}
break;
}
+ // if the entry is the gridlet's anchor point, then decrease the number of gridlets
+ // that rely on this entry to either mark their start time or completion time. If the
+ // number of Gridlets is 0 then, the entry is removed from the profile
if(entryTime == startTime) {
entry.decreaseGridlet();
if(entry.getNumGridlets() == 0){
@@ -911,9 +912,9 @@
}
}
// returns the ranges to the list of free ranges in the entry,
- // sorts it, and consolidates the ranges to avoid fragments
+ // and consolidates the ranges to avoid fragments
// As the list may be null, make sure that the list will not be
- // null or empty so the released ranges can be added back to it
+ // null so the released ranges can be added back to it
PERangeList listEntry = entry.getPERanges();
if(listEntry == null){
listEntry = new PERangeList();
@@ -928,9 +929,9 @@
/**
* This method performs the compression of the schedule and availability profile.
- * That means that the Gridlet is removed from the queue and the entries in the profile
- * are then updated. Once the gridlet is removed, the method remove a Gridlet from
- * the queue, updates the entries and then tries to reinsert the gridlet in the queue.
+ * That means that the Gridlet is removed from the queue and its entries in the profile
+ * are then updated. Once the gridlet is removed, the method selects a Gridlet from
+ * the queue, updates the entries and then tries to reinsert the gridlet in the profile.
* In the worst case, the Gridlet will be put back in the same place.<br>
* <b>NOTE:</b>
* <ul>
@@ -974,7 +975,8 @@
updateGridletEntriesAtProfile(false, queuedSgl);
- // Now try to either schedule or reinsert the gridlet in the waiting queue
+ // Now try to either schedule the gridlet immediately or
+ // find the new anchor point
boolean success = false;
if(wasRunning){
success = scheduleGridletImmediately(queuedSgl);
@@ -1069,8 +1071,8 @@
}
/**
- * This class represents an entry in the usage profile. There is an entry
- * in the usage profile for each job scheduled by this policy.
+ * This class represents an entry in the usage profile. There is an entry
+ * at most in the usage profile for each job scheduled by this policy.
*
* @author Marcos Dias de Assuncao
* @since GridSim Turbo Alpha 0.1
@@ -1108,7 +1110,7 @@
/**
* Clears the list of PE ranges
*/
- public void clearPERange(){
+ public void clearPERangeList(){
ranges_.clear();
}
@@ -1179,7 +1181,6 @@
* @since GridSim Turbo Alpha 0.1
*/
class AvailabilityProfile extends LinkedList<ProfileEntry>{
- private OrderProfileByTimeAsc comparatorProfile_; // To order the profile in order of time
private static final long serialVersionUID = -1853610061073508770L;
@@ -1188,19 +1189,11 @@
*/
public AvailabilityProfile(){
super();
- comparatorProfile_ = new OrderProfileByTimeAsc();
}
/**
- * Sorts the availability profile by event times.
- */
- public void sortAvailabilityProfile(){
- Collections.sort(this, comparatorProfile_);
- }
-
- /**
* Returns a clone of this object.<br>
- * Note that this method does not clone the entries
+ * <b>NOTE:</b> this method does not clone the entries
* @return the cloned object
*/
public AvailabilityProfile clone(){
@@ -1225,42 +1218,4 @@
}
}
-
- /**
- * Orders the usage profile by time
- *
- * @author Marcos Dias de Assuncao
- * @since GridSim Turbo Alpha 0.1
- */
- class OrderProfileByTimeAsc implements Comparator<ProfileEntry>{
-
- /**
- * Creates a new @{link OrderProfileByTimeAsc} object.
- */
- public OrderProfileByTimeAsc(){
- super();
- }
-
- /*
- * (non-Javadoc)
- * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object)
- */
- public int compare(ProfileEntry entrya, ProfileEntry entryb){
- if (entrya == null && entryb == null) {
- return -1;
- } else if (entryb == null) {
- return 1;
- } else if (entrya == null) {
- return 0;
- } else {
-
- // obtain the time corresponding time of the events
- Double timea = entrya.getTime();
- Double timeb = entryb.getTime();
-
- return timea.compareTo(timeb);
-
- } // end else
- }
- }
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
