Information Technology Journal

Year: 2008 | Volume: 7 | Issue: 8 | Page No.: 1176-1181
DOI: 10.3923/itj.2008.1176.1181

QPS_{Max-Min<>Min-Min}: A QoS Based Predictive Max-Min, Min-Min Switcher Algorithm for Job Scheduling in a Grid

M. Singh and P.K. Suri

Abstract: This study present a QoS based predictive Max-Min, Min-Min Switcher (QPS_{Max-Min<>Min-Min}) algorithm for scheduling jobs in a grid. The algorithm makes an appropriate selection among the QoS based Max-Min or QoS based Min-Min algorithm on the basis of heuristic applied, before scheduling the next job. The effect on the execution time of grid jobs due to non-dedicated property of resources has also been considered. The algorithm uses the history information about the execution of jobs to predict the performance of non-dedicated resources. Simulation demonstrates that (QPS_{Max-Min<>Min-Min}) outweighs the traditional QoS guided algorithms a lot in makespan.

Keywords: Job scheduling, QoS, makespan and grid computing

INTRODUCTION

A computational grid is a hardware and software infrastructure that provides dependable, consistent, pervasive and inexpensive access to high-end computational capabilities. Grid computing enables the sharing and aggregation of geographically distributed resources and support wide-area distributed computing (Foster and Kesselman, 2001; Singh and Sari, 2007). As a heterogeneous computing system, the job scheduling strategy directly influences the performance of grid applications, so one of the major research objectives in grid job scheduling is to devise new and efficient methods for improving computational efficiency. Reduction in makespan is one of the fundamental objectives of optimizing job scheduling problems in distributed heterogeneous computing systems. The problem of optimally scheduling large, diverse groups of jobs onto machines of a distributed heterogeneous computing environment has been shown to be NP-complete.

