gridsim.parallel.scheduler
Class AggressiveBackfill

Object
  Thread
      Sim_entity
          AllocPolicy
              AggressiveBackfill

All Implemented Interfaces:

Cloneable, Runnable

public class AggressiveBackfill
extends AllocPolicy

This class is an allocation strategy for ParallelResource that implements aggressive backfilling (EASY). The policy is based on the aggressive backfilling algorithm described in the following paper:

• Ahuva W. Mu'alem and Dror G. Feitelson, Utilization, Predictability, Workloads, and User Runtime Estimates in Scheduling the IBM SP2 with Backfilling. IEEE Transactions on Parallel and Distributed Systems, 12:(6), pp. 529-543, 2001.

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 or migrated.

Since:

5.0

Author:

Marcos Dias de Assuncao

See Also:

GridSim, ResourceCharacteristics, AllocPolicy, PERange, PERangeList

Nested Class Summary

Nested classes/interfaces inherited from class Thread

Thread.State, Thread.UncaughtExceptionHandler

Field Summary

protected ResourceDynamics	dynamics
protected Comparator<SSGridlet>	jobOrder
protected SSGridlet	pivot
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

AggressiveBackfill(String resourceName, String entityName)
Allocates a new AggressiveBackfill object

Method Summary

protected int	backfillGridlets() This method backfills/starts gridlets 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. Finish time = length / available rating
void	gridletCancel(int gridletId, int userId) Cancels a job running or in the waiting queue.
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.
boolean	setJobOrderingHeuristic(Comparator<SSGridlet> comparator) Sets the heuristic used to order the jobs considered for backfilling or when a cancellation takes place

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

pivot

protected SSGridlet pivot

UPT_SCHEDULE

protected static final int UPT_SCHEDULE

See Also:

Constant Field Values

Constructor Detail

AggressiveBackfill

public AggressiveBackfill(String resourceName,
                          String entityName)
                   throws Exception

Allocates a new AggressiveBackfill object

Parameters:

resourceName - the resource entity name that will contain this allocation policy

entityName - this object entity name

Throws:

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

• Creating this entity before initialising GridSim package
• The entity name is null or empty
• The entity has zero number of PEs (Processing Elements).
  No PEs, which means that the Gridlets cannot be processed. A GridResource must contain one or more Machines. A Machine must contain one or more PEs.

Method Detail

body

public void body()

Handles internal events that come to this entity.

Overrides:

body in class Sim_entity

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.

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)

Cancels a job running or in the waiting queue. If a job is cancelled and the job was either running or was the first job in the waiting queue (i.e. pivot), then the availability profile is updated.
NOTE THAT:

• This method firstly checks if the job has not finished. If the job has completed, it cannot be cancelled.
• Once a job has been cancelled, it cannot be resumed to execute again since this method will pass the job back to sender.
• If a job cannot be found in either execution and waiting lists, then a null job will be send back to sender.

Specified by:

gridletCancel in class AllocPolicy

Parameters:

gridletId - a job ID

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

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

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)

backfillGridlets

protected int backfillGridlets()

This method backfills/starts gridlets that are in the queue

Returns:

the number of gridlets started

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