Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [92] branches/gridsim4.0-branch3/source/gridsim/turbo
|
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] |