In grid environment, it is desirable to compete for the best QoS provided by resources to fulfill job constraints. The scheduler in grid needs to consider jobs and QoS constraint to get a better match between jobs and resources. The algorithm, based on job requirement of QoS (Shan et al., 2003; Dong et al., 2006), classifies jobs into two categories: high QoS-requiring jobs and low-QoS requiring jobs and schedules the two separately. It enhances the adaptability of scheduling algorithm to take QoS to some extent. Although the grid is aiming at coordinated resource sharing, this sharing is often conditional: resource owner make resources available, subject to constrain on when, where and what can be done (Martinovic and Budin, 2004). The grid scheduler places the jobs submitted by grid user in a job queue and later on maps these jobs over suitable resources to make them run. A grid resource usually contains many jobs on it, including the grid jobs and the resource owner`s local jobs. The local scheduler may schedule all these jobs in a parallel manner, which makes an impact on the execution time of grid jobs. So, the grid job scheduling can hardly promise the realization of its target. This study present a QoS based predictive max-min, min-min switcher (QPS_{Max-Min<>Min-Min}) algorithm for scheduling jobs in a grid. The proposed algorithm makes an appropriate selection among the QoS based min-min or QoS based max-min algorithm on the basis of heuristic applied, before scheduling the next job. The effect on the execution time of grid jobs due to non-dedicated resources has been reduced by using the history information about the execution of jobs to predict the performance of non-dedicated resources. Makespan is used as a bi-criterion for job scheduling with QoS consideration.

QoS BASED GRID SCHEDULING MODEL

QoS is an extensive concept. It is used differently based on its context while applying it to a resource (Daniel and Casalicchio, 2004). For instance, QoS for a network means the desirable bandwidth for the application, QoS for a computing-intensive jobs means the operation speed. We have used QoS parameter as network bandwidth (Plestys et al., 2007). A job with high QoS request can only be executed on a resource providing high quality of service (Ligang and Stephan, 2004). The traditional algorithms (Munir et al., 2007; (Jinnquan et al., 2005) may lead to a scenario where jobs with no special QoS requirement may be allotted to resources with high QoS guarantee. To overcome this drawback, modification has been made into the traditional Min-Min and Max-Min algorithms.

Scheduling model for QoS based Max-Min and Min-Min: Let J = {j₁, j₂,..., j_k} is a set of jobs to be scheduled on M = {m₁, m₂,..., m_k} list of machines. The job set J is further partitioned in two sets: J^h (jobs with high QoS requests) and J^l (jobs with low QoS requests). The expected execution time E_ij is defined as the amount of time taken by machine m_j to execute job j_i, when there is no load on m_j. Let C_ij represents the expected completion time of job j_i on m_j and R_j refers to the ready time of machine m_j. The makespan of the schedule is .

QoS guided Min-Min begins with the set J^h of all unassigned jobs. It has two phases: In the first phase, the set of minimum expected completion time for each job in J^h is found. In the second phase, the job with overall minimum expected completion time from J^h is chosen and assigned to the corresponding machine. Then this job is removed from J^h and process is repeated until all jobs in J^h are mapped. After finishing the mapping of all jobs with high QoS request, the algorithm repeats the same procedure for mapping the jobs with low QoS request of set J^l. The pseudo code of the algorithm follows:

QoS based max-min is similar to QoS based min-min, except in phase 2. Max-min assigns job with maximum expected completion time to the corresponding machine in phase 2. An example to illustrate the execution of QoS based min-min and max-min heuristic is given below. The expected execution time of 10 jobs on 5 machines are shown in Table 1. In Table 1 X denotes that the machine does not have the capability to perform that particular job due to its low QoS provision. Figure 1 shows the results for QoS min-min with makespan equal to 27.4 while Fig. 2 shows the result for QoS max-Min with makespan equal to 28.4.

Model for QoS based max-min, min-min switcher algorithm: The idea behind min-min (Wu et al., 2000) is to assign the jobs to the resources that will execute them fastest and in case of max-min (Maheswaran et al., 1999) the idea is to overlap the long-running jobs with the short-running ones.

For example, if there is a long job, max-min will execute many short jobs in parallel with the long job, however, min-min will execute short jobs in parallel and long job will follow the short job. The proposed scheduling algorithm selects the best algorithm between QoS max-min and QoS min-min according to the length of jobs while making each scheduling decision. Jobs with high QoS request are mapped first and after finishing the mapping of such jobs, it maps the jobs with low QoS requests. The pseudo code of QS_{Max-Min<>Min-Min} (QoS based max-min, min-min switcher) algorithm follows:

The algorithm selects between the two conventional algorithms, max-min and min-min, whenever one acts better than the other on the basis of SD of minimum completion time of unassigned jobs. A search is made to find a position in sorted list (on the basis of completion time) where, the difference between the completion times of two successive jobs is more than SD. It is a place where a big increase in length of jobs had occurred. If this position is in first half of list, it shows that the number of long jobs is more than the number of short jobs i.e., a situation where min-min outperforms max-min, so min-min is selected by mapping the first job of sorted list on corresponding machine. If this position is in second half, it means the number of short jobs is more than the number of long jobs i.e., a situation where max-min outperforms min-min, so max-min is selected by assigning the last job of sorted list. If this position does not exist then SD is compared with a threshold value. If SD is less than threshold, it means length of jobs are in small range, so min-min is selected. Otherwise, Max-Min is selected for assigning the next job.

The result of QS_{Max-Min<>Min-Min} algorithm corresponding to Table 1 is shown in Fig. 3 and the makespan is 26.4.

APPLYING PREDICTIVE SCHEDULING MECHANISM TO QS_{Max-Min<>Min-Min}

A grid resource usually contains many jobs on it, including the grid jobs and the resource owner`s local jobs. The local scheduler may schedule all these jobs in a parallel manner which makes an impact on the execution time of grid jobs. It is unpractical to expect the machines in a grid to be dedicated. Due to the simultaneous execution of local jobs, the actual execution time of grid jobs usually increases. If the scheduler does not know this change, it will persist on the former schedule, which leads to an increase in makespan. In continuation with the earlier example, let Table 2 shows the actual execution time of 10 jobs on the same 5 machines. Figure 4 shows the scenario of QS_{Max-Min<>Min-Min} scheduling, where scheduler persists on former schedule and the makespan is 33.5.

