gridsim.parallel.scheduler
Class SelectiveBackfill

Object
  Thread
      Sim_entity
          AllocPolicy
              SelectiveBackfill

All Implemented Interfaces:

Cloneable, Runnable

public class SelectiveBackfill
extends AllocPolicy

This scheduling strategy is the implementation of the backfilling based scheduler describe in the following paper:

• Srividya Srinivasan, Rajkumar Kettimuthu, Vijay Subramani, and Ponnuswamy Sadayappan. Selective Reservation Strategies for Backfill Job Scheduling. In JSSPP 2002, LNCS 2537, Springer-Verlag Berlin Heidelberg, pp. 55-71, 2002.

According to this scheduling strategy, jobs are not given a reservation (i.e. their start and finish times are not defined or they are not used for backfilling) until their expected slowdown exceeds some threshold, whereupon they get a reservation. In other words, if a job waits enough, then it is given a reservation. This is done when the eXpansion Factor (XFactor) of the job exceeds some starvation threshold. The XFactor of a job is defined as:

                XFactor = (Wait time + Estimated run time) / Estimated run time
 

The XFactor threshold is initially set to 1.0 and as jobs complete, it is updated to the average slowdown of the completed jobs. Alternatively, you can create job categories, each category will have its own starvation threshold. See addJobCategory(PartitionPredicate)

This policy maintains an availability profile. The availability profile contains information about the ranges of processing elements (PEs) that will be released when the running jobs complete.

NOTE THAT:

• The list of machines comprising this resource must be homogeneous.
• Local load is not considered. If you would like to simulate this, you have to model the local load as jobs. It is more precise and faster. To do so, please check WorkloadLublin99.
• Jobs cannot be paused nor migrated.

Since:

5.0

Author:

Marcos Dias de Assuncao

See Also:

GridSim, ResourceCharacteristics, AllocPolicy, PERange, PERangeList

Nested Class Summary

(package private) class

SelectiveBackfill.JobCategory

Nested classes/interfaces inherited from class Thread

Thread.State, Thread.UncaughtExceptionHandler

Field Summary

protected ArrayList<SelectiveBackfill.JobCategory>	categories
protected ResourceDynamics	dynamics
protected Comparator<SSGridlet>	jobOrder
protected SingleProfile	profile
protected int	ratingPE
protected SSGridletList	runningJobs
protected static int	UPT_SCHEDULE
protected SSGridletList	waitingJobs

Fields inherited from class AllocPolicy

initTime_, myId_, outputPort_, resCalendar_, resId_, resName_, resource_, totalPE_

Fields inherited from class Thread

MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY

Constructor Summary

SelectiveBackfill(String resName, String entityName)
Allocates a new SelectiveBackfill object

Method Summary

void	addJobCategory(PartitionPredicate predicate) Adds a job category to use to calculate the starvation threshold.
protected int	backfillGridlets() This method backfills/starts jobs that are in the queue
void	body() Handles internal events that come to this entity.
protected long	forecastExecutionTime(double availableRating, double length) Forecast finish time of a Gridlet.
protected double	getXFactor(SSGridlet sgl) Calculates the eXpansion Factor (XFactor) of a job.
protected double	getXFactorThreshold(SSGridlet sgl) Gets the eXpansion Factor (XFactor) threshold applicable for a particular job
void	gridletCancel(int gridletId, int userId) An abstract method that cancels a Gridlet in an execution list.
protected void	gridletFinish(SSGridlet sgl, int status) Updates the Gridlet's properties, such as status once a Gridlet is considered finished.
void	gridletMove(int gridletId, int userId, int destId, boolean ack) An abstract method that moves a Gridlet to another GridResource entity.
void	gridletPause(int gridletId, int userId, boolean ack) An abstract method that pauses a Gridlet during an execution.
void	gridletResume(int gridletId, int userId, boolean ack) An abstract method that resumes a previously paused Gridlet.
int	gridletStatus(int gridletId, int userId) Finds the status of a specified job.
void	gridletSubmit(Gridlet gridlet, boolean ack) Schedules/adds to the queue a new job received by the resource entity.
protected void	scheduleGridlet(SSGridlet sgl) Enqueues a job.
boolean	setJobOrderingHeuristic(Comparator<SSGridlet> comparator) Sets the heuristic used to order the jobs considered for backfilling or when a cancellation takes place
protected boolean	startGridlet(SSGridlet sgl) Starts a job using free PEs, sets the job status to INEXEC and updates the availability profile

Methods inherited from class AllocPolicy

