Two Approaches of Workflow Scheduling with QoS in the Grid

1. Introduction

The development of Grid infrastructures, for example, Condor DAGMan (DAGMan), Grid Flow (Cao, 2003) and Pegasus (Deelman, 2004), now enables workflow to be submitted and executed on remote computational resources. To harness the non-trivial power of Grid resources, effective task scheduling approaches are necessary. Typically, there are two ways to map a set of tasks to a set of resources: dynamic scheduling and static scheduling. The dynamic approach makes a schedule at real time when a task is ready, while the static approach makes a schedule by planning in advance based on available information on resources and tasks. Because of its advantage of “planning ahead”, a static scheduler can produce a schedule that overlaps communication time and computational time. Therefore, the makespan can be reduced. It can even achieve a near optimal schedule for some complex scientific workflows involving a larger number of computational tasks and data communications (Wieczorek, 2005). However, unlike dynamic scheduling, the static approach relies heavily on accurate resource and task information to make a schedule. Unfortunately, the performance of Grid resources is hard to accurately predict. The difficulty is due to the following facts. First, Grid resources are not dedicated to one particular Grid user. Resources’ local management policies and competition from other users may make the performance acquired by a user fluctuate. Second, existing Grid resources may fail without a notice and new Grid resources may join the resource pool; both cases will change the available performance for users.

In order to benefit from the merits of static scheduling for complex workflows in the Grid, new performance prediction and modeling methods are introduced. The differences of the presentation of stochastic performance information (e.g., deterministic vs. non-deterministic) influence the way that scheduling algorithms can take to meet QoS requirements.

The rescheduling approach (Yu, 2007; Sakellarion, 2004) can modify an initial schedule according to the fluctuation of resource performance at the run-time. This approach needs to first make an initial schedule and in order to make such an initial schedule, the algorithm usually relies on performance prediction mechanisms (McGough, 2005) to acquire the estimated performance that the tasks will get when they are running on the resources. This predicted performance is usually given as a deterministically specific value, although this value might not be the exact performance that the application will archive at the run-time. For example, the approach that will be introduced in this chapter uses the PFAS algorithm (Dong, 2007) to get an initial schedule and the PFAS algorithm needs information on resource performance in different time slots. Fig. 1 presents an example of the fluctuation of available performance in different time slots.

Fig. 1:

Performance fluctuation resulted from advance 
reservation on a resource along time