gridsim.parallel.scheduler
Class AggressiveMultiPartitions

Object
  Thread
      Sim_entity
          AllocPolicy
              AggressiveMultiPartitions

All Implemented Interfaces:

Cloneable, Runnable

public class AggressiveMultiPartitions
extends AllocPolicy

This class implements a non-FCFS policy to schedule parallel jobs. The policy is based on aggressive (EASY) backfilling. This policy can use multiple partitions or queues and the jobs can be directed to these partitions using a partition predicate (PartitionPredicate. A partition can borrow resources from another when it requires and the resources are not being used by the other partition. However, you can change this behaviour by calling setAllowBorrowing(boolean). Additionally, this policy supports priorities. Jobs are ordered according to their priorities; a high priority job can take the place of a pivot with lower priority. To change the way that the scheduler assigns priorities to the jobs, please see PrioritySelector. The implementation of this policy is based on the following paper:

• Barry G. Lawson and Evgenia Smirni, Multiple-Queue Backfilling Scheduling with Priorities and Reservations for Parallel Systems, 2002 Workshop on Job Scheduling Strategies for Parallel Processing (JSSPP), pp. 72-87, 2002.

We use an availability profile to store the availability of processing elements. In order to represent the pivots (i.e. the first jobs in the partitions), we schedule them creating the entries in the availability profile. This way, we do not need to store the pivots' start times (or shadow times) and extra nodes in different variables. It also makes the search for available resources for a new pivot easier.

NOTE THAT:

• The list of machines 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.
• Gridlets cannot be paused or migrated.
• This policy does not support advance reservations.

Since:

5.0

Author:

Marcos Dias de Assuncao

See Also:

AllocPolicy, ParallelResource

Nested Class Summary

(package private) class	AggressiveMultiPartitions.EasyBackFillingPartition
(package private) class	AggressiveMultiPartitions.OrderGridletsByPriority

Nested classes/interfaces inherited from class Thread

Thread.State, Thread.UncaughtExceptionHandler

Field Summary

protected boolean	allowBorrowing
protected ResourceDynamics	dynamics
protected Comparator<SSGridlet>	jobOrder
protected PrioritySelector	prioritySelector
protected PartProfile	profile
protected int	ratingPE
protected boolean	returnJob
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

AggressiveMultiPartitions(String resourceName, String entityName, int numPartitions)
Allocates a new object.

Method Summary

protected int	backfillGridlets() This method starts/backfills jobs that are in the queue and pivots (first jobs in the partitions) whose start time is smaller than the current simulation time.
void	body() Handles internal events that come to this entity.
boolean	createPartition(int partId, int numPE, PartitionPredicate predicate) Creates a new partition in this scheduler.
protected int	finishRunningGridlets() This method finalises the jobs in execution whose time is smaller or equals to the current simulation time.
protected long	forecastExecutionTime(double availableRating, double length) Forecast finish time of a job.
void	gridletCancel(int gridletId, int userId) Cancels a job running or in the waiting queue.
protected void	gridletFinish(SSGridlet sgl, int status) Updates the job's properties once a job 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 boolean	scheduleGridlet(SSGridlet sgl) Tries to schedule a job.
void	setAllowBorrowing(boolean allow) Indicates whether the borrowing of resources of the partitions from one another is allowed or not.
boolean	setJobOrderingHeuristic(Comparator<SSGridlet> comparator) Sets the heuristic used to order the jobs considered for backfilling
boolean	setPrioritySelector(PrioritySelector selector) Sets the priority selector to be used by this scheduler.
void	setReturnGridletBehaviour(boolean returnJob) This method is called to specify the behaviour of the policy if a job cannot be scheduled to its partition due to the lack of enough resources and the borrowing is disabled.
protected boolean	startGridlet(SSGridlet sgl) Tries to start a job.
protected void	updateSchedule() This method is called to update the schedule.
protected boolean	validateGridlet(SSGridlet sgl) Checks whether the job can be handled by the resource.

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

ratingPE

protected int ratingPE

profile

protected PartProfile profile

jobOrder

protected Comparator<SSGridlet> jobOrder

dynamics

protected ResourceDynamics dynamics

prioritySelector

protected PrioritySelector prioritySelector

allowBorrowing

protected boolean allowBorrowing

returnJob

protected boolean returnJob

UPT_SCHEDULE

protected static final int UPT_SCHEDULE

See Also:

Constant Field Values

Constructor Detail

AggressiveMultiPartitions

public AggressiveMultiPartitions(String resourceName,
                                 String entityName,
                                 int numPartitions)
                          throws Exception

Allocates a new object. If the policy is create with only one partition, it will then work as a normal aggressive (EASY) backfilling scheduler.

Parameters:

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

entityName - this object entity name

numPartitions - The number of partitions of the scheduling queue

Throws:

IllegalArgumentException - if number of partitions is <= 0

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

createPartition

public boolean createPartition(int partId,
                               int numPE,
                               PartitionPredicate predicate)

Creates a new partition in this scheduler.

Parameters:

partId - the id of the partition

numPE - the number of PEs in this partition

predicate - the predicate to be used to select jobs for this partition.

Returns:

true if the partition has been set correctly; false otherwise.

Throws:

IllegalArgumentException - if the number of PEs is <= 0 or you provide an invalid predicate.

IndexOutOfBoundsException - if you provide an invalid partition id

setJobOrderingHeuristic

public boolean setJobOrderingHeuristic(Comparator<SSGridlet> comparator)

Sets the heuristic used to order the jobs considered for backfilling

Parameters:

comparator - a comparator implementation that defines how jobs are ordered.

Returns:

true if the heuristic was set correctly; false otherwise.

setAllowBorrowing

public void setAllowBorrowing(boolean allow)

Indicates whether the borrowing of resources of the partitions from one another is allowed or not.

Parameters:

allow - true indicates that it is allowed; false otherwise.

setReturnGridletBehaviour

public void setReturnGridletBehaviour(boolean returnJob)

This method is called to specify the behaviour of the policy if a job cannot be scheduled to its partition due to the lack of enough resources and the borrowing is disabled. If a true value is passed to this method, it indicates that a job should be returned to the user immediately if it could not be scheduled to its corresponding partition and the borrowing of resources from other partitions is disabled. That is, if a job arrives at the resource, the partition does not have enough resources, borrowing is disabled and the returnGridlet behaviour is true, the job will be returned to the user entity. This prevents the policy from queueing job even if it will never be able to serve them. A user may want to change this behaviour if he wants to implement manual borrowing or resizing of the resource partitions. In such a case, the job will be queued even if they cannot be handled by its partition at the time of arrival.

Parameters:

returnJob - true indicates that the job should be returned; false otherwise.

setPrioritySelector

public boolean setPrioritySelector(PrioritySelector selector)

Sets the priority selector to be used by this scheduler. The selector defines what priorities the scheduler should assign to the jobs.

Parameters:

selector - the selector to be used.

Returns:

true if the selector has been defined successfully or false otherwise.

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 job 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. The User ID is important as many users might have the same job ID in the lists. If a job is cancelled and the job was either running or was a pivot, then the availability profile is updated. After that, the backfilling algorithm is called to check which jobs can be started or scheduled. NOTE:

• Before cancelling a job, this method updates when the expected completion time of the job is. If the completion time is smaller than the current time, then the job is considered to be finished. Therefore the job 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, i.e. the userId.
• If a job cannot be found in either execution and waiting lists, then a null Gridlet will be send back to sender, i.e. the userId.

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)

