Citation
An adaptive resource scheduler over grid-computing environments

Material Information

Title:
An adaptive resource scheduler over grid-computing environments
Creator:
Wise, Brian
Place of Publication:
Denver, Colo.
Publisher:
University of Colorado Denver
Publication Date:
Language:
English
Physical Description:
viii, 93 leaves : ; 28 cm

Thesis/Dissertation Information

Degree:
Master's ( Master of Science)
Degree Grantor:
University of Colorado Denver
Degree Divisions:
Department of Computer Science and Engineering, CU Denver
Degree Disciplines:
Computer Science
Committee Chair:
Ra, Ilkueun
Committee Members:
Alaghband, Gita
Altman, Tom
Chlebus, Bogdan

Subjects

Subjects / Keywords:
Computational grids (Computer systems) ( lcsh )
Production scheduling -- Computer simulation ( lcsh )
Computational grids (Computer systems) ( fast )
Production scheduling -- Computer simulation ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 92-93).
General Note:
Department of Computer Science and Engineering
Statement of Responsibility:
by Brian Wise.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
227792981 ( OCLC )
ocn227792981
Classification:
LD1193.E52 2007m W54 ( lcc )

Full Text
AN ADAPTIVE RESOURCE SCHEDULER OVER
GRID-COMPUTING ENVIRONMENTS
by
Brian Wise
B.S., University of Colorado, 2001
A thesis submitted to the
University of Colorado at Denver and Health Sciences Center
in partial fulfillment
of the requirements for the degree of
Master of Science
Computer Science
2007


This thesis for the Master of Science
degree by
Brian Wise
has been approved
by
Tom Altman
///>
Date
Bogdan Chlebus


Wise, Brian P. (M.S., Computer Science)
An Adaptive Resource Scheduler Over Grid-Computing Environments
Thesis directed by Assistant Professor llkyeun Ra
ABSTRACT
Grid computing has seen many advances recently and continues to be
an area of active research. One of the main issues of Grid computing is
resource scheduling algorithms due to the direct impact on Grid
performance. Current Grid resource schedulers have focused on many
areas ranging from brokering to fault-tolerant methods.
This thesis proposes an adaptive resource scheduler which changes
its scheduling criteria based on the current job computation requirements
and current load status of resources. The performance tests confirm that
our adaptive resource scheduler has outperformed the simple scheduling
methods in a GridSim environment. In this thesis, we present the detailed
implementation for the simple scheduling methods and the adaptive
resource scheduler. We also discuss the benchmark results and areas for
improvement and future study.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed
llkyeun Ra


ACKNOWLEDGEMENT
My thanks to my advisor, llkyeun Ra, for all his insight and support
throughout my graduate studies. I would also like to thank all my committee
members for their insight and participation.


TABLE OF CONTENTS
Figures..............................................................vii
Tables..............................................................viii
Chapter
1. Introduction........................................................1
1.1 Grids..............................................................1
1.2 Scheduler Qualities................................................3
1.2.1 Scalability......................................................3
1.2.2 Reliability......................................................4
1.2.3 Minimize Turnaround Time.........................................4
1.2.4 Maximize Resource Utilization....................................5
1.2.5 Throughput.......................................................6
1.2.6 Security.........................................................6
1.2.7 Minimize Complexity..............................................7
1.3 Research Focus....................................................8
2. Related Work........................................................9
2.1 Minimizing Makespan................................................9
2.2 Increasing Resource Utilization..................................10
2.3 Decreasing Job Queue Time........................................10
2.4 Increasing Reliability...........................................11
2.5 Economic Models..................................................11
2.6 Increasing Throughput............................................12
2.7 Simulation.......................................................13
3. Design and Implementation..........................................14
3.1 gridScheduler Class.............................................. 16
v


3.2 GridSim Modifications..........................................18
3.3 Scheduling Methods.............................................20
3.3.1 Round Robin Scheduler........................................20
3.3.2 Random Scheduler.............................................22
3.3.3 First Available Scheduler....................................23
3.3.4 Adaptive Resource Scheduler..................................26
3.4 Example Schedule.............................................29
4. Setup Test Environment..........................................31
4.1 Resources......................................................31
4.2 Gridlets.......................................................34
4.3 Test Run Execution and Statistics Collected....................35
5. Evaluation and Discussion.......................................38
6. Conclusions and Future Work.....................................47
Appendix
A. ResourceList Class..............................................49
B. gridScheduler Class.............................................51
C. Gridtest Class..................................................70
REFERENCES.........................................................92
VI


LIST OF FIGURES
Figure
3.1 AllocPolicy PE Allocation.....................................15
3.2 GridSim Scheduling............................................16
3.3 GridSim Scheduling with GridScheduler.........................17
3.4 Round Robin Algorithm.........................................21
3.5 Random Algorithm..............................................22
3.6 First Available Scheduler.....................................24
3.7 Adaptive Resource Scheduling Method...........................27
3.8 Example Schedule..............................................30
4.1 Resource Setup................................................33
5.1 a and p Comparison............................................39
5.2 Makespan Comparison...........................................41
5.3 Average Job Completion Time...................................41
5.4 Large Output Makespan.........................................43
5.6 Large Output Queue Time.......................................44
vii


LIST OF TABLES
Table
4.1 Resource characteristics...........................................32
4.2 Gridlet variables..................................................35
4.3 a and p values.....................................................36
5.1 Test parameters.....................................................38
5.2 Makespan differences in a and P values.............................39
5.3 Adaptive reduction.................................................42
viii


1. Introduction
The purpose of this section is to give a brief background on Grid
computing and introduce some desirable qualities in a Grid scheduler. As
the focus of this Thesis is an adaptive Grid resource scheduler, it is
important to first present some background information on Grids and Grid
schedulers.
1.1 Grids
Grid computing takes a collection of resources belonging to different
Virtual Organizations (VO) and manages them in a Grid of computational
and/or data resources. The use of these resources, whether it is file
storage and sharing, distributed computation, or running a single application,
needs to be defined by the VO and the organizations that actually own them
[1]. Users with credentials on the Grid are able to submit jobs to be
executed on the Grid. There can be a vast array of resources available to
the Grid, and the resources may join or leave unexpectedly. Based on
these characteristics of the Grid, several challenges arise for Grid
developers. These include differing policies between Virtual Organizations,
the dynamic nature of resources, resource discovery, scheduling of tasks
onto resources, and security of Grid resources. While there is extensive
work on each of these areas, this paper will address only the scheduling
issue. Areas such as resource discovery, how the Grid knows what types
of resources it currently has, and security will not be addressed in this
paper.
1


Assuming that all other Grid services are provided, it is the job of the
Grid scheduler to map the job requests onto the various resources in the
Grid. Several aspects of both the job and resource need to be considered.
First, the job and the resource may have specific criteria that need to be
met. For example, the job may require execution on only Linux Operating
Systems, while the resource may prefer to accept jobs originating from its
local organization before any jobs from remote organizations. One of the
primary goals of the scheduler is to ensure that these rules are met when
scheduling jobs onto resources. Another area for consideration is the
differing policies of each individual organization within the VO. Each
organization may contribute resources according to differing policies, and
maintains administrative control over its resources. As such, issues such
as local scheduling policies and local priorities need to be known and taken
into consideration by the Grid scheduler. Similarly, security is something
that the Grid scheduler must provide. The Grid framework should ensure
that only authorized users are able to access the resources, and the
scheduler should only submit and monitor authorized jobs. Unlike single
computer (SISD, SIMD), MIMD (either tightly coupled or distributed), and
cluster systems, the Grid environment is more dynamic. Depending on how
each Grid is architected, including the varying policies of the organizations
and VO, some grids will be more stable than others. However, in general,
the Grid environment will be more dynamic than single systems or cluster
systems. As such, the Grid scheduler must deal with a dynamic resource
pool. Ultimately, the Grid scheduler must make appropriate decisions to get
jobs submitted and executed on the Grid.
2


1.2 Scheduler Qualities
This section addresses some of the qualities for an ideal Grid
scheduler. Desirable qualities include scalability, reliability, minimization of
average job turnaround time, maximization of resource utilization,
maximization of throughput, security, and minimization of complexity.
Some of these qualities are common to a single CPU scheduler, but there
are different challenges presented by the Grid. Each of these qualities will
be defined and discussed in this section. Not all of these characteristics are
presented in Chapter 3, even though they are under study, but they are
listed here for completeness.
1.2.1 Scalability
One essential quality of a Grid scheduler is scalability. The
scheduler must to be able to deal with a large group of resources that
belong to different organizations. The size of the Grid will fluctuate, and the
scheduler needs to be able to deal with grids of different sizes. In addition,
the number of nodes in a Grid may grow to be very large. Both of these
aspects require that the scheduler be able to handle a large and changing
population of resources. Therefore, the architecture of the Grid scheduler
should reflect this characteristic of grids. A scheduler that is able to handle
small numbers of resources very well may not necessarily function well
when the number of nodes is very large. Grids will change size as
organizations join and leave the VO, and the scheduler must be able to
handle the different numbers of resources. In addition, the scheduler
3


should be able to handle the dynamic nature of the resource pool and scale
accordingly.
1.2.2 Reliability
Due to the dynamic resource pool in a Grid environment, another
desirable aspect in a scheduler is reliability. Since the resources may join
and leave unexpectedly, the Grid scheduler should be able to make sure
jobs are finished in the event of a node leaving. The failure of a node must
also be considered, similar to issues in cluster computing. This is an area
that is very relevant to grids as the frequency of nodes joining and leaving is
typically greater than that of a tightly-coupled system or a cluster. In
addition, since each organization maintains control over its own resources,
it is harder to maintain administrative control than if a single organization
had administrative control over all resources. Jobs may consist of single or
multiple processes and the scheduler should attempt to make sure that the
submitted job will finish in the event of one or more nodes leaving. The
methods that are used to accomplish this should be balanced with the other
qualities of a Grid scheduler. Examples of methods to accomplish job
completion include multiple copies of jobs and job migration.
1.2.3 Minimize Turnaround Time
Minimizing the average turnaround time (wait time in queue +
execution time) for all jobs submitted is another ideal characteristic of the
Grid scheduler. In the opinion of a Grid user, this may be the most
important aspect of a Grids performance as one typically wants their job to
finish in a short amount of time. This is somewhat analogous to
4


determining the best makespan, as makespan is the total amount of time to
finish a set of jobs scheduled on the Grid. In addition, this characteristic is
closely related to maximizing resource utilization and throughput. Jobs will
be submitted to the Grid that have long running times as well as short
running times. The job of the Grid scheduler is to make sure that resources
will get scheduled in a way such that the average turnaround time for a job
is as small as possible. This can be somewhat difficult to achieve if not all
jobs are known ahead of time, but by looking at history it can be
approximated. Thus, a balance will need to be made between the long
running jobs and short running jobs. Chapter 5 discusses this aspect in
more detail as it is one of the goals of this paper.
1.2.4 Maximize Resource Utilization
Maximization of resource utilization is another area of focus for Grid
schedulers. When tasks get submitted to the Grid scheduler, they may
have certain criteria that must be met for them to run. For example, they
may require a certain number of nodes, certain amount of disk space, or a
minimum amount of network bandwidth. Making sure that the resources
are utilized and not sitting idle while jobs are waiting for execution is a key
quality of the Grid scheduler. There may be instances where, due to
requirements of the jobs and resources, this is unavoidable. However, the
scheduler should assign jobs to resources such that as many jobs as
possible are executing, thus maximizing the utilization of the Grid, it is
important to note that if all jobs submitted to the Grid will run on any of the
Grid resources, then it is easy to fully utilize the Grid resources. However,
there may be mappings between tasks and resources that will offer the
5


same utilization but finish in less time. This can happen not only based
upon job complexity, but local prioritization may play a part as well.
1.2.5 Throughput
The throughput of the Grid is similar to utilization. Both of these
qualities must take into account the different types of tasks coming into the
Grid. In the case of throughput, the scheduler tries to maximize the amount
of tasks that are completed by the Grid in a given time. In this case,
running a lot of short tasks will produce more throughput than a few long-
running tasks. The computational Grid should be available for users to run
their tasks, and not be weighed down by long-running tasks. As such, a
good throughput algorithm might be Shortest Job First (SJF) that scheduled
each job on the resource that would complete it the fastest. However, this
must be balanced with the need to accomplish some of the larger tasks. An
algorithm that only relies on the throughput of the Grid may end up starving
some of the longer running jobs. Thus, some balance between throughput
and completing the long running jobs is necessary.
1.2.6 Security
Security is another key quality for the Grid scheduler. The scheduler
will assume that the security for the Grid, such as encryption of data at rest,
is handled by different pieces of the Grid framework, and this discussion
only applies to the scheduler itself. It must be able to accept jobs from
authorized sources, rejecting jobs from non-Grid users. In addition, each of
the organizations that compose the Grid has their own local scheduling
criteria as well as security policies. The Grid scheduler must account for
6


these as well. Not only does the Grid scheduler need to be aware of the
different local policies, but it also needs to adhere to the security policies of
the VO. There are many different authorization and encryption schemes in
use today, and the scheduler should implement the most commonly seen
ones. Finally, the Grid scheduler needs to have the ability to submit jobs to
the local schedulers in a secure way. Again, this may be different for the
varying organizations based upon their individual security policies. Security
is constantly being updated and revised as new research is done, and a
Grid scheduler needs to keep up with these updates. This applies not only
in the authorization and encryption methods, but also in any communication
with the local organizations.
1.2.7 Minimize Complexity
The last desirable quality of the Grid scheduler discussed is
minimizing the complexity of the scheduler. This is not as critical as the
other qualities as it does not directly influence the performance of the Grid,
but is something that should be considered. If the Grid scheduler excels at
the other areas, complexity is something that can be tolerated. However,
the scheduling system for the Grid should not be so complex that it is prone
to failure, which would violate the reliability requirement. The maintenance
of the software is something that should be taken into consideration. Both
the maintained of the scheduling software and the developers of new
features should not be overwhelmed by the complexity of the solution.
Again, the scheduling algorithm will be somewhat complex due to the
requirements above, but it should be minimized where possible to aid in the
support of the scheduler and the development of new features.
7