addTotalLoad, calculateTotalLoad, findGridlet, getTotalLoad, gridletMigrate, init, isEndSimulation, processOtherEvent, sendAck, sendCancelGridlet, sendFinishGridlet, sendInternalEvent, sendInternalEvent, setEndSimulation

Methods inherited from class Sim_entity

add_generator, add_param, add_port, clone, get_id, get_name, get_port, get_port, get_stat, run, send_on, set_invisible, set_stat, sim_cancel, sim_completed, sim_current, sim_get_next, sim_get_next, sim_hold_for, sim_hold, sim_pause_for, sim_pause_for, sim_pause_until, sim_pause_until, sim_pause, sim_process_for, sim_process_for, sim_process_until, sim_process_until, sim_process, sim_putback, sim_schedule, sim_schedule, sim_schedule, sim_schedule, sim_schedule, sim_schedule, sim_select, sim_trace, sim_wait_for, sim_wait_for, sim_wait_for, sim_wait, sim_waiting, sim_waiting

Methods inherited from class Thread

activeCount, checkAccess, countStackFrames, currentThread, destroy, dumpStack, enumerate, getAllStackTraces, getContextClassLoader, getDefaultUncaughtExceptionHandler, getId, getName, getPriority, getStackTrace, getState, getThreadGroup, getUncaughtExceptionHandler, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, resume, setContextClassLoader, setDaemon, setDefaultUncaughtExceptionHandler, setName, setPriority, setUncaughtExceptionHandler, sleep, sleep, start, stop, stop, suspend, toString, yield

Methods inherited from class Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

waitingJobs

protected SSGridletList waitingJobs

runningJobs

protected SSGridletList runningJobs

profile

protected SingleProfile profile

ratingPE

protected int ratingPE

jobOrder

protected Comparator<SSGridlet> jobOrder

dynamics

protected ResourceDynamics dynamics

categories

protected ArrayList<SelectiveBackfill.JobCategory> categories

UPT_SCHEDULE

protected static final int UPT_SCHEDULE

See Also:

Constant Field Values

Constructor Detail

SelectiveBackfill

public SelectiveBackfill(String resName,
                         String entityName)
                  throws Exception

Allocates a new SelectiveBackfill object

Parameters:

resName - the name of the Grid resource that will contain this scheduler.

entityName - this object entity name

Throws:

Exception - This happens when one of the following scenarios occur:

• Creating this entity before initialising the simulator
• The entity name is null or empty
• The resource has zero number of PEs (Processing Elements).
  

Method Detail

addJobCategory

public void addJobCategory(PartitionPredicate predicate)

Adds a job category to use to calculate the starvation threshold. Different job categories have different starvation thresholds.

Parameters:

predicate - the job category. If jobs match this predicate, then they fall into this category.

setJobOrderingHeuristic

public boolean setJobOrderingHeuristic(Comparator<SSGridlet> comparator)

Sets the heuristic used to order the jobs considered for backfilling or when a cancellation takes place

Parameters:

comparator - a comparator implementation.

Returns:

true if the heuristic was set correctly.

body

public void body()

Handles internal events that come to this entity.

Overrides:

body in class Sim_entity

gridletSubmit

public void gridletSubmit(Gridlet gridlet,
                          boolean ack)

Schedules/adds to the queue a new job received by the resource entity.

Specified by:

gridletSubmit in class AllocPolicy

Parameters:

gridlet - a Gridlet object to be executed