validateGridlet

protected boolean validateGridlet(SSGridlet sgl)

Checks whether the job can be handled by the resource. That is, verifies if it does not require more resources than what the resource can provide and if the partition can handle the request.

Parameters:

sgl - the server side gridlet to be examined

Returns:

true if it can be handled; false otherwise.

startGridlet

protected boolean startGridlet(SSGridlet sgl)

Tries to start a job.

Parameters:

sgl - the job to be started

Returns:

true if the job has been started

scheduleGridlet

protected boolean scheduleGridlet(SSGridlet sgl)

Tries to schedule a job. Only the first job in the waiting queue for a given partition is scheduled. If a pivot for that partition already exists, them the method returns null

Parameters:

sgl - the resource job

Returns:

true if the job was scheduled.

updateSchedule

protected void updateSchedule()

This method is called to update the schedule. It removes completed jobs and returns them to the users, then verifies which jobs can be started or scheduled.

finishRunningGridlets

protected int finishRunningGridlets()

This method finalises the jobs in execution whose time is smaller or equals to the current simulation time.

Returns:

the number of jobs completed

backfillGridlets

protected int backfillGridlets()

This method starts/backfills jobs that are in the queue and pivots (first jobs in the partitions) whose start time is smaller than the current simulation time.

Returns:

the number of jobs started

forecastExecutionTime

protected long forecastExecutionTime(double availableRating,
                                     double length)

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

Parameters:

availableRating - the shared MIPS rating for all jobs

length - remaining job length

Returns:

the job's finish time.

gridletFinish

protected void gridletFinish(SSGridlet sgl,
                             int status)

Updates the job's properties once a job is considered finished.

Parameters:

sgl - a SSGridlet object

status - the job status