Scheduling trade-off of dynamic multiple parallel workflows on heterogeneous distributed computing systems

摘要

Scheduling multiple parallel workflows, which arrive at different instants on heterogeneous distributed computing systems, is a great challenge because of the different requirements of resource providers and users. Overall scheduling length is the main concern of resource providers, whereas deadlines of workflows are the major requirements of users. Most algorithms use fairness-based strategies to reduce the overall scheduling length. However, these algorithms cause obvious unfairness to longer-makespan workflows or shorter-makespan workflows. Furthermore, the systems cannot meet the deadlines of all workflows, particularly on large-scale resource-constrained computational grids. Gaining a reasonable balance between the overall scheduling length and the deadlines of workflows is a desirable goal. In this study, we first propose a fairness-based scheduling algorithm called fairness-based dynamic multiple heterogeneous selection value to achieve high performance of systems compared with existing works. Then, to meet the deadlines of partial higher-priority worklows, we present a priority-based scheduling algorithm called priority-based dynamic multiple heterogeneous selection value. Finally, combining fairness-based dynamic multiple heterogeneous selection value and priority-based dynamic multiple heterogeneous selection value, we present the tradeoff-based scheduling algorithm to meet the deadlines of more higher-priority worklows while still allowing the lower-priority workflows to be processed actively for better performance of systems. Both example and extensive experimental evaluations demonstrate significant improvement of our proposed algorithms.