Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [184] branches/gridsim4.0-branch3
|
From: <mar...@us...> - 2008-06-17 07:21:08
|
Revision: 184
http://gridsim.svn.sourceforge.net/gridsim/?rev=184&view=rev
Author: marcos_dias
Date: 2008-06-17 00:21:14 -0700 (Tue, 17 Jun 2008)
Log Message:
-----------
This update contains bug fixes on the advance reservation policies. The cancellation of a reservation was not performed properly. Also, the option to get the scheduling options for a job was returning a list with incorrect slots.
Modified Paths:
--------------
branches/gridsim4.0-branch3/examples/examples/ar/ARTest.java
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/TimeSlot.java
Modified: branches/gridsim4.0-branch3/examples/examples/ar/ARTest.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/ar/ARTest.java 2008-06-13 00:55:20 UTC (rev 183)
+++ branches/gridsim4.0-branch3/examples/examples/ar/ARTest.java 2008-06-17 07:21:14 UTC (rev 184)
@@ -186,7 +186,7 @@
System.out.println("Availability information returned by the " +
"Grid resource # " + resID + " at time # " + GridSim.clock() +
- " is as follows: \n " + availability);
+ " is as follows: \n " + availability);
// try immediate reservation, where starting time is 0 meaning
// use current time as the start time
@@ -209,6 +209,22 @@
if(reservation != null && reservation.getStatus() != Reservation.STATUS_FAILED) {
System.out.println(super.get_name() + ": reservation has been accepted by "+
resName + " at time = " + GridSim.clock());
+
+// availability =
+// super.queryFreeTime(GridSim.clock(), Integer.MAX_VALUE, resID);
+//
+// System.out.println("Free time slots:\n" +
+// availability.getSchedulingOptions(20, 10000, 80, 1));
+
+// super.cancelReservation(reservation.getID());
+
+// // queries the availability of the Grid resource
+// availability = super.queryFreeTime(GridSim.clock(), Integer.MAX_VALUE, resID);
+//
+// System.out.println("Availability information returned by the " +
+// "Grid resource # " + resID + " at time # " + GridSim.clock() +
+// " after cancellation is as follows: \n " + availability);
+
success = true;
}
else {
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-06-13 00:55:20 UTC (rev 183)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2008-06-17 07:21:14 UTC (rev 184)
@@ -435,9 +435,6 @@
boolean inProgress = sRes.getStatus() == Reservation.STATUS_IN_PROGRESS;
- // sets the status of the reservation to cancelled
- sRes.setStatus(Reservation.STATUS_CANCELLED);
-
// remove the reservation from the reservation table
// and put it into the expiry table
reservTable_.remove(reservationId);
@@ -445,6 +442,9 @@
// 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 -------------------
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfo.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfo.java 2008-06-13 00:55:20 UTC (rev 183)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityInfo.java 2008-06-17 07:21:14 UTC (rev 184)
@@ -130,6 +130,122 @@
*/
public double getPotentialStartTime(double readyTime,
int duration, int reqPE) {
+ return getPotentialStartTime(readyTime, duration, reqPE, Double.MAX_VALUE);
+ }
+
+// /**
+// * Scans the entries in the availability info object returns the start
+// * time of the first time frame over which a request with the characteristics
+// * provided can be scheduled.
+// * @param readyTime the method will consider potential start times
+// * further in time than the value given by <tt>readyTime</tt>.
+// * @param duration the duration of the request
+// * @param reqPE the number of PEs required
+// * @return the start time or <tt>-1</tt> if not found.
+// */
+// public double getPotentialStartTime(double readyTime,
+// int duration, int reqPE) {
+//
+// if(readyTime < startTime_)
+// readyTime = startTime_;
+//
+// if(readyTime > finishTime_)
+// return UNKNOWN;
+//
+// // the anchor index, the entry in the profile where
+// // the request would be placed OR the closest entry to the
+// // point where the anchor of the request would be placed
+// int anchorIndex = -1;
+//
+// // a pointer to the anchor entry (described above)
+// AvailabilityInfoEntry anchorEntry = null;
+//
+// double potStartTime = -1; // keep the potential start time of the request
+// double potFinishTime = -1; // store the gridlet's expected finish time
+// int length = super.size();
+//
+// anchorEntry = getPrecedingEntry(readyTime);
+// int firstAnchorIndex = super.indexOf(anchorEntry);
+// if(firstAnchorIndex == -1)
+// firstAnchorIndex = 0;
+//
+// for(int j=firstAnchorIndex; j<length; j++) {
+// AvailabilityInfoEntry entry = super.get(j);
+// anchorIndex = super.indexOf(entry);
+//
+// // 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
+// // request expected completion time
+// PERangeList 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() > potFinishTime){
+// break;
+// }
+// else{
+// // if the finish time is equals to the entry time, so there
+// // is no need to check the intersection
+// if(nextEntry.getTime() < potFinishTime) {
+// intersectList = PERangeList.intersection(intersectList,
+// nextEntry.getAvailRanges());
+//
+// if(intersectList == null || intersectList.getNumPE() < reqPE) {
+// break;
+// }
+// }
+// }
+// }
+// // If a time slot with enough PEs has been found, then stop the search
+// if(intersectList != null && intersectList.getNumPE() >= reqPE) {
+// break;
+// }
+// }
+// }
+//
+// // if the potential finish time is larger than the end time of
+// // this list, then the request cannot be scheduled
+// if(potFinishTime > finishTime_) {
+// potStartTime = UNKNOWN;
+// }
+//
+// return potStartTime;
+// }
+
+ /**
+ * Scans the entries in the availability info object returns the start
+ * time of the first time frame over which a request with the characteristics
+ * provided can be scheduled.
+ * @param readyTime the method will consider potential start times
+ * further in time than the value given by <tt>readyTime</tt>.
+ * @param duration the duration of the request
+ * @param reqPE the number of PEs required
+ * @param deadline the deadline of the job, the user is not interested in
+ * the start time if the job cannot be completed by the deadline
+ * @return the start time or <tt>-1</tt> if not found.
+ */
+ public double getPotentialStartTime(double readyTime,
+ int duration, int reqPE, double deadline) {
if(readyTime < startTime_)
readyTime = startTime_;
@@ -174,6 +290,11 @@
// the gridlet is put at this position
potFinishTime = potStartTime + duration;
+ // The job would not complete before the deadline, then just
+ // return the potential start time as unknown
+ if(potFinishTime > deadline)
+ return UNKNOWN;
+
// 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
@@ -210,7 +331,7 @@
// if the potential finish time is larger than the end time of
// this list, then the request cannot be scheduled
- if(potFinishTime > finishTime_) {
+ if(potFinishTime > finishTime_ || potFinishTime > deadline) {
potStartTime = UNKNOWN;
}
@@ -222,77 +343,16 @@
* 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 readyTime the start time of the request. This is the time before
+ * which, the request will not be ready for scheduling. The user is not
+ * interested in starting the job before this time.
* @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;
+ public boolean canSchedule(double readyTime, int duration, int reqPE) {
+ return canSchedule(readyTime, Double.MAX_VALUE, duration, reqPE);
}
/**
@@ -300,19 +360,21 @@
* 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 readyTime the start time of the request. This is the time before
+ * which, the request will not be ready for scheduling. The user is not
+ * interested in starting the job before this time.
+ * @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) {
+ int duration, int reqPE) {
- if(duration < deadline - readyTime) {
+ if(duration > (deadline - readyTime)) {
System.out.println("AvailabilityInfo.canSchedule(): Duration cannot " +
- "be smaller than (deadline - readyTime).");
+ "be larger than (deadline - readyTime).");
return false;
}
else if(deadline < readyTime) {
@@ -321,67 +383,8 @@
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;
+ double potStartTime = getPotentialStartTime(readyTime, duration, reqPE, deadline);
+ return potStartTime > UNKNOWN ? true : false;
}
/**
@@ -403,57 +406,72 @@
LinkedList<TimeSlot> slots = new LinkedList<TimeSlot>();
// start time cannot be smaller than the start time of the info obj
- if(startTime < startTime_)
+ if(startTime < startTime_) {
startTime = startTime_;
-
+ }
// start time cannot be larger than the finish time of the info obj
- if(startTime > finishTime_) {
+ else if(startTime > finishTime_) {
return slots;
}
+
+ // the finish time cannot be larger than this object finish time
+ if(finishTime > finishTime_) {
+ finishTime = finishTime_;
+ }
AvailabilityInfoEntry entry = getPrecedingEntry(startTime);
AvailabilityInfoEntry nextEntry = null;
PERangeList slotRanges = null;
PERangeList intersect = null;
int size = super.size();
+ int firstIndex = super.indexOf(entry);
- for(int i=super.indexOf(entry); i<size; i++) {
+ if(firstIndex < 0)
+ firstIndex = 0;
+
+ for(int i=firstIndex; i<size; i++) {
entry = super.get(i);
+
if(entry.getTime() >= finishTime) {
break;
}
else if (entry.getNumPE() == 0) {
continue;
}
-
- double slotStart =
- entry.getTime() < startTime ? startTime : entry.getTime();
+
slotRanges = entry.getAvailRanges();
+ double slotStart = Math.max(entry.getTime(), startTime);
- for(int j=i; j<size; j++) {
- nextEntry = super.get(j);
- intersect = PERangeList.intersection(slotRanges, nextEntry.getAvailRanges());
- double endTime = entry.getTime();
- boolean different = !intersect.equals(slotRanges);
- if(j < (size-1) && different) {
- if((endTime - slotStart) >= duration && slotRanges.getNumPE() >= numPEs) {
- TimeSlot slot = new TimeSlot(slotStart, endTime, slotRanges);
- slots.add(slot);
+ do {
+ int initialPE = slotRanges.getNumPE();
+
+ for(int j=i+1; j<size; j++) {
+ nextEntry = super.get(j);
+ intersect = PERangeList.intersection(slotRanges, nextEntry.getAvailRanges());
+
+ // if there was a change in the number of PEs, so that less PEs are available
+ // after the next entry, then considers the next entry as the end of the
+ // current time slot
+ if(intersect == null || intersect.getNumPE() < slotRanges.getNumPE()) {
+ double endTime = Math.min(nextEntry.getTime(), finishTime);
+ if((endTime - slotStart) >= duration && slotRanges.getNumPE() >= numPEs) {
+ TimeSlot slot = new TimeSlot(slotStart, endTime, slotRanges.clone());
+ slots.add(slot);
+ }
+ slotRanges = intersect;
+ break;
}
- slotRanges = intersect;
}
- else if (j == (size-1)) {
- if((endTime - slotStart) >= duration && slotRanges.getNumPE() >= numPEs) {
- TimeSlot slot = new TimeSlot(slotStart, finishTime, slotRanges);
+
+ if(slotRanges != null && slotRanges.getNumPE() == initialPE) {
+ if((finishTime - slotStart) >= duration && slotRanges.getNumPE() >= numPEs) {
+ TimeSlot slot = new TimeSlot(slotStart, finishTime, slotRanges.clone());
slots.add(slot);
}
- continue;
+ slotRanges = null;
}
- if(intersect == null && intersect.getNumPE() == 0) {
- break;
- }
- }
+ } while(slotRanges != null && slotRanges.getNumPE() > 0);
}
return slots;
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlot.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlot.java 2008-06-13 00:55:20 UTC (rev 183)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlot.java 2008-06-17 07:21:14 UTC (rev 184)
@@ -117,4 +117,13 @@
public int getNumPE() {
return ranges_ == null ? 0 : ranges_.getNumPE();
}
+
+ /**
+ * Creates a string representation of the list
+ * @return a string representation
+ */
+ public String toString() {
+ return "TimeSlot={startTime=" + startTime_ +
+ ", finishTime=" + finishTime_ + ", ranges=" + ranges_ + "}";
+ }
}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
