An Adaptive Scheduler Framework for Complex Workflow Jobs on Grid Systems

An Adaptive Scheduler Framework for Complex Workflow Jobs on Grid Systems

G. M. Siddesh (Jawaharlal Nehru Technological University, Hyderabad, India) and K. G. Srinisas (Department of Computer Science & Engineering, M S Ramaiah Institute of Technology, Bangalore, India)
Copyright: © 2012 |Pages: 17
DOI: 10.4018/jdst.2012100106
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Grid Computing provides sharing of geographically distributed resources among large scale complex applications. Due to dynamic nature of resources in grid, there is a need of highly efficient job scheduling and resource management policies in grid. A novel Grid Resource Scheduler (GRS) is proposed to effectively utilize the available resources in Grid. Proposed GRS contributes, an optimal job scheduling algorithm on Job Rank-Backfilling policy and a resource matching algorithm based on ranking of resources with best fit allocation model. Performance of GRS is measured by considering a web based BLAST algorithm – a bioinformatics application. GRS aims in reducing; Makespan of the job workflow, execution time of varied size jobs, response time of the submitted jobs and overhead of using the system. It also considers improving the utilization factor and throughput of the available heterogeneous resources in grid. The experimental results prove that proposed grid scheduler framework performs better when evaluated against widely used First Come First Serve (FCFS), Shortest Job First (SJF) and Minimum Time to Due Date (MTTD) scheduling strategies.
Article Preview

Introduction

In recent years increasing number of parallel computers has become a part of Grid computing (Gridfourm, http://www.gridfourm.org). Grid computing enables the sharing, selection, and aggregation of geographically distributed heterogeneous resources, such as computational clusters, supercomputers, storage devices, and scientific instruments. These resources are under control of different Grid sites and being utilized to solve many important scientific, engineering, and business problems (Rahman, Ranjan, & Buyya, 2010). These sites participate in grid computing by providing resources with its own set of policies. A grid enables sharing, scheduling and coordination of distributed resources, managing these geographically distributed heterogeneous resources is a challenging task. Scheduling in grid systems is a challenging task, as it involves coordinating multiple computational sites for resource sharing and scheduling in an efficient manner (Viswanathan, Veeravalli, & Robertazzi, 2007). To accomplish this task an effective grid scheduling strategy is required. Grid scheduling is defined as the process of making scheduling decisions involving resources over multiple administrative domains. This process can include searching multiple administrative domains to use a single machine or scheduling a single job to use multiple resources at a single site or multiple sites (Schopf, 2003). The management and scheduling system generates job schedules for each resource in the grid by taking static restrictions and dynamic parameters of jobs and resources into consideration. Usually a grid resource broker is responsible for management of jobs and resources, the scheduling task normally distributes the jobs among the different sites resources and the need to coordinate the grid with the underlying scheduling policy which has already been defined (Rodero, Guim, & Corbalan, 2009). Resource brokers abstract the complexity of grids by transforming user requirements in to set of jobs that are scheduled on the appropriate resources, managing them and collecting results when they are finished (Garg, Buyya, & Siegel, 2010). Scheduling infrastructure can be classified in to centralized scheduling, Hierarchical scheduling and Decentralized scheduling. In centralized scheduling decisions are taken by the centralized server, this kind of scheduling is efficient because of the central instance has all necessary information on the available resources. This scheduling is useful at a computing center where all resources are under one objective. In hierarchical scheduling centralized scheduler is responsible for scheduling jobs, in addition every machine uses separate scheduler for local scheduling. The main advantage of hierarchical scheduling is different policies can be applied for global and local scheduling. In decentralized scheduling, distributed schedulers interact with each other and submits jobs to remote resource. This approach provides better fault tolerance and reliability (Hamscher, Schwiegelshohn, Streit, & Yahyapour, 2000). Scheduling consists of Job scheduling and resource allocation algorithms. Job scheduling is selection of jobs for scheduling to the resources based on different approaches like; First-Come-First-Serve (FCFS), Smallest Job First (SJF), Largest Job First (LJF), Minimum Time to Due Date (MTTD), Backfilling. Resource allocation is done based on different approaches like; Biggest free, Random, Best fit, Exact match. To make an effective grid computing possible a decentralized and cooperative Grid Resource scheduler (GRS) is proposed in this paper. The main contribution of this paper includes:

  • Decentralized and cooperative approach in scheduling.

  • Job scheduling algorithm by ranking the jobs.

  • Resource provision algorithm by ranking the resources.

  • Job-Resource matching approach.

  • Evaluated on an BLAST workflow application.

  • Various performance metrics like makespan, execution time, response time, resource utilization, throughput and overhead factors are considered.

  • An comparison study of proposed GRS with FCFS, SJF, MTTD with biggest free policy.

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing