Novel Backfilling Technique with Deadlock Avoidance and Migration for Grid workflow Scheduling

摘要

The objective of this research is to develop a task scheduling algorithm for grid services with improved resource utilization, fault tolerance capability and to avoid deadlocks. The algorithm simulated using GridSim toolkit, which is used to measure the effectiveness of scheduling and related algorithms in grid environments with reduced complexity than the real implementation. Two advanced methods, Two Phase Commit Protocol with novel back filling Technique (TPCNBF) and Two Phase Commit Protocol with novel back filling technique and task migration (TPCNBFM) were developed to schedule the tasks. The backfilling technique is used to improve resource utilization and fault tolerance in job scheduling. Two phase commit protocol prevents deadlocks in task scheduling. Fault tolerance in task scheduling is improved by task migration to protect tasks from any resource failure. TPCNBF and TPCNBFM methods give higher performance improvement than the current method called Cost Driven Work Flow Scheduling (CDWFS). In this method, the scheduling is based on deadline and the resource status. The experimental results showed that the TPCNBF and TPCNBFM have less makespan, cost, high success rate and throughput. The new algorithm can be used to schedule computing intensive tasks in grid services like Astronomy, high energy physics with deadlock avoidance, fault tolerance and improved resource utilization.