ack - an acknowledgement, i.e. true if wanted to know whether this operation is successful or not; false otherwise (don't care)

See Also:

ResGridlet, ResGridletList

gridletCancel

public void gridletCancel(int gridletId,
                          int userId)

Description copied from class: AllocPolicy

An abstract method that cancels a Gridlet in an execution list. When writing this code, there are few things to consider:

• if a Gridlet can't be found in any data structures
• if a Gridlet has finished executing upon canceling
• if a Gridlet can be canceled

This method is always required to send back the Gridlet to sender. If the Gridlet is not found, then send back a null Gridlet. Therefore, at the end of this method, should include the following code:

... // other code

// A ResGridlet object stored in a container or other data structure
// before exit, finalize all the Gridlet's relevant time information
resGridlet.finalizeGridlet();

// sends the Gridlet back to sender
// Here, gridlet can be null if not found
Gridlet gridlet = resGridlet.getGridlet();
sendCancelGridlet(GridSimTags.GRIDLET_CANCEL, gridlet, gridletId, userId);


Specified by:

gridletCancel in class AllocPolicy

Parameters:

gridletId - a Gridlet ID

userId - the user or owner's ID of this Gridlet

gridletMove

public void gridletMove(int gridletId,
                        int userId,
                        int destId,
                        boolean ack)

Description copied from class: AllocPolicy

An abstract method that moves a Gridlet to another GridResource entity. When writing this code, there are few things to consider:

• if a Gridlet can't be found in any data structures.
  Hence, only need to send an ack with a false boolean value by using AllocPolicy.sendAck(int, boolean, int, int).
  
  
• if a Gridlet has finished executing upon moving.
  Then need to send an ack with a false boolean value by using AllocPolicy.sendAck(int, boolean, int, int).
  Moreover, need to send the completed Gridlet by using AllocPolicy.sendFinishGridlet(Gridlet).
  
  
• if a Gridlet can be moved, then need to use AllocPolicy.gridletMigrate(Gridlet, int, boolean).

Specified by:

gridletMove in class AllocPolicy

Parameters:

gridletId - a Gridlet ID

userId - the user or owner's ID of this Gridlet

destId - a new destination GridResource ID for this Gridlet

ack - an acknowledgement, i.e. true if wanted to know whether this operation is success or not, false otherwise (don't care)

gridletPause

public void gridletPause(int gridletId,
                         int userId,
                         boolean ack)

Description copied from class: AllocPolicy

An abstract method that pauses a Gridlet during an execution.

If an acknowledgement is required, then at the end of this method, should include the following code:

... // other code

// sends back an ack if required
boolean success = true; // If this method success, false otherwise
if (ack == true) {
sendAck(GridSimTags.GRIDLET_PAUSE_ACK, success, gl.getGridletID(), gl.getUserID() );
}



Specified by:

gridletPause in class AllocPolicy

Parameters:

gridletId - a Gridlet ID

userId - the user or owner's ID of this Gridlet

ack - an acknowledgement, i.e. true if wanted to know whether this operation is success or not, false otherwise (don't care)

gridletResume

public void gridletResume(int gridletId,
                          int userId,
                          boolean ack)

Description copied from class: AllocPolicy

An abstract method that resumes a previously paused Gridlet.

If an acknowledgement is required, then at the end of this method, should include the following code:

... // other code

// sends back an ack if required
boolean success = true; // If this method success, false otherwise
if (ack == true) {
sendAck(GridSimTags.GRIDLET_RESUME_ACK, success, gl.getGridletID(), gl.getUserID() );
}



Specified by:

gridletResume in class AllocPolicy

Parameters:

gridletId - a Gridlet ID

userId - the user or owner's ID of this Gridlet

ack - an acknowledgement, i.e. true if wanted to know whether this operation is success or not, false otherwise (don't care)

gridletStatus

public int gridletStatus(int gridletId,
                         int userId)

Finds the status of a specified job.

Specified by:

gridletStatus in class AllocPolicy

Parameters:

gridletId - a job ID

userId - the user or owner's ID of this job

Returns:

the job status or -1 if not found

See Also:

Gridlet

backfillGridlets

protected int backfillGridlets()

This method backfills/starts jobs that are in the queue

Returns:

the number of jobs started

startGridlet

protected boolean startGridlet(SSGridlet sgl)

Starts a job using free PEs, sets the job status to INEXEC and updates the availability profile

Parameters:

sgl - a SSGridlet object

Returns:

true if there if the job has started; false otherwise

scheduleGridlet

protected void scheduleGridlet(SSGridlet sgl)

Enqueues a job. That is, finds the anchor point, which is the point in the availability profile where there are enough processors to execute the job.

Parameters:

sgl - the job to be scheduled

getXFactor

protected double getXFactor(SSGridlet sgl)

Calculates the eXpansion Factor (XFactor) of a job. The expansion factor guarantees that the jobs do not exceed some starvation threshold.

Parameters:

sgl - the job to be examined.

Returns:

the XFactor of the job.

getXFactorThreshold

protected double getXFactorThreshold(SSGridlet sgl)

Gets the eXpansion Factor (XFactor) threshold applicable for a particular job

Parameters:

sgl - the job to be examined

Returns:

the XFactor of the job

forecastExecutionTime

protected long forecastExecutionTime(double availableRating,
                                     double length)

Forecast finish time of a Gridlet. Finish time = length / available rating

Parameters:

availableRating - the shared MIPS rating for all Gridlets

length - remaining Gridlet length

Returns:

Gridlet's finish time.

Pre Condition:

availableRating >= 0.0, length >= 0.0

Post Condition:

$none

gridletFinish

protected void gridletFinish(SSGridlet sgl,
                             int status)

Updates the Gridlet's properties, such as status once a Gridlet is considered finished.

Parameters:

sgl - a SSGridlet object

status - the Gridlet status