Menu
▾
▴
[Gridsim-commits] SF.net SVN: gridsim: [70] branches/gridsim4.0-branch3
|
From: <mar...@us...> - 2007-10-16 07:12:50
|
Revision: 70
http://gridsim.svn.sourceforge.net/gridsim/?rev=70&view=rev
Author: marcos_dias
Date: 2007-10-16 00:12:49 -0700 (Tue, 16 Oct 2007)
Log Message:
-----------
This update contains:
+ Support for querying the availability of processing elements (PEs) at a Grid resource able to handle advance reservations.
Modified Paths:
--------------
branches/gridsim4.0-branch3/examples/examples/ar/ARTest.java
branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExample01.java
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/AvailabilityProfile.java
branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfileEntry.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
Added Paths:
-----------
branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlotEntry.java
branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlotList.java
Modified: branches/gridsim4.0-branch3/examples/examples/ar/ARTest.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/ar/ARTest.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/examples/examples/ar/ARTest.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -13,6 +13,7 @@
import gridsim.GridletList;
import gridsim.turbo.Reservation;
import gridsim.turbo.ReservationRequester;
+import gridsim.turbo.TimeSlotList;
import java.util.ArrayList;
import java.util.Calendar;
@@ -177,7 +178,15 @@
val = randObj.nextInt(totalResource);
resID = ( (Integer) resARList.get(val) ).intValue();
resName = (String) resNameList.get(val);
-
+
+ // queries the availability of the Grid resource
+ TimeSlotList availability =
+ super.queryFreeTime(GridSim.clock(), Integer.MAX_VALUE, resID);
+
+ System.out.println("Availability information returned by the " +
+ "Grid resource # " + resID + " at time # " + GridSim.clock() +
+ " is as follows: \n " + availability);
+
// try immediate reservation, where starting time is 0 meaning
// use current time as the start time
if (val == i) {
@@ -186,6 +195,10 @@
else {
time = 1 * HOUR + duration;
}
+
+ double potStartTime = availability.getPotentialStartTime(duration, totalPE);
+ System.out.println("The reservation requiring " + totalPE + " PEs could " +
+ "be served by Grid resource # " + resID + " at time # " + potStartTime);
// creates a new reservation
Reservation reservation = null;
@@ -206,6 +219,12 @@
// commit the reservation
if(success) {
+
+ // query the status of the reservation
+ int status = super.queryReservation(reservation.getID());
+ System.out.println("The status of reservation # " + reservation.getID() +
+ " is # " + Reservation.getStatusString(status));
+
// for a reservation with an even number, commits straightaway
// without sending any Gridlets yet
success = super.commitReservation(reservation.getID());
@@ -218,6 +237,11 @@
System.out.println("Reservation # "+ reservation.getID() +
" has NOT been committed successfully.");
}
+
+ // query the status of the reservation again
+ status = super.queryReservation(reservation.getID());
+ System.out.println("The status of reservation # " + reservation.getID() +
+ " is # " + Reservation.getStatusString(status));
}
if(success && i<list_.size()) {
Modified: branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExample01.java
===================================================================
--- branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExample01.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/examples/examples/workload/parallel/TurboExample01.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -85,10 +85,10 @@
//////////////////////////////////////////
// Starts the simulation in debug mode
- GridSim.startGridSimulation(true);
+// GridSim.startGridSimulation(true);
// Start the simulation in normal mode
-// GridSim.startGridSimulation();
+ GridSim.startGridSimulation();
//////////////////////////////////////////
// Final step: Prints the Gridlets when simulation is over
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARMessage.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARMessage.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARMessage.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -27,8 +27,16 @@
private int msgType_; // the type of this message
private int errorCode_; // an error code associated with the operation required
private Reservation reservation_; // the negotiation this message is about
- private double price_; // the price associate with this message
+
+ // 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 TimeSlotList resOptions_;
+ // the price associate with this message
+ private double price_;
+
// starting constant value for the tags to avoid conflicts
// with the GridSim tags and other tags
private static final int BASE = 5000;
@@ -105,6 +113,7 @@
msgType_ = TYPE_UNKNOWN;
errorCode_ = EC_NO_ERROR;
reservation_ = null;
+ resOptions_ = null;
}
/**
@@ -152,6 +161,7 @@
msgId_ = ARMessage.createUniqueID();
reservation_ = reservation;
errorCode_ = EC_NO_ERROR;
+ resOptions_ = null;
}
/**
@@ -367,6 +377,22 @@
public double getPrice() {
return price_;
}
+
+ /**
+ * Gets the reservation options given by the Grid resource
+ * @return the reservation options
+ */
+ public TimeSlotList getReservationOptions() {
+ return resOptions_;
+ }
+
+ /**
+ * Sets the reservation options given by the Grid resource
+ * @param resOptions the reservation options object
+ */
+ public void setReservationOptions(TimeSlotList resOptions) {
+ resOptions_ = resOptions;
+ }
/**
* Returns the size in bytes for this message.
@@ -391,7 +417,6 @@
ARMessage newMessage = new ARMessage(dstId_, srcId_, reservation_);
newMessage.msgType_ = msgType_;
newMessage.price_ = price_;
- newMessage.reservation_ = reservation_;
return newMessage;
}
catch (Exception ex) {
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ARParallelSpaceShared.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -83,7 +83,7 @@
* <li> cancel a reservation
* <li> commit a reservation
* <li> process a reservation status query
- * <li> list free time over a certain period of time (under development)
+ * <li> list free time over a certain period of time
* </ul>
* <p>
* <b>LIMITATIONS:</b><br>
@@ -639,12 +639,34 @@
}
/**
- * Handles a query free time request (NOTE: <b>NOT YET SUPPORTED</b>).
+ * Handles a query free time request.
* @param message the advance reservation message received.
*/
public void handleQueryFreeTime(ARMessage message) {
- System.out.println(super.get_name() +
- ".handleQueryFreeTime(): not supported at the moment.");
+
+ double currentTime = GridSim.clock();
+
+ // stores the last action time for debugging purposes
+ lastActionTime_ = currentTime;
+
+ // gets the reservation id of the message
+ Reservation reservation = message.getReservation();
+
+ // creates a response message to be sent to the requester
+ ARMessage response = message.createResponse();
+
+ // gets the start time and finish time the user is interested in
+ double startTime = reservation.getStartTime();
+ int duration = reservation.getDurationTime();
+
+ // gets the availability information from the availability profile
+ TimeSlotList availability = getAvailabilityInfo(startTime, duration);
+
+ // sets the options as the availability over the requested period
+ response.setReservationOptions(availability);
+
+ // Sends the response back to the user
+ super.sendARMessage(response);
}
/**
@@ -2313,4 +2335,96 @@
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
+ * resource allocation policy.
+ * @param startTime the start time in which the requester is interested.
+ * @param finishTime the finish time in which the requester is interested.
+ * @return the list of free time slots. The list is actually a list of
+ * entries that correspond to the availability profile between the times
+ * specified by the requester.
+ */
+ private TimeSlotList getAvailabilityInfo(double startTime, int duration) {
+
+ TimeSlotList list = new TimeSlotList();
+ int anchorIndex = -1;
+
+ // if the user specified the start time as 0, it means that the
+ // user is interested to know the availability starting from the
+ // current time, or the time when the resource received this request
+ if(startTime == 0) {
+ startTime = GridSim.clock();
+ }
+
+ list.setStartTime(startTime);
+
+ // calculate the reservation's finish time
+ double finishTime = startTime + duration;
+ list.setFinishTime(finishTime);
+
+ // a pointer to the anchor entry (described above)
+ AvailabilityProfileEntry anchorEntry = null;
+ int length = availProfile_.size();
+ TimeSlotEntry 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;
+ }
+ }
+
+ // if the entry is null, then it means that the reservation is
+ // before the first entry of the profile, so the intersection list
+ // has to start with the ranges of PEs currently available
+ if (anchorEntry == null) {
+ firstEntry =
+ new TimeSlotEntry(startTime, resource_.getFreePERanges().clone());
+ }
+ else {
+ PERangeList newList = anchorEntry.getPERanges();
+ if(newList != null) {
+ newList = newList.clone();
+ }
+ firstEntry = new TimeSlotEntry(startTime, newList);
+ anchorIndex = availProfile_.indexOf(anchorEntry);
+ }
+
+ list.add(firstEntry);
+
+ // 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;
+ 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();
+ }
+ TimeSlotEntry tsEntry =
+ new TimeSlotEntry(nextEntry.getTime(), peList.clone());
+ list.add(tsEntry);
+ }
+ previousEntry = nextEntry;
+ }
+ }
+
+ return list;
+ }
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfile.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -25,7 +25,7 @@
/**
* Creates a new @link{AvailabilityProfile} object.
*/
- public AvailabilityProfile(){
+ public AvailabilityProfile() {
super();
}
@@ -34,7 +34,7 @@
* <b>NOTE:</b> this method does not clone the entries
* @return the cloned object
*/
- public AvailabilityProfile clone(){
+ public AvailabilityProfile clone() {
AvailabilityProfile clone = new AvailabilityProfile();
for(AvailabilityProfileEntry entry : this){
clone.add(entry);
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfileEntry.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfileEntry.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/AvailabilityProfileEntry.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -106,6 +106,23 @@
}
/**
+ * Returns <tt>true</tt> if this entry has the same list of ranges of PEs
+ * as the entry provided.
+ * @param entry the entry whose ranges have to be compared
+ * @return <tt>true</tt> if the ranges are the same or false otherwise.
+ */
+ public boolean hasSamePERanges(AvailabilityProfileEntry entry) {
+ boolean result = false;
+ if(ranges_ == null && entry.ranges_ == null) {
+ result = true;
+ }
+ else if(ranges_ != null) {
+ result = ranges_.equals(entry.ranges_);
+ }
+ return result;
+ }
+
+ /**
* Creates a string representation of this entry
*/
public String toString(){
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/PERangeList.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -128,6 +128,11 @@
* @return <tt>true</tt> if they are equals or <tt>false</tt> otherwise.
*/
public boolean equals(PERangeList list) {
+
+ if(list == null) {
+ return false;
+ }
+
if(super.size() != list.size()) {
return false;
}
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/Reservation.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -10,9 +10,6 @@
package gridsim.turbo;
import gridsim.GridSim;
-import gridsim.gui.GridSimVisualizer;
-
-import java.text.DecimalFormat;
import java.util.Calendar;
/**
Modified: branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java 2007-10-14 23:06:27 UTC (rev 69)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/ReservationRequester.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -105,7 +105,7 @@
int numPE, int resID) {
// check all the values first
- boolean success = validateValue(startTime, duration, numPE, resID);
+ boolean success = validateValue(startTime, duration, numPE);
if (!success) {
return null;
}
@@ -187,7 +187,7 @@
int resId = currReservation.getResourceID();
// check all the values first
- boolean success = validateValue(startTime, duration, numPE, resId);
+ boolean success = validateValue(startTime, duration, numPE);
if (!success) {
return null;
}
@@ -297,26 +297,84 @@
}
/**
- * Querys to a resource regarding to list of free time during a period of
- * time. Each object inside ArrayList is <tt>long array[3]</tt>, with:
+ * Queries to a resource regarding to list of free time during a period of
+ * time. This method returns a list that contains the availability
+ * of PEs at simulation times between the start and end time. Each entry
+ * contains:
* <ul>
- * <li> array[0] = start time
- * <li> array[1] = duration time
- * <li> array[2] = number of PEs
+ * <li> time of the entry
+ * <li> list of ranges of PEs available at that particular time
* </ul>
*
- * @param resourceID a resource ID
- * @param from starting time in milliseconds
- * @param to ending time in milliseconds
- * @return ArrayList object or <tt>null</tt> if error occurs
+ * @param resID a resource ID
+ * @param startTime the simulation start time in which
+ * the requester is interested
+ * @param duration duration time in seconds
+ * @return a list of entries that describe the ranges of PEs
+ * available at simulation time between the requested time
* @pre resourceID > 0
- * @pre from > 0
- * @pre to > 0
- * @post $none
+ * @pre startTime >= 0
+ * @pre finishTime > 0
*/
- public ArrayList queryFreeTime(int resourceID, long from, long to) {
- // TODO: To find a nice way to do it.
- return null;
+ public TimeSlotList queryFreeTime(double startTime,
+ int duration, int resID) {
+
+ // check all the values first
+ boolean success = validateValue(startTime, duration, 1);
+ if (!success) {
+ return null;
+ }
+
+ TimeSlotList resOptions = null;
+ try {
+
+ // create the reservation itself
+ Reservation reservation = new Reservation(super.get_id());
+ reservation.setStartTime(startTime);
+ reservation.setDurationTime(duration);
+ reservation.setResourceID(resID);
+
+ // creates the message to be sent to the grid resource
+ ARMessage message = new ARMessage(super.get_id(), resID, reservation);
+ message.setMessageType(ARMessage.TYPE_AR_LIST_FREE_TIME);
+
+ // sends the message to the grid resource
+ sendARMessage(message);
+
+ // wait for feedback whether the reservation has been accepted or not
+ FilterARMessage tagObj =
+ new FilterARMessage(reservation.getID(),
+ ARMessage.TYPE_AR_LIST_FREE_TIME);
+
+ // only look for this type of ack for same reservation ID
+ Sim_event ev = new Sim_event();
+ super.sim_get_next(tagObj, ev);
+
+ // gets the reply from the grid resource
+ ARMessage reply = (ARMessage)ev.get_data();
+
+ // 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
+ int error = reply.getErrorCode();
+ if(error == ARMessage.EC_NO_ERROR) {
+ resOptions = reply.getReservationOptions();
+ }
+ else {
+ System.out.println(super.get_name() + ": Resource # " + resID +
+ " could not inform the availability at time " + GridSim.clock());
+ resOptions = null;
+ }
+ }
+
+ catch (Exception ex) {
+ System.out.println(super.get_name() + ": Resource # " + resID +
+ " could not inform the availability at time " + GridSim.clock());
+ ex.printStackTrace();
+ resOptions = null;
+ }
+
+ return resOptions;
}
/**
@@ -450,8 +508,7 @@
* @param resID a resource ID
* @return <tt>true</tt> if they are valid or <tt>false</tt> otherwise.
*/
- private boolean validateValue(double startTime,
- int duration, int numPE, int resID) {
+ private boolean validateValue(double startTime, int duration, int numPE) {
// current time = simulation time
double currentTime = GridSim.clock();
Added: branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlotEntry.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlotEntry.java (rev 0)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlotEntry.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -0,0 +1,129 @@
+/*
+ * 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;
+
+/**
+ * The {@link TimeSlotEntry} class represents an entry in a list of
+ * time slots available, which can be allocated to a user. This is used
+ * in return to a query for free time slots in an advance reservation
+ * based allocation policy.
+ *
+ * @author Marcos Dias de Assuncao
+ * @since GridSim Turbo Alpha 0.1
+ *
+ * @see ARTPolicy
+ * @see PERange
+ * @see PERangeList
+ * @see TimeSlotList
+ * @see ARParallelSpaceShared
+ * @see ARParallelSpaceShared#handleQueryFreeTime(ARMessage)
+ */
+
+public class TimeSlotEntry implements Comparable <TimeSlotEntry> {
+
+ private double time_;
+ private PERangeList availRanges_;
+
+ /**
+ * Creates a new instance of {@link TimeSlotEntry}
+ * @time the time associated with this entry
+ */
+ public TimeSlotEntry(double time) {
+ time_ = time;
+ availRanges_ = null;
+ }
+
+ /**
+ * Creates a new instance of {@link TimeSlotEntry}
+ * @time the time associated with this entry
+ * @ranges the list of ranges of PEs available
+ */
+ public TimeSlotEntry(double time, PERangeList ranges) {
+ time_ = time;
+ availRanges_ = ranges;
+ }
+
+ /**
+ * Gets the time associated with this entry
+ * @return the time associated with this entry
+ */
+ public double getTime() {
+ return time_;
+ }
+
+ /**
+ * Sets the time associated with this entry
+ * @param time the time associated with this entry
+ * @return <tt>true</tt> if the time has been set successfully or
+ * <tt>false</tt> otherwise.
+ */
+ public boolean setTime(double time) {
+ if(time < 0)
+ return false;
+
+ time_ = time;
+ return true;
+ }
+
+ /**
+ * Returns the list of ranges available at this entry
+ * @return the list of ranges available
+ */
+ public PERangeList getAvailRanges() {
+ return availRanges_;
+ }
+
+ /**
+ * Sets the ranges of PEs available at this entry
+ * @param availRanges the list of ranges of PEs available
+ */
+ public void setAvailRanges(PERangeList availRanges) {
+ availRanges_ = availRanges;
+ }
+
+ /**
+ * Compares this object with the specified object for order.
+ * Returns a negative integer, zero, or a positive integer
+ * as this object is less than, equal to, or greater
+ * than the specified object.
+ * @param entry the entry to be compared.
+ * @return a negative integer, zero, or a positive integer as
+ * this entry is less than, equal to, or greater
+ * than the specified entry.
+ */
+ public int compareTo(TimeSlotEntry entry) {
+ int result = 0;
+ if(time_ < entry.time_) {
+ result = -1;
+ }
+ else if(time_ > entry.time_) {
+ result = 1;
+ }
+ return result;
+ }
+
+ /**
+ * Gets the number of PEs associated with this entry
+ * @return the number of PEs
+ */
+ public int getNumPE(){
+ if(availRanges_ == null)
+ return 0;
+ else
+ return availRanges_.getNumPE();
+ }
+
+ /**
+ * Creates a string representation of this entry
+ * @return a representation of this entry
+ */
+ public String toString(){
+ return "{time="+ time_ + "; "
+ + ( (availRanges_!=null) ? availRanges_ : "{[]}") + "}";
+ }
+}
Added: branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlotList.java
===================================================================
--- branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlotList.java (rev 0)
+++ branches/gridsim4.0-branch3/source/gridsim/turbo/TimeSlotList.java 2007-10-16 07:12:49 UTC (rev 70)
@@ -0,0 +1,314 @@
+/*
+ * 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;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Iterator;
+
+/**
+ * The {@link TimeSlotList} class represents a list of time slots
+ * that are available and can be allocated to a user. This is used
+ * in return to a query for free time slots in an advance reservation
+ * based allocation policy.
+ *
+ * @author Marcos Dias de Assuncao
+ * @since GridSim Turbo Alpha 0.1
+ *
+ * @see ARTPolicy
+ * @see PERange
+ * @see PERangeList
+ * @see ARParallelSpaceShared
+ * @see ARParallelSpaceShared#handleQueryFreeTime(ARMessage)
+ */
+
+public class TimeSlotList {
+
+ private static final long serialVersionUID = -3951650752024908016L;
+
+ private ArrayList<TimeSlotEntry> list_;
+ private double startTime_;
+ private double finishTime_;
+
+ private static final int UNKNOWN = -1;
+
+ /**
+ * Default constructor.
+ */
+ public TimeSlotList() {
+ list_ = new ArrayList<TimeSlotEntry>();
+ startTime_ = UNKNOWN;
+ finishTime_ = UNKNOWN;
+ }
+
+ /**
+ * Returns the start time of this list. That is,
+ * the time of the first element of this list
+ * @return the start time
+ */
+ public double getStartTime() {
+ return startTime_;
+ }
+
+ /**
+ * Returns the end time of this list.
+ * @return the end time
+ */
+ public double getEndTime() {
+ return finishTime_;
+ }
+
+ /**
+ * Sets the start time of this list.
+ * @param startTime the start time
+ */
+ public void setStartTime(double startTime) {
+ startTime_ = startTime;
+ }
+
+ /**
+ * Sets the end time of this list.
+ * @param finishTime the end time
+ */
+ public void setFinishTime(double finishTime) {
+ finishTime_ = finishTime;
+ }
+
+ /**
+ * Adds the specified element to this list.
+ * @param entry the entry to be added to this list
+ * @return <tt>true
+ */
+ public boolean add(TimeSlotEntry entry) {
+ if(entry == null) {
+ return false;
+ }
+ else {
+ double entryTime = entry.getTime();
+ int size = list_.size();
+ int index = 0;
+ for (index=0; index<size; index++) {
+ if(list_.get(index).getTime() > entryTime) {
+ break;
+ }
+ }
+ list_.add(index, entry);
+ }
+ return true;
+ }
+
+ /**
+ * 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 TimeSlotEntry> 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);
+ Collections.sort(list_);
+ }
+ 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 TimeSlotEntry 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<TimeSlotEntry> 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 TimeSlotEntry 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();
+ }
+
+ /**
+ * Scans the entries in a list and returns the first time frame over
+ * which a request with the characteristics provided can be scheduled
+ * @param duration the duration of the request
+ * @param numPE the number of PEs required
+ * @return the start time or <tt>-1</tt> if not found
+ */
+ public double getPotentialStartTime(int duration, int reqPE) {
+
+ // 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)
+ TimeSlotEntry anchorEntry = null;
+
+ // the list of selected ranges
+ PERangeList intersectList = null;
+
+ double potStartTime = -1; // keep the potential start time of the request
+ double potFinishTime = -1; // store the gridlet's expected finish time
+
+ intersectList = null;
+ int length = list_.size();
+
+ Iterator<TimeSlotEntry> iterProfile = list_.iterator();
+ while(iterProfile.hasNext()) {
+
+ TimeSlotEntry entry = iterProfile.next();
+ anchorEntry = entry;
+ anchorIndex = list_.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 {
+ // 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
+ 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++){
+ TimeSlotEntry nextEntry = list_.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;
+ }
+
+ /**
+ * Creates a string representation of the list
+ * @return a string representation
+ */
+ public String toString() {
+ String result = "Availability={\n";
+ for(TimeSlotEntry entry : list_){
+ result += entry + "\n";
+ }
+ result += "}";
+ return result;
+ }
+}
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
