gridsim.parallel.scheduler
Class ConservativeBackfill

Object
  Thread
      Sim_entity
          AllocPolicy
              ConservativeBackfill

All Implemented Interfaces:

Cloneable, Runnable

Direct Known Subclasses:

ARConservativeBackfill

public class ConservativeBackfill
extends AllocPolicy

ConservativeBackfill class is an allocation policy for ParallelResource that implements conservative backfilling. The policy is based on the conservative backfilling algorithm described in the following papers:

• Dror G. Feitelson and Ahuva Mu'alem Weil, Utilization and Predictability in Scheduling the IBM SP2 with Backfilling, in Proceedings of the 12th International Parallel Processing Symposium on International Parallel Processing Symposium (IPPS 1998), pp. 542-546.
• 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) available at future times. The size of the availability profile is proportional to the number of jobs in the running and waiting queues.

To illustrate how the availability profile works, imagine that the simulation has just started and the availability profile is empty. The grid resource has 500 PEs. Therefore, the range of PEs available is [0..499]. At simulation time 100, a job (Ja) arrives requiring 100 PEs. The job is expected to execute for 500 seconds. As the resource is not executing any jobs, Ja is accepted and given the range [0..99]. The ranges of current PEs available is updated to [100..499] and one entry is inserted at the profile to indicate that the range [0..499] will be available again at simulation time 600 seconds.

Now suppose that a job (Jb) arrives at simulation time 200 requiring 400 PEs and expected to run for 500 seconds. The policy checks the ranges currently available and find [100..499]. It then scans the availability profile and analyses all the entries whose time is smaller than the expected termination time of Jb. The policy finds the intersections of PEs amongst the entries, process similar to finding intersections of sequences. While scanning the profile, the policy finds the entry at 600 seconds. The intersection of [100..499] and [0..499] is [100..499]. That means that there are enough resources to schedule Jb and then Jb starts the execution. The policy then updates the ranges of current PEs to []. After that, the policy updates the entry at 600 seconds to [0..99] and inserts an entry with time 700 seconds with the range [0..499].

Now consider that a third job (Jc) arrives at simulation time 250 requiring 500 PEs and expected to run for 100 seconds. As the current ranges available is [], the policy scans the profile until it finds an entry with enough PEs available. In this case, the entry found is at 700 seconds. The policy would continue scanning the profile finding the intersection with other ranges if there were more. In this case, 700 seconds is the last entry in the profile. The job is then set to start execution at time 700 seconds. The policy then updates the entry at time 700 seconds to [] and creates an entry at 800 with [0..499]. Jc is then put in the waiting queue.

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 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

ConservativeBackfill(String resourceName, String entityName)
Allocates a new ConservativeBackfill object.

Method Summary

void	body() Handles internal events that come to this entity.
protected boolean	compressSchedule(double refTime, boolean execute) This method performs the compression of the schedule.
protected void	enqueueGridlet(SSGridlet sgl) Enqueues a gridlet.
protected int	finishRunningGridlets() This method finalises the jobs that have completed
protected long	forecastExecutionTime(double availableRating, double length) Forecast finish time of a Gridlet.
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 a new job received by the Grid resource entity.
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) Allocates a job into free PEs, sets the job status to INEXEC,
protected int	startQueuedGridlets() This method starts jobs that are in the queue and can be started
protected void	updateSchedule() This method is called to update the schedule.

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

UPT_SCHEDULE

protected static final int UPT_SCHEDULE

See Also:

Constant Field Values

Constructor Detail

ConservativeBackfill

public ConservativeBackfill(String resourceName,
                            String entityName)
                     throws Exception

Allocates a new ConservativeBackfill object.

Parameters:

resourceName - the grid 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

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 a new job received by the Grid 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

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

gridletCancel

public void gridletCancel(int gridletId,
                          int userId)

Cancels a job running or in the waiting queue. This method will search the running and waiting queues. If a job is cancelled, the availability profile is shifted forwards. This process ensures that the job will not have an expected completion time worse than that initially stipulated. This process if known as the compression of the schedule.
NOTE:

• 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 the queues, then a null job will be send back to sender.
• After the job is cancelled, the jobs are moved forwards in the schedule. The entries in the profile incurred by each job are updated. This process consists in removing a job, returning its time slot to the profile and finding the schedule for the job again.

Specified by:

gridletCancel in class AllocPolicy

Parameters:

gridletId - a job ID

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

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)

compressSchedule

protected boolean compressSchedule(double refTime,
                                   boolean execute)

This method performs the compression of the schedule. The method iterates the waiting jobs list. For each job, it removes its entry from the profile and then tries to reinsert the job in the profile. In the worst case, the job will be put back in the same place. This process ensures no job has a worse start time than that initially given.

Parameters:

refTime - jobs whose start time is larger than refTime may be shifted

execute - true means that the job cancelled was running, so this method will try to start waiting jobs. If not possible they are reinserted in the waiting queue with the new start time.

Returns:

true if the job has been updated.

finishRunningGridlets

protected int finishRunningGridlets()

This method finalises the jobs that have completed

Returns:

the number of jobs completed

startQueuedGridlets

protected int startQueuedGridlets()

This method starts jobs that are in the queue and can be started

Returns:

the number of jobs started

updateSchedule

protected void updateSchedule()

This method is called to update the schedule. It removes completed jobs and returns them to the users and verifies whether there are jobs in the waiting list that should start execution.

startGridlet

protected boolean startGridlet(SSGridlet sgl)

Allocates a job into free PEs, sets the job status to INEXEC,

Parameters:

sgl - a SSGridlet object

Returns:

true if there is are free PE to process this job, false otherwise

enqueueGridlet

protected void enqueueGridlet(SSGridlet sgl)

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

Parameters:

sgl - the resource gridlet

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