Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [104] branches/gridsim4.0-branch3
|
From: <mar...@us...> - 2008-02-15 07:03:55
|
Revision: 104
http://gridsim.svn.sourceforge.net/gridsim/?rev=104&view=rev
Author: marcos_dias
Date: 2008-02-14 23:03:53 -0800 (Thu, 14 Feb 2008)
Log Message:
-----------
Implementation of priorities in the multiple queue policy.
Modified Paths:
--------------
branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues02.java
branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/MultipleEasyBackfillingQueues.java
branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java
branches/gridsim4.0-branch3/source/gridsim/turbo/SSReservation.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ScheduleItem.java
Modified: branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues02.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues02.java 2008-02-15 04:13:00 UTC (rev 103)
+++ branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExampleMultiEBQueues02.java 2008-02-15 07:03:53 UTC (rev 104)
@@ -89,10 +89,10 @@
//////////////////////////////////////////
// Starts the simulation in debug mode
- GridSim.startGridSimulation(true);
+// GridSim.startGridSimulation(true);
// Start the simulation in normal mode
-// GridSim.startGridSimulation();
+ GridSim.startGridSimulation();
//////////////////////////////////////////
// Final step: Prints the Gridlets when simulation is over
@@ -150,18 +150,20 @@
MultipleEasyBackfillingQueues policy = null;
try {
- policy = new MultipleEasyBackfillingQueues(name, "Policy", 2);
+ policy = new MultipleEasyBackfillingQueues(name, "Policy", 3);
} catch (Exception e1) {
e1.printStackTrace();
}
- // creates two partitions, one for small jobs and another for long jobs
- // assign the same number of PEs to both
- QueuePredicateExample pred1 = new QueuePredicateExample(0, 10000, peRating);
- QueuePredicateExample pred2 = new QueuePredicateExample(10000, Integer.MAX_VALUE, peRating);
+ // creates three partitions, one for small jobs, one for medium size jobs
+ // and another for long jobs
+ QueuePredicateExample express = new QueuePredicateExample(0, 1000, peRating);
+ QueuePredicateExample medium = new QueuePredicateExample(1000, 10000, peRating);
+ QueuePredicateExample large = new QueuePredicateExample(10000, Integer.MAX_VALUE, peRating);
- policy.createPartition(0, resConfig.getNumPE() / 2, pred1);
- policy.createPartition(1, resConfig.getNumPE() / 2, pred2);
+ policy.createPartition(0, resConfig.getNumPE() / 3, express);
+ policy.createPartition(1, resConfig.getNumPE() / 3, medium);
+ policy.createPartition(2, resConfig.getNumPE() / 3, large);
//////////////////////////////////////////
// 6. Finally, we need to create a GridResource object.
@@ -197,6 +199,12 @@
}
} // end class
+/**
+ * Example of queue predicate. This predicate filters
+ * gridlets according to their runtime
+ *
+ * @author Marcos Dias de Assuncao
+ */
class QueuePredicateExample implements QueuePartitionPredicate {
int minRuntime_;
int maxRuntime_;
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-02-15 04:13:00 UTC (rev 103)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-02-15 07:03:53 UTC (rev 104)
@@ -783,7 +783,7 @@
// if the above method returns null, it means that there are not enough
// PEs to serve the reservation or Gridlet
- if(availObj == null){
+ if(availObj == null) {
return false;
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/MultipleEasyBackfillingQueues.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/MultipleEasyBackfillingQueues.java 2008-02-15 04:13:00 UTC (rev 103)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/MultipleEasyBackfillingQueues.java 2008-02-15 07:03:53 UTC (rev 104)
@@ -18,6 +18,8 @@
import java.util.ArrayList;
import java.util.Calendar;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
@@ -52,11 +54,8 @@
* <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. This could be
- * easily done, but due to time constraints, I could not
- * implement these features.
- * <li> This policy still neither supports priorities nor advance
- * reservation.
+ * <li> Gridlets cannot be paused nor migrated.
+ * <li> This policy does not support advance reservations.
* </ul>
*
* @author Marcos Dias de Assuncao
@@ -94,13 +93,16 @@
// the last time when the schedule updated was called
private double lastScheduleUpdate_;
+ // to order the gridlets according to their priorities and submission times
+ private OrderGridletsByPriority orderByPriority_;
+
// a tag to indicate that a gridlet has finished
private static final int UPDATE_SCHEDULE_TAG = 10;
// a constant that denotes an unknown value
private static final int UNKNOWN = -1;
- /**
+ /**
* Allocates a new <tt>MultiEasyBackfillingQueues</tt> object.
* If the policy is create with only one partition, it will then work as
* a normal aggressive (EASY) backfilling scheduler.
@@ -136,6 +138,7 @@
// initialises local data structure
runningGridlets_ = new LinkedList<SSGridlet>();
queuedGridlets_ = new LinkedList<SSGridlet>();
+ orderByPriority_ = new OrderGridletsByPriority();
numPartitions_ = numPartitions;
profile_ = new MultiPartitionProfile();
lastScheduleUpdate_ = 0.0D;
@@ -337,6 +340,9 @@
if(!success) {
scheduleGridlet(sgl);
queuedGridlets_.add(sgl);
+
+ // order gridlets according to their priorities
+ Collections.sort(queuedGridlets_, orderByPriority_);
}
//------------------ FOR DEBUGGING PURPOSES ONLY ----------------
@@ -365,7 +371,7 @@
* @pre userId > 0
* @post $none
*/
- public int gridletStatus(int gridletId,int userId){
+ public int gridletStatus(int gridletId, int userId) {
return UNKNOWN;
}
@@ -537,7 +543,18 @@
// if queue has a pivot already, then just add
// the job to the waiting queue
if(queue.pivot_ != null) {
- return false;
+ // checks whether the priority of the pivot is lower than the
+ // job being considered for scheduling.
+ // If priority of pivot is higher or equals to sgl's, then do not
+ // make any change
+ if(queue.pivot_.getPriority() >= sgl.getPriority())
+ return false;
+ else {
+ profile_.updateEntriesAtProfile(queue.pivot_);
+ queue.pivot_.setStartTime(-1);
+ queue.pivot_.setFinishTime(-1);
+ queue.pivot_ = null;
+ }
}
PERangeList ranges = null;
@@ -1696,6 +1713,103 @@
}
}
}
+
+ /**
+ * This method removes/updates the entries from the profile
+ * corresponding to a the given Gridlet or advance reservation.
+ * @param removedItem the Gridlet or advance reservation whose entries
+ * have to be removed or updated
+ */
+ protected void updateEntriesAtProfile(ScheduleItem removedItem) {
+
+ int partitionId = removedItem.getPartitionID();
+
+ // ranges of PEs used by the Gridlet
+ PERangeList allocatedRanges = removedItem.getPERangeList();
+
+ // the reference time used to update the entries in the profile
+ double startTime = removedItem.getStartTime();
+
+ // the entries between reference time and endTime must be updated
+ double finishTime = removedItem.getFinishTime();
+
+ // transfer the PEs back to the queue
+ transferPEs(partitionId, allocatedRanges, startTime, finishTime);
+
+ ProfileEntry entry = getPrecedingEntry(startTime);
+ if(entry.getTime() == startTime) {
+ entry.decreaseGridlet();
+ if(entry.getNumGridlets() == 0)
+ super.remove(entry);
+ }
+
+ entry = getPrecedingEntry(finishTime);
+ if(entry.getTime() == startTime) {
+ entry.decreaseGridlet();
+ if(entry.getNumGridlets() == 0)
+ super.remove(entry);
+ }
+
+// // 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
+// resource_.setPEsAvailable(allocatedRanges);
+// }
+//
+// Iterator<ProfileEntry> iterProfile = super.iterator();
+// while(iterProfile.hasNext()) {
+// ProfileEntry entry = iterProfile.next();
+//
+// double entryTime = entry.getTime();
+// if(entryTime < startTime) {
+// continue;
+// }
+// else if(entryTime > finishTime) {
+// break;
+// }
+// else{
+// if(entryTime == finishTime) {
+// // if the entry is equals to the finish time of the
+// // gridlet, then it means that the gridlet uses this entry
+// // to mark its termination. Therefore, it decreases the
+// // number of gridlets that rely on this entry to mark
+// // the finish time. If the number of gridlets is 0, it
+// // means that the entry can be deleted because it is
+// // not needed anymore
+// entry.decreaseGridlet();
+// if(entry.getNumGridlets() == 0) {
+// iterProfile.remove();
+// }
+// continue;
+// }
+// // 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) {
+// iterProfile.remove();
+// continue;
+// }
+// }
+// // returns the ranges to the list of free ranges in
+// // the entry, and consolidates the ranges to avoid fragments
+// // As the list may be null, make sure that the list will not be
+// // null so the released ranges can be added back to it
+// PERangeList listEntry = entry.getPERanges(partitionId);
+// if(listEntry == null){
+// listEntry = new PERangeList();
+// }
+//
+// listEntry.addAll(allocatedRanges.clone());
+// listEntry.mergePERanges();
+// entry.setPERangeList(partitionId, listEntry);
+// }
+// }
+ }
/**
* Creates an string representation of the profile
@@ -1710,4 +1824,26 @@
return result;
}
}
+
+ /**
+ * Comparator to order jobs according to their priorities
+ * and start time
+ * @author Marcos Dias de Assuncao
+ */
+ private class OrderGridletsByPriority implements Comparator<SSGridlet> {
+
+ public int compare(SSGridlet gl0, SSGridlet gl1) {
+ int result;
+ Integer priority0 = gl0.getPriority();
+ Integer priority1 = gl1.getPriority();
+ result = priority0.compareTo(priority1);
+
+ if(result == 0) {
+ Double submission0 = gl0.getSubmissionTime();
+ Double submission1 = gl1.getSubmissionTime();
+ result = submission0.compareTo(submission1);
+ }
+ return result;
+ }
+ }
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java 2008-02-15 04:13:00 UTC (rev 103)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/SSGridlet.java 2008-02-15 07:03:53 UTC (rev 104)
@@ -52,7 +52,7 @@
// A list of ranges of PEs used by this Gridlet
private PERangeList peRangeList_ = null;
- // the partiton or queue in the resource to which this
+ // the partition or queue in the resource to which this
// gridlet was scheduled
private int partition_;
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/SSReservation.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/SSReservation.java 2008-02-15 04:13:00 UTC (rev 103)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/SSReservation.java 2008-02-15 07:03:53 UTC (rev 104)
@@ -36,6 +36,13 @@
// expiry time once a reservation has been made
private double expiryTime_;
+ // the partition or queue in the resource to which this
+ // reservation was scheduled
+ private int partition_;
+
+ // the priority of this reservation assigned by the scheduler
+ private int priority_;
+
// used to format the values for display
private static DecimalFormat decFormater_;
@@ -157,6 +164,50 @@
}
/**
+ * Gets the id of the partition or queue to which this
+ * reservation was scheduled
+ * @return the partition id or <tt>-1</tt> if not found
+ */
+ public int getPartitionID() {
+ return partition_;
+ }
+
+ /**
+ * Sets the id of the partition or queue to which this
+ * reservation was scheduled
+ * @param partition the partition id
+ * @return <tt>true</tt> if set correctly or <tt>false</tt> otherwise.
+ */
+ public boolean setPartitionID(int partition) {
+ if(partition < 0)
+ return false;
+
+ partition_ = partition;
+ return true;
+ }
+
+ /**
+ * Gets the priority of this reservation assigned by the scheduler
+ * @return the priority or <tt>-1</tt> if not found
+ */
+ public int getPriority() {
+ return priority_;
+ }
+
+ /**
+ * Sets the priority of this reservation assigned by the scheduler
+ * @param priority the priority
+ * @return <tt>true</tt> if set correctly or <tt>false</tt> otherwise.
+ */
+ public boolean setPriority(int priority) {
+ if(priority < 0)
+ return false;
+
+ priority_ = priority;
+ return true;
+ }
+
+ /**
* Sets the time of submission of this reservation
* @param time the submission time
* @return <tt>true</tt> if the time has been set or
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ScheduleItem.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ScheduleItem.java 2008-02-15 04:13:00 UTC (rev 103)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ScheduleItem.java 2008-02-15 07:03:53 UTC (rev 104)
@@ -51,7 +51,7 @@
* @return the number of items
*/
int getNumPE();
-
+
/**
* Returns the time of submission of this item
* @return the submission time
@@ -73,6 +73,19 @@
double getFinishTime();
/**
+ * Gets the priority of this item assigned by the scheduler
+ * @return the priority or <tt>-1</tt> if not found
+ */
+ int getPriority();
+
+ /**
+ * Gets the id of the partition or queue to which this
+ * item was scheduled
+ * @return the partition id or <tt>-1</tt> if not found
+ */
+ int getPartitionID();
+
+ /**
* Gets the list of ranges of PEs used by this item
* @return a list containing the ranges
*/
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
