Performability-Based Workflow Scheduling in Grids. (10th January 2018)

• Record Type: Journal Article
• Authors: Entezari-Maleki, Reza; Trivedi, Kishor S; Sousa, Leonel; Movaghar, Ali
• Editors: Berenbrink, Petra
• Is Part Of: Computer journal. Volume 61:Number 10(2018)
• Page Start: 1479
• Page End: 1495
• Publication Date: 2018-01-10
• Subjects: performability -- grid computing -- stochastic reward net -- universal generating function -- task scheduling; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxx125
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: In this paper, the performance of a grid resource is modeled and evaluated using stochastic reward nets (SRNs), wherein the failure–repair behavior of its processors is taken into account. The proposed SRN is used to compute the blocking probability and service time of a resource for two different types of tasks: grid and local tasks. After modeling a grid resource and evaluating the performability measures, an algorithm is presented to find the probability mass function (pmf) of the service time of the grid resource for a program which is composed of grid tasks. The proposed algorithm exploits the universal generating function to find the pmf of service time of a single grid resource for a given program. Therefore, it can be used to compute the pmf of the service time of entire grid environment for a workflow with several dependent programs. Each possible scheduling of programs on grid resources may result in different service times and successful execution probabilities. Due to this fact, a genetic-based scheduling algorithm is proposed to appropriately dispatch programs of a workflow application to the resources distributed within a grid computing environment. Numerical results obtained by applying the proposed SRN model, the algorithm to find the pmf of grid service time, and the genetic-based scheduling algorithm to a comprehensive case study demonstrate the applicability of the proposed approach to real systems.