1.3 Research Focus
This thesis focuses on reducing the makespan and average job
turnaround time. The job turnaround time breaks down to two factors: time
spent in the queue and time spent running. Typically, faster hardware
means the job will finish faster, so it is the job of the scheduler to utilize
faster hardware more often while trying to still finish all jobs. As discussed
above, there are many areas in Grid scheduling that can be researched.
Indeed, there is much research that has been done which is discussed in
Chapter 2. Makespan and average job turnaround time are somewhat
related and gains made in one will typically see gains in the other, though
this is not always the case. In addition, Grid simulation is useful in
researching these two areas, whereas areas like security may be harder to
research in simulation. While all areas seek to improve users experience
with the Grid environment, having the average job complete faster is the
goal of this thesis.
The following areas are discussed in this thesis, and are considered
to be in scope. Chapter 1 gave background information on Grids as well as
desirable qualities of a Grid scheduler. Related work is presented in
Chapter 2. The design and implementation of four Grid schedulers using
GridSim is described in Chapter 3. There are three simple Grid schedulers
in addition to the proposed Adaptive Resource Scheduler. Chapter 4
defines how the test environment is set up. Results of the experiments are
presented in Chapter 5. Finally, the conclusions and future work will be
discussed in Chapter 6.
8


2. Related Work
This section will list some of the areas being researched in Grid
scheduling. Not all possible areas are listed as this paper focuses mainly
on makespan, throughput, and utilization aspects; reducing the makespan
and average job turnaround time is the goal of this project. As such, areas
such as security will not be analyzed and presented in this paper. Areas of
study that are presented include minimizing makespan, increasing resource
utilization, decreasing wait times for jobs, increasing reliability, economic
models, and increasing throughput. Also discussed is the use of simulation
in Grid development. The remainder of this section describes the problems
being solved.
2.1 Minimizing Makespan
The first area discussed is minimizing the makespan for a schedule.
In [7], the authors suggest a genetic algorithm in order to decrease the
makespan for the schedule. The solution they present does accomplish
this, but it raises questions on the complexity of the solution. They do give
a good example of performance prediction, which is used to predict the end
times for programs, and a scheduling system. The solution presented
involves a genetic algorithm that performs mutations to the schedule that try
to ultimately reduce the makespan. This may work well in a Grid, but it is
important to keep in mind the time it takes to perform these calculations,
especially on a larger population size.
9


2.2 Increasing Resource Utilization
Resource utilization is another area that is addressed. In [2], the
authors use computing power used by the schedule (utilization) as the
criterion for judging the schedule. They argue in favor of a round-robin
technique for independent, coarse-grain tasks which requires no knowledge
of the nodes. This attempts to maximize the resource utilization. The
results of this paper argue that this method works well because the nodes
which finish tasks keep getting tasks. This is based on the fact that nodes
are not scheduled again if they are in use. Using this method also would
reduce the makespan for reasons noted above. However, this seems to fit
better into the utilization category because the goal of the scheduler is to
keep scheduling jobs on the next available resource via the unused round
robin nodes. This method is discussed further in Chapter 3 in comparison
with several of this researchs implemented schedulers.
2.3 Decreasing Job Queue Time
The third area that other research tries to solve is decreasing queue
times for jobs. In [3], the authors propose two methods that use multiple
submissions of a job to sites. One involves a single queue and the other
involves a local and remote queue. Once the job has been scheduled, the
scheduler will cancel the other jobs so resources are not used twice. The
overall goal is to get jobs scheduled and run faster by submitting them to
multiple sites. The author in [5] discusses a method for scheduling jobs first
at a local site, then branching out in order to schedule a job quickly. The
paper title suggests real-time scheduling, but it appears that the author is
10


trying to schedule as fast as possible as real-time wasnt really defined.
The goal was to find a dynamic way to get jobs scheduled as fast as
possible by using the local machine first, then the cluster machines, and
finally machines in other clusters.
2.4 Increasing Reliability
Reliability is another area where several papers were focused. The
GrADS project proposed new extensions to their scheduling system [12].
As such, this paper was heavily based on work in the GrADS environment.
One of the major areas addressed was re-scheduling of failed jobs, which
falls under the reliability heading. This paper had other contributions, but
the focus on reliability seemed to be one of the bigger areas being
addressed. In [9], the authors discuss reliability issues for completing a
specific task in an organic Grid. The use of agents is intriguing, but the
paper is limited to dealing, as the title suggests, with a single application.
Another paper that discusses reliability is [4]. The authors suggest
scheduling k replicas for jobs. The goal is to improve reliability of the
system, though it does suffer from utilizing multiple resources for one task.
However, once one of the copies finishes, the rest of the jobs are
terminated so as to not waste resources.
2.5 Economic Models
Economic models for matching jobs to resources in a Grid
environment are an active area of research. There are several different
methods to accomplish this matchmaking, and the authors of [11] do a good
job describing each. One of the main ideas behind economic models is the
bidding system. Several different methods exist, again as described in [11].
11


English auction and Dutch auction are two examples. These can have
either the resource or job bidding. In an English auction, the bids start out
low and increase until none of the bidders are willing to continue the auction.
The Dutch auction, on the other hand, starts high and the auctioneer lowers
the price until one bidder agrees to the price. The auction ends when a
price is agreed upon or a reserve low is met. Assigning different costs to
the resources and jobs allows some preference to be displayed outside of
just run time or CPU speed. This can be used to develop a Quality of
Service (QoS) model for Grid computing. Giving more important tasks
greater budgets can ensure that they can use the faster resources or have
the ability to complete on-time.
2.6 Increasing Throughput
Increasing throughput is an area that is addressed by several papers.
In [8], the authors discuss local scheduling issues, via two queues, in the
average wait time for a job to start. This has the effect of measuring how
fast jobs are being completed on the Grid and is based on the job
acceptance rate. If the wait time for jobs is low, then jobs are being finished
quickly or that the Grid is not fully utilized. In [6], the authors discuss
partitioning a job based on different criteria. This could be the job of the
scheduler if the task submitted allowed for variation in the number of
parallel nodes it can run on. Nonetheless, the authors tried to maximize
throughput by scheduling as the job on the appropriate number of nodes
based on constraints. The authors in [10] discuss some of the issues with
data storage in a computational Grid. The solution presented aims to solve
the overall throughput of the Grid by making sure computational resources
12


have good access to the data they require and not high-latency, low-
bandwidth to the data store.
2.7 Simulation
In order to effectively try out new ideas for Grid scheduling,
simulation is an invaluable tool. GridSim is a Grid simulation toolkit
developed to aid in Grid research. Building and maintaining even a small
Grid for development of new experimental algorithms is not an easy
undertaking. As such, simulation is a powerful aid in testing out new
algorithms without having to build and test on a full size Grid. GridSim
features quite a few Grid features, including facilities to create Broker
scheduling, GIS information, resource and job descriptions. There have
been several papers written and presentations given on GridSim and its
features. In addition, there have been multiple areas of research that have
used GridSim to simulate their algorithms and obtain results for future
research. These can be found on the GridSim website at
http://www.gridbus.org/gridsim.
13


3. Design and Implementation
The GridSim toolkit (http://www.gridbus.org/gridsim/ version 4.0
with SimJava 2.0) was used in this project to implement several simple
scheduling algorithms as well as the proposed Adaptive Resource
Scheduler. GridSim uses the SimJava package, a discrete event simulator,
to provide a simulation environment for Grid computing. Users of GridSim
will typically create one or more resources. Each resource has common
characteristics such as OS, architecture, bandwidth, scheduling policy,
timezone, and cost. The resource is made up of a list of machines, and
each machine can have one or more Processing Elements (PE). A list of
jobs, which are called Gridlets, also needs to be created. These jobs have
characteristics such as userlD, length (in Million Instructions), and
input/output file sizes. As each Gridlet has a userlD associated with it, it is
important to have a user entity that is responsible for scheduling and
receiving the results of each Gridlet that is associated with the userlD. This
is typically done by extending the GridSim class and instantiating a new
instance per user then assigning that ID to each Gridlet that is associated
with the user. It is important to note that the local scheduling of Gridlets to
PEs is done by the local scheduler and that each user entity, derived from
the GridSim class, is responsible for submitting its Gridlets to resources.
The GridSim web site, http://www.gridbus.org/gridsim, offers the source
code, examples, and full documentation.
Certain characteristics were not taken into account for any of the
schedulers. Grid scheduler characteristics like matching a job to a
14


particular OS, architecture, and local scheduling policy are not taken into
account by the schedulers. This is because the Gridlets currently do not
contain that information, and the local schedulers do not enforce these
restrictions. However, these areas could potentially be added to the
GridSim framework. All local schedulers use a policy of space shared,
which uses the SpaceShared class. The SpaceShared class schedules
only one task to a PE at a time, as its name suggests. This is used
because if time shared is used then the First Available scheduler will
always receive events indicating that there are available PEs on each
resource. Technically this is true since the PEs are available, but not
appropriate for the tests using First Available. Also, it should be noted that
the current local schedulers implemented in GridSim do not allow more than
one PE to work on a job. Thus, if the job specifies it requires n PEs, the
length is assumed to be per PE and the job length is increased as indicated
by Figure 3.1 from the Spaceshared (SpaceShared.java lines 147-151)
GridSim class below. However, this project always used one PE per Gridlet
to avoid confusion from this limitation. If a different local scheduler is
implemented, which can be done by extending the AllocPolicy class,
the limitation of one PE per Gridlet can be worked around.
// adjusted the length because the number of PEs are reduced
int numPE = gl.getNumPE();
double len = gl.getGridletLength();
gl.setGridletLength(len*numPE);
gl.setNumPE(1);
Figure 3.1 AllocPolicy PE Allocation
In order to implement different Grid schedulers, certain modifications
needed to be made to GridSim. While GridSim does provide an AllocPolicy
class to override the local scheduling of Gridlets to individual PEs, it does
15


not provide a framework for submitting Gridlets to resources. Examples
given in the GridSim distribution show how one can develop an application
to do this work, such as the GridBroker application. As such, the
modifications needed include the development of a global Grid scheduler
and extensions to existing classes to support gathering data and ensuring
accurate timing. The changes are described below, and then the
algorithms implemented are presented.
3.1 gridScheduler Class
In the Gridsim toolkit, it is normally up to the user to schedule a
Gridletto a resource, as is seen in Figure 3.2.
f Gridlet J ( Gridlet ) User ( Gridlet J ( Gridlet ^ User <3D<3> <2DC£> Machine C2><2} (2X2} Machine
C2><2} Machine C2><2} C5}<2> Machine

Application Machine Lis'. Machine List
Resource Resource
Figure 3.2 GridSim Scheduling
Certain applications, like the GridBroker included in the toolkit, provide a
framework for scheduling Gridlets using additional parameters such as cost.
The cost already built into the resources and Gridlets. As such, developing
a general class or application that schedules Gridlets to resources was
needed. This is similar to the AllocPolicy scheduling for intra-resource
16


scheduling. The gridsched. gridScheduler class was developed for
this, as is shown in Figure 3.3.
gridScheduler extends the GridSim class and handles getting the
resource characteristics. The user first sets a scheduling policy and passes
it a list of Gridlets to be scheduled. Then the gridScheduler simply
handles the distribution of Gridlets to resources according to the selected
scheduling policy. Currently, only one gridScheduler is allowed per
application as it does not yet register multiple userlDs to the underlying
discrete event simulator in order to get the results back. In order to
implement a new policy, the policy first must be added to the enum
schedPolicy, a function implemented for the new policy, and a statement
added to the switch statement in the body () method that calls the policy
for the scheduling algorithm. This is somewhat complex, but was
necessary to compare scheduling algorithms without implementing an
application for each algorithm. Any new scheduling method may make us
of some utility functions that gridScheduler implements. Also, the new
scheduler should collect some statistics for time spent in the global
scheduler. Please see the GridSim modifications for more details.
17


3.2 GridSim Modifications
The Gridlet class had to be extended to record time spent in a
global scheduling queue. The GridSim framework already records the
arrival time at a resource, start of execution time, and end of execution time
in the Gridlet class. This allows the calculation of any time spent in the
local queue as well as execution time. To calculate time spent in the global
queue, two fields were required in a Gridlet, along with methods to get/set
the values. These were: gridSubmissionTime_ and
localSubmissionTime_ which keep track of the time the Gridlet was
submitted to the global scheduler and the time the global scheduler
submitted it to the resource, respectively. Note that
localSubmissionTime_ does not equal the time the resource sees the
Gridlet arrive. The only time when this is true is when the filesize is 0 as
there is no need to transfer data. Thus, the difference in
localSubmissionTime_ and the result of the Gridlet method of
getSubmissionTime is how long it took to transfer the file. In addition,
the Gridlet class had a field arrivalDelta_ added to address the
interarrival times of the Gridlets into the system. This field specifies the
amount of time that should have passed from the previous Gridlet until this
Gridlet arrived. There is a method, setGridletSubmissionTime (), that
is responsible for ensuring the times are correct for the global queue. It
checks the current simulation time via the clock () method of GridSim. If
clock () returns less than the previous Gridlets Grid submission time +
arrivalDelta_, then the method will advance the simulation by the
18


difference and set the current Gridlets Grid arrival time. If the current
simulation time is greater than the previous Gridlets Grid submission time +
arrivalDelta_, then the method will set the current Gridlets time to
when it was supposed to arrive. This ensures that global timing is
consistent, even though the data is modified after the events. The time
when the Gridlet leaves, localSubmissionTime_, is unchanged as it is a
valid indication of how long the gridScheduler took.
Gridlets do not currently store the time they arrive at the user or
gridScheduler after they are returned by the resource. The latest event
stored in the Gridlet is the end of execution, which is set by the resource
before the Gridlet is set for transmission back to the user. Finding out the
arrival time could be resolved by scheduling an event in the global
scheduler every second and checking for a waiting event. However,
currently the end of the job is measured by when it finished executing, and
does not take into account any output file transfer time.
To track resource usage, the ResourceCharacteristic class
was modified to include two new variables: totalGridletsScheduled_
and totalProcessTime_. These were updated by looking at the Gridlets
as they were being processed when the simulation was finished, but it was
necessary to keep these statistics with the resources themselves. Methods
for incrementing the variables were also implemented.
The GridletList class was also modified to allow sorting by
Gridlet ID, which made reporting the result list more consistent. This was
simply done by implementing a new Comparator class and taking
19


advantage of Javas inherent sort function GridletList extends the
LinkedList Java class which is a Collection.
3.3 Scheduling Methods
The three comparison scheduling algorithms Round Robin,
Random, and First Available are implemented in a straightforward manner.
The gridScheduler class is responsible for making sure the total number
of resources, which needs to be passed to it, is available prior to running
the selected scheduling policy. Due to the multi-threaded nature of GridSim,
it is possible for the resources to arrive from the framework, Grid
Information Service (GIS), in a different order on different runs of the
simulation. Thus, this list is sorted according to resource ID and ensures
that on multiple runs the resources are in the same order. In all code
samples below, the setGridletSubmissionTime () function will
advance the discrete event simulator to the time when the Gridlet should
have arrived or set the gridSubmissionTime_ for the Gridlet to the
appropriate time, as discussed above. Since the local scheduler does not
take factors such as OS and architecture into account, none of the Grid
schedulers use these in scheduling decisions.
3.3.1 Round Robin Scheduler
The Round Robin (RR) algorithm first gets the list of resources from
the gridScheduler class. Since this list is sorted by resource ID, the
lowest resource id will be scheduled first there is no effort made to sort
resources by any desirable characteristics. This can make a difference in
the results depending on the type and number of jobs and varying resource
20


characteristics. The Round Robin algorithm then starts at the head of the
Gridlet list and submit Gridlet 0 to Resource 0. It proceeds down the Gridlet
list, scheduling each Gridlet to the next resource. Once the last resource
has been scheduled, the RR algorithm will then continue at the top of the
resource list. This continues until there are no more Gridlets in the input list.
This can be seen in the pseudo code listed in Figure 3.4.
current_resource := 0
for i:= 0 to total_gridlets do
if current_resource >= total_resources then
current_resource := 0
end
gridlet = get_gridlet(i)
gridletSubmit(gridlet, current_resource)
current_resource := current_resource + 1
done
Figure 3.4 Round Robin Algorithm
The RR scheduler will then enter a loop to receive all Gridlets this
received list is requested by the main application so it can examine the
results. This algorithm is different than the RR described in [2] since it does
not ensure that a resource is available before scheduling it. The local
schedulers in this case queue up the requests and will schedule them,
although it would be possible that certain local schedulers could discard
jobs. This algorithm will never spend any time in the global queue due to
the fact that it immediately dispatches the Gridlet to the resource.
21


3.3.2 Random Scheduler
The Random scheduler simply schedules the Gridlets randomly to a
resource. It uses a seeded random number generator to ensure that
subsequent runs will always return the same order. This was necessary for
comparison as it would not be possible to compare algorithms if the Gridlets
were not assigned to the same resources for different runs. Nonetheless,
the scheduler still performs in a random fashion. The operation will loop
through all the Gridlets and for each one take a random number and mod it
by the number of resources. It will then schedule the Gridlet to the result of
the mod as depicted in the code excerpt shown in Figure 3.5.
for i := 0 to total_gridlets do
random_int := Math.abs(random.nextInt())
resource := random_int % total_resources
gridlet = get_gridlet(i)
gridletSubmit(gridlet, current_resource)
done
Figure 3.5 Random Algorithm
Like the RR scheduler, the Random scheduler will then enter a loop
and receive all of the Gridlets. It also does not ensure that the resource is
available before scheduling, and as such it also spends no time in the
global queue.
22


3.3.3 First Available Scheduler
The First Available (FA) scheduling algorithm queries each resource
in the ordered resource list and will schedule the Gridlet to the first one that
has an available PE. There are several differences in the general function
of the FA algorithm. First, simulation time will run while it is querying the
resources. This is because querying the resources is done by invoking
GridSim methods which use SimJava to advance the simulation time. As
such, the arrival times are modified to reflect the arrival delta so that it
accurately represents when the Gridlet arrived; this is done by the
setGridletSubmissionTime () method. Second, it may be that all
resources are busy. The method will then gridSimHold (1.0), which will
advance the simulation by 1 second. It will then start the query for an
available resource from the beginning of the ordered resource list. This
also means that the order of the resources matters as time is lost while
querying for resources. If all the slow resources are first in the resource list,
they will be assigned jobs first. When all resources are busy, it is probable
that the fastest resources will complete jobs before the slower ones. The
FA algorithm must first check with all slow resources, since they are first in
the list, before finding an available resource. This will cause the job to
remain in the scheduling queue longer as the algorithm spends time waiting
on status from the resources. The pseudo code for the First Available
scheduler is shown in Figure 3.6.
23


for i := 0 to total_gridlets do
sched_to := -1
while sched_to == -1 do
for j: = 0 to total_resources do
free_pe := -1
while free_pe == -1 do
event = get_resource_free_pe(j)
if event == FREE_PE then
free_pe := event
end
if event == GRIDLET_RETURN
return_list_add(event)
end
done
if free_pe > 0 then
schedule_to = j
break for loop
end
done
if sched_to == -1 then
sleep(1)
end
done
gridlet = get_gridlet(i)
gridletSubmit(gridlet, sched_to)
done
Figure 3.6 First Available Scheduler
The code is similar to the other loops shown over the Gridlet list,
although there is one difference. When the FA algorithm sends a request
out to get the number of free PEs that a resource has, it needs to wait for a
24


response. This, as stated above, will cause the simulation to advance. As
there may have been other Gridlets scheduled prior to this request, there is
a chance that Gridlet results are waiting to be processed by the
gridScheduler. This would normally be processed by the User, which is
extended from Gridsim, and all events are sent to the same ID.
Nonetheless, the FA algorithm must test the type of object received and
deal with it appropriately. The FA algorithm will add a received Gridlet to
the received list or verify the number of PEs for a resource if that is the type
that was received. Also, since the FA scheduler will keep Gridlets in the
global queue while waiting for a resource to schedule them, time can be
spent in the global queue. There will be no time spent in the local queues,
as Gridlets only arrive at resources when they can be processed. Once all
Gridlets have been scheduled, the FA scheduler must wait for any
outstanding Gridlets. This is done by a receive loop that waits until the
receive list is the same size as the submit list.
The implementation of the FA algorithm, as described above, is very
similar to the RR algorithm described in [2]. Both of these algorithms loop
through the list of jobs. Each also assigns the next available job when a
resource becomes available. The Round Robin algorithm in [2]
accomplishes this by realizing when a job is done and assigning the next
job to the resource, whereas FA queries until it finds a free resource.
However, the end result is very similar. When all jobs have been assigned,
FA enters a loop waiting for the results to come back. In contrast, when the
RR in [2] is done scheduling jobs, it will schedule, in a similar RR fashion,
any remaining jobs onto the resources as they are free. This allows the
potential for a long running job on a slow machine to finish faster if it gets
25


re-allocated on a faster machine. However, this only happens after all jobs
have been scheduled.
3.3.4 Adaptive Resource Scheduler
Prior to designing the Adaptive Resource Scheduler, some
simulations were run using the simple scheduling algorithms. It was
observed that getting information from the resources, as is done with the FA
algorithm, generally resulted in a better makespan and smaller average job
turnaround time. This will be discussed in more detail in Chapters 5 and 6,
but it illustrated that knowing updated data was important to make good
scheduling decisions. However, there is time lost during the transmissions
to find the up-to-date resource information. Using information about what is
currently allocated to a resource, the speed of the resource, the to-be-
scheduled job, and the past performance of the resource, it is possible to
make a good approximation without the overhead of querying each
resource. This also has the advantage of using the faster resources first
rather than relying on them to be available more often due to them finishing
jobs faster. The Adaptive Resource Scheduler uses the method in Figure
3.7 to find the resource to schedule a job on.
26


// total_completed_tasks represents the completed
// tasks from all resources
use_gamma := 1
alpha := set_alpha()
beta := set_beta()
gamma := 0.0
for i := 1 to n do
if tasks_completedi == 0 then
use_gamma := 0
end
end
if use_gamma then
gamma := total_completed_tasks / total_tasks
if gamma < 0.10 then
gamma := 0.0
end
end
score := MAX_FLOAT
for i := 1 to n do
res_score := S(alpha, beta, gamma, i)
if res_score < score
selected_resource := i
end
end
Figure 3.7 Adaptive Resource Scheduling Method
This method ensures that each resource has completed at least one
task, and sets y to be the same for each calculation of s (). Since s ()
adds terms, it is important for all calculations use the same multipliers for
each term. This allows the resource-specific values to determine the best
resource, and not a multiplier. The function s (), defined in Eq 3.1, returns
a value for the resource, with a smaller value being better.
27