Although, such change in the execution time of jobs is unavoidable due to site autonomy (Akl and Dong, 2006), if the scheduling strategy can predict in advance, a better schedule will be made. So, QS_{Max-Min<>Min-Min} algorithm is modified by adding a predictive scheduling mechanism to it, in which every expected execution time is treated as a random variable rather than a predetermined constant. By estimating the value of each random variable, the scheduler can make a better schedule, which takes into account the actual status of resources (Gong et al., 2002). The random variable PE_ij is predicted from past observations. The relation between PE_ij and E_ij can be expressed as:

where, θ_ij is the additional amount of time needed by machine m_j to finish job j_i caused by the execution of local jobs and other grid jobs. Let . Suppose before job j_i is assigned to machine m_j, it has already executed n jobs. θ_ij can be predicted as:

where, X_u is the weight of θ_uj.

After estimating θ_ij, we can obtain Pe_ij and PR_j as:

where, t stands for the No. of grid jobs that machine m_j allow running simultaneously. QS_{Max-Min<>Min-Min} algorithm is modified after substituting the predicted values of C_ij, E_ij and R_j as PC_ij, PE_ij and PR_j to produce QoS based predictive max-min, min-min switcher (QPS_{Max-Min<>Min-Min}). QoS based max-min and QoS based min-min algorithms are modified in the same way to produce QP_Max-Min and QP_Min-Min algorithms.

SIMULATION AND RESULTS

A simulation program is implemented in java to evaluate the performance of QPS_{Max-Min<>Min-Min}, running on a Pentium 4 1.73 GHz laptop_. In order to compare the performance of QPS_{Max-Min<>Min-Min} with QS_{Max-Min<>Min-Min} algorithm, the predicted value of 10 jobs on the same 5 machines is generated and recorded in Table 3 for the previous problem.

Figure 5 shows the scenario of QPS_{Max-Min<>Min-Min} scheduling, where scheduler has already predicted the change in completion time of jobs leading to a new schedule and the makespan is 29.2.

The performance of QPS_{Max-Min<>Min-Min} is also compared with QoS guided Min-Min and QoS based Max-Min (generating schedule on non-dedicated machines with prediction). The PTC (Predicted Time to Compute) matrices containing the predicted execution time of 50 (|j^h| = 30, |J^l| = 20), 100 (|J^h| = 75, | J^l| = 25), 150 (|J^h| = 110, |J^l| = 40), 200 (J^h|| = 120, |J^l| = 80) jobs on 10 machines are generated to make a comparison among these heuristic algorithms. The expected execution time of jobs varies from 1 to 50. The heuristic with shortest makespan is declared the best heuristic to perform job scheduling in grid. As shown in Fig. 6, the QPS_{Max-Min<>Min-Min} out performs the conventional scheduling algorithms. In conclusion, the proposed algorithm by exploiting the merits of QoS based min-min and max-min along with prediction scheduling mechanism leads to significant performance gain for a variety of jobs having different QoS requirements.

CONCLUSION

Job scheduling is one of the important problem to be solved in grid computing. In this study, a novel scheduling algorithm is presented which merges the efficiency of max-min along with min-min and also considers both QoS and non-dedicated property of grid resources. A simulation system was developed to test the proposed algorithm and the simulation results show that QPS_{Max-Min<>Min-Min} algorithm outperforms the traditional heuristics. The future work will focus on job scheduling with multi-dimensional QoS and extend the proposed scheduling algorithm in a real grid.

REFERENCES