Menu
▾
▴
gridsim-commits
|
From: <mar...@us...> - 2008-02-05 02:43:50
|
Revision: 87
http://gridsim.svn.sourceforge.net/gridsim/?rev=87&view=rev
Author: marcos_dias
Date: 2008-02-04 18:43:51 -0800 (Mon, 04 Feb 2008)
Log Message:
-----------
Small changes in the provision of reservation options. Now the options are part of the reservation object.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/ARMessage.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARMessage.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARMessage.java 2008-02-05 00:28:29 UTC (rev 86)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARMessage.java 2008-02-05 02:43:51 UTC (rev 87)
@@ -29,12 +29,6 @@
private int errorCode_; // an error code associated with the operation required
private Reservation reservation_; // the negotiation this message is about
- // If a Grid resource cannot make a reservation, it may provide options
- // by informing the reservation requester when resource will be available to
- // fulfil the reservation. This attribute contains the list of PEs
- // available at a set of simulation times
- private AvailabilityInfo resOptions_;
-
// the price associate with this message
private double price_;
@@ -76,6 +70,10 @@
/** Indicates that the operation requested could not be fulfilled */
public static final int EC_OPERATION_FAILURE = 1;
+ /** Indicates that the operation requested could not be fulfilled,
+ * but advance reservation options are provided */
+ public static final int EC_OPERATION_FAILURE_BUT_OPTIONS = 2;
+
private static int lastUniqueID;
static{
@@ -114,7 +112,6 @@
msgType_ = TYPE_UNKNOWN;
errorCode_ = EC_NO_ERROR;
reservation_ = null;
- resOptions_ = null;
}
/**
@@ -163,7 +160,6 @@
msgId_ = ARMessage.createUniqueID();
reservation_ = reservation;
errorCode_ = EC_NO_ERROR;
- resOptions_ = null;
}
/**
@@ -384,22 +380,6 @@
}
/**
- * Gets the reservation options given by the Grid resource
- * @return the reservation options
- */
- public AvailabilityInfo getReservationOptions() {
- return resOptions_;
- }
-
- /**
- * Sets the reservation options given by the Grid resource
- * @param resOptions the reservation options object
- */
- public void setReservationOptions(AvailabilityInfo resOptions) {
- resOptions_ = resOptions;
- }
-
- /**
* Returns the size in bytes for this message.
* <tt>NOTE:</tt> This is used to get network statistics
* @return the size in bytes of this message
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-02-05 00:28:29 UTC (rev 86)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-02-05 02:43:51 UTC (rev 87)
@@ -649,7 +649,7 @@
AvailabilityInfo availability = getAvailabilityInfo(startTime, duration);
// sets the options as the availability over the requested period
- response.setReservationOptions(availability);
+ response.getReservation().setReservationOptions(availability);
// Sends the response back to the user
super.sendARMessage(response);
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java 2008-02-05 00:28:29 UTC (rev 86)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java 2008-02-05 02:43:51 UTC (rev 87)
@@ -35,6 +35,12 @@
private int reservID_; // reservation ID
private double submissionTime_; // the time of submission of this advance reservation
+ // If a Grid resource cannot make a reservation, it may provide options
+ // by informing the reservation requester when resource will be available to
+ // fulfil the reservation. This attribute contains the list of PEs
+ // available at a set of simulation times
+ private AvailabilityInfo resOptions_;
+
private static final int NOT_FOUND = -1; // constant
private static int lastReservationId_ = 0;
@@ -301,7 +307,23 @@
public int getID() {
return reservID_;
}
+
+ /**
+ * Gets the reservation options given by the Grid resource
+ * @return the reservation options
+ */
+ public AvailabilityInfo getReservationOptions() {
+ return resOptions_;
+ }
+ /**
+ * Sets the reservation options given by the Grid resource
+ * @param resOptions the reservation options object
+ */
+ public void setReservationOptions(AvailabilityInfo resOptions) {
+ resOptions_ = resOptions;
+ }
+
/**
* Returns a clone of this object
* @return a cloned reservation object
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java 2008-02-05 00:28:29 UTC (rev 86)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java 2008-02-05 02:43:51 UTC (rev 87)
@@ -144,6 +144,9 @@
if(error == ARMessage.EC_NO_ERROR) {
reservations_.put(reservation.getID(), reservation);
}
+ else if(error == ARMessage.EC_OPERATION_FAILURE_BUT_OPTIONS) {
+ reservation = reply.getReservation();
+ }
else {
System.out.println(super.get_name() + ": Reservation # " +
reservation.getID() + " has not been accepted by "+
@@ -356,7 +359,7 @@
// Otherwise, print the error message
int error = reply.getErrorCode();
if(error == ARMessage.EC_NO_ERROR) {
- resOptions = reply.getReservationOptions();
+ resOptions = reply.getReservation().getReservationOptions();
}
else {
System.out.println(super.get_name() + ": Resource # " + resID +
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-02-10 06:04:25
|
Revision: 92
http://gridsim.svn.sourceforge.net/gridsim/?rev=92&view=rev
Author: marcos_dias
Date: 2008-02-09 22:04:30 -0800 (Sat, 09 Feb 2008)
Log Message:
-----------
This update contains small bug fixes and improvements:
+ The advance reservation policy and the conservative backfilling could present overlapping ranges of available processing elements. Although that did not affect the resource allocation results, that could lead to infinite loops on software that queried the resource availability.
+ Small changes in the availability information objects and the lists of PEs.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfo.java
branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfoEntry.java
branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java
branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java
branches/gridsim4.0-branch3/source/gridsim/turbo/TResourceCharacteristics.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-02-08 03:25:23 UTC (rev 91)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-02-10 06:04:30 UTC (rev 92)
@@ -156,9 +156,6 @@
// the last time when the schedule update was called
private double lastScheduleUpdate_;
-
- // last time when a reservation started
- private double lastReservationStart_;
// last time the expiration of reservations was checked
private double lastCheckExpiryTime_;
@@ -452,8 +449,8 @@
super.sendARMessage(response);
// then send this into itself to check for expired reservations
- int roundUpTime = (int) (expTime - currentTime) + 1;
- super.sendInternalEvent(roundUpTime, EXPIRY_TIME);
+ super.sendInternalEvent(expTime - currentTime,
+ EXPIRY_TIME);
//-------------- FOR DEBUGGING PURPOSES ONLY --------------
@@ -605,8 +602,8 @@
sRes.setStatus(Reservation.STATUS_COMMITTED);
// then send this into itself to start the reservation
- int roundUpTime = (int) (sRes.getStartTime() - currentTime) + 1;
- super.sendInternalEvent(roundUpTime, START_RESERVATION);
+ super.sendInternalEvent(sRes.getStartTime() - currentTime,
+ START_RESERVATION);
}
// sends the response message with no error
@@ -614,7 +611,8 @@
//-------------- FOR DEBUGGING PURPOSES ONLY --------------
- GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_STATUS_CHANGED, true, sRes);
+ GridSim.notifyListeners(this.get_id(),
+ AllocationAction.ITEM_STATUS_CHANGED, true, sRes);
//----------------------------------------------------------
}
@@ -912,8 +910,11 @@
double currentTime = GridSim.clock();
switch(ev.get_tag()) {
- // time to check the finish time of a Gridlet
+ // time to update the schedule, finish gridlets,
+ // finish reservations, start reservations and start gridlets
case GRIDLET_FINISHED:
+ case START_RESERVATION:
+ case FINISH_RESERVATION:
if(currentTime > lastScheduleUpdate_) {
updateSchedule();
}
@@ -928,22 +929,6 @@
lastCheckExpiryTime_ = currentTime;
break;
- // time to start the reservation
- case START_RESERVATION:
- if(currentTime > lastReservationStart_) {
- startReservation();
- }
- lastReservationStart_ = currentTime;
- break;
-
- // time to start the reservation
- case FINISH_RESERVATION:
- if(currentTime > lastScheduleUpdate_) {
- finishReservation();
- }
- lastScheduleUpdate_ = currentTime;
- break;
-
default:
System.out.println(super.get_name() + ".processEvent():" +
"could not handle the event with tag #" + ev.get_tag());
@@ -970,7 +955,6 @@
expiryTable_ = new LinkedHashMap<Integer, SSReservation>();
orderStartTime_ = new OrderGridletByStartTime();
lastScheduleUpdate_ = -1;
- lastReservationStart_ = -1;
lastCheckExpiryTime_ = -1;
ratingPE_ = 0;
}
@@ -1214,8 +1198,7 @@
// then send this event to itself to update the queues after
// this gridlet's completion time
- int roundUpTime = (int)(executionTime + 1);
- super.sendInternalEvent(roundUpTime, GRIDLET_FINISHED);
+ super.sendInternalEvent(executionTime, GRIDLET_FINISHED);
return true;
}
@@ -1552,18 +1535,20 @@
* gridlets in the waiting list that should start execution. It also
* removes old entries from the availability profile.
*/
- private void updateSchedule(){
+ private void updateSchedule() {
+ int itemsFinished = 0;
double currentTime = GridSim.clock();
- int gridletFinished = 0;
- int gridletStarted = 0;
- boolean reserved;
+ int itemsStarted = 0;
+
+ // finishes the advance reservations first
+ itemsFinished = finishReservation(currentTime);
+ boolean reserved;
// remove all Gridlets that have already completed from
// the queue of running Gridlets
PERangeList releasedRanges = new PERangeList();
- LinkedList<SSGridlet> grlsCompleted = new LinkedList<SSGridlet>();
-
+
// iterates the list to check what has finished
Iterator<SSGridlet> iter = runningGridlets_.iterator();
while (iter.hasNext()) {
@@ -1577,41 +1562,44 @@
if(!reserved) {
releasedRanges.addAll(gridlet.getPERangeList().clone());
}
- grlsCompleted.add(gridlet);
gridletFinish(gridlet, Gridlet.SUCCESS);
iter.remove();
- gridletFinished++;
- }
- }
+ itemsFinished++;
+ }
+ }
+ resource_.setPEsAvailable(releasedRanges);
+
+ if(PERangeList.containsOverlappingRanges(resource_.getFreePERanges())) {
+ System.out.println("Overlap! Ranges = " + resource_.getFreePERanges());
+ System.exit(1);
+ }
- resource_.setPEsAvailable(releasedRanges);
-
+ itemsStarted = startReservation(currentTime);
+
// remove past entries from the availability profile
cleanAvailabilityProfile(currentTime);
- if (gridletFinished > 0) {
- // Start the execution of Gridlets that are queued and whose
- // potential start execution time is smaller than current time
- gridletStarted = startQueuedGridlets();
- }
-
+ // Start the execution of Gridlets that are queued and whose
+ // potential start execution time is smaller than current time
+ itemsStarted += startQueuedGridlets();
+
//---------------- USED FOR DEBUGGING PURPOSES ONLY --------------------
// If a gridlet has started execution or one has finished,
// then inform the listeners
- if(gridletStarted > 0 || gridletFinished > 0){
- GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_COMPLETED,
- true, grlsCompleted);
+ if(itemsStarted > 0 || itemsFinished > 0){
+ GridSim.notifyListeners(this.get_id(), AllocationAction.SCHEDULE_CHANGED, true);
}
}
/**
* This method is called to start a reservation and consequently update
* the availability profile.
+ * @refTime the reservations whose start time is smaller
+ * or equals to refTime will be started
*/
- private void startReservation() {
+ private int startReservation(double refTime) {
- double currentTime = GridSim.clock();
LinkedList<SSReservation> startedReservations = new LinkedList<SSReservation>();
PERangeList allocatedRanges = new PERangeList();
int numStartedRes = 0;
@@ -1620,7 +1608,7 @@
while(iterRes.hasNext()) {
SSReservation sRes = iterRes.next();
- if(sRes.getStartTime() <= currentTime &&
+ if(sRes.getStartTime() <= refTime &&
sRes.getStatus() == Reservation.STATUS_COMMITTED) {
// Start the reservation and update the ranges of
@@ -1630,16 +1618,13 @@
allocatedRanges.addAll(sRes.getPERangeList().clone());
startedReservations.add(sRes);
- int roundUpTime = (int)(sRes.getFinishTime()-currentTime)+1;
- super.sendInternalEvent(roundUpTime, FINISH_RESERVATION);
+ super.sendInternalEvent(sRes.getFinishTime()-refTime,
+ FINISH_RESERVATION);
numStartedRes++;
}
}
- // remove past entries from the availability profile
- cleanAvailabilityProfile(currentTime);
-
// if any reservation has been started, then update
// the list of PEs available at the moment and start
// the gridlets in the queue that can be started
@@ -1653,12 +1638,6 @@
// notify the listeners
GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_STATUS_CHANGED,
true, startedReservations);
-
- //------------------------------------------------------------------
-
- startQueuedGridlets();
-
- //-------------- USED FOR DEBUGGING PURPOSES ONLY ------------------
// If a gridlet has started execution or one has finished,
// then inform the listeners
@@ -1666,16 +1645,19 @@
//------------------------------------------------------------------
}
+
+ return numStartedRes;
}
/**
* This method is called to finish a reservation and consequently update
* the availability profile.
- * @param reservation the reservation to be finished
+ * @param refTime the time reference to check what reservations should
+ * be finished. All reservations whose finish time is smaller or
+ * equals to refTime will be completed
+ * @return the number of reservations completed
*/
- private void finishReservation() {
-
- double currentTime = GridSim.clock();
+ private int finishReservation(double refTime) {
int reservationFinished = 0;
// remove all reservations that have already completed
@@ -1684,7 +1666,7 @@
Iterator<SSReservation> iterRes = reservTable_.values().iterator();
while(iterRes.hasNext()) {
SSReservation sRes = iterRes.next();
- if(sRes.getFinishTime() <= currentTime) {
+ if(sRes.getFinishTime() <= refTime) {
// Finish the reservation and include ranges in the
// list of ranges to be released
sRes.setStatus(Reservation.STATUS_FINISHED);
@@ -1694,16 +1676,11 @@
expiryTable_.put(sRes.getID(), sRes);
}
}
-
- // remove past entries from the availability profile
- cleanAvailabilityProfile(currentTime);
// returns the ranges to the list of current available ranges
resource_.setPEsAvailable(releasedRanges);
-
- if(reservationFinished > 0) {
- startQueuedGridlets();
+ if(reservationFinished > 0) {
//------------- USED FOR DEBUGGING PURPOSES ONLY ------------------
@@ -1713,6 +1690,8 @@
//-----------------------------------------------------------------
}
+
+ return reservationFinished;
}
/**
@@ -1726,6 +1705,13 @@
Iterator<AvailabilityProfileEntry> iterProfile = availProfile_.iterator();
while(iterProfile.hasNext()) {
AvailabilityProfileEntry entry = iterProfile.next();
+
+// if(PERangeList.containsOverlappingRanges(entry.getPERanges())) {
+// System.out.println(" Profile entry at time " + entry.getTime() +
+// " contains overlapping ranges. Ranges = " + entry.getPERanges());
+// System.exit(0);
+// }
+
if(entry.getTime() <= referenceTime){
iterProfile.remove();
}
@@ -1766,11 +1752,12 @@
// change Gridlet status
gridlet.setStatus(Gridlet.INEXEC);
- int roundUpTime = (int)(gridlet.getFinishTime()-currentTime)+1;
- super.sendInternalEvent(roundUpTime, GRIDLET_FINISHED);
+ super.sendInternalEvent(gridlet.getFinishTime()-currentTime,
+ GRIDLET_FINISHED);
}
}
- resource_.setPEsBusy(allocatedRanges);
+
+ resource_.setPEsBusy(allocatedRanges);
return gridletStarted++;
}
@@ -1969,6 +1956,9 @@
}
}
+ if(intersectList == null || intersectList.getNumPE() < reqPE)
+ return null;
+
anchorIndex = availProfile_.indexOf(anchorEntry);
tailIndex = availProfile_.indexOf(tailEntry);
@@ -2033,20 +2023,8 @@
intersectList = null;
int length = availProfile_.size();
- double entryTime;
-
- Iterator<AvailabilityProfileEntry> iterProfile = availProfile_.iterator();
- while(iterProfile.hasNext()) {
- AvailabilityProfileEntry entry = iterProfile.next();
- entryTime = entry.getTime();
- if(entryTime > startTime) {
- break;
- }
- else {
- anchorEntry = entry;
- tailEntry = entry;
- }
- }
+
+ anchorEntry = tailEntry = availProfile_.getPrecedingEntry(startTime);
// if the entry is null, then it means that the reservation is
// before the first entry of the profile, so the intersection list
@@ -2125,12 +2103,12 @@
// to represent its completion time. This reduces the number of
// entries in the availability profile
boolean addEntryAfterTail = true;
- int updTo = tailIndex;
if(tailIndex == -1) {
// Creates a new entry to be added to the profile
newEntryAfterTail = new AvailabilityProfileEntry(finishTime);
newEntryAfterTail.setPERangeList(resource_.getFreePERanges().clone());
+ tailIndex++;
}
else {
// get the tail entry (that is, the closest entry
@@ -2140,7 +2118,6 @@
if (tailEntry.getTime() == finishTime) {
addEntryAfterTail = false;
- updTo--;
tailEntry.increaseGridlet();
}
// If a new entry is required, then add it to the profile
@@ -2153,11 +2130,16 @@
// Creates a new entry to be added to the profile
newEntryAfterTail = new AvailabilityProfileEntry(finishTime);
newEntryAfterTail.setPERangeList(listTail);
+ tailIndex++;
}
}
+
+ if(addEntryAfterTail) {
+ availProfile_.add(tailIndex, newEntryAfterTail);
+ }
// Update entries of the profile
- for(int index=0; index<=updTo; index++) {
+ for(int index=0; index<tailIndex; index++) {
AvailabilityProfileEntry entry = availProfile_.get(index);
if(entry.getTime() < startTime){
continue;
@@ -2167,12 +2149,9 @@
entry.setPERangeList(uptList);
}
- if(addEntryAfterTail) {
- availProfile_.add(tailIndex + 1, newEntryAfterTail);
- }
-
// subtract the selected ranges from the currently free ranges
resource_.setPEsBusy(selected);
+
}
/**
@@ -2295,7 +2274,7 @@
availProfile_.add(tailInsertPos, newEntryAfterTail);
}
}
-
+
/**
* This method returns a list that corresponds to the free time slots
* in the scheduling queue managed by this scheduler or
@@ -2307,7 +2286,7 @@
* entries that correspond to the availability profile between the times
* specified by the requester.
*/
- private AvailabilityInfo getAvailabilityInfo(double startTime, int duration) {
+ protected AvailabilityInfo getAvailabilityInfo(double startTime, int duration) {
AvailabilityInfo list = new AvailabilityInfo();
int anchorIndex = -1;
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfo.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfo.java 2008-02-08 03:25:23 UTC (rev 91)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfo.java 2008-02-10 06:04:30 UTC (rev 92)
@@ -8,7 +8,6 @@
package gridsim.turbo;
import java.util.ArrayList;
-import java.util.Collection;
import java.util.Collections;
import java.util.Iterator;
@@ -28,11 +27,9 @@
* @see ARParallelSpaceShared#handleQueryAvailability(ARMessage)
*/
-public class AvailabilityInfo {
+public class AvailabilityInfo extends ArrayList<AvailabilityInfoEntry> {
private static final long serialVersionUID = -3951650752024908016L;
-
- private ArrayList<AvailabilityInfoEntry> list_;
private double startTime_;
private double finishTime_;
@@ -42,7 +39,7 @@
* Default constructor.
*/
public AvailabilityInfo() {
- list_ = new ArrayList<AvailabilityInfoEntry>();
+ super();
startTime_ = UNKNOWN;
finishTime_ = UNKNOWN;
}
@@ -60,7 +57,7 @@
* Returns the end time of this list.
* @return the end time
*/
- public double getEndTime() {
+ public double getFinishTime() {
return finishTime_;
}
@@ -81,145 +78,21 @@
}
/**
- * Adds the specified element to this list.
- * @param entry the entry to be added to this list
- * @return <tt>true
- */
- public boolean add(AvailabilityInfoEntry entry) {
- if(entry == null) {
- return false;
- }
- else {
- list_.add(entry);
- }
- return true;
- }
-
- /**
* Sorts the entries of this availability info object.
*/
public void sort() {
- Collections.sort(list_);
+ Collections.sort(this);
}
/**
- * Adds all of the elements in the specified Collection to this list,
- * The behaviour of this operation is undefined if the specified
- * Collection is modified while the operation is in progress.
- * (This implies that the behaviour of this call is undefined if the
- * specified Collection is this list, and this list is nonempty.)
- * @param collection the collection to be included in this list
- * @return <tt>true<tt> if the collection has been added successfully
- * or <tt>false</tt> otherwise.
- */
- public boolean addAll(Collection<? extends AvailabilityInfoEntry> collection) {
- boolean result = true;
-
- // adds the collection to the list and sets the start
- // and finish time again
- if(collection != null && !collection.isEmpty()) {
- list_.addAll(collection);
- }
- return result;
- }
-
- /**
- * Removes all elements from the list.
- */
- public void clear() {
- list_.clear();
- }
-
- /**
- * Returns a shallow copy of this list.
- * (The elements themselves are not copied.)
- */
- public Object clone() {
- return list_.clone();
- }
-
- /**
- * Returns <tt>true</tt> if this list contains the specified element.
- * @param entry the entry whose presence in this List is to be tested.
- * @return <tt>true</tt> if the specified element is present;
- * <tt>false</tt> otherwise.
- */
- public boolean contains(Object entry) {
- return list_.contains(entry);
- }
-
- /**
- * Returns the element at the specified position in this list.
- * @param index the index of the element to return
- * @return the element at the specified position in this list.
- */
- public AvailabilityInfoEntry get(int index) {
- return list_.get(index);
- }
-
- /**
- * Searches for the first occurence of the given argument,
- * testing for equality using the equals method.
- * @param entry the entry whose index is to be returned
- * @return the index of the first occurrence of the argument
- * in this list; returns <tt>-1</tt> if the object is not found.
- */
- public int indexOf(Object entry) {
- return list_.indexOf(entry);
- }
-
- /**
- * Tests if this list has no elements.
- * @return <tt>true</tt> if the list has no elements.
- */
- public boolean isEmpty() {
- return list_.isEmpty();
- }
-
- /**
- * Returns an iterator over the elements in this list in proper sequence.
- * @return the iterator.
- */
- public Iterator<AvailabilityInfoEntry> iterator() {
- return list_.iterator();
- }
-
- /**
- * Removes the element at a given index
- * @param index the index of the element to be removed
- * @return the removed element.
- */
- public AvailabilityInfoEntry remove(int index) {
- return list_.remove(index);
- }
-
- /**
- * Removes a given element from the list.
- * @param entry the entry to be removed
- * @return <tt>true</tt> if the collection contained the
- * specified entry.
- */
- public boolean remove(Object entry) {
- return list_.remove(entry);
- }
-
- /**
- * Returns the size of this list.
- * @return the size of this list
- */
- public int size() {
- return list_.size();
- }
-
- /**
* Returns the entry whose time is closest to the <tt>time</tt> given but
* smaller, or whose time is equals to <tt>time</tt>
* @param time the time to be used to search for the entry
* @return the entry whose time is closest to the <tt>time</tt> given but
* smaller, or whose time is equals to <tt>time</tt>
*/
- private AvailabilityInfoEntry getPrecedingEntry(double time) {
- Iterator<AvailabilityInfoEntry> it = list_.iterator();
+ protected AvailabilityInfoEntry getPrecedingEntry(double time) {
+ Iterator<AvailabilityInfoEntry> it = super.iterator();
AvailabilityInfoEntry preceding = null;
while(it.hasNext()) {
@@ -273,32 +146,33 @@
double potStartTime = -1; // keep the potential start time of the request
double potFinishTime = -1; // store the gridlet's expected finish time
- int length = list_.size();
+ int length = super.size();
anchorEntry = getPrecedingEntry(readyTime);
- int firstAnchorIndex = list_.indexOf(anchorEntry);
+ int firstAnchorIndex = super.indexOf(anchorEntry);
if(firstAnchorIndex == -1)
firstAnchorIndex = 0;
for(int j=firstAnchorIndex; j<length; j++) {
- AvailabilityInfoEntry entry = list_.get(j);
- anchorIndex = list_.indexOf(entry);
+ AvailabilityInfoEntry entry = super.get(j);
+ anchorIndex = super.indexOf(entry);
- // sets the start time as the time of the entry
- if(entry.getTime() < readyTime)
- potStartTime = readyTime;
- else
- potStartTime = entry.getTime();
-
- // calculates when the finish time will be if
- // the gridlet is put at this position
- potFinishTime = potStartTime + duration;
-
// scan the profile until an entry with enough PEs is found
if(entry.getNumPE() < reqPE) {
continue;
}
else {
+
+ // sets the start time as the time of the entry
+ if(entry.getTime() < readyTime)
+ potStartTime = readyTime;
+ else
+ potStartTime = entry.getTime();
+
+ // calculates when the finish time will be if
+ // the gridlet is put at this position
+ potFinishTime = potStartTime + duration;
+
// if an entry with enough PEs is found, then scan the list
// from that point onwards analysing the intersection of
// the ranges available in the entries until the
@@ -309,7 +183,7 @@
// the anchor until the end of the profile or until
// the entries are further than the expected completion time
for(int i=anchorIndex+1; i<length; i++){
- AvailabilityInfoEntry nextEntry = list_.get(i);
+ AvailabilityInfoEntry nextEntry = super.get(i);
if(nextEntry.getTime() > potFinishTime){
break;
}
@@ -341,17 +215,184 @@
return potStartTime;
}
+
+ /**
+ * This method checks whether a given request with hard deadline
+ * can be scheduled or not. The method verifies whether there are enough
+ * processing elements at the start time to serve the request and
+ * whether enough elements will be available over the request's duration.
+ * @param startTime the start time of the request.
+ * @param duration the duration of the request.
+ * @param reqPE the number of processing elements required.
+ * @return <tt>true</tt> if the request can be scheduled,
+ * or <tt>false</tt> otherwise.
+ */
+ public boolean canSchedule(double startTime, int duration, int reqPE) {
+
+ // calculate the reservation's finish time
+ double finishTime = startTime + duration;
+
+ // a pointer to the anchor entry (described above)
+ AvailabilityInfoEntry anchorEntry = null;
+ // the list of selected ranges
+ PERangeList intersectList = null;
+
+ intersectList = null;
+ int length = super.size();
+ double entryTime;
+
+ int anchorIndex = -1;
+
+ Iterator<AvailabilityInfoEntry> it = super.iterator();
+ while(it.hasNext()) {
+ AvailabilityInfoEntry entry = it.next();
+ entryTime = entry.getTime();
+ if(entryTime > startTime) {
+ break;
+ }
+ else {
+ anchorEntry = entry;
+ }
+ }
+
+ intersectList = (anchorEntry != null ) ?
+ anchorEntry.getAvailRanges().clone() : null;
+
+ if(intersectList == null || intersectList.getNumPE() < reqPE) {
+ // there are not enough PEs available to serve the
+ // advance reservation request, then returns null
+ return false;
+ }
+
+ anchorIndex = super.indexOf(anchorEntry);
+
+ // Look for the intersection of available ranges from
+ // the anchor until the end of the profile or until
+ // the entries are further than the expected completion time
+ for(int i=anchorIndex+1; i<length; i++) {
+ AvailabilityInfoEntry nextEntry = super.get(i);
+ if(nextEntry.getTime() > finishTime){
+ break;
+ }
+ else {
+ // if the finish time is equals to the entry time, so there
+ // is no need to check the intersection
+ if(nextEntry.getTime() < finishTime) {
+ intersectList = PERangeList.intersection(intersectList,
+ nextEntry.getAvailRanges());
+ }
+ }
+
+ if(intersectList == null || intersectList.getNumPE() < reqPE) {
+ // there are not enough PEs available to serve the
+ // advance reservation request, then returns null
+ return false;
+ }
+ }
+
+ return true;
+ }
+
/**
+ * This method checks whether a given request with hard deadline
+ * can be scheduled or not. The method verifies whether there are enough
+ * processing elements during ready time until the deadline for the
+ * specified duration.
+ * @param readyTime the start time of the request.
+ * @param deadline the deadline of the request
+ * @param duration the duration of the request.
+ * @param reqPE the number of processing elements required.
+ * @return <tt>true</tt> if the request can be scheduled,
+ * or <tt>false</tt> otherwise.
+ */
+ public boolean canSchedule(double readyTime, double deadline,
+ int duration, int reqPE) {
+
+ if(duration < deadline - readyTime) {
+ System.out.println("AvailabilityInfo.canSchedule(): Duration cannot " +
+ "be smaller than (deadline - readyTime).");
+ return false;
+ }
+ else if(deadline < readyTime) {
+ System.out.println("AvailabilityInfo.canSchedule(): Deadline cannot " +
+ "be smaller than readyTime.");
+ return false;
+ }
+
+ // the list of selected ranges
+ PERangeList intersectList = null;
+ int length = super.size();
+ double entryTime;
+
+ int anchorIndex = -1;
+
+ Iterator<AvailabilityInfoEntry> it = super.iterator();
+ while(it.hasNext()) {
+ AvailabilityInfoEntry entry = it.next();
+ entryTime = entry.getTime();
+ if(entryTime < readyTime) {
+ continue;
+ }
+
+ // calculate the reservation's finish time
+ double finishTime = entryTime + duration;
+ if(finishTime > deadline) {
+ return false;
+ }
+
+ if(entry.getNumPE() < reqPE) {
+ continue;
+ }
+ else {
+ anchorIndex = super.indexOf(entry);
+ intersectList = entry.getAvailRanges().clone();
+
+ // Look for the intersection of available ranges from
+ // the anchor until the end of the profile or until
+ // the entries are further than the expected completion time
+ for(int i=anchorIndex+1; i<length; i++) {
+ AvailabilityInfoEntry nextEntry = super.get(i);
+ if(nextEntry.getTime() > finishTime){
+ break;
+ }
+ else {
+ // if the finish time is equals to the entry time, so there
+ // is no need to check the intersection
+ if(nextEntry.getTime() < finishTime) {
+ intersectList = PERangeList.intersection(intersectList,
+ nextEntry.getAvailRanges());
+ }
+ }
+
+ if(intersectList == null || intersectList.getNumPE() < reqPE) {
+ // there are not enough PEs available to serve the
+ // advance reservation request, then returns null
+ break;
+ }
+ }
+ }
+ }
+
+ if(intersectList == null || intersectList.getNumPE() < reqPE) {
+ // there are not enough PEs available to serve the
+ // advance reservation request, then returns null
+ return false;
+ }
+
+ return true;
+ }
+
+ /**
* Creates a string representation of the list
* @return a string representation
*/
public String toString() {
String result = "Availability={\n";
- for(AvailabilityInfoEntry entry : list_){
+ for(AvailabilityInfoEntry entry : this){
result += entry + "\n";
}
result += "}";
return result;
}
-}
+}
\ No newline at end of file
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfoEntry.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfoEntry.java 2008-02-08 03:25:23 UTC (rev 91)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfoEntry.java 2008-02-10 06:04:30 UTC (rev 92)
@@ -29,6 +29,10 @@
private double time_;
private PERangeList availRanges_;
+ // number of gridlets that rely on this entry
+ // to mark their completion time or anchor point
+ private int numGridlets_ = 1;
+
/**
* Creates a new instance of {@link AvailabilityInfoEntry}
* @param time the time associated with this entry
@@ -85,6 +89,34 @@
public void setAvailRanges(PERangeList availRanges) {
availRanges_ = availRanges;
}
+
+ /**
+ * Increases the number of Gridlets that rely on this entry to mark
+ * their expected completion time or their anchor point
+ */
+ public void increaseGridlet(){
+ numGridlets_++;
+ }
+
+ /**
+ * Decreases the number of Gridlets that rely on this entry to mark
+ * their expected completion time or their anchor point
+ */
+ public void decreaseGridlet(){
+ numGridlets_--;
+ }
+
+ /**
+ * Adds the ranges provided to the list of ranges available
+ * @param list the list to be added
+ * @return <tt>true</tt> if the ranges changed as result of this call
+ */
+ public boolean addRanges(PERangeList list) {
+ if(availRanges_ == null)
+ availRanges_ = new PERangeList();
+
+ return availRanges_.addAll(list);
+ }
/**
* Compares this object with the specified object for order.
@@ -126,4 +158,17 @@
return "{time="+ time_ + "; "
+ ( (availRanges_!=null) ? availRanges_ : "{[]}") + "}";
}
+
+ /**
+ * Returns a clone of this entry. The ranges are cloned, but the time
+ * and the number of requests relying on this entry are not.
+ * @param time the time for the new entry
+ * @return the new entry with the number of requests set to default.
+ */
+ public AvailabilityInfoEntry clone(double time) {
+ AvailabilityInfoEntry entry = new AvailabilityInfoEntry(time);
+ entry.availRanges_ = availRanges_ == null ? null : availRanges_.clone();
+ entry.numGridlets_ = 1;
+ return entry;
+ }
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java 2008-02-08 03:25:23 UTC (rev 91)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java 2008-02-10 06:04:30 UTC (rev 92)
@@ -9,6 +9,7 @@
package gridsim.turbo;
import java.util.ArrayList;
+import java.util.Iterator;
/**
* This class represents the profile containing the ranges of PEs
@@ -43,6 +44,28 @@
}
/**
+ * Returns the entry whose time is closest to the <tt>time</tt> given but
+ * smaller, or whose time is equals to <tt>time</tt>
+ * @param time the time to be used to search for the entry
+ * @return the entry whose time is closest to the <tt>time</tt> given but
+ * smaller, or whose time is equals to <tt>time</tt>; <tt>null</tt> if
+ * not found.
+ */
+ protected AvailabilityProfileEntry getPrecedingEntry(double time) {
+ Iterator<AvailabilityProfileEntry> it = super.iterator();
+ AvailabilityProfileEntry preceding = null;
+
+ while(it.hasNext()) {
+ AvailabilityProfileEntry entry = it.next();
+ if(entry.getTime() > time)
+ break;
+
+ preceding = entry;
+ }
+ return preceding;
+ }
+
+ /**
* Creates an string representation of the profile
* @return an string representation
*/
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-02-08 03:25:23 UTC (rev 91)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-02-10 06:04:30 UTC (rev 92)
@@ -157,7 +157,7 @@
/**
* Handles internal events that come to this entity.
*/
- public void body(){
+ public void body() {
// get the resource characteristics object to be used
resource_ = getTResourceCharacteristics();
@@ -514,8 +514,7 @@
// then send this event to itself to update the queues after
// this gridlet's completion time
- int roundUpTime = (int)(executionTime + 1);
- super.sendInternalEvent(roundUpTime);
+ super.sendInternalEvent(executionTime);
return true;
}
@@ -616,7 +615,6 @@
break;
}
else {
- tailEntry = entry;
// Sep. 29, 2007 - Changed by Marcos
// if the finish time is equals to the entry time, so there
// is no need to check the intersection
@@ -626,6 +624,7 @@
if(intersectList == null || intersectList.getNumPE() < reqPE)
break;
}
+ tailEntry = entry;
}
tailIndex = availProfile_.indexOf(tailEntry);
}
@@ -653,7 +652,8 @@
* @param finishTime the finish time of the Gridlet
*/
private void allocateImmediatePERanges(int tailIndex,
- PERangeList selected, double startTime, double finishTime) {
+ PERangeList selected,
+ double startTime, double finishTime) {
AvailabilityProfileEntry newEntryAfterTail = null;
@@ -664,12 +664,12 @@
// to represent its completion time. This reduces the number of
// entries in the availability profile
boolean addEntryAfterTail = true;
- int updTo = tailIndex;
if(tailIndex == -1) {
// Creates a new entry to be added to the profile
newEntryAfterTail = new AvailabilityProfileEntry(finishTime);
newEntryAfterTail.setPERangeList(resource_.getFreePERanges().clone());
+ tailIndex++;
}
else {
// get the tail entry (that is, the closest entry to the finish time
@@ -677,7 +677,6 @@
if (tailEntry.getTime() == finishTime) {
addEntryAfterTail = false;
- updTo--;
tailEntry.increaseGridlet();
}
// If a new entry is required, then add it to the profile
@@ -689,12 +688,17 @@
// Creates a new entry to be added to the profile
newEntryAfterTail = new AvailabilityProfileEntry(finishTime);
- newEntryAfterTail.setPERangeList(listTail);
+ newEntryAfterTail.setPERangeList(listTail);
+ tailIndex++;
}
}
+ if(addEntryAfterTail) {
+ availProfile_.add(tailIndex, newEntryAfterTail);
+ }
+
// Update entries of the profile
- for(int index=0; index<=updTo; index++) {
+ for(int index=0; index<tailIndex; index++) {
AvailabilityProfileEntry entry = availProfile_.get(index);
if(entry.getTime() < startTime){
continue;
@@ -703,10 +707,6 @@
PERangeList.difference(entry.getPERanges(), selected);
entry.setPERangeList(uptList);
}
-
- if(addEntryAfterTail) {
- availProfile_.add(tailIndex + 1, newEntryAfterTail);
- }
// subtract the selected ranges from the currently free ranges
resource_.setPEsBusy(selected);
@@ -751,24 +751,23 @@
Iterator<AvailabilityProfileEntry> iterProfile = availProfile_.iterator();
while(iterProfile.hasNext()) {
-
AvailabilityProfileEntry entry = iterProfile.next();
- anchorEntry = entry;
- anchorIndex = availProfile_.indexOf(anchorEntry);
- tailEntry = entry;
-
- // sets the start time as the time of the entry
- potStartTime = entry.getTime();
- // calculates when the finish time will be if
- // the gridlet is put at this position
- potFinishTime = potStartTime + duration;
-
// scan the profile until an entry with enough PEs is found
if(entry.getNumPE() < reqPE) {
continue;
}
else {
+ anchorEntry = entry;
+ anchorIndex = availProfile_.indexOf(anchorEntry);
+ tailEntry = entry;
+
+ // sets the start time as the time of the entry
+ potStartTime = entry.getTime();
+ // calculates when the finish time will be if
+ // the gridlet is put at this position
+ potFinishTime = potStartTime + duration;
+
// if an entry with enough PEs is found, then scan the profile
// from that point onwards analysing the intersection of
// the ranges available in the entries until the
@@ -783,7 +782,7 @@
if(nextEntry.getTime() > potFinishTime){
break;
}
- else{
+ else {
// Sep. 29, 2007 - Changed by Marcos
// if the finish time is equals to the entry time, so there
// is no need to check the intersection
@@ -804,6 +803,9 @@
}
}
+ if(intersectList == null || intersectList.getNumPE() < reqPE)
+ return null;
+
anchorIndex = availProfile_.indexOf(anchorEntry);
tailIndex = availProfile_.indexOf(tailEntry);
@@ -831,7 +833,6 @@
double finishTime) {
AvailabilityProfileEntry newEntryAfterTail = null;
- AvailabilityProfileEntry newEntryAfterAnchor = null;
// if the time of the entry at (tailIndex) is equals to
// the gridlet finish time, then a new entry in the profile
@@ -840,18 +841,7 @@
// to represent its completion time. This reduces the number of
// entries in the availability profile
boolean addEntryAfterTail = true;
-
- // if the time of the entry at (anchor) is equals to
- // the gridlet finish time, then a new entry in the profile
- // is not needed. In this case, the entry at (anchorIndex)
- // 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 addEntryAfterAnchor = false;
-
- int updFrom = anchorIndex;
- int updTo = tailIndex;
-
+
AvailabilityProfileEntry tailEntry = availProfile_.get(tailIndex);
AvailabilityProfileEntry anchorEntry = availProfile_.get(anchorIndex);
// increment the counter to denote that one more gridlet uses this entry
@@ -859,31 +849,26 @@
if (tailEntry.getTime() == finishTime) {
addEntryAfterTail = false;
- updTo--;
tailEntry.increaseGridlet();
}
-
// If a new entry is required, then created it to be added to the profile
else {
// Creates a new entry to be added to the profile
newEntryAfterTail = new AvailabilityProfileEntry(finishTime);
newEntryAfterTail.setPERangeList(tailEntry.getPERanges().clone());
+ tailIndex++;
}
+
+ if(addEntryAfterTail) {
+ availProfile_.add(tailIndex, newEntryAfterTail);
+ }
// Update entries of the profile
- for(int index=updFrom; index<=updTo; index++){
+ for(int index=anchorIndex; index<tailIndex; index++){
AvailabilityProfileEntry entry = availProfile_.get(index);
PERangeList uptList = PERangeList.difference(entry.getPERanges(), selected);
entry.setPERangeList(uptList);
}
-
- if(addEntryAfterAnchor) {
- availProfile_.add(anchorIndex + 1, newEntryAfterAnchor);
- }
-
- if(addEntryAfterTail) {
- availProfile_.add(tailIndex + 1, newEntryAfterTail);
- }
}
/**
@@ -901,7 +886,6 @@
// remove all Gridlets that have already completed from
// the queue of running Gridlets
PERangeList releasedRanges = new PERangeList();
- LinkedList<SSGridlet> grlsCompleted = new LinkedList<SSGridlet>();
// iterates the list to check what has finished
Iterator<SSGridlet> iter = runningGridlets_.iterator();
@@ -913,7 +897,6 @@
if(gridlet.getFinishTime() <= currentTime) {
// Update the list of ranges released
releasedRanges.addAll(gridlet.getPERangeList().clone());
- grlsCompleted.add(gridlet);
gridletFinish(gridlet, Gridlet.SUCCESS);
iter.remove();
gridletFinished++;
@@ -950,20 +933,18 @@
// change Gridlet status
gridlet.setStatus(Gridlet.INEXEC);
- int roundUpTime = (int)(gridlet.getFinishTime()-currentTime)+1;
- super.sendInternalEvent(roundUpTime);
+ super.sendInternalEvent(gridlet.getFinishTime()-currentTime);
}
}
resource_.setPEsBusy(allocatedRanges);
}
-
+
//---------------- USED FOR DEBUGGING PURPOSES ONLY --------------------
// If a gridlet has started execution or one has finished,
// then inform the listeners
if(gridletStarted > 0 || gridletFinished > 0){
- GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_COMPLETED,
- true, grlsCompleted);
+ GridSim.notifyListeners(this.get_id(), AllocationAction.SCHEDULE_CHANGED, true);
}
//----------------------------------------------------------------------
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-02-08 03:25:23 UTC (rev 91)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-02-10 06:04:30 UTC (rev 92)
@@ -468,8 +468,7 @@
// then send this event to itself to update the queues after
// this gridlet's completion time
- int roundUpTime = (int)(executionTime + 1);
- super.sendInternalEvent(roundUpTime);
+ super.sendInternalEvent(executionTime);
return true;
}
@@ -634,20 +633,22 @@
while(iterProfile.hasNext()) {
AvailabilityProfileEntry entry = iterProfile.next();
- anchorEntry = entry;
- anchorIndex = availProfile_.indexOf(anchorEntry);
-
- // sets the start time as the time of the entry
- potStartTime = entry.getTime();
- // calculates when the finish time will be if
- // the gridlet is put at this position
- potFinishTime = potStartTime + duration;
// scan the profile until an entry with enough PEs is found
if(entry.getNumPE() < reqPE) {
continue;
}
else {
+
+ anchorEntry = entry;
+ anchorIndex = availProfile_.indexOf(anchorEntry);
+
+ // sets the start time as the time of the entry
+ potStartTime = entry.getTime();
+ // calculates when the finish time will be if
+ // the gridlet is put at this position
+ potFinishTime = potStartTime + duration;
+
// if an entry with enough PEs is found, then scan the profile
// from that point onwards analysing the intersection of
// the ranges available in the entries until the
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java 2008-02-08 03:25:23 UTC (rev 91)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java 2008-02-10 06:04:30 UTC (rev 92)
@@ -157,76 +157,6 @@
// ---------------------------- STATIC METHODS ------------------------
/**
- * Returns the common range between two ranges of PEs
- * @param rangea the first range
- * @param rangeb the second range
- * @return the common range of PEs
- */
- public static PERange intersection(PERange rangea, PERange rangeb){
- if(rangea == null || rangeb == null)
- return null;
-
- int starta = rangea.getBeginning();
- int startb = rangeb.getBeginning();
- int enda = rangea.getEnd();
- int endb = rangeb.getEnd();
- int starti = -1;
- int endi = Integer.MAX_VALUE;
-
- while( !(starta > enda) && !(startb > endb) ){
- if(starta < startb){
- starta++;
- }
- else if(startb < starta){
- startb++;
- }
- else{
- if(starti < 0){
- starti = starta;
- }
- endi = starta;
- starta++;
- startb++;
- }
- }
-
- if(starti == -1 && endi == Integer.MAX_VALUE)
- return null;
-
- return new PERange(starti, endi);
- }
-
- /**
- * Checks whether two ranges have common elements
- * @param rangea the first range
- * @param rangeb the second range
- * @return <tt>true</tt> if the two ranges have an intersection
- * or <tt>false</tt> otherwise.
- */
- public static boolean intersect(PERange rangea, PERange rangeb){
- if(rangea == null || rangeb == null)
- return false;
-
- int starta = rangea.getBeginning();
- int startb = rangeb.getBeginning();
- int enda = rangea.getEnd();
- int endb = rangeb.getEnd();
-
- while( !(starta > enda) && !(startb > endb) ){
- if(starta < startb){
- starta++;
- }
- else if(startb < starta){
- startb++;
- }
- else{
- return true;
- }
- }
- return false;
- }
-
- /**
* Identifies the intersections between lists of ranges
* @param lista the first list
* @param listb the second list
@@ -271,13 +201,178 @@
}
/**
+ * Returns the result of subtracting the sequences of the
+ * second list from the first one.
+ * @param lista the first list of ranges
+ * @param listb the second list of ranges
+ * @return the range corresponding to the difference
+ */
+ public static PERangeList difference(PERangeList lista, PERangeList listb) {
+
+ if(lista == null || lista.getNumPE() == 0) {
+ return null;
+ }
+ else if(listb == null){
+ return lista.clone();
+ }
+
+ PERangeList difference = lista.clone();
+ difference.mergePERanges();
+
+ PERangeList universe = listb;
+ universe.sortRanges();
+
+ boolean finished = false;
+ while(!finished){
+ finished = true;
+ PERangeList diffRange = null;
+ look:{
+ Iterator<PERange> iterDiff = difference.iterator();
+ while(iterDiff.hasNext()) {
+ PERange rangeq = iterDiff.next();
+ for(PERange rangeu : universe ){
+ if(intersect(rangeq, rangeu)){
+ finished = false;
+ diffRange = difference(rangeq, rangeu);
+ iterDiff.remove();
+ break look;
+ }
+ }
+ }
+ }
+ if(diffRange != null){
+ difference.addAll(diffRange);
+ difference.sortRanges();
+ }
+ }
+
+ if(difference == null || difference.size() == 0){
+ return null;
+ }
+ else{
+ difference.mergePERanges();
+ return difference;
+ }
+ }
+
+ /**
+ * 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 ranges the list of free ranges.
+ * @return the range to be allocated or <tt>null</tt> if no
+ * range suitable is found.
+ */
+ public static PERangeList selectPERangeList(int reqPE, PERangeList ranges){
+ PERangeList selected = new PERangeList();
+ try{
+ ranges.sortRanges();
+ for(PERange range: ranges){
+ 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(Exception ex){
+ ex.printStackTrace();
+ selected = null;
+ }
+
+ return selected;
+ }
+
+ //TODO: The method below is not working properly. To fix it.
+ //TODO: As I am not using it at the moment, leave it as it is.
+ /**
+ * Returns the symmetric difference of two lists of ranges.
+ * The output sequence will contain all elements that are in the ranges
+ * of one list but are not in the ranges of the other.
+ * @param lista the first list of range
+ * @param listb the second list of range
+ * @return the range corresponding to the symmetric difference
+ */
+ public static PERangeList symmetricDifference(PERangeList lista, PERangeList listb){
+ if(lista == null || listb == null)
+ return null;
+
+ PERangeList query = lista;
+ PERangeList universe = listb;
+
+ for(PERange rangeq : query){
+ boolean intersected = false;
+ PERangeList tempDiff = new PERangeList();
+ Iterator<PERange> iterUni = universe.iterator();
+ while( !intersected || iterUni.hasNext()){
+ PERange rangeu = iterUni.next();
+ if(intersect(rangeq, rangeu)){
+ PERangeList diffRange = symmetricDifference(rangeq, rangeu);
+ if(diffRange != null){
+ tempDiff.addAll(diffRange);
+ }
+ intersected = true;
+ }
+ else{
+ tempDiff.add(rangeu);
+ }
+ }
+ if(!intersected){
+ tempDiff.add(rangeq);
+ }
+ universe = tempDiff.clone();
+ }
+
+ if(universe == null || universe.size() == 0){
+ return null;
+ }
+ else{
+ universe.mergePERanges();
+ return universe;
+ }
+ }
+
+ /**
+ * Method that returns true if there are overlaps between the
+ * ranges in this list. Note that this method is used for debugging purposes
+ * as there should not be overlaps in any list used thoughout the simulation.
+ * @param list the list to be analysed.
+ * @return <tt>true</tt> if there are overlaps; <tt>false</tt> otherwise.
+ */
+ public static boolean containsOverlappingRanges(PERangeList list){
+ if(list == null || list.getNumPE() == 0) {
+ return false;
+ }
+
+ boolean intersect = false;
+ for(PERange rq : list) {
+ for(PERange ru : list) {
+ if(rq != ru) {
+ intersect = PERangeList.intersect(rq, ru);
+ if(intersect)
+ return true;
+ }
+ }
+ }
+
+ return false;
+ }
+
+ // ---------------------------- PRIVATE METHODS ------------------------
+
+ /**
* Returns the list of ranges resulting from subtracting the second
* range from the first one.
* @param rangea the first range
* @param rangeb the second range
* @return the range corresponding to the difference
*/
- public static PERangeList difference(PERange rangea, PERange rangeb){
+ private static PERangeList difference(PERange rangea, PERange rangeb){
if(rangea == null || rangeb == null)
return null;
@@ -342,58 +437,73 @@
}
/**
- * Returns the result of subtracting the sequences of the
- * second list from the first one.
- * @param lista the first list of ranges
- * @param listb the second list of ranges
- * @return the range corresponding to the difference
+ * Returns the common range between two ranges of PEs
+ * @param rangea the first range
+ * @param rangeb the second range
+ * @return the common range of PEs
*/
- public static PERangeList difference(PERangeList lista, PERangeList listb) {
-
- if(lista == null || lista.getNumPE() == 0) {
+ private static PERange intersection(PERange rangea, PERange rangeb){
+ if(rangea == null || rangeb == null)
return null;
- }
- else if(listb == null){
- return lista.clone();
- }
- PERangeList difference = lista.clone();
- difference.mergePERanges();
+ int starta = rangea.getBeginning();
+ int startb = rangeb.getBeginning();
+ int enda = rangea.getEnd();
+ int endb = rangeb.getEnd();
+ int starti = -1;
+ int endi = Integer.MAX_VALUE;
- PERangeList universe = listb;
- universe.sortRanges();
-
- boolean finished = false;
- while(!finished){
- finished = true;
- PERangeList diffRange = null;
- look:{
- Iterator<PERange> iterDiff = difference.iterator();
- while(iterDiff.hasNext()) {
- PERange rangeq = iterDiff.next();
- for(PERange rangeu : universe ){
- if(intersect(rangeq, rangeu)){
- finished = false;
- diffRange = difference(rangeq, rangeu);
- iterDiff.remove();
- break look;
- }
- }
- }
+ while( !(starta > enda) && !(startb > endb) ){
+ if(starta < startb){
+ starta++;
}
- if(diffRange != null){
- difference.addAll(diffRange);
- difference.sortRanges();
- }
+ else if(startb < starta){
+ startb++;
+ }
+ else{
+ if(starti < 0){
+ starti = starta;
+ }
+ endi = starta;
+ starta++;
+ startb++;
+ }
}
+
+ if(starti == -1 && endi == Integer.MAX_VALUE)
+ return null;
- if(difference == null || difference.size() == 0){
- return null;
+ return new PERange(starti, endi);
+ }
+
+ /**
+ * Checks whether two ranges have common elements
+ * @param rangea the first range
+ * @param rangeb the second range
+ * @return <tt>true</tt> if the two ranges have an intersection
+ * or <tt>false</tt> otherwise.
+ */
+ private static boolean intersect(PERange rangea, PERange rangeb){
+ if(rangea == null || rangeb == null)
+ return false;
+
+ int starta = rangea.getBeginning();
+ int startb = rangeb.getBeginning();
+ int enda = rangea.getEnd();
+ int endb = rangeb.getEnd();
+
+ while( !(starta > enda) && !(startb > endb) ){
+ if(starta < startb){
+ starta++;
+ }
+ else if(startb < starta){
+ startb++;
+ }
+ else{
+ return true;
+ }
}
- else{
- difference.mergePERanges();
- return difference;
- }
+ return false;
}
/**
@@ -403,7 +513,7 @@
* @param rangeb the second range
* @return the range corresponding to the symmetric difference
*/
- public static PERangeList symmetricDifference(PERange rangea, PERange rangeb){
+ private static PERangeList symmetricDifference(PERange rangea, PERange rangeb){
if(rangea == null || rangeb == null)
return null;
@@ -474,55 +584,6 @@
return difference.size() == 0 ? null : difference;
}
-
- //TODO: The method below is not working properly. To fix it.
- //TODO: As I am not using it at the moment, leave it as it is.
- /**
- * Returns the symmetric difference of two lists of ranges.
- * The output sequence will contain all elements that are in the ranges
- * of one list but are not in the ranges of the other.
- * @param lista the first list of range
- * @param listb the second list of range
- * @return the range corresponding to the symmetric difference
- */
- public static PERangeList symmetricDifference(PERangeList lista, PERangeList listb){
- if(lista == null || listb == null)
- return null;
-
- PERangeList query = lista;
- PERangeList universe = listb;
-
- for(PERange rangeq : query){
- boolean intersected = false;
- PERangeList tempDiff = new PERangeList();
- Iterator<PERange> iterUni = universe.iterator();
- while( !intersected || iterUni.hasNext()){
- PERange rangeu = iterUni.next();
- if(intersect(rangeq, rangeu)){
- PERangeList diffRange = symmetricDifference(rangeq, rangeu);
- if(diffRange != null){
- tempDiff.addAll(diffRange);
- }
- intersected = true;
- }
- else{
- tempDiff.add(rangeu);
- }
- }
- if(!intersected){
- tempDiff.add(rangeq);
- }
- universe = tempDiff.clone();
- }
-
- if(universe == null || universe.size() == 0){
- return null;
- }
- else{
- universe.mergePERanges();
- return universe;
- }
- }
// FOR DEBUGGING PURPOSES ONLY...
// public static void main(String args[]){
@@ -540,4 +601,4 @@
//
// System.out.println("Consolidated# " + list);
// }
-}
+}
\ No newline at end of file
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java 2008-02-08 03:25:23 UTC (rev 91)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java 2008-02-10 06:04:30 UTC (rev 92)
@@ -357,7 +357,9 @@
// gets the error code. If the error code is EC_NO_ERROR
// it means that the reservation has been successful.
// Otherwise, print the error message...
[truncated message content] |
|
From: <mar...@us...> - 2008-03-02 22:54:11
|
Revision: 139
http://gridsim.svn.sourceforge.net/gridsim/?rev=139&view=rev
Author: marcos_dias
Date: 2008-03-02 14:53:59 -0800 (Sun, 02 Mar 2008)
Log Message:
-----------
QueuePartition is now a public class. Users extending the multi-partition policies may find it useful.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java
Added Paths:
-----------
branches/gridsim4.0-branch3/source/gridsim/turbo/QueuePartition.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java 2008-03-01 01:10:44 UTC (rev 138)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java 2008-03-02 22:53:59 UTC (rev 139)
@@ -1041,112 +1041,3 @@
return entry;
}
}
-
-/**
- * This class represents a partition in this scheduler. It only
- * stores a few variables used to control the partition.
- * @author Marcos Dias de Assuncao
- * @since GridSim Turbo Alpha 0.1
- */
-class QueuePartition {
- private int partitionId_; // this partition's identifier
- private int initialNumPEs_; // the initial number of PEs allocated
- private PERangeList idlePERanges_; // idle resources in this partition
-
- // to check whether a gridlet can be scheduled in this queue
- private QueuePartitionPredicate predicate_;
-
- /**
- * Creates a new <tt>Queuepartition</tt> object.
- * @param queueId the partition ID
- * @param numPE the number of PEs initially assigned to the partition
- * @param predicate the queue predicate
- * @see gridsim.turbo.QueuePartitionPredicate
- */
- public QueuePartition(int queueId,
- int numPE, QueuePartitionPredicate predicate) {
- this.partitionId_ = queueId;
- initialNumPEs_ = numPE;
- predicate_ = predicate;
- }
-
- /**
- * Gets the partition ID
- * @return the partition ID
- */
- public int getPartitionId() {
- return partitionId_;
- }
-
- /**
- * Sets the partition ID
- * @param partitionId the partition ID
- * @return <tt>true</tt> if set properly; <tt>false</tt> otherwise.
- */
- public boolean setPartitionId(int partitionId) {
- if(partitionId < 0)
- return false;
-
- partitionId_ = partitionId;
- return true;
- }
-
- /**
- * Gets the number of PEs initially assigned to the partition
- * @return the number of PEs initially assigned to the partition
- */
- public int getInitialNumPEs() {
- return initialNumPEs_;
- }
-
- /**
- * Sets the number of PEs initially assigned to the partition
- * @param initialNumPEs the number of PEs initially assigned
- * @return <tt>true</tt> if set properly; <tt>false</tt> otherwise.
- */
- public boolean setInitialNumPEs(int initialNumPEs) {
- if(initialNumPEs < 0)
- return false;
-
- initialNumPEs_ = initialNumPEs;
- return true;
- }
-
- /**
- * Gets the number of PEs currently idle at a partition
- * @return the number of PEs currently idle at a partition
- */
- public PERangeList getIdlePERanges() {
- return idlePERanges_;
- }
-
- /**
- * Sets the number of PEs currently idle at a partition
- * @param idlePERanges the number of PEs currently idle at a partition
- */
- public void setIdlePERanges(PERangeList idlePERanges) {
- idlePERanges_ = idlePERanges;
- }
-
- /**
- * Gets the predicate of this partition
- * @return the predicate of this partition
- */
- public QueuePartitionPredicate getPredicate() {
- return predicate_;
- }
-
- /**
- * Sets the predicate of this partition
- * @param predicate the predicate of this partition
- * @return <tt>true</tt> if set properly; <tt>false</tt> otherwise.
- */
- public boolean setPredicate(QueuePartitionPredicate predicate) {
- if(predicate == null)
- return false;
-
- predicate_ = predicate;
- return true;
- }
-}
-
Added: branches/gridsim4.0-branch3/source/gridsim/turbo/QueuePartition.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/QueuePartition.java (rev 0)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/QueuePartition.java 2008-03-02 22:53:59 UTC (rev 139)
@@ -0,0 +1,109 @@
+package gridsim.turbo;
+
+/**
+ * This class represents a partition in this scheduler. It only
+ * stores a few variables used to control the partition.
+ * @author Marcos Dias de Assuncao
+ * @since GridSim Turbo Alpha 0.1
+ */
+public class QueuePartition {
+ private int partitionId_; // this partition's identifier
+ private int initialNumPEs_; // the initial number of PEs allocated
+ private PERangeList idlePERanges_; // idle resources in this partition
+
+ // to check whether a gridlet can be scheduled in this queue
+ private QueuePartitionPredicate predicate_;
+
+ /**
+ * Creates a new <tt>Queuepartition</tt> object.
+ * @param queueId the partition ID
+ * @param numPE the number of PEs initially assigned to the partition
+ * @param predicate the queue predicate
+ * @see gridsim.turbo.QueuePartitionPredicate
+ */
+ public QueuePartition(int queueId,
+ int numPE, QueuePartitionPredicate predicate) {
+ this.partitionId_ = queueId;
+ initialNumPEs_ = numPE;
+ predicate_ = predicate;
+ }
+
+ /**
+ * Gets the partition ID
+ * @return the partition ID
+ */
+ public int getPartitionId() {
+ return partitionId_;
+ }
+
+ /**
+ * Sets the partition ID
+ * @param partitionId the partition ID
+ * @return <tt>true</tt> if set properly; <tt>false</tt> otherwise.
+ */
+ public boolean setPartitionId(int partitionId) {
+ if(partitionId < 0)
+ return false;
+
+ partitionId_ = partitionId;
+ return true;
+ }
+
+ /**
+ * Gets the number of PEs initially assigned to the partition
+ * @return the number of PEs initially assigned to the partition
+ */
+ public int getInitialNumPEs() {
+ return initialNumPEs_;
+ }
+
+ /**
+ * Sets the number of PEs initially assigned to the partition
+ * @param initialNumPEs the number of PEs initially assigned
+ * @return <tt>true</tt> if set properly; <tt>false</tt> otherwise.
+ */
+ public boolean setInitialNumPEs(int initialNumPEs) {
+ if(initialNumPEs < 0)
+ return false;
+
+ initialNumPEs_ = initialNumPEs;
+ return true;
+ }
+
+ /**
+ * Gets the number of PEs currently idle at a partition
+ * @return the number of PEs currently idle at a partition
+ */
+ public PERangeList getIdlePERanges() {
+ return idlePERanges_;
+ }
+
+ /**
+ * Sets the number of PEs currently idle at a partition
+ * @param idlePERanges the number of PEs currently idle at a partition
+ */
+ public void setIdlePERanges(PERangeList idlePERanges) {
+ idlePERanges_ = idlePERanges;
+ }
+
+ /**
+ * Gets the predicate of this partition
+ * @return the predicate of this partition
+ */
+ public QueuePartitionPredicate getPredicate() {
+ return predicate_;
+ }
+
+ /**
+ * Sets the predicate of this partition
+ * @param predicate the predicate of this partition
+ * @return <tt>true</tt> if set properly; <tt>false</tt> otherwise.
+ */
+ public boolean setPredicate(QueuePartitionPredicate predicate) {
+ if(predicate == null)
+ return false;
+
+ predicate_ = predicate;
+ return true;
+ }
+}
\ No newline at end of file
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-03-09 02:52:01
|
Revision: 141
http://gridsim.svn.sourceforge.net/gridsim/?rev=141&view=rev
Author: marcos_dias
Date: 2008-03-08 18:52:03 -0800 (Sat, 08 Mar 2008)
Log Message:
-----------
This update includes an option in the aggressive backfilling policies that allows the user to provide an implementation of comparator, which defines how the queued jobs are ordered.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfileEntry.java
branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfileEntry.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfileEntry.java 2008-03-05 02:36:56 UTC (rev 140)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfileEntry.java 2008-03-09 02:52:03 UTC (rev 141)
@@ -3,7 +3,6 @@
* 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;
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java 2008-03-05 02:36:56 UTC (rev 140)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java 2008-03-09 02:52:03 UTC (rev 141)
@@ -503,7 +503,7 @@
// iterates the waiting queue and for each gridlet, put the ranges
// used back in the profile. That is, updates the entries
- Collections.sort(queuedGridlets_, orderByPriority_);
+ Collections.sort(queuedGridlets_, jobOrderHeuristic_);
Iterator<SSGridlet> iterQueue = queuedGridlets_.iterator();
while(iterQueue.hasNext()) {
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-03-05 02:36:56 UTC (rev 140)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-03-09 02:52:03 UTC (rev 141)
@@ -15,6 +15,7 @@
import gridsim.ParameterException;
import gridsim.gui.AllocationAction;
+import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collections;
import java.util.Comparator;
@@ -73,7 +74,7 @@
protected LinkedList<SSGridlet> runningGridlets_;
// Queue of Gridlets waiting in this queue
- protected LinkedList<SSGridlet> queuedGridlets_;
+ protected ArrayList<SSGridlet> queuedGridlets_;
// The rating of one PE
protected int ratingPE_;
@@ -84,8 +85,8 @@
// The availability profile
protected MPAvailabilityProfile profile_;
- // to order the gridlets according to their priorities and submission times
- protected OrderGridletsByPriority orderByPriority_;
+ // heuristic used to order the jobs for backfilling
+ protected Comparator<SSGridlet> jobOrderHeuristic_;
// used by the scheduler to specify the priority of the item
protected PrioritySelector prioritySelector_;
@@ -141,8 +142,8 @@
// initialises local data structure
runningGridlets_ = new LinkedList<SSGridlet>();
- queuedGridlets_ = new LinkedList<SSGridlet>();
- orderByPriority_ = new OrderGridletsByPriority();
+ queuedGridlets_ = new ArrayList<SSGridlet>();
+ jobOrderHeuristic_ = new OrderGridletsByPriority();
numPartitions_ = numPartitions;
profile_ = new MPAvailabilityProfile();
prioritySelector_ = null;
@@ -188,6 +189,21 @@
}
/**
+ * Sets the heuristic used to order the jobs considered for backfilling
+ * @param comparator a comparator implementation that defines
+ * how gridlets are ordered.
+ * @return <tt>true</tt> if the heuristic was set correctly;
+ * <tt>false</tt> otherwise.
+ */
+ public boolean setJobOrderingHeuristic(Comparator<SSGridlet> comparator) {
+ if(comparator == null)
+ return false;
+
+ jobOrderHeuristic_ = comparator;
+ return true;
+ }
+
+ /**
* Indicates whether the borrowing of resources of the partitions from
* one another is allowed or not.
* @param allow <tt>true</tt> indicates that it is allowed;
@@ -372,12 +388,8 @@
}
sgl.setPartitionID(queueId);
-
sgl.setStatus(Gridlet.QUEUED);
queuedGridlets_.add(sgl);
-
- // order gridlets according to their priorities
- Collections.sort(queuedGridlets_, orderByPriority_);
backfillGridlets(GridSim.clock());
//------------------ FOR DEBUGGING PURPOSES ONLY ----------------
@@ -592,14 +604,15 @@
EasyBackFillingPartition queue = getPartition(queueId);
- // if queue has a pivot already, then just add
- // the job to the waiting queue
+ // if queue has a pivot already, then check whether the pivot appears
+ // before in the queue after reordering. If it does, then the job
+ // to be scheduled becomes the new pivot
if(queue.pivot_ != null) {
- // 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())
+
+ int indexPivot = queuedGridlets_.indexOf(queue.pivot_);
+ int indexNewGrl = queuedGridlets_.indexOf(sgl);
+
+ if(indexPivot < indexNewGrl)
return false;
else {
profile_.updateEntriesAtProfile(queue.pivot_);
@@ -851,6 +864,9 @@
}
}
+ // order gridlets according to the job ordering heuristic provided
+ Collections.sort(queuedGridlets_, jobOrderHeuristic_);
+
// Start the execution of Gridlets that are queued and whose
// potential start execution time is smaller than reference time
Iterator<SSGridlet> iter = queuedGridlets_.iterator();
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-03-05 02:36:56 UTC (rev 140)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-03-09 02:52:03 UTC (rev 141)
@@ -16,6 +16,8 @@
import gridsim.gui.AllocationAction;
import java.util.Calendar;
+import java.util.Collections;
+import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
@@ -83,8 +85,11 @@
protected AvailabilityProfile availProfile_;
// the resource characteristics object to be used
- protected TResourceCharacteristics resource_;
+ protected TResourceCharacteristics resource_;
+ // heuristic used to order the jobs for backfilling
+ protected Comparator<SSGridlet> jobOrderHeuristic_;
+
// the last time when the schedule updated was called
private double lastScheduleUpdate_;
@@ -178,6 +183,21 @@
}
/**
+ * Sets the heuristic used to order the jobs considered for backfilling
+ * @param comparator a comparator implementation that defines
+ * how gridlets are ordered.
+ * @return <tt>true</tt> if the heuristic was set correctly;
+ * <tt>false</tt> otherwise.
+ */
+ public boolean setJobOrderingHeuristic(Comparator<SSGridlet> comparator) {
+ if(comparator == null)
+ return false;
+
+ jobOrderHeuristic_ = comparator;
+ 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
@@ -478,7 +498,6 @@
sgl.setPERangeList(selected);
// changes the Gridlet status
-// sgl.setStatus(Gridlet.QUEUED);
sgl.setStartTime(startTime);
sgl.setActualFinishTime(finishTime);
pivot_ = sgl;
@@ -679,6 +698,11 @@
pivot_ = null;
}
}
+
+ // order jobs according to the ordering heuristic provided.
+ // That is, if one was provided by the user.
+ if(jobOrderHeuristic_ != null)
+ Collections.sort(queuedGridlets_, jobOrderHeuristic_);
// Start the execution of Gridlets that are queued
Iterator<SSGridlet> iter = queuedGridlets_.iterator();
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-03-21 23:28:34
|
Revision: 163
http://gridsim.svn.sourceforge.net/gridsim/?rev=163&view=rev
Author: marcos_dias
Date: 2008-03-21 16:10:38 -0700 (Fri, 21 Mar 2008)
Log Message:
-----------
This update fixes a bug in the advance reservation policies. Immediate reservations could be refused if the start time was slightly smaller than current time. If the start time of an advance reservation is smaller than the current time, then the start time will be changed to current simulation time.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java 2008-03-19 08:30:54 UTC (rev 162)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java 2008-03-21 23:10:38 UTC (rev 163)
@@ -302,7 +302,7 @@
int duration = reservation.getDurationTime();
int reqPE = reservation.getNumPE();
- if(startTime == 0)
+ if(startTime == 0 || startTime < currentTime)
startTime = currentTime;
// creates a Server Side Reservation (i.e. SSReservation)
@@ -356,9 +356,16 @@
" PEs from " + startTime + " to " + (startTime + duration));
System.out.println("--> The resource could not handle the reservation.");
+ // Gets availability information and provides it as options
+ AvailabilityInfo availability = super.allowBorrowing_ ?
+ getAvailabilityInfo(startTime, Integer.MAX_VALUE) :
+ getAvailabilityInfo(sRes.getPartitionID(),
+ startTime, Integer.MAX_VALUE);
+
reservation.setStatus(Reservation.STATUS_FAILED);
- response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
- sendARMessage(response);
+ reservation.setReservationOptions(availability);
+ response.setErrorCode(ARMessage.EC_OPERATION_FAILURE_BUT_OPTIONS);
+ sendARMessage(response);
return;
}
@@ -700,7 +707,8 @@
* entries that correspond to the availability profile between the times
* specified by the requester.
*/
- protected AvailabilityInfo getAvailabilityInfo(double startTime, int duration) {
+ protected AvailabilityInfo getAvailabilityInfo(double startTime,
+ int duration) {
AvailabilityInfo list = new AvailabilityInfo();
int anchorIndex = -1;
@@ -1012,9 +1020,10 @@
// updates the availability profile accordingly
profile_.allocateImmediateRanges(queueId, startTime + duration, selected);
+ return true;
}
// Tries all the queues
- else {
+ else if (super.allowBorrowing_) {
// gets all available PEs during given time interval
PERangeList overallAvailPEs =
@@ -1030,22 +1039,19 @@
// additional PEs required
int addRequired = reqPE - ranges.getNumPE();
- if(addRanges != null && addRanges.getNumPE() >= addRequired) {
- // borrows the additional PEs required from the partitions
- // and adds them into the specified queue
- addRanges = super.selectPERangeList(addRequired, addRanges);
- profile_.transferPEs(queueId, addRanges, startTime, startTime + duration);
+ // borrows the additional PEs required from the partitions
+ // and adds them into the specified queue
+ addRanges = super.selectPERangeList(addRequired, addRanges);
+ profile_.transferPEs(queueId, addRanges, startTime, startTime + duration);
- // allocates the ranges to the gridlet
- ranges.addAll(addRanges);
- profile_.allocateImmediateRanges(queueId, startTime + duration, ranges);
- res.setPERangeList(ranges);
- }
- else {
- return false;
- }
+ // allocates the ranges to the gridlet
+ ranges.addAll(addRanges);
+ profile_.allocateImmediateRanges(queueId, startTime + duration, ranges);
+ res.setPERangeList(ranges);
+ return true;
}
- return true;
+
+ return false;
}
/*
@@ -1089,8 +1095,10 @@
// allocates the ranges and updates the availability profile
profile_.allocatePERanges(queueId, anchorIndex,
tailIndex, selected, startTime, res.getActualFinishTime());
+
+ return true;
}
- else {
+ else if (super.allowBorrowing_) {
// number of additional PEs required
int addRequired = reqPE - ranges.getNumPE();
@@ -1131,9 +1139,11 @@
ranges, startTime, startTime + duration);
res.setPERangeList(ranges);
+
+ return true;
}
- return true;
+ return false;
}
/**
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java 2008-03-19 08:30:54 UTC (rev 162)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java 2008-03-21 23:10:38 UTC (rev 163)
@@ -306,7 +306,7 @@
int duration = reservation.getDurationTime();
int reqPE = reservation.getNumPE();
- if(startTime == 0)
+ if(startTime == 0 || startTime < currentTime)
startTime = currentTime;
// creates a Server Side Reservation (i.e. SSReservation)
@@ -360,9 +360,16 @@
" PEs from " + startTime + " to " + (startTime + duration));
System.out.println("--> The resource could not handle the reservation.");
+ // Gets availability information and provides it as options
+ AvailabilityInfo availability = super.allowBorrowing_ ?
+ getAvailabilityInfo(startTime, Integer.MAX_VALUE) :
+ getAvailabilityInfo(sRes.getPartitionID(),
+ startTime, Integer.MAX_VALUE);
+
reservation.setStatus(Reservation.STATUS_FAILED);
- response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
- sendARMessage(response);
+ reservation.setReservationOptions(availability);
+ response.setErrorCode(ARMessage.EC_OPERATION_FAILURE_BUT_OPTIONS);
+ sendARMessage(response);
return;
}
@@ -1019,9 +1026,11 @@
// updates the availability profile accordingly
profile_.allocateImmediateRanges(queueId, startTime + duration, selected);
+
+ return true;
}
// Tries all the queues
- else {
+ else if (super.allowBorrowing_) {
// gets all available PEs during given time interval
PERangeList overallAvailPEs =
@@ -1037,22 +1046,20 @@
// additional PEs required
int addRequired = reqPE - ranges.getNumPE();
- if(addRanges != null && addRanges.getNumPE() >= addRequired) {
- // borrows the additional PEs required from the partitions
- // and adds them into the specified queue
- addRanges = super.selectPERangeList(addRequired, addRanges);
- profile_.transferPEs(queueId, addRanges, startTime, startTime + duration);
+ // borrows the additional PEs required from the partitions
+ // and adds them into the specified queue
+ addRanges = super.selectPERangeList(addRequired, addRanges);
+ profile_.transferPEs(queueId, addRanges, startTime, startTime + duration);
- // allocates the ranges to the gridlet
- ranges.addAll(addRanges);
- profile_.allocateImmediateRanges(queueId, startTime + duration, ranges);
- res.setPERangeList(ranges);
- }
- else {
- return false;
- }
+ // allocates the ranges to the gridlet
+ ranges.addAll(addRanges);
+ profile_.allocateImmediateRanges(queueId, startTime + duration, ranges);
+ res.setPERangeList(ranges);
+
+ return true;
}
- return true;
+
+ return false;
}
/*
@@ -1096,8 +1103,10 @@
// allocates the ranges and updates the availability profile
profile_.allocatePERanges(queueId, anchorIndex,
tailIndex, selected, startTime, res.getActualFinishTime());
+
+ return true;
}
- else {
+ else if(super.allowBorrowing_) {
// number of additional PEs required
int addRequired = reqPE - ranges.getNumPE();
@@ -1138,9 +1147,11 @@
ranges, startTime, startTime + duration);
res.setPERangeList(ranges);
+
+ return true;
}
- return true;
+ return false;
}
/**
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-03-19 08:30:54 UTC (rev 162)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-03-21 23:10:38 UTC (rev 163)
@@ -239,7 +239,7 @@
boolean success = true;
// if start time is 0, then it is an immediate reservation
- if(startTime == 0 || startTime == currentTime) {
+ if(startTime == 0 || startTime <= currentTime) {
// sets the start time of the reservation as the current time
startTime = currentTime;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-05-08 07:44:12
|
Revision: 172
http://gridsim.svn.sourceforge.net/gridsim/?rev=172&view=rev
Author: marcos_dias
Date: 2008-05-08 00:44:14 -0700 (Thu, 08 May 2008)
Log Message:
-----------
Small improvements in the allocation policies to allow the user to extend the advance reservation methods and implement his own logging features.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ARTPolicy.java
branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java
branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java
branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java
branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -294,29 +294,40 @@
/**
* Handles an advance reservation request.<br>
* @param message the advance reservation message received
+ * @return <tt>true</tt> if the reservation has been accepted;
+ * <tt>false</tt> otherwise.
* @pre message != null
*/
- public void handleCreateReservation(ARMessage message) {
+ public boolean handleCreateReservation(ARMessage message) {
double currentTime = GridSim.clock();
+ boolean success;
// gets the reservation object and extract some
// information from it
Reservation reservation = message.getReservation();
- double startTime = reservation.getStartTime();
- int duration = reservation.getDurationTime();
- int reqPE = reservation.getNumPE();
- if(startTime == 0 || startTime < currentTime)
- startTime = currentTime;
-
// creates a Server Side Reservation (i.e. SSReservation)
SSReservation sRes = new SSReservation(reservation);
- sRes.setPartitionID(profile_.getCorrespondingPartitionID(sRes));
- double expTime = Double.NaN;
-
+
// creates a response message to be sent to the requester
ARMessage response = message.createResponse();
+ // validate the reservation, check num of PEs required, partition, etc.
+ success = validateReservation(sRes);
+
+ if(!success) {
+ reservation.setStatus(Reservation.STATUS_FAILED);
+ response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
+ sendARMessage(response);
+ return false;
+ }
+
+ double startTime = reservation.getStartTime();
+ if(startTime == 0 || startTime < currentTime)
+ startTime = currentTime;
+
+ double expTime = Double.NaN;
+
//-------------- FOR DEBUGGING PURPOSES ONLY --------------
// informs the listeners that a reservation request has arrived
@@ -324,24 +335,7 @@
AllocationAction.ITEM_ARRIVED, true, sRes);
//----------------------------------------------------------
-
- if (reqPE > super.totalPE_) {
- String userName = GridSim.getEntityName( message.getSourceID() );
- System.out.println(super.get_name() + ".handleCreateReservation():" +
- " Reservation #" + reservation.getID() + " from " +
- userName + " user requires " + reservation.getNumPE() +
- " PEs from " + startTime + " to " + (startTime + duration));
- System.out.println("--> The resource has only " +
- super.totalPE_ + " PEs available.");
-
- reservation.setStatus(Reservation.STATUS_FAILED);
- response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
- sendARMessage(response);
- return;
- }
- boolean success = true;
-
// if start time = current time, then it is an immediate reservation
if(startTime == currentTime) {
success = handleImmediateReservation(sRes);
@@ -355,9 +349,9 @@
if(!success) {
String userName = GridSim.getEntityName( message.getSourceID() );
System.out.println(super.get_name() + ".handleCreateReservation():" +
- " Reservation #" + reservation.getID() + " from " +
- userName + " user requires " + reservation.getNumPE() +
- " PEs from " + startTime + " to " + (startTime + duration));
+ " Reservation #" + sRes.getID() + " from " +
+ userName + " user requires " + sRes.getNumPE() +
+ " PEs from " + startTime + " to " + sRes.getActualFinishTime());
System.out.println("--> The resource could not handle the reservation.");
// Gets availability information and provides it as options
@@ -370,7 +364,7 @@
reservation.setReservationOptions(availability);
response.setErrorCode(ARMessage.EC_OPERATION_FAILURE_BUT_OPTIONS);
sendARMessage(response);
- return;
+ return false;
}
// if the expiration time is greater than the start time of the
@@ -408,13 +402,18 @@
// Informs the listeners about the reservation that has been created
GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_SCHEDULED,
true, sRes);
+
+ //----------------------------------------------------------
+ return true;
}
/**
* Handles a commit reservation request.
* @param message the advance reservation message received
+ * @return <tt>true</tt> if the reservation has been committed;
+ * <tt>false</tt> otherwise.
*/
- public void handleCommitReservation(ARMessage message) {
+ public boolean handleCommitReservation(ARMessage message) {
// gets the reservation id of the message
int reservationId = message.getReservationID();
@@ -462,7 +461,7 @@
if(!success) {
response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
sendARMessage(response);
- return;
+ return false;
}
// sets the reservation to committed if it has not been set before
@@ -481,28 +480,32 @@
GridSim.notifyListeners(this.get_id(),
AllocationAction.ITEM_STATUS_CHANGED, true, sRes);
-
//----------------------------------------------------------
+ return true;
}
/**
* Handles a modify reservation request<br>
* (NOTE: <b>NOT SUPPORTED YET</b>).
* @param message the advance reservation message received.
+ * @return <tt>false</tt>.
*/
- public void handleModifyReservation(ARMessage message) {
+ public boolean handleModifyReservation(ARMessage message) {
System.out.println(super.get_name() +
".handleModifyReservation(): not supported at the moment.");
+ return false;
}
/**
* Handles a cancel reservation request<br>
* (NOTE: <b>NOT SUPPORTED YET</b>).
* @param message the advance reservation message received.
+ * @return <tt>false</tt>.
*/
- public void handleCancelReservation(ARMessage message) {
+ public boolean handleCancelReservation(ARMessage message) {
System.out.println(super.get_name() +
".handleCancelReservation(): not supported at the moment.");
+ return false;
}
/**
@@ -589,6 +592,41 @@
// --------------------- PROTECTED METHODS -----------------------
/**
+ * Checks whether the reservation can be handled by the resource. That is,
+ * verifies if it does not require more resources than what the resource
+ * can provide and if the corresponding partition can handle the reservation.
+ * @param res the server side reservation to be examined
+ * @return <tt>true</tt> if it can be handled; <tt>false</tt> otherwise.
+ */
+ protected boolean validateReservation(SSReservation res) {
+ int reqPE = res.getNumPE();
+
+ if (reqPE > super.totalPE_) {
+ String userName = GridSim.getEntityName( res.getSenderID() );
+ System.out.println(super.get_name() + ".validateReservation():" +
+ " Reservation #" + res.getID() + " from " +
+ userName + " user requires " + reqPE +
+ " PEs from " + res.getStartTime() + " to " + res.getActualFinishTime());
+ System.out.println("--> The resource has only " +
+ super.totalPE_ + " PEs available.");
+ return false;
+ }
+
+ // gets the id of the partition that can handle the reservation
+ int partitionId = profile_.getCorrespondingPartitionID(res);
+ if(partitionId == UNKNOWN) {
+ String userName = GridSim.getEntityName( res.getSenderID() );
+ System.out.println(super.get_name() + ".validateReservation():" +
+ " Reservation #" + res.getID() + " from " +
+ userName + " cannot be served because no partition can do so.");
+ return false;
+ }
+
+ res.setPartitionID(partitionId);
+ return true;
+ }
+
+ /**
* 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
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -302,29 +302,40 @@
/**
* Handles an advance reservation request.<br>
* @param message the advance reservation message received
+ * @return <tt>true</tt> if the reservation has been accepted;
+ * <tt>false</tt> otherwise.
* @pre message != null
*/
- public void handleCreateReservation(ARMessage message) {
+ public boolean handleCreateReservation(ARMessage message) {
double currentTime = GridSim.clock();
+ boolean success;
// gets the reservation object and extract some
// information from it
Reservation reservation = message.getReservation();
- double startTime = reservation.getStartTime();
- int duration = reservation.getDurationTime();
- int reqPE = reservation.getNumPE();
- if(startTime == 0 || startTime < currentTime)
- startTime = currentTime;
-
// creates a Server Side Reservation (i.e. SSReservation)
SSReservation sRes = new SSReservation(reservation);
- sRes.setPartitionID(profile_.getCorrespondingPartitionID(sRes));
- double expTime = Double.NaN;
-
+
// creates a response message to be sent to the requester
ARMessage response = message.createResponse();
+ // validate the reservation, check num of PEs required, partition, etc.
+ success = validateReservation(sRes);
+
+ if(!success) {
+ reservation.setStatus(Reservation.STATUS_FAILED);
+ response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
+ sendARMessage(response);
+ return false;
+ }
+
+ double startTime = reservation.getStartTime();
+ if(startTime == 0 || startTime < currentTime)
+ startTime = currentTime;
+
+ double expTime = Double.NaN;
+
//-------------- FOR DEBUGGING PURPOSES ONLY --------------
// informs the listeners that a reservation request has arrived
@@ -332,24 +343,7 @@
AllocationAction.ITEM_ARRIVED, true, sRes);
//----------------------------------------------------------
-
- if (reqPE > super.totalPE_) {
- String userName = GridSim.getEntityName( message.getSourceID() );
- System.out.println(super.get_name() + ".handleCreateReservation():" +
- " Reservation #" + reservation.getID() + " from " +
- userName + " user requires " + reservation.getNumPE() +
- " PEs from " + startTime + " to " + (startTime + duration));
- System.out.println("--> The resource has only " +
- super.totalPE_ + " PEs available.");
-
- reservation.setStatus(Reservation.STATUS_FAILED);
- response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
- sendARMessage(response);
- return;
- }
- boolean success = false;
-
// if start time = current time, then it is an immediate reservation
if(startTime == currentTime) {
success = handleImmediateReservation(sRes);
@@ -363,9 +357,9 @@
if(!success) {
String userName = GridSim.getEntityName( message.getSourceID() );
System.out.println(super.get_name() + ".handleCreateReservation():" +
- " Reservation #" + reservation.getID() + " from " +
- userName + " user requires " + reservation.getNumPE() +
- " PEs from " + startTime + " to " + (startTime + duration));
+ " Reservation #" + sRes.getID() + " from " +
+ userName + " user requires " + sRes.getNumPE() +
+ " PEs from " + startTime + " to " + sRes.getActualFinishTime());
System.out.println("--> The resource could not handle the reservation.");
// Gets availability information and provides it as options
@@ -378,7 +372,7 @@
reservation.setReservationOptions(availability);
response.setErrorCode(ARMessage.EC_OPERATION_FAILURE_BUT_OPTIONS);
sendARMessage(response);
- return;
+ return false;
}
// if the expiration time is greater than the start time of the
@@ -416,13 +410,18 @@
// Informs the listeners about the reservation that has been created
GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_SCHEDULED,
true, sRes);
+
+ //----------------------------------------------------------
+ return true;
}
/**
* Handles a commit reservation request.
* @param message the advance reservation message received
+ * @return <tt>true</tt> if the reservation has been accepted;
+ * <tt>false</tt> otherwise.
*/
- public void handleCommitReservation(ARMessage message) {
+ public boolean handleCommitReservation(ARMessage message) {
// gets the reservation id of the message
int reservationId = message.getReservationID();
@@ -470,7 +469,7 @@
if(!success) {
response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
sendARMessage(response);
- return;
+ return false;
}
// sets the reservation to committed if it has not been set before
@@ -491,26 +490,31 @@
AllocationAction.ITEM_STATUS_CHANGED, true, sRes);
//----------------------------------------------------------
+ return true;
}
/**
* Handles a modify reservation request<br>
* (NOTE: <b>NOT SUPPORTED YET</b>).
* @param message the advance reservation message received.
+ * @return <tt>false</tt>.
*/
- public void handleModifyReservation(ARMessage message) {
+ public boolean handleModifyReservation(ARMessage message) {
System.out.println(super.get_name() +
".handleModifyReservation(): not supported at the moment.");
+ return false;
}
/**
* Handles a cancel reservation request<br>
* (NOTE: <b>NOT SUPPORTED YET</b>).
* @param message the advance reservation message received.
+ * @return <tt>false</tt>.
*/
- public void handleCancelReservation(ARMessage message) {
+ public boolean handleCancelReservation(ARMessage message) {
System.out.println(super.get_name() +
".handleCancelReservation(): not supported at the moment.");
+ return false;
}
/**
@@ -597,6 +601,41 @@
// --------------------- PROTECTED METHODS -----------------------
/**
+ * Checks whether the reservation can be handled by the resource. That is,
+ * verifies if it does not require more resources than what the resource
+ * can provide and if the corresponding partition can handle the reservation.
+ * @param res the server side reservation to be examined
+ * @return <tt>true</tt> if it can be handled; <tt>false</tt> otherwise.
+ */
+ protected boolean validateReservation(SSReservation res) {
+ int reqPE = res.getNumPE();
+
+ if (reqPE > super.totalPE_) {
+ String userName = GridSim.getEntityName( res.getSenderID() );
+ System.out.println(super.get_name() + ".validateReservation():" +
+ " Reservation #" + res.getID() + " from " +
+ userName + " user requires " + reqPE +
+ " PEs from " + res.getStartTime() + " to " + res.getActualFinishTime());
+ System.out.println("--> The resource has only " +
+ super.totalPE_ + " PEs available.");
+ return false;
+ }
+
+ // gets the id of the partition that can handle the reservation
+ int partitionId = profile_.getCorrespondingPartitionID(res);
+ if(partitionId == UNKNOWN) {
+ String userName = GridSim.getEntityName( res.getSenderID() );
+ System.out.println(super.get_name() + ".validateReservation():" +
+ " Reservation #" + res.getID() + " from " +
+ userName + " cannot be served because no partition can do so.");
+ return false;
+ }
+
+ res.setPartitionID(partitionId);
+ return true;
+ }
+
+ /**
* 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
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -195,9 +195,11 @@
/**
* Handles an advance reservation request.<br>
* @param message the advance reservation message received
+ * @return <tt>true</tt> if the reservation was accepted;
+ * <tt>false</tt> otherwise.
* @pre message != null
*/
- public void handleCreateReservation(ARMessage message) {
+ public boolean handleCreateReservation(ARMessage message) {
double currentTime = GridSim.clock();
// gets the reservation object and extract some
@@ -233,7 +235,7 @@
reservation.setStatus(Reservation.STATUS_FAILED);
response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
sendARMessage(response);
- return;
+ return false;
}
boolean success = true;
@@ -380,16 +382,21 @@
reservation.setReservationOptions(availability);
response.setErrorCode(ARMessage.EC_OPERATION_FAILURE_BUT_OPTIONS);
sendARMessage(response);
+ return false;
}
+
+ return true;
}
/**
* This method handles a cancel reservation request.
* @param message the advance reservation message received requesting
* the cancellation
+ * @return <tt>true</tt> if the reservation was cancelled;
+ * <tt>false</tt> otherwise.
* @pre message != null
*/
- public void handleCancelReservation(ARMessage message) {
+ public boolean handleCancelReservation(ARMessage message) {
double currentTime = GridSim.clock();
// gets the reservation id of the message
@@ -426,7 +433,7 @@
if(!success) {
response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
sendARMessage(response);
- return;
+ return false;
}
boolean inProgress = sRes.getStatus() == Reservation.STATUS_IN_PROGRESS;
@@ -461,13 +468,16 @@
// send the response message back to the requester
sendARMessage(response);
+ return true;
}
/**
* Handles a commit reservation request.
* @param message the advance reservation message received
+ * @return <tt>true</tt> if the reservation was committed;
+ * <tt>false</tt> otherwise.
*/
- public void handleCommitReservation(ARMessage message) {
+ public boolean handleCommitReservation(ARMessage message) {
double currentTime = GridSim.clock();
@@ -517,7 +527,7 @@
if(!success) {
response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
sendARMessage(response);
- return;
+ return false;
}
// sets the reservation to committed if it has not been set before
@@ -538,16 +548,19 @@
AllocationAction.ITEM_STATUS_CHANGED, true, sRes);
//----------------------------------------------------------
+ return true;
}
/**
* Handles a modify reservation request<br>
* (NOTE: <b>NOT SUPPORTED YET</b>).
* @param message the advance reservation message received.
+ * @return <tt>false</tt>.
*/
- public void handleModifyReservation(ARMessage message) {
+ public boolean handleModifyReservation(ARMessage message) {
System.out.println(super.get_name() +
".handleModifyReservation(): not supported at the moment.");
+ return false;
}
/**
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARTPolicy.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARTPolicy.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARTPolicy.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -30,32 +30,40 @@
* A method that handles a new advanced reservation request.
* @param message the advance reservation message received requesting
* the reservation
+ * @return <tt>true</tt> if the reservation was accepted;
+ * <tt>false</tt> otherwise.
* @pre message != null
*/
- void handleCreateReservation(ARMessage message);
+ boolean handleCreateReservation(ARMessage message);
/**
* A method that handles a modify reservation request.
* @param message the advance reservation message received requesting
- * the change
+ * the change
+ * @return <tt>true</tt> if the reservation was modified;
+ * <tt>false</tt> otherwise.
* @pre message != null
*/
- void handleModifyReservation(ARMessage message);
+ boolean handleModifyReservation(ARMessage message);
/**
* A method that handles a cancel reservation request.
* @param message the advance reservation message received requesting
* the cancellation
+ * @return <tt>true</tt> if the reservation was cancelled;
+ * <tt>false</tt> otherwise.
* @pre message != null
*/
- void handleCancelReservation(ARMessage message);
+ boolean handleCancelReservation(ARMessage message);
/**
* A method that handles a commit reservation request.
* @param message the advance reservation message received
+ * @return <tt>true</tt> if the reservation was committed;
+ * <tt>false</tt> otherwise.
* @pre message != null
*/
- void handleCommitReservation(ARMessage message);
+ boolean handleCommitReservation(ARMessage message);
/**
* A method that handles a query reservation request.
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -94,31 +94,23 @@
* 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.");
+ // Create a server side Gridlet
+ SSGridlet sgl = new SSGridlet(gridlet);
+ boolean success = super.validateGridlet(sgl);
+ if(!success) {
+ try {
+ // reject the Gridlet
gridlet.setGridletStatus(Gridlet.FAILED);
super.sendFinishGridlet(gridlet);
return;
}
+ catch(Exception ex) {
+ System.out.println(super.get_name() +
+ ": Exception on submission of a 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(),
@@ -126,29 +118,8 @@
//----------------------------------------------------------
- // the id of the queue where the job can be scheduled
- int queueId = profile_.getCorrespondingPartitionID(sgl);
-
- // if no queue can handle the gridlet, then reject it
- if(queueId == UNKNOWN) {
- String userName = GridSim.getEntityName( gridlet.getUserID() );
- System.out.println(super.get_name() + ".gridletSubmit(): " +
- " Gridlet #" + gridlet.getGridletID() + " from " +
- userName + " cannot be handled by any queue in this resource.");
- try {
- gridlet.setGridletStatus(Gridlet.FAILED);
- } catch (Exception ex) {
- System.out.println(super.get_name() +
- ": Exception on submission of a Gridlet");
- }
- super.sendFinishGridlet(gridlet);
- return;
- }
-
- sgl.setPartitionID(queueId);
-
// try to schedule gridlet immediately
- boolean success = startGridlet(sgl);
+ success = startGridlet(sgl);
if(!success) {
scheduleGridlet(sgl);
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -100,6 +100,16 @@
// partitions is allowed or not
protected boolean allowBorrowing_;
+ // indicates whether a gridlet should be returned to the user immediately
+ // if it could not be scheduled to its corresponding partition and the
+ // borrowing of resources from other partitions is disabled. That is, if
+ // a gridlet arrives to the resource, the partition does not have enough
+ // resources, borrowing is disabled and this attribute is true, the gridlet
+ // will be returned to the user entity. A user may want to change this
+ // behaviour if he wants to implement manual borrowing or resizing
+ // of the resource partitions
+ protected boolean returnGridlet_;
+
// the number of partitions or queues in this scheduler
protected int numPartitions_;
@@ -154,6 +164,7 @@
prioritySelector_ = null;
lastScheduleUpdate_ = 0.0D;
allowBorrowing_ = true;
+ returnGridlet_ = true;
ratingPE_ = 0;
}
@@ -219,6 +230,28 @@
}
/**
+ * This method is called to specify the behaviour of the policy if a gridlet
+ * cannot be scheduled to its partition due to the lack of enough resources
+ * and the borrowing is disabled. If a <tt>true</tt> value is passed to this
+ * method, it indicates that a gridlet should be returned to the user
+ * immediately if it could not be scheduled to its corresponding partition
+ * and the borrowing of resources from other partitions is disabled. That is,
+ * if a gridlet arrives at the resource, the partition does not have enough
+ * resources, borrowing is disabled and the returnGridlet behaviour is true,
+ * the gridlet will be returned to the user entity. This prevents the policy
+ * from queueing gridlets even if it will never be able to serve them.
+ * A user may want to change this behaviour if he wants to implement manual
+ * borrowing or resizing of the resource partitions. In such a case, the
+ * gridlets will be queued even if they cannot be handled by its partition
+ * at the time of arrival.
+ * @param returnGridlet <tt>true</tt> indicates that the gridlet should be
+ * returned; <tt>false</tt> otherwise.
+ */
+ public void setReturnGridletBehaviour(boolean returnGridlet) {
+ returnGridlet_ = returnGridlet;
+ }
+
+ /**
* Sets the priority selector to be used by this scheduler. The selector
* defines what priorities the scheduler should assign to the gridlets.
* @param selector the selector to be used.
@@ -339,30 +372,23 @@
* 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.");
+ // Create a server side Gridlet
+ SSGridlet sgl = new SSGridlet(gridlet);
+ boolean success = validateGridlet(sgl);
+ if(!success) {
+ try {
+ // reject the Gridlet
gridlet.setGridletStatus(Gridlet.FAILED);
super.sendFinishGridlet(gridlet);
return;
}
+ catch(Exception ex) {
+ System.out.println(super.get_name() +
+ ": Exception on submission of a 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);
if(prioritySelector_ != null)
sgl.setPriority(prioritySelector_.getSchedulePriority(sgl));
@@ -373,26 +399,6 @@
//----------------------------------------------------------
- // the id of the queue where the job can be scheduled
- int queueId = profile_.getCorrespondingPartitionID(sgl);
-
- // if no queue can handle the gridlet, then reject it
- if(queueId == UNKNOWN) {
- String userName = GridSim.getEntityName( gridlet.getUserID() );
- System.out.println(super.get_name() + ".gridletSubmit(): " +
- " Gridlet #" + gridlet.getGridletID() + " from " +
- userName + " cannot be handled by any queue in this resource.");
- try {
- gridlet.setGridletStatus(Gridlet.FAILED);
- } catch (Exception ex) {
- System.out.println(super.get_name() +
- ": Exception on submission of a Gridlet");
- }
- super.sendFinishGridlet(gridlet);
- return;
- }
-
- sgl.setPartitionID(queueId);
sgl.setStatus(Gridlet.QUEUED);
queuedGridlets_.add(sgl);
backfillGridlets(GridSim.clock());
@@ -611,6 +617,61 @@
// -------------------- PROTECTED METHODS ----------------------------
/**
+ * Checks whether the gridlet can be handled by the resource. That is,
+ * verifies if it does not require more resources than what the resource
+ * can provide and if the partition can handle the request.
+ * @param sgl the server side gridlet to be examined
+ * @return <tt>true</tt> if it can be handled; <tt>false</tt> otherwise.
+ */
+ protected boolean validateGridlet(SSGridlet sgl) {
+ int reqPE = sgl.getNumPE();
+
+ // reject the Gridlet if it requires more PEs than the resource
+ // is able to provide
+ if(reqPE > super.totalPE_){
+ String userName = GridSim.getEntityName(sgl.getSenderID());
+ System.out.println(super.get_name() + ".validateGridlet(): " +
+ " Gridlet #" + sgl.getID() + " from " +
+ userName + " user requires " + sgl.getNumPE() + " PEs.");
+ System.out.println("--> The resource has only " +
+ super.totalPE_ + " PEs.");
+ return false;
+ }
+
+ // the id of the queue where the job can be scheduled
+ int queueId = profile_.getCorrespondingPartitionID(sgl);
+
+ // if no queue can handle the gridlet, then reject it
+ if(queueId == UNKNOWN) {
+ String userName = GridSim.getEntityName(sgl.getSenderID());
+ System.out.println(super.get_name() + ".validateGridlet(): " +
+ " Gridlet #" + sgl.getID() + " from " +
+ userName + " cannot be handled by any partition of this resource.");
+ return false;
+ }
+ // if a partition can serve the gridlet, but it was not given enough
+ // resources to do so, the borrowing is disabled and the behaviour is
+ // to return the gridlet in such case, then returns false, forcing
+ // the gridlet to be returned to the user
+ else {
+ QueuePartition partition = profile_.getPartition(queueId);
+ if(!allowBorrowing_ && returnGridlet_
+ && partition.getInitialNumPEs() < reqPE) {
+ String userName = GridSim.getEntityName(sgl.getSenderID());
+ System.out.println(super.get_name() + ".validateGridlet(): " +
+ " Gridlet #" + sgl.getID() + " from " +
+ userName + " user requires " + sgl.getNumPE() + " PEs whereas the " +
+ "partition does not have enough resources and borrowing " +
+ "is disabled.");
+ return false;
+ }
+ }
+
+ sgl.setPartitionID(queueId);
+ return true;
+ }
+
+ /**
* Tries to start a gridlet if there are enough processing elements
* available at the current simulation time.
* @param sgl the gridlet to be started
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -261,6 +261,20 @@
}
/**
+ * Gets the idle PEs as a profile entry
+ * @return the ranges of PEs available at present in all partitions
+ */
+ public MPProfileEntry getIdlePEs() {
+ MPProfileEntry entry = new MPProfileEntry(GridSim.clock());
+ for(QueuePartition queue: queues_.values()) {
+ PERangeList list = queue.getIdlePERanges() == null ?
+ null : queue.getIdlePERanges().clone();
+ entry.setPERangeList(queue.getPartitionId(), list);
+ }
+ return entry;
+ }
+
+ /**
* Checks what PE ranges are available during the given interval.
* @param duration the duration of the Gridlet
* @return the list of ranges of PEs available
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -109,19 +109,22 @@
* @return the string representation
*/
public String toString() {
+ if(super.size() == 0)
+ return "{[]}";
+
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("{");
int index = -1;
int last = super.size() - 1;
- String delim = ",";
for(PERange range : this) {
index++;
stringBuilder.append(range);
- delim = index < last ? delim : "}";
- stringBuilder.append(delim);
+ if(index < last)
+ stringBuilder.append(",");
}
+ stringBuilder.append("}");
return stringBuilder.toString();
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -404,6 +404,24 @@
}
return result;
}
+
+ /**
+ * Creates a string representation of the reservation for debugging purposes.
+ * @return a string representation of this reservation.
+ * @see java.lang.Object#toString()
+ */
+ public String toString(){
+ StringBuilder stringBuilder = new StringBuilder();
+ stringBuilder.append("Reservation={Reservation ID: " + reservID_);
+ stringBuilder.append(", User ID: " + userID_);
+ stringBuilder.append(", Status: " + getStatusString(status_));
+ stringBuilder.append(", Sub. Time: " + submissionTime_);
+ stringBuilder.append(", Start Time: " + startTime_);
+ stringBuilder.append(", FinishTime: " + (startTime_ + duration_));
+ stringBuilder.append(", Duration: " + duration_);
+ stringBuilder.append(", Num. PEs: " + numPE_ + "}");
+ return stringBuilder.toString();
+ }
//------------------------ PRIVATE METHODS ------------------------
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -157,8 +157,8 @@
catch (Exception ex) {
System.out.println(super.get_name() + ": Reservation # " +
reservation.getID() + " has not been accepted by "+
- "resource # " + resID + " at time = " + GridSim.clock());
- ex.printStackTrace();
+ "resource # " + resID + " at time = " + GridSim.clock() +
+ ", exception=" + ex.getMessage());
reservation = null;
}
return reservation;
@@ -545,10 +545,11 @@
}
/**
- * Sends a reservation message.
+ * Sends a reservation message. This message is protected in case
+ * the user wants to change it to not consider network delay, for example.
* @param message the message to be sent
*/
- private void sendARMessage(ARMessage message) {
+ protected void sendARMessage(ARMessage message) {
// send message to the destination
super.send(message.getDestinationID(), GridSimTags.SCHEDULE_NOW,
message.getMessageType(), message);
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java 2008-04-28 06:23:28 UTC (rev 171)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java 2008-05-08 07:44:14 UTC (rev 172)
@@ -167,7 +167,8 @@
* @post $none
*/
protected double forecastExecutionTime(double availableRating, double length){
- double finishTime = (length / availableRating);
+ double finishTime = (length / availableRating);
+ finishTime = (long)(finishTime + 1);
// This is as a safeguard since the finish time can be extremely
// small close to 0.0, such as 4.5474735088646414E-14. Hence causing
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-05-11 00:55:14
|
Revision: 173
http://gridsim.svn.sourceforge.net/gridsim/?rev=173&view=rev
Author: marcos_dias
Date: 2008-05-10 17:55:20 -0700 (Sat, 10 May 2008)
Log Message:
-----------
Just a small fix in case the user does not want to specify an heuristic to order jobs in multiple partition policies.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java 2008-05-08 07:44:14 UTC (rev 172)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java 2008-05-11 00:55:20 UTC (rev 173)
@@ -511,7 +511,8 @@
// iterates the waiting queue and for each gridlet, put the ranges
// used back in the profile. That is, updates the entries
- Collections.sort(queuedGridlets_, jobOrderHeuristic_);
+ if(jobOrderHeuristic_ != null)
+ Collections.sort(queuedGridlets_, jobOrderHeuristic_);
Iterator<SSGridlet> iterQueue = queuedGridlets_.iterator();
while(iterQueue.hasNext()) {
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-05-08 07:44:14 UTC (rev 172)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-05-11 00:55:20 UTC (rev 173)
@@ -20,7 +20,6 @@
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
-import java.util.LinkedList;
/**
* This class implements a non-FCFS policy to schedule parallel jobs. The
@@ -76,7 +75,7 @@
public class EBMultiplePartitions extends TAllocPolicy {
// Queue of running Gridlets
- protected LinkedList<SSGridlet> runningGridlets_;
+ protected ArrayList<SSGridlet> runningGridlets_;
// Queue of Gridlets waiting in this queue
protected ArrayList<SSGridlet> queuedGridlets_;
@@ -156,7 +155,7 @@
}
// initialises local data structure
- runningGridlets_ = new LinkedList<SSGridlet>();
+ runningGridlets_ = new ArrayList<SSGridlet>();
queuedGridlets_ = new ArrayList<SSGridlet>();
jobOrderHeuristic_ = new OrderGridletsByPriority();
numPartitions_ = numPartitions;
@@ -1039,7 +1038,8 @@
}
// order gridlets according to the job ordering heuristic provided
- Collections.sort(queuedGridlets_, jobOrderHeuristic_);
+ if(jobOrderHeuristic_ != null)
+ Collections.sort(queuedGridlets_, jobOrderHeuristic_);
// Start the execution of Gridlets that are queued and whose
// potential start execution time is smaller than reference time
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-06-18 14:16:56
|
Revision: 185
http://gridsim.svn.sourceforge.net/gridsim/?rev=185&view=rev
Author: marcos_dias
Date: 2008-06-18 07:16:44 -0700 (Wed, 18 Jun 2008)
Log Message:
-----------
This update includes cancellation features in the advance reservation policy that uses conservative backfilling and multiple partitions
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/Lublin99Workload.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java 2008-06-17 07:21:14 UTC (rev 184)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java 2008-06-18 14:16:44 UTC (rev 185)
@@ -500,15 +500,86 @@
}
/**
- * Handles a cancel reservation request<br>
- * (NOTE: <b>NOT SUPPORTED YET</b>).
- * @param message the advance reservation message received.
- * @return <tt>false</tt>.
+ * This method handles a cancel reservation request.
+ * @param message the advance reservation message received requesting
+ * the cancellation
+ * @return <tt>true</tt> if the reservation was cancelled;
+ * <tt>false</tt> otherwise.
+ * @pre message != null
*/
public boolean handleCancelReservation(ARMessage message) {
- System.out.println(super.get_name() +
- ".handleCancelReservation(): not supported at the moment.");
- return false;
+ double currentTime = GridSim.clock();
+
+ // gets the reservation id of the message
+ int reservationId = message.getReservationID();
+ boolean success = true;
+ SSReservation sRes = null;
+
+ // creates a response message to be sent to the requester
+ ARMessage response = message.createResponse();
+
+ if(!reservTable_.containsKey(reservationId)
+ && !expiryTable_.containsKey(reservationId)) {
+
+ System.out.println(super.get_name() + ".handleCancelReservation() " +
+ "Reservation # " + reservationId + " cannot be cancelled " +
+ "because the allocation policy could not find it.");
+ success = false;
+ }
+ else if (expiryTable_.containsKey(reservationId)) {
+ System.out.println(super.get_name() + ".handleCancelReservation()" +
+ " Reservation # " + reservationId + " cannot be cancelled " +
+ " because it is already in the expiry list.");
+ success = false;
+ }
+ else if( (sRes = reservTable_.get(reservationId)).getActualFinishTime() <= currentTime ) {
+ System.out.println(super.get_name() + ".handleCancelReservation()" +
+ " Reservation # " + reservationId + " cannot be cancelled because " +
+ " it has already finished.");
+ success = false;
+ }
+
+ // if it was not possible to cancel the reservation, then return
+ // an error message back to the requester
+ if(!success) {
+ response.setErrorCode(ARMessage.EC_OPERATION_FAILURE);
+ sendARMessage(response);
+ return false;
+ }
+
+ boolean inProgress = sRes.getStatus() == Reservation.STATUS_IN_PROGRESS;
+
+ // remove the reservation from the reservation table
+ // and put it into the expiry table
+ reservTable_.remove(reservationId);
+ expiryTable_.put(reservationId, sRes);
+
+ // remove/update the entries of the profile
+ removeReservation(sRes);
+
+ // sets the status of the reservation to cancelled
+ sRes.setStatus(Reservation.STATUS_CANCELLED);
+
+ //----------------- USED FOR DEBUGGING PURPOSES ONLY -------------------
+
+ // If a gridlet has been cancelled, then inform the listeners
+ GridSim.notifyListeners(this.get_id(), AllocationAction.ITEM_CANCELLED, true, sRes);
+
+ //----------------------------------------------------------------------
+
+ // performs the compression of the schedule
+ compressSchedule(sRes.getStartTime(), inProgress);
+
+ //----------------- USED FOR DEBUGGING PURPOSES ONLY -------------------
+
+ // Inform the listeners about the new schedule
+ GridSim.notifyListeners(this.get_id(), AllocationAction.SCHEDULE_CHANGED, true);
+
+ //----------------------------------------------------------------------
+
+ // send the response message back to the requester
+ sendARMessage(response);
+ return true;
}
/**
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/Lublin99Workload.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/Lublin99Workload.java 2008-06-17 07:21:14 UTC (rev 184)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/Lublin99Workload.java 2008-06-18 14:16:44 UTC (rev 185)
@@ -1180,9 +1180,7 @@
System.out.println(super.get_name() + ": Collecting Gridlets ...");
list_ = new ArrayList<Gridlet>(gridletID_ + 1);
gridletsReturned_ = 1; // starts at 1, since gridletID_ starts at 1 too
-
Object data = null;
- Gridlet gl = null;
Sim_event ev = new Sim_event();
while ( Sim_system.running() )
@@ -1658,7 +1656,6 @@
}
return -1; // error, did not converged
}
-
/*
* Returns the GCF
@@ -1759,7 +1756,7 @@
w = logGamma(q);
p = Math.floor(q);
if (p == q)
- throw new ArithmeticException("lgamma: Overflow");
+ throw new ArithmeticException("logGamma: Overflow");
z = q - p;
if (z > 0.5) {
p += 1.0;
@@ -1767,7 +1764,7 @@
}
z = q * Math.sin(Math.PI * z);
if (z == 0.0)
- throw new ArithmeticException("lgamma: Overflow");
+ throw new ArithmeticException("logGamma: Overflow");
z = LOGPI - Math.log(z) - w;
return z;
}
@@ -1780,7 +1777,7 @@
}
while (x < 2.0) {
if (x == 0.0)
- throw new ArithmeticException("lgamma: Overflow");
+ throw new ArithmeticException("logGamma: Overflow");
z /= x;
x += 1.0;
}
@@ -1794,7 +1791,7 @@
}
if (x > 2.556348e305)
- throw new ArithmeticException("lgamma: Overflow");
+ throw new ArithmeticException("logGamma: Overflow");
q = (x - 0.5) * Math.log(x) - x + 0.91893853320467274178;
if (x > 1.0e8)
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-02-10 07:09:47
|
Revision: 94
http://gridsim.svn.sourceforge.net/gridsim/?rev=94&view=rev
Author: marcos_dias
Date: 2008-02-09 23:09:51 -0800 (Sat, 09 Feb 2008)
Log Message:
-----------
This update contains small bug fixes and improvements:
+ The advance reservation policy and the conservative backfilling could present overlapping ranges of available processing elements. Although that did not affect the resource allocation results, that could lead to infinite loops on software that queried the resource availability.
+ Small changes in the availability information objects and the lists of PEs.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-02-10 06:19:19 UTC (rev 93)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-02-10 07:09:51 UTC (rev 94)
@@ -261,7 +261,10 @@
Sim_event ev = new Sim_event();
while ( Sim_system.running() ) {
super.sim_get_next(ev);
- processEvent(ev);
+ if (ev.get_src() == super.myId_)
+ processEvent(ev);
+ else
+ processOtherEvent(ev);
}
// CHECK for ANY INTERNAL EVENTS WAITING TO BE PROCESSED
@@ -906,39 +909,32 @@
private void processEvent(Sim_event ev) {
// handle an internal event
- if(ev.get_src() == super.myId_) {
- double currentTime = GridSim.clock();
+ double currentTime = GridSim.clock();
- switch(ev.get_tag()) {
- // time to update the schedule, finish gridlets,
- // finish reservations, start reservations and start gridlets
- case GRIDLET_FINISHED:
- case START_RESERVATION:
- case FINISH_RESERVATION:
- if(currentTime > lastScheduleUpdate_) {
- updateSchedule();
- }
- lastScheduleUpdate_ = currentTime;
- break;
+ switch(ev.get_tag()) {
+ // time to update the schedule, finish gridlets,
+ // finish reservations, start reservations and start gridlets
+ case GRIDLET_FINISHED:
+ case START_RESERVATION:
+ case FINISH_RESERVATION:
+ if(currentTime > lastScheduleUpdate_) {
+ updateSchedule();
+ }
+ lastScheduleUpdate_ = currentTime;
+ break;
- // checks the expiry time for a given gridlet
- case EXPIRY_TIME:
- if(currentTime > lastCheckExpiryTime_) {
- checkExpiryTime();
- }
- lastCheckExpiryTime_ = currentTime;
- break;
+ // checks the expiry time for a given gridlet
+ case EXPIRY_TIME:
+ if(currentTime > lastCheckExpiryTime_) {
+ checkExpiryTime();
+ }
+ lastCheckExpiryTime_ = currentTime;
+ break;
- default:
- System.out.println(super.get_name() + ".processEvent():" +
- "could not handle the event with tag #" + ev.get_tag());
- break;
- }
- }
- else {
- System.out.println(super.get_name() + ".processEvent():" +
- "could not handle the event with tag #" + ev.get_tag());
- }
+ default:
+ processOtherEvent(ev);
+ break;
+ }
}
/**
@@ -2309,20 +2305,7 @@
int length = availProfile_.size();
AvailabilityInfoEntry firstEntry = null;
- double entryTime;
-
- Iterator<AvailabilityProfileEntry> iterProfile =
- availProfile_.iterator();
- while(iterProfile.hasNext()) {
- AvailabilityProfileEntry entry = iterProfile.next();
- entryTime = entry.getTime();
- if(entryTime > startTime) {
- break;
- }
- else {
- anchorEntry = entry;
- }
- }
+ anchorEntry = availProfile_.getPrecedingEntry(startTime);
// if the entry is null, then it means that the reservation is
// before the first entry of the profile, so the intersection list
@@ -2346,24 +2329,20 @@
// Iterates the availability profile and adds all the entries
// whose times are between start and finish time in the list
- // to be returned. It removes duplicated entries
- AvailabilityProfileEntry previousEntry = null;
+ // to be returned.
for(int i=anchorIndex+1; i<length; i++) {
AvailabilityProfileEntry nextEntry = availProfile_.get(i);
if(nextEntry.getTime() > finishTime){
break;
}
else {
- if( !(previousEntry != null && previousEntry.hasSamePERanges(nextEntry)) ) {
- PERangeList peList = nextEntry.getPERanges();
- if(peList != null) {
- peList = peList.clone();
- }
- AvailabilityInfoEntry tsEntry =
- new AvailabilityInfoEntry(nextEntry.getTime(), peList);
- list.add(tsEntry);
- }
- previousEntry = nextEntry;
+ PERangeList peList = nextEntry.getPERanges();
+ if(peList != null) {
+ peList = peList.clone();
+ }
+ AvailabilityInfoEntry tsEntry =
+ new AvailabilityInfoEntry(nextEntry.getTime(), peList);
+ list.add(tsEntry);
}
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-02-10 06:19:19 UTC (rev 93)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-02-10 07:09:51 UTC (rev 94)
@@ -120,6 +120,9 @@
// the last time when the schedule updated was called
private double lastScheduleUpdate_;
+
+ // a tag to indicate that a gridlet has finished
+ private static final int GRIDLET_FINISHED = 10;
/**
* Allocates a new <tt>CBParallelSpaceShared</tt> object
@@ -178,13 +181,17 @@
}
// Internal Event if the event source is this entity
- if (ev.get_src() == super.myId_) {
+ if (ev.get_src() == super.myId_ &&
+ ev.get_tag() == GRIDLET_FINISHED) {
double currentTime = GridSim.clock();
if(currentTime > lastScheduleUpdate_) {
updateSchedule();
}
lastScheduleUpdate_ = currentTime;
}
+ else {
+ processOtherEvent(ev);
+ }
}
// CHECK for ANY INTERNAL EVENTS WAITING TO BE PROCESSED
@@ -514,7 +521,7 @@
// then send this event to itself to update the queues after
// this gridlet's completion time
- super.sendInternalEvent(executionTime);
+ super.sendInternalEvent(executionTime, GRIDLET_FINISHED);
return true;
}
@@ -933,7 +940,7 @@
// change Gridlet status
gridlet.setStatus(Gridlet.INEXEC);
- super.sendInternalEvent(gridlet.getFinishTime()-currentTime);
+ super.sendInternalEvent(gridlet.getFinishTime()-currentTime, GRIDLET_FINISHED);
}
}
resource_.setPEsBusy(allocatedRanges);
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-02-10 06:19:19 UTC (rev 93)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-02-10 07:09:51 UTC (rev 94)
@@ -99,6 +99,9 @@
// used only to set the extraPEs_ back to the default value
private PERangeList allPEs_;
+
+ // a tag to indicate that a gridlet has finished
+ private static final int GRIDLET_FINISHED = 10;
/**
* Allocates a new <tt>EBParallelSpaceShared</tt> object
@@ -161,13 +164,17 @@
}
// Internal Event if the event source is this entity
- if (ev.get_src() == super.myId_) {
+ if (ev.get_src() == super.myId_ &&
+ ev.get_tag() == GRIDLET_FINISHED) {
double currentTime = GridSim.clock();
if(currentTime > lastScheduleUpdate_) {
updateSchedule();
}
lastScheduleUpdate_ = currentTime;
}
+ else {
+ processOtherEvent(ev);
+ }
}
// CHECK for ANY INTERNAL EVENTS WAITING TO BE PROCESSED
@@ -468,7 +475,7 @@
// then send this event to itself to update the queues after
// this gridlet's completion time
- super.sendInternalEvent(executionTime);
+ super.sendInternalEvent(executionTime, GRIDLET_FINISHED);
return true;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-03-01 01:10:39
|
Revision: 138
http://gridsim.svn.sourceforge.net/gridsim/?rev=138&view=rev
Author: marcos_dias
Date: 2008-02-29 17:10:44 -0800 (Fri, 29 Feb 2008)
Log Message:
-----------
Additional features in the easy backfilling multi partition policy:
+ Option to provide a priority selector that indicates what priorities the scheduler should assign to gridlets submitted to the resource.
+ The user can indicate whether the partitions can borrow resources from one another or not. This may be useful if the user wants to implement complex policies where he controls how the resources are allocated to the partitions.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java
Added Paths:
-----------
branches/gridsim4.0-branch3/source/gridsim/turbo/PrioritySelector.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-02-28 04:11:36 UTC (rev 137)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-03-01 01:10:44 UTC (rev 138)
@@ -87,6 +87,13 @@
// to order the gridlets according to their priorities and submission times
protected OrderGridletsByPriority orderByPriority_;
+ // used by the scheduler to specify the priority of the item
+ protected PrioritySelector prioritySelector_;
+
+ // indicates whether the borrowing of resources by the
+ // partitions is allowed or not
+ private boolean allowBorrowing_;
+
// the number of partitions or queues in this scheduler
protected int numPartitions_;
@@ -138,7 +145,9 @@
orderByPriority_ = new OrderGridletsByPriority();
numPartitions_ = numPartitions;
profile_ = new MPAvailabilityProfile();
+ prioritySelector_ = null;
lastScheduleUpdate_ = 0.0D;
+ allowBorrowing_ = true;
ratingPE_ = 0;
}
@@ -177,6 +186,31 @@
profile_.addPartition(partition);
return true;
}
+
+ /**
+ * Indicates whether the borrowing of resources of the partitions from
+ * one another is allowed or not.
+ * @param allow <tt>true</tt> indicates that it is allowed;
+ * <tt>false</tt> otherwise.
+ */
+ public void setAllowBorrowing(boolean allow) {
+ allowBorrowing_ = allow;
+ }
+
+ /**
+ * Sets the priority selector to be used by this scheduler. The selector
+ * defines what priorities the scheduler should assign to the gridlets.
+ * @param selector the selector to be used.
+ * @return <tt>true</tt> if the selector has been defined successfully or
+ * <tt>false</tt> otherwise.
+ */
+ public boolean setPrioritySelector(PrioritySelector selector) {
+ if(selector == null || Sim_system.running())
+ return false;
+
+ prioritySelector_ = selector;
+ return true;
+ }
/**
* Handles internal events that come to this entity.
@@ -227,8 +261,13 @@
PERangeList freeRanges = resource_.getFreePERanges().clone();
for(QueuePartition partition : profile_.getPartitions()) {
allocPE += partition.getInitialNumPEs();
- PERangeList selected =
- super.selectPERangeList(partition.getInitialNumPEs(), freeRanges);
+ PERangeList selected = null;
+
+ if(partition.getInitialNumPEs() > 0)
+ selected = super.selectPERangeList(partition.getInitialNumPEs(), freeRanges);
+ else
+ selected = new PERangeList();
+
partition.setIdlePERanges(selected);
freeRanges = PERangeList.difference(freeRanges, selected);
}
@@ -281,7 +320,7 @@
public void gridletSubmit(Gridlet gridlet, boolean ack) {
int reqPE = gridlet.getNumPE();
- try{
+ try {
// reject the Gridlet if it requires more PEs than the resource
// is able to provide
if(reqPE > super.totalPE_){
@@ -296,13 +335,15 @@
return;
}
}
- catch(Exception ex){
+ catch(Exception ex) {
System.out.println(super.get_name() +
": Exception on submission of a Gridlet");
}
// Create a resource Gridlet
SSGridlet sgl = new SSGridlet(gridlet);
+ if(prioritySelector_ != null)
+ sgl.setPriority(prioritySelector_.getSchedulePriority(sgl));
//-------------- FOR DEBUGGING PURPOSES ONLY --------------
@@ -480,7 +521,7 @@
// If the queue to which the gridlet is assigned does not have the
// required PEs, then tries to borrow the additional PEs from other queues
- if(!success) {
+ if(!success && allowBorrowing_) {
// gets all available PEs during given time interval
PERangeList overallAvailPEs =
profile_.getImmediateAvailability(executionTime);
@@ -595,14 +636,19 @@
anchor = (Integer)availObjQueue[0];
startTimeQueue=profile_.get(anchor).getTime();
}
+
+ double startTimeAll;
+ if (!allowBorrowing_)
+ startTimeAll = Double.MAX_VALUE;
+ else {
+ anchor = (Integer)availObj[0];
+ startTimeAll=profile_.get(anchor).getTime();
+ }
- anchor = (Integer)availObj[0];
- double startTimeAll = profile_.get(anchor).getTime();
-
// if the time if the selected partition is smaller or the same as
// considering all the partitions, so that means that we can select
// resources from the selected partition
- if(startTimeQueue <= startTimeAll) {
+ if(startTimeQueue < Double.MAX_VALUE && startTimeQueue <= startTimeAll) {
ranges = (PERangeList)availObjQueue[2];
ranges = super.selectPERangeList(reqPE, ranges);
@@ -617,7 +663,7 @@
}
// If the queue to which the gridlet is assigned does not have the
// required PEs, then try to borrow the additional PEs from other queues.
- else {
+ else if (startTimeAll < Double.MAX_VALUE) {
PERangeList addRanges = (PERangeList)availObj[2];
// the anchor index, the entry in the profile where
@@ -653,6 +699,9 @@
profile_.allocatePERanges(queueId, anchorIndex, tailIndex,
ranges, startTime, finishTime);
}
+ else {
+ return false;
+ }
queue.pivot_ = sgl;
@@ -660,7 +709,6 @@
sgl.setPERangeList(ranges);
// change Gridlet status
-// sgl.setStatus(Gridlet.QUEUED);
sgl.setStartTime(startTime);
sgl.setActualFinishTime(finishTime);
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java 2008-02-28 04:11:36 UTC (rev 137)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/MPAvailabilityProfile.java 2008-03-01 01:10:44 UTC (rev 138)
@@ -37,7 +37,7 @@
super();
queues_ = new HashMap<Integer, QueuePartition>();
}
-
+
/**
* Returns the number of PEs assigned to the partitions
* @return the number of PEs assigned to the partitions
@@ -266,7 +266,7 @@
* @return the list of ranges of PEs available
*/
public PERangeList getImmediateAvailability(double duration) {
-
+
double startTime = GridSim.clock(); // start time is now
// the gridlet's expected finish time
@@ -426,7 +426,7 @@
* array[2] = the list of PEs available at that time
*/
public Object[] checkPERangesAvailability(int reqPE, double duration) {
-
+
// the anchor index, the entry in the profile where
// the gridlet will be placed OR the closest entry to the
// point where the anchor of the advance reservation will be placed
Added: branches/gridsim4.0-branch3/source/gridsim/turbo/PrioritySelector.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/PrioritySelector.java (rev 0)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/PrioritySelector.java 2008-03-01 01:10:44 UTC (rev 138)
@@ -0,0 +1,30 @@
+/*
+ * 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;
+
+/**
+ * This interface is used by a scheduler to obtain the priority of a given
+ * schedule item (i.e. gridlet or advance reservation). This information is
+ * used by allocation policies that use priorities
+ * such as {@link EBMultiplePartitions}.
+ *
+ * @author Marcos Dias de Assuncao
+ * @since GridSim Turbo Alpha 0.1
+ */
+
+public interface PrioritySelector {
+
+ /**
+ * Returns the priority of the item to be assigned by the scheduler
+ * or allocation policy.
+ * @param item the item whose priority needs to be obtained.
+ * @return the priority of the schedule item or <tt>-1</tt> if unknown.
+ */
+ int getSchedulePriority(ScheduleItem item);
+
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-03-10 00:09:56
|
Revision: 143
http://gridsim.svn.sourceforge.net/gridsim/?rev=143&view=rev
Author: marcos_dias
Date: 2008-03-09 17:10:00 -0700 (Sun, 09 Mar 2008)
Log Message:
-----------
Some methods have been moved from the allocation policies to TAllocPolicy.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java
branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java 2008-03-09 02:56:01 UTC (rev 142)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBMultiplePartitions.java 2008-03-10 00:10:00 UTC (rev 143)
@@ -539,20 +539,6 @@
}
/**
- * Updates the Gridlet's properties, such as status once a
- * Gridlet is considered finished.
- * @param sgl a SSGridlet object
- * @param status the Gridlet status
- */
- protected void gridletFinish(SSGridlet sgl, int status) {
- // the order is important! Set the status first then finalise
- // due to timing issues in SSGridlet class
- sgl.setStatus(status);
- sgl.finalizeGridlet();
- super.sendFinishGridlet( sgl.getGridlet() );
- }
-
- /**
* 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 gridlet the Gridlet to be removed
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-03-09 02:56:01 UTC (rev 142)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/CBParallelSpaceShared.java 2008-03-10 00:10:00 UTC (rev 143)
@@ -1169,20 +1169,6 @@
}
/**
- * Updates the Gridlet's properties, such as status once a
- * Gridlet is considered finished.
- * @param sgl a SSGridlet object
- * @param status the Gridlet status
- */
- private void gridletFinish(SSGridlet sgl, int status) {
- // the order is important! Set the status first then finalise
- // due to timing issues in SSGridlet class
- sgl.setStatus(status);
- sgl.finalizeGridlet();
- super.sendFinishGridlet( sgl.getGridlet() );
- }
-
- /**
* 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 gridlet the Gridlet to be removed
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-03-09 02:56:01 UTC (rev 142)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBMultiplePartitions.java 2008-03-10 00:10:00 UTC (rev 143)
@@ -901,20 +901,6 @@
return gridletStarted;
}
- /**
- * Updates the Gridlet's properties, such as status once a
- * Gridlet is considered finished.
- * @param sgl a SSGridlet object
- * @param status the Gridlet status
- */
- private void gridletFinish(SSGridlet sgl, int status) {
- // the order is important! Set the status first then finalise
- // due to timing issues in SSGridlet class
- sgl.setStatus(status);
- sgl.finalizeGridlet();
- super.sendFinishGridlet( sgl.getGridlet() );
- }
-
/*
* This method obtains the queue from the profile and does a casting
*/
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-03-09 02:56:01 UTC (rev 142)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/EBParallelSpaceShared.java 2008-03-10 00:10:00 UTC (rev 143)
@@ -722,18 +722,4 @@
return gridletStarted;
}
-
- /**
- * Updates the Gridlet's properties, such as status once a
- * Gridlet is considered finished.
- * @param sgl a SSGridlet object
- * @param status the Gridlet status
- */
- protected void gridletFinish(SSGridlet sgl, int status) {
- // the order is important! Set the status first then finalise
- // due to timing issues in SSGridlet class
- sgl.setStatus(status);
- sgl.finalizeGridlet();
- super.sendFinishGridlet( sgl.getGridlet() );
- }
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java 2008-03-09 02:56:01 UTC (rev 142)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java 2008-03-10 00:10:00 UTC (rev 143)
@@ -223,7 +223,7 @@
universe.sortRanges();
boolean finished = false;
- while(!finished){
+ while(!finished) {
finished = true;
PERangeList diffRange = null;
look:{
@@ -288,8 +288,6 @@
return selected;
}
- //TODO: The method below is not working properly. To fix it.
- //TODO: As I am not using it at the moment, leave it as it is.
/**
* Returns the symmetric difference of two lists of ranges.
* The output sequence will contain all elements that are in the ranges
@@ -299,41 +297,28 @@
* @return the range corresponding to the symmetric difference
*/
public static PERangeList symmetricDifference(PERangeList lista, PERangeList listb){
- if(lista == null || listb == null)
+ if(lista == null && listb != null)
+ return listb.clone();
+ else if(lista != null && listb == null)
+ return lista.clone();
+ else if(lista == null && listb == null)
return null;
+
+ PERangeList difference = new PERangeList();
+ PERangeList diff = difference(lista, listb);
+ if(diff != null && diff.size() > 0)
+ difference.addAll(diff);
- PERangeList query = lista;
- PERangeList universe = listb;
-
- for(PERange rangeq : query){
- boolean intersected = false;
- PERangeList tempDiff = new PERangeList();
- Iterator<PERange> iterUni = universe.iterator();
- while( !intersected || iterUni.hasNext()){
- PERange rangeu = iterUni.next();
- if(intersect(rangeq, rangeu)){
- PERangeList diffRange = symmetricDifference(rangeq, rangeu);
- if(diffRange != null){
- tempDiff.addAll(diffRange);
- }
- intersected = true;
- }
- else{
- tempDiff.add(rangeu);
- }
- }
- if(!intersected){
- tempDiff.add(rangeq);
- }
- universe = tempDiff.clone();
- }
+ diff = difference(listb, lista);
+ if(diff != null && diff.size() > 0)
+ difference.addAll(diff);
- if(universe == null || universe.size() == 0){
+ if(difference.size() == 0){
return null;
}
else{
- universe.mergePERanges();
- return universe;
+ difference.mergePERanges();
+ return difference;
}
}
@@ -505,87 +490,8 @@
}
return false;
}
-
- /**
- * Returns the symmetric difference of two ranges. The output will
- * contain a list of ranges that are in one range but not in the other.
- * @param rangea the first range
- * @param rangeb the second range
- * @return the range corresponding to the symmetric difference
- */
- private static PERangeList symmetricDifference(PERange rangea, PERange rangeb){
- if(rangea == null || rangeb == null)
- return null;
-
- int starta = rangea.getBeginning();
- int startb = rangeb.getBeginning();
- int enda = rangea.getEnd();
- int endb = rangeb.getEnd();
-
- int startai = -1;
- int endai = Integer.MAX_VALUE;
-
- int startbi = -1;
- int endbi = Integer.MAX_VALUE;
-
- while( !(starta > enda) || !(startb > endb) ){
- if(starta < startb){
- if(startai < 0){
- startai = starta;
- }
- endai = starta;
- starta++;
- }
- else if(startb < starta){
- if(startai < 0){
- startai = startb;
- }
- endai = startb;
- startb++;
- }
- else{
- break;
- }
- }
-
- starta = rangea.getBeginning();
- startb = rangeb.getBeginning();
-
- while( !(enda < starta) || !(endb < startb) ){
- if(enda > endb){
- if(endbi == Integer.MAX_VALUE){
- endbi = enda;
- }
- startbi = enda;
- enda--;
- }
- else if(endb > enda){
- if(endbi == Integer.MAX_VALUE){
- endbi = endb;
- }
- startbi = endb;
- endb--;
- }
- else{
- break;
- }
- }
-
- PERangeList difference = new PERangeList();
- if( (startai >= 0) && (endai != Integer.MAX_VALUE) ){
- PERange rBefore = new PERange(startai, endai);
- difference.add(rBefore);
- }
-
- if( (startbi >= 0) && (endbi != Integer.MAX_VALUE) ){
- PERange rAfter = new PERange(startbi, endbi);
- difference.add(rAfter);
- }
-
- return difference.size() == 0 ? null : difference;
- }
- // FOR DEBUGGING PURPOSES ONLY...
+// // FOR DEBUGGING PURPOSES ONLY...
// public static void main(String args[]){
//
// PERange ra = new PERange(0, 10);
@@ -600,19 +506,20 @@
//// System.out.println("Consolidated# " + list);
//
// PERangeList list1 = new PERangeList();
-// list1.add(ra); list1.add(rb);
-// list1.add(rc); list1.add(rd);
+// list1.add(new PERange(400, 1000));
+//// list1.add(ra); list1.add(rb);
+//// list1.add(rc); list1.add(rd);
//
// PERangeList list2 = new PERangeList();
// list2.add(ra); list2.add(rb);
// list2.add(rc); list2.add(rd);
//
// PERangeList list3 = new PERangeList();
-// list3.add(new PERange(500, 1000));
-// list3.add(new PERange(0, 499));
-// list3.add(new PERange(1001, 1005));
+// list3.add(new PERange(500, 2000));
+//// list3.add(new PERange(0, 499));
+//// list3.add(new PERange(1001, 1005));
//
-// PERangeList difference = difference(null, list3);
-// System.out.println("Range list " + null + " minus " + list3 + " is " + difference);
+// PERangeList difference = symmetricDifference(list1, list3);
+// System.out.println("Symmetric difference between list " + list1 + " and " + list3 + " is " + difference);
// }
}
\ No newline at end of file
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java 2008-03-09 02:56:01 UTC (rev 142)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/TAllocPolicy.java 2008-03-10 00:10:00 UTC (rev 143)
@@ -177,4 +177,18 @@
return finishTime;
}
+
+ /**
+ * Updates the Gridlet's properties, such as status once a
+ * Gridlet is considered finished.
+ * @param sgl a SSGridlet object
+ * @param status the Gridlet status
+ */
+ protected void gridletFinish(SSGridlet sgl, int status) {
+ // the order is important! Set the status first then finalise
+ // due to timing issues in SSGridlet class
+ sgl.setStatus(status);
+ sgl.finalizeGridlet();
+ super.sendFinishGridlet( sgl.getGridlet() );
+ }
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mar...@us...> - 2008-04-28 06:23:55
|
Revision: 171
http://gridsim.svn.sourceforge.net/gridsim/?rev=171&view=rev
Author: marcos_dias
Date: 2008-04-27 23:23:28 -0700 (Sun, 27 Apr 2008)
Log Message:
-----------
Bug fix, a job would not start if the reservation was made for the exact runtime estimate of the job.
Modified Paths:
--------------
branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java
branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java 2008-04-16 10:39:27 UTC (rev 170)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARCBMultiplePartitions.java 2008-04-28 06:23:28 UTC (rev 171)
@@ -220,7 +220,7 @@
}
// check whether the gridlet is expected to run for longer than
// the time previously reserved
- else if (executionTime >= sRes.getDurationTime()) {
+ else if (executionTime > sRes.getDurationTime()) {
String userName = GridSim.getEntityName( gridlet.getUserID() );
System.out.println(super.get_name() + ".gridletSubmit(): " +
" Gridlet #" + gridlet.getGridletID() + " from " +
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java 2008-04-16 10:39:27 UTC (rev 170)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AREBMultiplePartitions.java 2008-04-28 06:23:28 UTC (rev 171)
@@ -228,7 +228,7 @@
}
// check whether the gridlet is expected to run for longer than
// the time previously reserved
- else if (executionTime >= sRes.getDurationTime()) {
+ else if (executionTime > sRes.getDurationTime()) {
String userName = GridSim.getEntityName( gridlet.getUserID() );
System.out.println(super.get_name() + ".gridletSubmit(): " +
" Gridlet #" + gridlet.getGridletID() + " from " +
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-04-16 10:39:27 UTC (rev 170)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-04-28 06:23:28 UTC (rev 171)
@@ -715,13 +715,13 @@
}
// check whether the gridlet is expected to run for longer than
// the time previously reserved
- else if (executionTime >= sRes.getDurationTime()) {
+ else if (executionTime > sRes.getDurationTime()) {
String userName = GridSim.getEntityName( gridlet.getUserID() );
System.out.println(super.get_name() + ".gridletSubmit(): " +
" Gridlet #" + gridlet.getGridletID() + " from " +
userName + " cannot be accepted because the reservation #" +
- sRes.getID() + " is for " + sRes.getDurationTime() +
- " while the gridlet is expected to run for " +
+ sRes.getID() + " is for " + sRes.getDurationTime() + " seconds," +
+ " whereas the gridlet is expected to run for " +
executionTime + " seconds.");
success = false;
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X