f
\
Iff
Si{a,P,y) = a-Y,
k=1
Tk-fk
M.
+ p
(nr \
Im+\
+ y

&>*>
\j=s
where:
a Scaling factor between [0,1] that is passed in
P Scaling factor between [0,1] that is passed in
y Scaling factor between [0,1] that is passed in
/ Resource number
m number of tasks currently scheduled
Tk MI (Million Instructions) of Task k
Mj MIPS (Million Instructions Per Second) rating of resource i
t time in seconds
5 start of time interval
e end of time interval
(Eq. 3.1)
fk= 0 if Tk is not running
1 if Tk is running on resource /
gk = 0 if Tj is running or not started
1 if Tj is complete on resource i
Equation 3.1 consists of three terms which are added together for
the final result. Each term has a scalar associated with it that determines
how much the term contributes to the overall result. The first term
represents the allocated tasks to the resource, scaled by the speed of the
resource. The second term represents the expected completion time for
the job that is being scheduled. The last term constitutes completed tasks
over a given timeframe. The term is inverted as a smaller number is more
desirable. This gives an approximation for performance since more
desirable resources will complete more tasks. Also, y is the same for each
resource calculation.
28


In a real-world scenario, more data would be needed to make a
scheduling decision. Adding additional terms such as server throughput,
network load, disk speed, etc. would add to the ability for the scheduler to
make better scheduling decisions. Simulation is a good place to begin
testing these, but not all aspects are able to be tested. As such, the
Adaptive Resource Scheduler may need to be extended based on results
obtained in a real environment.
3.4 Example Schedule
Based on the descriptions above, an example schedule for the
different schedulers is given in Figure 3.8. This represents when the jobs
get scheduled on the resources, and not when they are submitted. The
First Available scheduler will wait until jobs are received back before
scheduling to the resources, while all others dispatch their jobs immediately.
It is up to the local schedulers to determine the order, but in this example it
is assumed that they follow a First Come First Serve approach. Also, it
should be noted that the resources run jobs at different speeds, and the
jobs are scaled according to the speed of the resource they are run on.
The schedule presented here is only an example for how the jobs may be
allocated. The actual results for Random and Adaptive Resource
Scheduler will depend on random number generation and the resource
parameters, respectively.
29


Time
Jobs
Resource Speeds
R1 -75 MIPS
R2-100 MIPS
R3-125 MIPS
Figure 3.8 Example Schedule
30


4. Setup Test Environment
In order to test the performance of the different scheduling
algorithms, it was necessary to define a set of resources and job
characteristics for different test runs. Resources are collections of
machines in Gridsim, and each of these machines is a collection of
Processing Elements (PE). The resources always stayed the same for the
test runs. Certain parameters of the jobs varied to compare performance of
the algorithms. This section will describe, as implemented in GridSim, the
resource setup, jobs (Gridlets) and their characteristics, and how the test
runs were executed and data collected.
4.1 Resources
Resources in GridSim are collections of machines, and these
machines are collections of PEs. The PEs may be of different speeds, and
there may be varying numbers of PEs per machine in the machine list. For
the purposes of this experiment, given a particular resource, all machines
will have the same number of PEs and each PE will have the same speed
for that resource. In GridSim, the speed of the PE is described in terms of a
MIPS rating. Different PE speeds can be compared directly; a higher MIPS
rating indicates a particular PE is faster, regardless of the architecture or
05. Resource characteristics such as architecture, OS, cost, timezone,
and communication link speed are all the same across the list of machines,
which makes the resources homogeneous. The resources defined for this
experiment were similar to some of the resources discussed in [13] on
31


scheduling simulation experiments. They were also similar to several of the
papers referenced on http://www.gridbus.org/gridsim. However, some
changes were made to allow for a slightly greater difference in Million
Instructions Per Second (MIPS) rating, the OS, and the architecture. All
resources in this experiment use space shared for the local scheduling
policy as discussed in Chapter 3. Table 4.1 lists the resource
characteristics.
Table 4.1 Resource characteristics
Resource Number of Machines PEs per Machine MIPS rating per PE Total MIPS rating for Resource Arch OS
0 5 2 200 2000 Intel Linux
1 7 1 350 2450 Intel Windows
2 3 4 100 1200 Sparc Solaris
3 1 8 200 1600 Intel Linux
4 10 1 500 5000 Intel Solaris
This gives 5 resources with a total MIPS rating varying from 1200 to
5000, which represents the different computing powers for the resources.
This allows there to be a difference in processing speed for comparison
with the different scheduling algorithms. The network speed was kept
constant as initially there didnt seem to be a difference for the file sizes
during initial testing. However, since the discrete simulator will take the file
size and calculate how long it will take to transmit the file over the
communication link, the network speed is really an extension of the job size.
If GridSim was extended to include information on where the input and
output job sizes were, then perhaps this would be important. The reason is
that if a scheduler was presented with a job with big input/output it may try
to schedule it on a resource where the data was local or there was a fast
link to avoid long transfer times. However, this functionality is not currently
32


in GridSim, and all network links were the same speed. The GridSim entity
itself, which controls job distribution and is incorporated into the
Interconnection Network in Figure 4.1, had a speed of 560 Mbps which is a
greater rate than all links combined so as not to be a limiting factor. Figure
4.1 depicts the logical layout of the resources.
100 MIPS rasing par Pg
1200 seta! MIPS rating
Figure 4.1 Resource Setup
33


4.2 Gridlets
This section defines what characteristics make up a job, or Gridlet, in
GridSim as well as how they were created for this experiment. There are 3
main characteristics that define a job in GridSim: the number of instructions
the job will execute (GridSim defines this as the job length), the input file
size, and the output file size. Due to limitations in the schedulers that
assign a Gridlet to a PE within a resource, each Gridlet is an independent
task and is not executed in parallel. If a Gridlet is defined as requiring
multiple PEs, it will be normalized to one PE as described in Chapter 3. A
Gridlet will have various other status variables and methods, but this
experiment only requires that these three characteristics are set. Any other
information about a job, such as required OS or architecture, is not in the
scope of this work. This is due to the fact that these fields are not currently
defined in a Gridlet. To simulate the arrival times of jobs into the Grid, a
fourth required field was added to the Gridlet: the job interarrival time. This
can be set to different values to indicate various loads. All values were
randomized to a value in the range presented in Table 4.2 using Javas
Random class. This was done to provide some variation for the parameters.
The same seed was used for Random so that the same values were
produced on subsequent runs. This was necessary to ensure the same
jobs were presented to the schedulers to provide a valid comparison.
Possible values for these variables are listed in Table 4.2.
34


Table 4.2 Gridlet variables
interarrival time job length input size output size
0-5 s 500,000 1,500,000 Ml 250 750 bytes 250 750 bytes
0-50 s 2,500,000 7,500,000 Ml 1500-4500 bytes 1500-4500 bytes
0-100 s
There are a total of 24 scenarios when one value from each column
in Table 4.2 is selected (3*2*2*2=24). For each scenario 1000 Gridlets
were created and stored in a list. This list represents the Gridlets that each
scheduler will need to assign to resources. The next section describes how
this process works.
4.3 Test Run Execution and Statistics Collected
Each scheduler runs a test run using one of the 24 possible
scenarios depicted by Table 4.2. For the Adaptive Resource Scheduler, the
values of a and (3 will be varied according to Table 4.3.
35


Table 4.3 a and P values
a P
0.00 1.00
0.25 0.75
0.50 0.50
0.75 0.25
1.00 0.00
Each row in Table 4.3 represents one set of values that was used,
unlike the case for the other variations. This was done to give a
comparison of the different values that could be set in the Adaptive
Resource Scheduler, and required 5 runs for each of the 24 different test
scenarios defined by Table 4.2.
A single test run happens as follows. The resources are created by
the end user in addition to a set of 1000 Gridlets according to one of the
scenarios in Table 4.2. A scheduler is selected and parameters are set in
that scheduler, if necessary. The list of Gridlets is then passed to the
gridScheduler and the simulation is started. The scheduler receives the
list of Gridlets, and proceeds through the list sequentially. Gridlets are
timestamped by the scheduler to arrive according to the interarrival delay
defined in the Gridlet. The simulation time is advanced if necessary as
described in Chapter 3. Each scheduler will then select a resource to
assign the Gridlet to, advancing the simulation time if necessary. The
Gridlet is timestamped again for the time that it departs the
gridScheduler and it is passed to GridSim methods to be dispatched to
36


the selected resource. Transmission delay due to the input file size, arrival
time at the resource, start of execution time, end of execution time, and the
output file transmission delay are all handled by the GridSim framework.
These are set in each Gridlet, and are used to calculate the makespan and
average job turnaround time when the job is received by the scheduler that
dispatched it.
37


5. Evaluation and Discussion
In general, the order of performance ranked, from worst to best,
Round Robin (RR), Random (Rand), First Available (FA), and Adaptive
Resource Scheduler (Adap). The majority of tests followed the same
patterns with schedulers performing similarly during the different tests.
There were some exceptions to this which will be discussed. However, for
simplicity the test parameters in Table 5.1 will be used in the discussion of
the results. When the exceptions are discussed, the differences will be
noted.
Table 5.1 Test parameters
interarrival time job length input size output size
0-50 s 500,000 1,500,000 Ml 250 750 bytes 250 750 bytes
First, a discussion of the different effects of the a and p values in the
Adaptive Resource Scheduler will be presented. This will also include a
discussion on the Adaptive Resource Scheduler, and what values proved to
be the best. Next, the makespan and average job turnaround time of the
different schedulers will be compared. Finally, some interesting exceptions
will be presented and discussed.
For the most part, varying a and p did not affect the performance of
the makespan or average job turnaround time. However, there were
differences when different values were used. The differences in makespan
38


are shown in Table 5.2, while a graph of these differences is shown in
Figure 5.1.
Table 5.2 Makespan differences in a and p values
(a.P) (0.00,1.00) (0.25,0.75) (0.50,0.50) (0.75,0.25) (1.00,0.00)
makespan 200,362.39 s 84,473.28 s 84,455.37 s 85,856.80 s 87,404.78 s
Adaptive Resource Scheduler 1M Ml, 0-50 s delay, 500 bytes in, 500 bytes out
Figure 5.1 a and p Comparison
When a is 0, any scheduling decision will get allocated to the fastest
resource. This is due to the fact that only the term that estimates the
completion time of the job will be used. Since only the fastest resource will
be used, no jobs will be allocated to other resources, and the y term will not
be used. The other variations of a and p did not show very significant
39


differences in the resulting makespan or average job turnaround time.
However, it was clear in all tests that a = 0.25 and p = 0.75 produced the
best makespan and average job turnaround time. The value in the a term
will generally be much larger than the p term, so scaling it down somewhat
is desirable. This is because the terms are additive. When the schedulers
are compared the values of a and p will be 0.25 and 0.75, respectively.
Out of the 120 tests that were run using the Adaptive Resource
Scheduler, only 29 utilized the y term. The reason for this is that not many
jobs were returned, and as such there was not enough confidence to use
the y term. In addition, for the tests that utilized the y term, if it was set to 0
the scheduling result was still the same. This means that in the
experiments that were run, y did not provide a significant change to the
schedule. There are several reasons for this. First, since GridSim uses a
discrete event simulator and the length of the job is known beforehand, the
end time of the job is known when it is scheduled. The y term is intended to
provide feedback for the resource performing better or worse, but since the
resources perform according to their MIPS rating it isnt as useful in
simulation. Also, the other two terms are generally larger than the y term.
As such, the contribution it makes is less. By modifying the a and p values,
along with scaling the y term appropriately, the effects should be seen more
clearly.
The makespan and average job turnaround time are closely related,
and the schedulers performed in the same order for both in the experiments.
Figures 5.2 and 5.3 show the results of the different schedulers based on
the criteria given in Table 5.1, with the addition of two other job interarrival
40


times. The value of 24.6397 seconds corresponds to the arrival delay of
0-50 seconds.
1M Ml, 500 bytes in, 500 bytes out
200,000.00
180,000.00
160,000.00
140.000. 00
120.000. 00
100,000.00
80,000.00
60,000.00
40.000. 00
20.000. 00
0.00
*-



-RR
-Rand
-FA
- Adap
2.464 24.6397
Average Job Interarrival Time (s)
49.2794
Figure 5.2 Makespan Comparison
Figure 5.3 Average Job Completion Time
41


It can be seen in Figures 5.2 and 5.3 that the Adaptive Resource
Scheduler outperformed the simple scheduling methods. The job
completion time is defined as the total time from job submission to job
completion. Thus, the reason that the average job completion time
decreased as the job interarrival time increased is that there is less time
spent waiting in the queue. This is due to the fact that the job has not
entered the system yet, and thus the timer is not started. This trend
presented in Figure 5.3 held true for all tests, although the decrease in this
configuration was the most pronounced. There was not much variation in
the makespan due to different job interarrival times due to the interarrival
times being relatively small compared to the overall execution times. The
Adaptive Resource Scheduler did outperform the schedulers in all the tests,
and the graphs above are representative of the results for a majority of the
tests. It is clear that taking dynamic data into account, such as the state of
the resource and expected completion time of the job, helps a scheduler
allocate jobs better. Table 5.3 shows the percent improvement of the
Adaptive Resource Scheduler over the simple schedulers.
Table 5.3 Adaptive reduction
n (comp and i/l Ml, 500 bytes in, 500 bytes out, t=24.6397 seconds ared to Adap which had makespan of 84,224.37 seconds Average Job Turnaround Time of 30,649.95 seconds)
Scheduler Makespan % Reduction Average Job Turnaround Time % Reduction
RR 176,250.49 s 109.26% 42,342.78 s 38.15%
Rand 158,188.69 s 87.82% 40,550.97 s 32.30%
FA 101,036.45 s 19.96% 35,399.32 s 15.50%
There were some instances where schedulers did not perform the
same as in the general case. These cases center around the FA algorithm
42


and a test where the output size is large. When the output size is large,
there is one very big difference between the FA algorithm and the other
algorithms. This is that FA will not schedule a job until it has received the
output back from the resource. All other schedulers immediately schedule
the job to the resource and allow the local scheduler to queue the job.
When a job has finished running, the local scheduler will dispatch it back to
the user, which in this case is the gridScheduler. However, it also starts
another job from the queue at this time, rather than waiting for the I/O to
finish for the completed job. Figure 5.4 shows this effect on the makespan.
I
1M Ml, 500 bytes in, 3000 bytes out

i
l
i
RR 'j
Rand
AFA
* Adap
Average Job Interarrival Time (s)
Figure 5.4 Large Output Makespan
Since the local schedulers start the job right away, the difference is
due to the FA scheduler waiting until it receives the job back from the
resource. This can be seen by looking at Figure 5.5, which depicts the
queue time for the test.
43


1M Ml, 500 bytes in, 3000 bytes out
Figure 5.6 Large Output Queue Time
This shows that it is preferred to not wait for a local resource to be
free before scheduling as time may be lost waiting for data transfer.
However, it should be noted that all Grid schedulers will have to take the
local scheduling policy into account. For example, the global scheduler
should wait for the resource to be free if the local scheduler will cancel the
job. The cancellation could be because of load, local preference, or various
other reasons.
The GridSim toolkit is designed to test various aspects of a Grid, and
it does this by utilizing a discrete event simulator. There are some
limitations to this which influenced how the gridScheduler class was
implemented, although these can be worked around. Adding some logic in
the local schedulers to simulate server load, job failures, etc. would be a
first step. Also, the Gridlet class can be extended with little difficulty to
44


include information about OS, architecture, and other requirements. The
schedulers and resources would also need to implement ways to handle
these new additions. This would allow for better matchmaking decisions
where jobs required a certain OS and architecture. Adding some indication
of where the files reside would allow algorithms using that information in
scheduling decisions to be tested.
The gridScheduler class also has several areas that can be
improved upon. First, the class needs to be modified to include several
other scheduling algorithms. This is helpful for comparing any new
algorithms to be tested. Comparing the Adaptive Resource Scheduler to
some simple scheduling algorithms is a good first step, but comparing
against other published algorithms is desirable. It also should incorporate
any enhancements in GridSim into its scheduling decisions. The methods
for implementing new scheduling algorithms could be refined so it doesnt
take modifications in several different places in the class. Currently, the
class has a limitation that requires all Gridlets it will schedule to be
associated with its ID. This should be changed to include scheduling for all
user IDs. The return jobs would either need to come back to the
gridScheduler or possibly to an external user entity. In the case of the
former, the class could either substitute its ID for the users ID and then
remember to route it back to the appropriate user or be the end destination
for the job. Finally, the gridScheduler class can be integrated better into
GridSim as a whole.
To summarize, the scheduling algorithms that took the state of the
resource into account preformed better on average than those that did not.
45


In addition, polling the resources for information is not always desirable as it
leads to increased communication and latency in making a scheduling
decision. In the case of the FA scheduler, a fast resource at the end of the
resource list means that it will poll all others before getting to the fast
resource. This was the case in the resources used in the examples. Also,
waiting on jobs to finish before scheduling to local resources can be costly
depending on the communication delay. Using information about the state
of the resource without polling can provide similar or better results without
having to poll the resources. The Adaptive Resource Scheduler makes use
of this data, and also provides for feedback on resource performance.
46


6. Conclusions and Future Work
The goal of this thesis was to develop a Grid scheduler that reduced
the makespan and average job turnaround time. A Grid simulator, GridSim,
was set up and customized to provide an environment to evaluate different
scheduling methods. Several scheduling methods were implemented and
the performance of each was observed. Based on these results, the
Adaptive Resource Scheduler was designed and implemented in the
GridSim environment. Each scheduler was then run through a series of
experiments so that comparisons could be made between the different
scheduling methods.
The results showed that the algorithms which took some dynamic
information into account, either directly or indirectly, performed better than
algorithms that did not take any dynamic information into account. This did
not hold true all the time for the FA algorithm, but did remain true for the
Adaptive Resource Scheduler. Indeed, the Adaptive Resource Scheduler
performed better than the comparison scheduling algorithms in all scenarios.
The FA scheduler showed that time can be lost in the scheduling algorithm
if it needs to constantly check with resources for updated information. By
using a combination of expected completion time, jobs scheduled to a
resource, and resource performance history, the Adaptive Resource
Scheduler is able to make good scheduling decisions without the overhead
of constantly querying the resources.
47


The Adaptive Resource Scheduler can be modified to choose more
precise values for a, J3, and y as found in Equation 3.1. In addition, more
detailed statistics can be added to the three terms in order to provide more
accurate information to each term. For example, better resource utilization
can be tracked and included in the y term. As the Adaptive Resource
Scheduler was only run in simulation, work could be done to evaluate
performance in a test Grid environment to improve Equation 3.1.
Matchmaking considerations such as OS, Architecture, and libraries can be
included into the scheduling decision. In a more dynamic environment, it
may be that the resource history term becomes much more important as it
gauges the performance history of the resources better than allocated and
estimated completion times.
Currently, the Adaptive Resource Scheduler only makes a
scheduling determination on one job at a time. As jobs enter the scheduler,
they are evaluated and scheduled in the order they are received. This
means that jobs are evaluated on a First Come First Serve basis, even
though there may be many jobs waiting to be scheduled. The algorithm
should be modified to include multiple jobs, such that a job arriving later
may be scheduled first in order to minimize average job turnaround time
and/or makespan.
48


APPENDIX A
ResourceList Class
// File: ResourceList.java
// Date: 2007-10-24
//
// Copyright (C) 2007, Brian Wise
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later
// version.
//
// This library is distributed in the hope that it will be
// useful, but WITHOUT ANY WARRANTY; without even the implied
// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
// PURPOSE. See the GNU Lesser General Public License for more
// details.
//
// You should have received a copy of the GNU Lesser General
// Public License along with this library; if not, write to the
// Free Software Foundation, Inc., 59 Temple Place, Suite 330,
// Boston, MA 02111-1307 USA
//
//----------------------------
//
// This file defines the ResourceList class, which has a
// private class, OrderlD, which implements a Comparator
// Define us as part of the gridsched package
package gridsched;
// Import namespaces
import gridsched.*;
import java.util.*;
import gridsim.*;
// ResourceList is simply an extension of LinkedList that
// keeps track of resources. We implement our own comparator
// in order to sort the list by resource ID. Since GridSim
// is multi-threaded, it is possible for resources to register
// to the GIS in different orders on different runs. We need
// to be able to have them in the same order always for our
// comparisions.
49


public class ResourceList extends LinkedList
{
// Just call base constructor
public ResourceList()
{
super();
}
// Sorts the Gridlets in a list based on the ID.
public void sortID()
{
Collections.sort(this, new OrderID() );
}
// Private class that implements Comparator and sorts based
// on the resource ID.
private class OrderlD implements Comparator
{
public OrderlD()
{
super();
}
// Compare function. a and b should not be null. This
// will throw a ClassCastException as we need to cast to
// a ResourceCharacteristic to grab the resource ID.
public int compare(Object a, Object b)
throws ClassCastException
{
Integer jla = new Integer(
((ResourceCharacteristics) a).getResourcelD() );
Integer jib = new Integer(
((ResourceCharacteristics) b).getResourcelD() );
return jla.compareTo(jib);
)
}
}
50


APPENDIX B
gridScheduler Class
// File: gridScheduler.java
// Date: 2007-10-24
//
// Copyright (C) 2007, Brian Wise
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later
// version.
//
// This library is distributed in the hope that it will be
// useful, but WITHOUT ANY WARRANTY; without even the implied
// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
// PURPOSE. See the GNU Lesser General Public License for more
// details.
//
// You should have received a copy of the GNU Lesser General
// Public License along with this library; if not, write to the
// Free Software Foundation, Inc., 59 Temple Place, Suite 330,
// Boston, MA 02111-1307 USA
//
//----------------------------
//
// This file defines the gridScheduler class, which handles
// scheduling of Gridlets to Resources. The enum schedulePolicy
// is defined in this class, which determines the scheduling
// policy to be used. In addition, a private class that the
// Adaptive Resource Scheduler uses to keep track of resource
// history is included.
// Define us as part of the gridsched package
package gridsched;
// Import namespaces
import gridsched.*;
import java.util.*;
import java.lang.Math;
import java.io.*;
import gridsim.*;
import eduni.simjava.*;
51


// This is the main gridScheduler class. It needs to extend
// GridSim so that it can implement the body() function which
// is called at the start of simulation. This currently is set
// up to handle one grid user, and changes will be required if
// multiple grid users are to be supported,
public class gridScheduler extends GridSim
{
// Variable definitions
// This needs to be updated if a new scheduling method is
// implemented
public enum schedulePolicy { ROUNDROBIN, FIRSTAVAILABLE,
RANDOM, ADAPTIVE } ;
// State of configuration scheduling policy, and how many
// resources are present.
private schedulePolicy currentPolicy_;
private int totalResource_;
// Verbose level
private int verbLevel_;
// Our ID and name (corresponds to a grid user id)
private Integer ID_;
private String name_;
// For adaptive scheduler, the alpha and beta values
private double adapAlpha;
private double adapBeta;
// History of gamma values used for reporting,
private LinkedList gammaHistory;
private final double minGamma=0.10;
// Keeps track of how many updates we receive while
// scheduling.
private int runningUpdates;
// Gridlet list to process
private GridletList list_;
// Received Gridlets from Resources
private GridletList receiveList_;
// List of resources
private ResourceList resList_;
// Used for printing to separate sections
private final String sectionSep =
52


// Constructor. Uses the name, baud_rate super call,
public gridScheduler(String name, double baud_rate, int tRes)
throws Exception
{
// Call our base constructor
super(name, baud_rate);
II Set our values
this.name_ = name;
this.ID_ = new Integer( getEntityld(name) );
this.totalResource_ = tRes;
// Also, set a default policy and create the receiveList_
currentPolicy_ = schedulePolicy.ROUNDROBIN;
receiveList_ = new GridletList();
// Create resource list and gamma history list
resList_ = new ResourceList();
gammaHistory = new LinkedList();
// Set default values for configuration variables
verbLevel_ = 0;
runningUpdates=0;
adapAlpha=l.0;
adapBeta=l.0;
// Returns the gamma history. Each time gamma is used
// it is added to this list for reporting purposes,
public LinkedList getGammaHistory()
{
return gammaHistory;
// Returns the number of gridlets we received while scheduling
// gridlets. After all scheduling is done, any received
// gridlets are not added to this count,
public int getRunningUpdates()
{
return runningUpdates;
}
// Sets the verbosity level. Greater numbers mean more
// output. Currently this goes from 0-2
public void setVerbLevel(int vLevel)
{
verbLevel_ = vLevel;
}
53


// Returns the resources used during the experiment. This
// is helpful for reporting and statistics,
public ResourceList getResourceList()
t
return resList_;
}
// Sets a new scheduling policy
public void setSchedulePolicy(schedulePolicy newPolicy)
{
currentPolicy_ = newPolicy;
}
// Returns the current scheduling policy
public schedulePolicy getSchedulePolicy()
{
return currentPolicy_;
}
// Sets the values for alpha and beta in the Adaptive
// Resource Scheduler.
public void setAdaptiveValues(double alpha, double beta)
{
adapAlpha = alpha;
adapBeta = beta;
}
// Sets the gridlet list (job list)
public void setGridletList(GridletList list)
{
list = list;
// Returns the current girdlet list (job list)
public GridletList getGridletList()
{
return list_;
}
// Returns the gridlet return list, which contains the
// job results.
public GridletList getReturnList()
{
return receiveList_;
}
// Returns the ID
public Integer getID()
{
return ID ;
54


}
// Round robin scheduler. This does not wait for any
// results, nor consult with the resource prior to scheduling
// It simply goes through the gridlet list, scheduling in
// a round robin fashion,
private void roundRobinO
{
// Local variables
Gridlet gridlet;
String info;
int currentResource=0;
ResourceCharacteristics resChar;
// a loop to get one Gridlet at one time and sends it to
// a grid resource entity. Then waits for a reply
for(int i=0; i {
// Loop to beginning if we fell off the end.
if(currentResource>=totalResource_)
{
currentResource=0;
}
// Get resource characteristics. Used for printing
// and we need the ID, not the position in the
// resource list
resChar = (ResourceCharacteristics)resList_.get(
currentResource);
// Get next gridlet to be scheduled and set its arrival
// time.
gridlet = (Gridlet) this.list_.get(i);
setGridletSubmissionTime(i);
// Debug printing
if(verbLevel_>2)
{
info = "Gridlet_" + gridlet.getGridletID();
System.out.printf("Sending %s to %s with id = %d\n",
info, resChar.getResourceName(),
resChar.getResourcelD());
)
// And submit the gridlet after setting the time that
// it left the gridScheduler
gridlet. setLocalSubmissionTime (clock () )
super.gridletSubmit(gridlet, resChar.getResourcelD());
}
55


// Loop to receive all jobs. Simply receive, print out
// debug if needed, and add to the receive list
for(int i=0; i {
gridlet = super.gridletReceive();
if(verbLevel_>2)
{
System.out.printf("Receiving Gridlet %d\n",
gridlet.getGridletID());
}
this.receiveList_.add(gridlet);
}
} // End Round Robin scheduler
// Random scheduler. This is a very simple scheduler that
// just loops through the gridlet list and assigns each
// gridlet to a random resource. Uses the same seed so that
// multiple runs produce the same output. We need this so
// our comparisons are valid,
private void randomScheduler()
{
// Local variables
Gridlet gridlet;
String info;
int schedTo=0;
ResourceCharacteristics resChar;
// Ensure that we get the same random numbers... We really
// want to just randomize once so that multiple runs can
//be compared.
long seed = 11L*13*17*19*23+1;
Random random = new Random(seed);
// a loop to get one Gridlet at one time and sends it to
// a grid resource entity. Then waits for a reply
for(int i=0; icthis.list_.size(); i++)
{
int randomlnt = Math.abs(random.nextInt());
schedTo = randomlnt % this.totalResource_;
gridlet = (Gridlet) this.list_.get(i);
setGridletSubmissionTime(i);
info = "Gridlet_" + gridlet.getGridletID();
resChar = (ResourceCharacteristics)resList_.get(
schedTo);
// Debug if needed
if(verbLevel >2)
56


{
System.out.printf("Sending %s to %s with id = %d\n",
info, resChar.getResourceName(),
resChar.getResourcelD());
}
// Schedule it, after setting departure time
gridlet.setLocalSubmissionTime(clock()) ;
super.gridletSubmit(gridlet, resChar.getResourcelD());
// Now receive all results. Prints debug if needed and
// adds them to the receive list.
for(int i=0; i {
gridlet = super.gridletReceive();
if(verbLevel_>2)
{
System.out.printf("Receiving Gridlet %d\n",
gridlet.getGridletID()) ;
}
this.receiveList_.add(gridlet) ;
}
} // End of random scheduler
// First available scheduler,
private void firstAvailable()
{
// Local variables.
Gridlet gridlet;
ResourceCharacteristics resChar;
String info;
int availResource = -1;
int resPEList[] = new int[totalResource_];
int busyPEList[] = new int[totalResource_] ;
long seed = 11L*13*17*19*23+1;
Random arrive = new Random(seed);
// Loop through all the gridlets. We may end up receiving
// completed gridlets in this loop as we need to send
// requests to resources for available PEs...
for(int i=0; icthis.list_.size(); i++)
{
// Ok, we need to find the first available
while(availResource<0)
{
Object o;
57


// Send a request to each resource asking for
// available PEs
for(int j=0; j {
// Set this to invalid as we need to keep j
// constant until we hear back about the free
// PE. This is because we may have several
// completed gridlets in the queue before
// getting to the response about num PE...
resPEList[j] = -1;
resChar = (ResourceCharacteristics)
resList_.get(j);
super.send(resChar.getResourceID(),
GridSimTags.SCHEDULE_NOW,
GridSimTags.RESOURCE_NUM_FREE_PE,
this.ID_);
// Again, we may get multiple things back...
while(resPEList[j] < 0)
{
0 = super.receiveEventObject();
if(o instanceof Integer)
{
resPEList[j] = ((Integer)o).intValue();
}
else if(o instanceof Gridlet)
{
// Recieve the gridlet and update stats
this.receiveList_.add((Gridlet)o);
runningUpdates++;
1
else
{
// Print if verbose...
if(verbLevel_>0)
{
System.out.printf("Shouldn't be here, +
"but we got an object '%s' and +
" we wanted an Integer or +
"Gridlet...\n",
o.getClass().getName());
}
}
// If there is more than 0 free PE, then we found
// an availalbe resource
if(resPEList[j] > 0)
{
58


availResource=j ;
break;
}
}
// This was set to -1 at the start, so if we did not
// find a free PE, this will still be 0
if(availResourcecO)
{
super.gridSimHold(1.0); // hold by 1 second
}
//At this point, we have the resource we want to
// schedule to. So get the gridlet and set submission
// time
gridlet = (Gridlet) this.list_.get(i);
setGridletSubmissionTime(i);
info = "Gridlet_" + gridlet.getGridletID();
resChar = (ResourceCharacteristics)resList_. get(
availResource);
// Debug
if(verbLevel_>2)
{
System.out.printf("Sending %s to %s with id = %d\n",
info, resChar.getResourceName() ,
resChar.getResourcelD());
// We check the status of the schedule here, and if
// verbosity level is high we print it.
gridlet.setLocalSubmissfonTime(clock()) ;
if(super.gridletSubmit(gridlet, resChar.getResourcelD() ,
GridSimTags.SCHEDULE_NOW, true))
{
if(verbLevel_>2)
{
System.out.printf("Scheduled OK.\n");
}
}
else
{
if(verbLevel_>2)
{
System.out.printf("Not scheduled 0K.\n");
)
59


// Ok, now reset this so we find the next available
// resource.
availResource=-l ;
}
// At this point we have scheduled all available gridlets.
// There is at least one, and possibly all, gridlets still
// outstanding. We know how many we haev received and how
// many we had, so we loop that many times to receive all
// outstanding gridlets
while(this.receiveList_.size() < this.list_.size())
{
gridlet = super.gridletReceive();
if(verbLevel_>2)
{
System.out.printf("Receiving Gridlet %d\n",
gridlet.getGridletID()) ;
}
this.receiveList_.add(gridlet);
}
} // End first available
// Class that holds resource history. This is used by the
// Adaptive Resource Scheduler. Everything is public rather
// than access each variable through a method,
private class resHist
{
// Default that initializes to 0
public resHist()
{
mipsRating = 0;
scheduled = 0.0;
completedJobs =0;
completedMI = 0;
public int completedJobs;
public int mipsRating;
public double scheduled;
public double completedMI;
public String name;
// The resource history was done as a hash for the following
// reason: No matter what, all resources need to be
// examined for scheduling decisions (basically, we need to
// pull performance and unfinished MI that has been allocated
// and put it through our scheduling function). However, the
60


// hash is much quicker for updating performance because we
// know the resource id that a job was completed from (there
// is no job migration between resources). So rather than
// loop through the resource history twice, we only loop
// through once. However, investigation should be done to see
// how much of a hit is taken by getting an Iterator. If it
// is much worse than a for() over an array, then an array
// should be used. During the run we will always get the
// resource history values more than we will update them.
// Adaptive Resource Scheduler
private void adaptive!)
{
// Local variables
int schedTo=0; // Resource we are going to sched to
int totalComp=0; // Total completed jobs
double newMI=0.0; // MI of job to be scheduled
double gamma=0.0;
double start = clock(); // Starts off at current time
Gridlet gridlet;
Iterator reslter; // Iterator to go through resources
Sim_event ev; // Need this to select on a simjava event
Sim_type_p tag =
new Sim_type_p(GridSimTags.GRIDLET_RETURN);
// Default of 16 entries 75% is ok
HashMap resMap = new HashMap();
// First we need to get the MIPS rating for each resource.
// We would do better to get it per PE, but unfortunately
// the local scheduler decides where to allocate the jobs,
for (int i=0; i {
resHist newHist = new resHist () ;
ResourceCharacteristics rChar =
(ResourceCharacteristics)resList_.get(i);
newHist.mipsRating = rChar.getMIPSRating();
newHist.name = rChar.getResourceName();
resMap.put(new Integer(rChar.getResourcelD()) newHist);
}
// Ok, loop through all the gridlets...
for(int i=0; icthis.list_.size(); i++)
{
// First, set the submission time. This may advance the
// simulation if the arrival time of the gridlet is in
61


// the future.
setGridletSubmissionTime(i);
// Update the counters, and we need to see if there is
// a gridlet in the return queue. sim_select doesn't
// block, which is nice,
do {
ev = new Sim_event();
super.sim_select(tag, ev); // Tag is GRIDLET_RETURN
if(ev.get_data() != null &&
(ev.get_data() instanceof Gridlet))
{
// Get the gridlet (we are now receiving it),
// add it to the receive list, and update the
// MI executing on the resource and stats
Gridlet myg = (Gridlet)ev.get_data();
resHist myrh = (resHist)(resMap.get(
new Integer(myg.getResourcelD())));
this.receiveList_.add(myg);
double rem = myg.getGridletLength();
myrh.scheduled -= rem;
myrh.completedJobs++;
runningUpdates++;
}
} while(ev.get_data() != null &&
(ev.get_data() instanceof Gridlet));
// Now get the current job and its length
gridlet = (Gridlet) this.list_.get(i);
newMI = gridlet.getGridletLength();
// The next step is to calculate gamma. Gamma will
// be 0 if 1 or more resources have not returned a
// result. Also, we check against minGamma and set
// gamma to 0 if it is not >= minGamma...
// Start off assuming we will use gamma. If any
II check fails, it turns this off...
boolean useGamma = true;
totalComp=0;
// Loop through all resources
reslter = (resMap.keySet()).iterator();
while(reslter.hasNext ())
{
int key = ((Integer)reslter.next()).intValue();
int comp = ((resHist)resMap.get(
new Integer(key))).completedJobs;
// If there are no completed jobs, we dont use gamma
62


if(comp<=0)
{
useGamma=false;
break;
}
totalComp += comp;
}
II If we need to use gamma, and i != 0, then calculate.
// Technically, the first job we find (i=0), should
// never allow useGamma to be set. But just sanity
// check this since we are dividing by the number of
// jobs prior to the current one.. .
if(useGamma && i!=0)
{
gamma = (double)totalComp/(double)(i);
if(gamma gamma = 0.0; // Again, if it doesn't meet min
}
// Ok, look through the resources and get the values
// and plug them into the scheduling function. Set
// the best score to MAX since we are looking for the
// minimum possible score. Also, in our experiment,
// we use the time range of start to current for
// the current jobs. This means that we only need
// to find out what outstanding MI are on each
// resource since it will be in the time frame,
double bestScore = Double.MAX_VALUE;
reslter = (resMap.keySet()).iterator();
while(reslter.hasNext())
{
int key = ((Integer)reslter.next()).intValue();
int mips = ((resHist)resMap.get(
new Integer(key))).mipsRating;
double sched = ((resHist)resMap.get(
new Integer(key))).scheduled;
// Call the adap function which returns a score.
// If the score is lower than the best score, then
// we select this resource. The alpha and beta
// values, which are required by the function, are
// class variables so do not need to be passed
// in...
double score = adapFunc(mips, sched, newMI, gamma,
clock()-start,
((resHist)resMap.get(
new Integer(key))).completedMI) ;
if(scoreebestScore)
63


{
schedTo = key;
bestScore = score;
}
}
// If we use gamma, add it to the list...
i f(gamma>=minGamma)
{
gammaHistory.add(new Double(gamma));
}
// Debug
if(verbLevel_>2)
{
System.out.printf("Sending Gridlet_%s to %s +
"with id = %d\n",
gridlet.getGridletID(),
((resHist)(resMap.get(new Integer(schedTo)))).name,
schedTo);
}
// Need to update the numbers as we are going to be
// scheduling more MI to a resource...
resHist myrh = (resHist)(resMap.get(
new Integer(schedTo)));
myrh.scheduled += newMI;
// Finally, submit the gridlet after setting when it
// leaves the global scheduler,
gridlet.setLocalSubmissionTime(clock());
super.gridletSubmit(gridlet, schedTo);
)
// Ok, at this point we have scheduled all gridlets. We
// may also have received some of them due to the
// sim_select. We know how many we have back, and so
// we need to loop waiting for the rest to get back...
while(this.receiveList_.size() < this.list_.size())
{
gridlet = super.gridletReceive();
if(verbLevel_>2)
{
System.out.printf("Receiving Gridlet %d\n" +
gridlet.getGridletID());
)
// stores the received Gridlet into the receive list
this.receiveList_.add(gridlet);
64


} // End of Adaptive Resource Scheduler
// mips MIPS rating for the RESOURCE (note we don't know
// per machine)
// sched allocated MI to this resource (so should be
// running now)
// newMI MI of the job to be scheduled
// gamma Value of gamma. If this is 0 then the gamma term
// is not even calculated
// deltaT time delta - the top part of the gamma term
// compMI Completed MI of this resource
private double adapFunc(int mips, double sched, double newMI,
double gamma, double deltaT,
double compMI)
{
double retVal=0.0;
// Enforce some requirements of the equation. If we have
// sched or newMI==0, then the result is 0. Which is not
// what we want (newMI really shouldn't be 0 though).
// Also, no division by 0...
if (schedcl.0)
sched = 1.0;
if(mips==0)
mips = 1; // Just make it low (don't want div by 0)
if (newMKl. 0)
newMI = 1.0;
if(gamma<0 || gamma>l)
gamma=0.0;
if(compMI<=0)
compMI=l;
// Calculate the first two terms based on what was passed
// in. These are always used, no matter if we have data
// back from the resources...
retVal = ((adapAlpha*(sched/mips))+adapBeta*(newMI/mips));
// The adaptive algorithm will pass us either 0, or a
// number between 0-1. It already decided to use the
// adaptive part of this formula based on the value of
// gamma and if there was enough data. We also validated
// this is 0<=gamma<=l...
if(gamma>0)
{
retVal += gamma*(deltaT/compMI);
}
return retVal;
}
65


// This is the core of the gridScheduler class. It is called
//by the GridSim framework when the simulation starts. The
// job of this is to ensure that the resources are registered
// and then call a scheduling algorithm,
public void body()
{
// Local variables
LinkedList resList;
ResourceCharacteristics resChar;
// waiting to get list of resources. Since GridSim
// package uses multi-threaded environment, your request
// might arrive earlier before one or more grid resource
// entities manage to register themselves to
// GridlnformationService (GIS) entity.
// Therefore, it's better to wait in the first place
while(true)
{
// need to pause for a while to wait GridResources
// finish registering to GIS
super.gridSimHold(1.0); // hold by 1 second
// Just wait until the resource list is = expected
// number of resources.
resList = super.getGridResourceList() ;
if(resList.size() == this.totalResource_)
{
break;
}
else
{
if(verbLevel_>0)
{
System.out.printf("Waiting to get list of +
"resources...\n");
>
}
}
// Now that we know we have all resources registered,
// we need to get their characteristics. These are used
//by the scheduling methods.
for(int i=0; icthis.totalResource_; i++)
{
// Resource list contains list of resource IDs not
// grid resource objects.
int resourcelD = ( (Integer)resList.get(i) ).intValue();
// Requests to resource entity to send its
// characteristics
66


super.send(resourcelD, GridSimTags.SCHEDULE_NOW,
GridSimTags.RESOURCE_CHARACTERISTICS,
this.ID_);
// waiting to get a resource characteristics
resChar = (ResourceCharacteristics)
super.receiveEventObj ect();
resList_.add(resChar);
if(verbLevel_>l)
{
System.out.printf("Received ResourceCharacteristics
+ "from %s, with id = %d (%d)\n",
resChar.getResourceName(), resourcelD,
resChar.getResourcelD());
// Sort these so that they are always in the same order
// (due to threading they may arrive in different orders
// during different runs). These need to be in order so
// comparisons can be made between runs.
resList_.sortID();
if(verbLevel_>l)
{
System.out.printf("\n%s\n", sectionSep);
}
for(int i=0; i {
resChar = (ResourceCharacteristics) resList_.get(i);
if(verbLevel_>l)
{
printResourceChar(resChar);
}
}
System.out.printf("\n");
// Here is where we call the scheduling policy...
switch(currentPolicy_)
{
case ROUNDROBIN:
roundRobin();
break;
case FIRSTAVAILABLE:
firstAvailable();
break;
case RANDOM:
randomScheduler();
67


break;
case ADAPTIVE:
adaptive();
break;
default:
roundRobin();
break;
}
// After the scheduler finishes, we need to shut down the
// Grid entity...
super.shutdownGridStatisticsEntity();
super.shutdownUserEntity();
super.terminatelOEntities();
} // End of body()
//We set the gridlet submission time, using the
// setGridSubmissionTime(subTime) method in Gridlet. We
// *may* sleep in this function, depending on if we the
// submission time is in the future. If it is in the
// future, we will sleep until that time and mark the
// submission time.
private void setGridletSubmissionTime(int num)
{
// This shouldn't happen, but if it does we would throw
//an ArrayOutOfBounds exception. So just check it
// in case...
if(num<0)
{
return;
}
// Gets the gridlet from our list
Gridlet gridlet = (Gridlet) this.list_.get(num);
// If i==0, then submission time is current time,
if(num==0)
{
gridlet.setGridSubmissionTime(clock()) ;
}
else
{
// Otherwise, we need to see if we should sleep. The
// gridlet should arrive at
// previous.getGridSubmissionTime() +
// current.getArrivalDelta(). This may be in the
// future. If it is, then we need to gridSimHold ()
// until then. Otherwise, we just set the time to
// what it should be.
Gridlet pGrid = (Gridlet) this.list_.get(num-1);
68


double curTime = clock ();
double prevSub = pGrid.getGridSubmissionTime();
double delta = gridlet.getArrivalDelta();
if(curTime < prevSub+delta)
{
// hold until time gridlet is actually here
super.gridSimHold((prevSub+delta)-curTime);
}
// Make sure that this is set right since we are
// messin around with time...
gridlet.setGridSubmissionTime(prevSub+delta) ;
}
} // End of setGridletSubmissionTime
// Simply prints the resource characteristics.
// Used for debugging
private void printResourceChar(ResourceCharacteristics r)
{
MachineList mList;
Machine m;
System.out.printf("%s (%d)\n", r.getResourceName(),
r. getResourcelD());
System.out.printf("%s %s %.lf\n", r.getResourceArch(),
r.getResourceOS(),
r.getResourceTimeZone());
System.out.printf{"Cost per second: %.lf\n",
r.getCostPerSec());
System.out.printf("Allocation policy: %d\n",
r.getResourceAllocationPolicy() ) ;
System.out.printf("Total PEs: %d (MIPS Rating of %d)\n",
r.getNumPE(), r.getMIPSRating());
mList = r.getMachineList();
for(int i=0; i {
m = mList.getMachine(i);
System.out.printf(" %d (MIPS rating %d), %d PEs ",
m.getMachinelD(), m.getMIPSRating() ,
m. getNumPE());
System.out.printf("(Free: %d, Busy: %d)\n",
m. getNumFreePE(), m.getNumBusyPE());
}
System.out.printf("%s\n", sectionSep);
) // End of printResourceChar
} // end class
69


APPENDIX C
Gridtest Class
// File: Gridtest.java
// Date: 2007-10-24
//
// Copyright (C) 2007, Brian Wise
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later
// version.
//
// This library is distributed in the hope that it will be
// useful, but WITHOUT ANY WARRANTY; without even the implied
// warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
// PURPOSE. See the GNU Lesser General Public License for more
// details.
//
// You should have received a copy of the GNU Lesser General
// Public License along with this library; if not, write to the
// Free Software Foundation, Inc., 59 Temple Place, Suite 330,
// Boston, MA 02111-1307 USA
//
//----------------------------
//
// This is the class file that runs tests using the
// gridScheduler class. It contains the Gridtest class,
// which is responsible for creating the grid environment,
// setting values, and starting the simulation. It will also
// print out the results when done.
// Imports
import java.util.*;
import java.io.*;
import gridsim.*;
import gridsched.*;
// Main class
class Gridtest
{
// Class variables
private static int resIDList[];
private static int totalResource;
70


private static ResourceList resList_;
private final static String sectionSep =
M___________________________________________ __ II ,
/
private static String statFile =
private static String verString = "1.0 (Beta)";
private static String resName[];
// These are the defaults. They can be passed in via
// arguments, though this needs work as there is not much
// input validation. See the printUsage() method for a
// description.
// Adaptive algorithm alpha value
private static double adapAlpha = 1.0;
// Adaptive algorithm beta value
private static double adapBeta = 1.0;
private static int inFile = 500; // InFile size
private static int outFile = 500; // OutFile size
// Selected scheduler (see printUsage())
private static int selSched = 0;
private static int totalJobs = 1000; // Total jobs to run
private static int verbLevel =0; // Verbosity level
private static long jobSize = 1000000; // Job size in MI
// Maximum submission
private static double maxSubmissionDelay = 5.0;
// Constructor
Gridtest()
{
// Don't need to do anything here
// userlD is the user id of the user. Should be set to the
// ID of the gridScheduler.
// maxDelay is the maximum delay between submissions of
// gridlets (0 maxDelay)
// baselnFile is the base for input file size.
// Range is .5*base to 1.5*base
// baseOutFile is the base for output file size.
// Range is .5*base to 1.5*base
// baseMISize is the base for the size of the gridlet.
// Range is .5*base to 1.5*base
// numGridlets is the number of gridlets that should be
// created.
// startJobID is the start ID of the job. Each job must have
// its own job ID.
71


private static GridletList createGridlet(int userlD,
double maxDelay, int baselnFile, int baseOutFile,
long baseMISize, int numGridlets, int startJobID)
{
// Creates a container to store Gridlets
GridletList list = new GridletList(};
// Local variables
double length = 0;
double delay = 0;
long file_size = 0;
long output_size = 0;
long seed = 11L*13*17*19*23+1;
// Different Random numbers
Random rndSize = new Random(seed);
Random rndArrive = new Random(seed);
Random rndSrc = new Random(seed);
Random rndlnFile = new Random(seed);
Random rndOutFile = new Random(seed);
int randomlnt;
int source;
System.out.printf("\nCreating Jobs (Gridlets)...\n");
if(verbLevel>2)
{
System.out.printf ("%s\n", sectionSep);
}
for(int i=startJobID; i {
// Get our values using random classes...
delay = GridSimRandom.real(maxDelay, 1.0, 0.0,
rndArrive.nextDouble());
randomlnt = Math.abs(rndSrc.nextlnt());
source = randomlnt % totalResource;
length = GridSimRandom.real(baseMISize, 0.50, 0.50,
rndSize.nextDouble() ) ;
file_size = (long) GridSimRandom.real(baselnFile, 0.50,
0.50, rndlnFile.nextDouble());
output_size = (long) GridSimRandom.real(baseOutFile,
0.50, 0.50, rndOutFile.nextDouble());
Gridlet newGridlet = new Gridlet(i, length, file_size,
output_size);
newGridlet.setUserlD(userlD);
newGridlet.setSubmittedSitelD(resIDList[source]);
newGridlet.setNumPE(1);
if(i==0)
{
// For the first job, there is no delay...
72


newGridlet.setArrivalDelta(0);
)
else
{
newGridlet.setArrivalDelta(delay);
}
list.add(newGridlet);
if(verbLevel>2)
{
System.out.printf("Creating job %2d (%10.2f +
"%4d %4d %3.2f)\n", i, length, file_size,
output_size, delay);
}
}
if(verbLevel>2)
{
System.out.printf("%s\n", sectionSep);
return list;
} // End of createGridlet
// Main function
public static void main(String[] args)
{
// Variables
GridletList list_;
GridletList receiveList_;
gridScheduler myScheduler_ = null;
// See if we need to change any of the parameters...
// Note that this sets class variables...
parseArguments(args);
// Print out some stuff if verbose option was given
if(verbLevel>0)
{
System.out.printf("\n") ;
System.out.printf("Values of configurable options:\n");
System.out.printf(" inFile: %d\n", inFile);
System.out.printf(" outFile: %d\n", outFile);
System.out.printf(" jobSize: %d\n", jobSize);
System.out.printf(" maxSubmissionDelay: %f\n",
maxSubmissionDelay);
System.out.printf(" verbLevel: %d\n", verbLevel);
System.out.printf(" statFile: %s'\n", statFile);
System.out.printf(" Scheduler: ");
switch(selSched)
{
case 0:
73


System.out.printf("'Round Robin'\n");
break;
case 1:
System.out.printf("'Random'\n");
break;
case 2:
System.out.printf("* First Available'\n");
break;
case 3:
System.out.printf("'Adaptive Algorithm' (alpha +
%.4f, beta %.4f)\n", adapAlpha,
adapBeta);
break;
case 4:
System.out.printf("'Cost Broker'\n");
break;
default:
System.out.printf("**UNKNOWN**\n");
}
}
// Print starting message
System.out.printf("\nStarting Gridtest\n");
// This gets enclosed in a big try block. This is
// somewhat left over from messing around based on the
// GridSim examples, and can probably be moved to more
// specific locations where Exceptions are actually
// thrown,
try
{
int num_user =1; // number of grid users
totalResource = 5;
Calendar calendar = Calendar.getlnstance();
boolean trace_flag = false; // trace GridSim events
// list of files or processing names to be excluded
// from any statistical measures
String[] exclude_from_file = { "" };
String[] exclude_from_processing = { "" };
// Don't write a report...
String report_name = null;
// Initialize the GridSim package. This MUST be
// done first
System.out.printf("Initializing GridSim package\n");
GridSim.init(num_user, calendar, trace_flag,
exclude_from_file, exclude_from_processing,
report_name);
74


// We need to get the list of ResourcelDs so that when
// we create the gridlet list we can assign what
// resource they are coining from.
resIDList = new int[totalResource];
resName = new String[totalResource];
// Creates GridResource objects
createGridResources();
// Create a gridScheduler using an ID and baud rate
// (and num res)
myScheduler_ = new gridScheduler("Gridtest", 560.00,
totalResource);
myScheduler_.setVerbLevel(verbLevel);
// Set the correct scheduler.
// TODO: Maybe replace the enums with ints.
switch(selSched)
{
case 1:
myScheduler_.setSchedulePolicy(
gridScheduler.schedulePolicy.RANDOM);
break;
case 2:
myScheduler_.setSchedulePolicy(
gridScheduler.schedulePolicy.FIRSTAVAILABLE)
break;
case 3:
myScheduler_.setSchedulePolicy(
gridScheduler.schedulePolicy.ADAPTIVE);
myScheduler_.setAdaptiveValues(
adapAlpha, adapBeta);
break;
case 0:
default:
myScheduler_.setSchedulePolicy(
gridScheduler.schedulePolicy.ROUNDROBIN);
System.out.printf("Current policy = +
myScheduler_.getSchedulePolicy());
// Create our gridlet list and assign it to the
// scheduler
list_ = createGridlet(myScheduler_.getID().intValue(),
maxSubmissionDelay, inFile, outFile, jobSize,
totalJobs, 0);
// Below is how you would add more jobs with different
75


// characterstics. Note how you need to keep track of
// the start job ID (totalJobs=1000)
// list_.addAll(createGridlet(
// myScheduler_.getID().intValue(), 50.0,
// 500, 500, 750000, 3000, 1000));
//list_.addAll(createGridlet(
// myScheduler_.getID().intValue(), 10.0,
// 500, 500, 3000000, 2000, 4000));
// Set the gridlet list in the scheduler
myScheduler_.setGridletList(list_);
// Start the simulation
GridSim.startGridSimulation();
// Prints the Gridlets when simulation is over
GridletList newList = null;
newList = myScheduler_.getReturnList();
resList_ = myScheduler_.getResourceList();
printGridletList(newList, myScheduler_);
System.out.printf("Finish Gridtest\n\n");
System.out.printf("Youre dead, Zeta Leader.\n\n");
}
catch(Exception e)
{
e.printStackTrace() ;
System.out.printf("Error Occurred during processing\n");
System.out.printf("TODO: Track errors better...\n");
}
} // End of main()
// Simply prints usage
private static void printUsage()
{
printVersion();
System.out.printf("\n");
System,out.printf("Usage:\n");
System.out.printf("\n");
System.out.printf("java Gridtest [options]\n");
System.out.printf("\n");
System.out.printf("Where [options] are optional and one +
"of:\n");
System.out.printf(" -a : sets alpha in +
"Adaptive Algorithm (0-1)\n");
System.out.printf(" -b : sets beta in +
"Adaptive Algorithm (0-1)\n");
System.out.printf(" -d : is the +
76


System.out.
System.out.
System.out,
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
System.out
"submission delay (float)\n");
.printf(" -f : is the stat +
"file to save to\n");
.printf(" -h help : Print this usage +
"and exit\n");
.printf(" -i : is the inFile +
"size (int)\n");
,printf(" -j : is the job +
"size (int)\n");
.printf(" -o : is the +
"outFile size (int)\n");
.printf(" -s : is an int +
"which specifies the scheduler:\n");
0 - Round RobinXn");
1 - Random\n");
2 - First AvailableXn")
3 - Adaptive +
.printf ("
.printf("
.printf("
printf("
"Algorithm\n");
.printf(" -v : Prints verbose +
"output. If this is given\n");
.printf (" multiple times, it +
"increases the level.\n");
.printf(" -V version : Prints version and +
"exits\n");
.printf("\n");
printf("If the stat file (-f option) exists, "
"it will be APPENDED to.\n);
.printf("\n");
.printf("The format of the stat file +
"(-f option) is a CSV with the\n");
.printf("following fields (in order):\n");
.printf(" Scheduler\n");
.printf(" t (inter-arrival time)\n");
.printf(" p (Server Utilization)\n");
.printf(" u (Mean service rate per server)\n")
.printf(" 1 (mean arrival rate)\n");
.printf(" Makespan\n");
.printf(" Queue time\n");
.printf(" Total Job Time\n");
.printf(" Average Job Time\n");
.printf(" Gridlets received while +
"scheduling\n");
.printf(" Times Gamma used (only non-zero +
"for Adaptive)\n");
} // End printUsage
// Prints out the version
private static void printVersion()
{
77


System.out.printf("Gridtest: Version + verString + "\n")
// Parses the arguments. Pretty simple and doesn't error
// check much...
private static void parseArguments(String[] args)
{
// This is some quick and dirty command line processing.
// If this is to be released, this should be cleaned up
//to validate input better...
for(int i=0; i {
// Can't use a switch for strings... This is also
// quick and dirty and we don't support partial
// length or GNU-style long args.
if(args[i].equals("-a")) // Set alpha value
{
i++; // Advance to the next argument
if(i>=args.length)
(
System.out.printf("\nERROR:\n");
System.out.printf(" -a MUST be supplied +
"a value.\n");
System.exit(3);
}
try
{
adapAlpha = Float.parseFloat(args[i]);
}
catch(NumberFormatException in)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" Cannot convert '%s' +
"to a float.\n", args[i]);
System.out.printf(" -a flag MUST be passed +
"a float.\n");
System.exit(1);
}
if(adapAlpha<0 M adapAlpha>l)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" Alpha (-a flag) must be +
"between 0 and l.\n");
System.exit(1);
}
}
else if(args[i].equals("-b")) // Set beta value
{
i++; // Advance to the next argument
if(i>=args.length)
78


{
System.out.printf("\nERROR:\n");
System.out.printf(" -b MUST be supplied a +
"value.\n");
System.exit ( 3) ;
}
try
{
adapBeta = Float.parseFloat(args[i]);
}
catch(NumberFormatException in)
{
System.out.printf("\n**ERROR:\n") ;
System.out.printf(" Cannot convert '%s' to +
"a float.\n", args[i]);
System.out.printf(" -b flag MUST be passed a +
"float.\n);
System.exit(1);
}
if(adapBeta<0 || adapBeta>l)
{
System.out.printf("\n**ERROR:\n") ;
System.out.printf(" Beta (-b flag) must be +
"between 0 and l.\n");
System.exit (1) ;
}
}
else if(args[i].equals("-d")) // Set maxSubmissionDelay
{
i++; // Advance to the next argument
if(i>=args.length)
{
System.out.printf("\nERROR:\n") ;
System.out.printf(" -d MUST be supplied a +
"value.\n");
System.exit (3);
try
{
maxSubmissionDelay = Float.parseFloat(args[i]);
}
catch(NumberFormatException in)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" Cannot convert '%s' to +
"a float.\n", args[i]);
System.out.printf(" -d flag MUST be passed a +
"float.\n");
System.exit(1);
}
79


if(maxSubmissionDelay<0)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" Delay (-d flag) must +
"be >= 0.\n");
System.exit(1) ;
}
}
else if(args[i].equals("-f")) // Output file name
{
i++; // Increment this must be followed by file name
if(i>=args.length)
{
System.out.printf("\nERROR:\n") ;
System.out.printf(" -f MUST be supplied a +
"value.\n") ;
System.exit(3);
}
statFile = args[i]; // Again, need better validation
)
else if(args[i].equals("-h") ||
args[i].equals("help"))
{
System.out.printf("\n");
printUsage();
System.exit(0);
}
else if(args[i].equals("-i")) // Infile size
{
i++; // Advance to the next argument
if(i>=args.length)
{
System.out.printf("\nERROR:\n");
System.out.printf(" -i MUST be supplied a +
"value.\n");
System.exit(3);
)
try
{
inFile = Integer.parselnt(args[i]);
}
catch(NumberFormatException in)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" Cannot convert '%s' to +
"an integer.\n", args[i]);
System.out.printf(" -i flag MUST be passed +
"an integer.\n");
System.exit(1);
}
80


if(inFile<0)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" inFile (-i flag) must +
"be >= 0.\n");
System.exit(1);
}
}
else if(args[i].equals("-j")) // Job size
{
i++; // Advance to the next argument
if(i>=args.length)
{
System.out.printf("\nERROR:\n") ;
System.out.printf(" -j MUST be supplied +
"a value.\n");
System.exit(3);
}
try
{
jobSize = Integer.parselnt(args[i]) ;
}
catch(NumberFormatException in)
{
System.out.printf("\n* *ERROR:\n");
System.out.printf(" Cannot convert '%s' to +
"an integer.\n", args[i]);
System.out.printf(" -j flag MUST be passed +
"an integer.\n");
System.exit(1);
}
if(jobSize<0)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" Job size (-j flag) must +
"be >= 0.\n");
System.exit (1) ;
}
}
else if(args[i].equals("-o")) // Output file size
{
i++; // Advance to the next argument
if(i>=args.length)
{
System.out.printf("\nERROR:\n");
System.out.printf(" -o MUST be supplied +
"a value.\n");
System.exit(3);
}
try
81


{
outFile = Integer.parselnt(args[i]);
}
catch(NumberFormatException in)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" Cannot convert '%s' to +
"an integer.\n", args[i]);
System.out.printf(" -o flag MUST be passed +
"an integer.\n");
System.exit(1);
}
if (outFile<0)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" outFile (-o flag) must +
"be >= 0.\n");
System.exit(1);
}
}
else if(args[i].equals("-s")) // Scheduler selection
{
i++; // Advance to the next argument
if(i>=args.length)
{
System.out.printf("\nERROR:\n");
System.out.printf(" -s MUST be supplied a +
"value.\n");
System.exit(3);
}
try
{
selSched = Integer.parselnt(args[i]);
}
catch(NumberFormatException in)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" Cannot convert '%s' to +
"an integer.\n", args[i]);
System.out.printf(" -s flag MUST be passed +
"an integer.\n");
System.exit(1);
}
// This should be handled better...
if(selSched>3 || selSchedcO)
{
System.out.printf("\n**ERROR:\n");
System.out.printf(" %s is not a valid +
"scheduler choice.\n", args[i])
System.out.printf(" Please see the help +
82


"(-h flag) for valid +
"choices.\n");
System.exit(3);
}
}
else if(args[i].equals("-v"))
{
verbLevel++;
)
else if(args[i].equals("-V") ||
args[i].equals("version"))
{
System.out.printf("\n") ;
printVersion();
System.exit(0);
}
else
{
System.out.printf("\n**ERROR: Option '%s' is +
"not valid.\n\n", args[i]);
printUsage();
System.exit(2);
}
}
} // End of parseArguments
// Creates a single resource given the passed parameters
private static void createResource(int num, int PErating,
int numPE, String arch, String os, int numMachine,
double cost, double tz)
{
// Local variables
long seed = 11L*13*17*19*23+1;
MachineList mList;
GridResource gridRes = null;
ResourceCharacteristics resource;
LinkedList Weekends = new LinkedList();
LinkedList Holidays = new LinkedList();
// Create the machines
mList = new MachineList();
for(int i=0; icnumMachine; i++)
{
// Machines are PEs, so create the PE list
PEList peList = new PEListO;
for(int j=0; j {
peList.add(new PE(j,PErating));
}
83


mList. add (new Machined, peList));
}
// Create the resource characteristics
resource = new ResourceCharacteristics(arch, os, mList,
ResourceCharacteristics.SPACE_SHARED, tz, cost);
// And make the resource...
try
{
gridRes = new GridResource("Resource_" + num 100.0,
seed, resource, 0.0, 0.0, 0.0, Weekends,
Holidays);
resName[num] = "Resource_" + num;
}
catch (Exception e)
{
e.printStackTrace();
}
resIDList[num] = gridRes.get_id();
if(verbLevel>0)
{
System.out.printf("Created Resource_%d (%d): %d +
"machines with %d PEs each, %d MIPS rating +
"per PE\n", num, resIDList[num], numMachine,
numPE, PErating);
System.out.printf(" - %s %s, %.lf timezone, cost +
"of %.lf\n", arch, os, tz,
cost);
}
} // End createResource
// Creates our resources. These are:
// Resource 1: 5 machines with 2 PEs each, 200 MIPS rating
// - Intel Linux, -7.0 timezone, cost of 10.0
// Resource 2: 7 machines with 1 PE each, 350 MIPS rating
// - Intel Windows, -8.0 timezone, cost of 5.0
// Resource 3: 3 machines with 4 PEs each, 100 MIPS rating
// - Sparc Solaris, -5.0 timezone, cost of 15.0
// Resource 4: 1 machine with 8 PEs, 200 MIPS rating
// - Intel Linux, -6.0 timezone, cost of 12.0
// Resource 5: 10 machines with 1 PE each, 500 MIPS rating
// - Intel Solaris, -8.0 timezone, cost of 14.0
private static void createGridResources()
{
// This could be stored better...
int PErating[] = { 200, 350, 100, 200, 500 };
int numPE[] ={2, 1, 4, 8, 1);
String arch[] = { "Intel", "Intel", "Sparc", "Intel",
84


"Intel" };
String os[] = { "Linux", "Windows", "Solaris",
"Linux", "Solaris" };
int numMachine[] = { 5, 7, 3, 1, 10 };
double cost[] = { 10.0, 5.0, 15.0, 12.0, 14.0 };
double tz[] = { -7.0, -8.0, -5.0, -6.0, -8.0 };
System.out.printf("\nCreating resources...\n");
if(verbLevel>0)
{
System.out.printf("%s\n", sectionSep);
}
for(int i=0; i {
createResource (i, PErating[i], numPE[-i], arch[i],
os[i], numMachine[i], cost[i], tz[i]);
}
if(verbLevel>0)
{
// Print a space after all the resources (makes
// output easier to read)
System.out.printf("%s\n\n", sectionSep);
}
} // End createGridResources
// Debug for printing resource characteristics
private static void printResourceChar(
ResourceCharacteristics r)
{
MachineList mList;
Machine m;
System.out.printf("%s (%d)\n", r.getResourceName(),
r.getResourcelD());
System.out.printf("%s %s %.lf\n", r.getResourceArch(),
r.getResourceOS(), r.getResourceTimeZone());
System.out.printf("Cost per second: %.lf\n",
r.getCostPerSec());
System.out.printf("Allocation policy: %d\n",
r.getResourceAllocationPolicy());
System.out.printf("Total PEs: %d (MIPS Rating of %d)\n",
r.getNumPE(), r.getMIPSRating());
mList = r.getMachineList();
for(int i=0; icmList.size(); i++)
{
m = mList.getMachine(i);
System.out.printf(" %d (MIPS rating %d), %d PEs ",
m.getMachinelD(), m.getMIPSRating(),
m.getNumPE());
System.out.printf("(Free: %d, Busy: %d)\n",
85


m.getNumFreePE(), m.getNumBusyPE());
}
System.out.printf("%s\n", sectionSep);
// Prints the gridlet list after it comes back. It requires
// the gridScheduler to get a bit of information...
private static void printGridletList(GridletList list,
gridScheduler gs) throws IOException
{
// Lots of local variables
int numGridlets = list.size();
int totalMachines = 0;
double totalTime = 0;
double allTotalTime = 0;
double g_time = 0;
double g_submission = 0;
double g_finish = 0;
double l_time = 0;
double l_submission = 0;
double l_finish = 0;
double l_execstart = 0;
double lowestSubmission = Double.MAX_VALUE;
double highestFinish = Double.MIN_VALUE;
double makespan =0;
int resID = 0;
int numRes = 0;
double g_q = 0;
long l_s = 0;
long l_q = 0;
long l_w = 0;
double allTotalArrivalDelay = 0.0;
double allTotalProcessingTime = 0.0;
double allGlobalQueue = 0.0;
double allLocalQueue = 0.0;
Gridlet gridlet;
int gammaUsed=0;
int runningUpdates=0;
// The below are used for the stats.
double t;
double p;
double u;
double 1;
// First we sort this so gridlets are in order by ID
list.sortID();
numRes = resList .size();
86


for(int i=0; i {
ResourceCharacteristics rChar =
(ResourceCharacteristics) resList_.get(i);
// Each PE counts as a machine, due to the way the
// scheduler ONLY schedules to one PE on the local
// resource. If this changes in the core of GridSim,
// then this code would need to be updated to reflect
// those changes...
totalMachines += rChar.getNumPE();
// Set these to 0 in case they were not (since we
// just accumulate below)
rChar.setGridletsScheduled(0);
rChar.setTotalProcessingTime(0);
if(verbLevel>l)
{
System.out.printf("\n");
System.out.printf("======'==== OUTPUT ==========\n");
System.out.printf(" Job | STATUS I Res | submit I +
" finish | total | g_q | l_s | l_q +
" | 1__w \n") ;
System.out .printf ( "-------------------------------" +
1 _____ ___________________________II _|_
If
}
+\n");
for(int i = 0; i < numGridlets; i++)
{
gridlet = (Gridlet) list.get(i);
if(verbLevel>l)
{
System.out.printf("%4d I ", gridlet.getGridletID());
if(gridlet.getGridletStatus() == Gridlet.SUCCESS)
{
System.out.print("SUCCESS I ") ;
}
else
{
System.out.print("FAILURE I ");
}
}
// Get and calculate numbers...
87


allTotalArrivalDelay += gridlet.getArrivalDelta();
resID = gridlet.getResourcelD();
l_submission = gridlet.getSubmissionTime();
l_finish = gridlet.getFinishTime();
l_execstart = gridlet.getExecStartTime();
l_time = l_finish l_submission;
g_submission = gridlet.getGridSubmissionTime();
g_finish = gridlet.getLocalSubmissionTime();
g_time = g_finish g_submission;
totalTime = l_finish g_submission;
l_q = (long)(l_execstart l_submission);
l_s = (long)(l_finish l_execstart);
l_w = (long)(l_finish l_submission);
allGlobalQueue += g_time;
allLocalQueue += l_q;
// Need to set this in the resource list
for(int j=0; j {
ResourceCharacteristics rChar =
(ResourceCharacteristics)resList_.get(j);
if(resID == rChar.getResourcelD())
{
rChar.addGridletsScheduled(1);
rChar.addTotalProcessingTime(l_finish-l_execstart);
break;
}
}
if(verbLevel>l)
{
System.out.printf("%3d | %7d | %7d | %7d | %7d | +
"%7d | %7d | %7d |\n", resID,
(long)g_submission, (long)l_finish,
(long)totalTime, (long)g_time, l_s, l_q, l_w);
}
allTotalTime += totalTime;
if(g_submission < lowestSubmission)
{
lowestSubmission = g_submission;
}
if(l_finish > highestFinish)
{
highestFinish = l_finish;
}
88


if(verbLevel>l)
{
System, out .printf ( "-----------------------------------" +
__________________________________________________ _|.
// Calculate service rate per server
for(int i=0; i {
ResourceCharacteristics rChar =
(ResourceCharacteristics)resList_.get(i);
allTotalProcessingTime += rChar.getTotalProcessingTime()
}
// calculate these
makespan = highestFinish lowestSubmission;
t = 1/(numGridlets/allTotalArrivalDelay);
u = numGridlets/(allTotalProcessingTime/totalMachines);
p = (numGridlets/allTotalArrivalDelay)/(totalMachines*u);
1 = numGridlets/allTotalArrivalDelay;
System.out.printf("\n");
System.out.printf("%s\n", sectionSep);
System.out.printf("\n");
if(gs != null)
{
runningUpdates = gs.getRunningUpdates();
System.out.printf("Scheduling policy: %s\n",
gs.getSchedulePolicy());
System.out.printf(" Updates processed while +
"scheduling: %d\n", runningUpdates);
if (gs.getSchedulePolicy() ==
gridScheduler.schedulePolicy.ADAPTIVE)
{
double minGamma=0.0;
double maxGamma=0.0;
double totGamma=0.0;
double avgGamma=0.0;
LinkedList gh = new LinkedList();
gh = gs.getGammaHistory();
gammaUsed=gh.size();
System.out.printf(" Alpha: %.4f\n", adapAlpha);
System.out.printf(" Beta: %.4f\n", adapBeta);
System, out .printf (" Gamma: %d total [ ", gh.sizeO)
if(gh.size()>0)
minGamma=maxGamma=totGamma=(Double)gh.get(0);
for(int i=l; i {
totGamma += (Double)gh.get(i);
89


i f ( (Double) gh. get (i) CirtinGamma)
minGamma = (Double)gh.get(i);
i f((Double)gh.get(i)>maxGamma)
maxGamma = (Double)gh.get(i);
}
if(gh.size()>0)
avgGamma = totGamma/gh.size();
System.out.printf("min: %f max: %f avg: %f]\n",
minGamma, maxGamma, avgGamma);
}
}
System.out.printf("c (number of servers): %d\n",
totalMachines);
System.out.printf("u (mean service rate per server): +
"%.8f jobs/second\n", u);
System.out.printf("1 (mean arrival rate of jobs): %.4f "
"jobs/second\n", 1);
System.out.printf("p (server utilization 1/cu): +
"%.6f\n", p);
System.out.printf("t (interarrival time for jobs): +
"%.4f seconds\n\n", t);
System.out.printf("Jobs allocated to resources +
"(total %d):\n", numGridlets);
for(int i=0; KnumRes; i++)
{
ResourceCharacteristics rChar =
(ResourceCharacteristics)resList_.get(i);
System.out.printf(" H> %s (%2d): %4d (%6.2f%%)\n",
rChar.getResourceName(), rChar.getResourcelD(),
rChar.getGridletsScheduled(),
((float)rChar.getGridletsScheduled() /
(float)numGridlets)*100);
System.out.printf(" | +-> %,.2f spent busy, +
"%.2f%% of the time.Xn",
rChar.getTotalProcessingTime(),
((rChar.getTotalProcessingTime() /
(double)rChar.getNumPE())/makespan)*100);
+
System.out.printf("\nTotal time spent in Global queue: +
"%,.2f (%,.2f per job)\n", allGlobalQueue,
(allGlobalQueue/totalMachines));
System.out.printf("Total time spent in Local queues: +
"%,.2f (%,.2f per job)\n", allLocalQueue,
(allLocalQueue/totalMachines));
System.out.printf("Total time of all jobs: %,.2f\n",
allTotalTime);
System.out.printf("Average job length: %,.2f\n",
allTotalTime/numGridlets);
System.out.printf("Makespan: %,.2f (%,.2f %,.2f)\n\n",
makespan, highestFinish, lowestSubmission);
90


// If we were passed a stat file, we need to append the
// CSV values to the end of it... See the printUsageO
// method for the fields that are printed
if(!statFile.equals(""))
{
FileWriter fw = null;
try
{
fw = new FileWriter(statFile, true);
String line =
if(gs != null)
{
line = String.format("%s,%.4f,%.6f, %.8f, %.4f, "
"%.2f,%.2f,%.2f,%.2f,%d,%d\n",
gs.getSchedulePolicy(), t, p, u, 1,
makespan, allGlobalQueue+allLocalQueue,
allTotalTime, allTotalTime/numGridlets,
runningUpdates, gammaUsed);
}
else
{
line = String.format("BROKER,%.4f, %.6f, %.8f, "
"%.4f,%.2f,%.2f,%.2f,%.2f\n", t, p, u, 1
makespan, allGlobalQueue+allLocalQueue,
allTotalTime, allTotalTime/numGridlets);
}
fw.write(line, 0, line.length());
}
finally
{
if(fw != null)
{
fw.close ();
}
}
} // end printGridletList
} // end class


REFERENCES
[1] Foster, I., Kesselman, C., and Tuecke, S. "The Anatomy of the Grid:
Enabling Scalable Virtual Organizations. Inti J. Supercomputer
Applications. 15, no. 3 (2001): 1-27.
[2] Fujimoto, N., and Hagihara, K. A Comparison among Grid Scheduling
Algorithms for Independent Coarse-Grained Tasks. Proceedings of the
2004 International Symposium on Applications and the Internet Workshops.
674-680. 2004.
[3] Subramani, V., Kettimuthu, R., Srinivasan, S., and Sadayappan, P.
Distributed Job Scheduling on Computational Grids using Multiple
Simultaneous Requests." Proceedings of the 11th IEEE International
Symposium on High Performance Distributed Computing. 359-366. 2002.
[4] Abawajy, J. Fault-Tolerant Scheduling Policy for Grid Computing
Systems. Proceedings of the 1&h International Parallel and Distributed
Processing Symposium. 238-244. 2004.
[5] Zhang, L. Scheduling Algorithm for Real-Time Applications in a Grid
Environment." Proceedings of the 2002 IEEE Conference on Systems, Man,
and Cybernetics. 6-11. 2002.
[6] Wu, M., and Sun, X. Memory Conscious Task Partition and Scheduling
in Grid Environments. Proceedings of the 5th IEEE/ACM International
Workshop on Grid Computing. 674-680. 2004.
[7] Spooner, D., Jarvis, S., Cao, J., Saini, S., and Nudd, G. Local Grid
scheduling techniques using performance prediction. IEE Proceedings
Computer and Digital Techniques. 150, no. 2 (2003): 87-96.
[8] Wiriyaprasit, S., and Muangsin, V. The Impact of Local Priority Policies
on Grid Scheduling Performance and an Adaptive Policy-based Grid
Scheduling Algorithm." Proceedings of the Seventh International
Conference on High Performance Computing and Grid in Asia Pacific
Region. 343-346. 2004.
92