Fairness-aware scheduling algorithm for multiple DAGs based on task replication

Most of the DAG scheduling algorithms only take the performance of the processor, bandwidth, the cost of the task and other factors into consideration, but regardless of the effect of reliability. In order to improve the reliability of DAG scheduling, we propose an algorithm, named as Fairness-Aware Single DAG Scheduling Algorithm based on Task Replication (FASS). In the FASS algorithm, with the active task replication, the tasks are mapped fairly to multiple processors to improve the reliability of the task execution process. Based on the FASS algorithm, we propose a Fairness-Aware Multiple DAGs Scheduling Algorithm based on Task Replication (FAMS) to dynamically deal with multiple DAGs which arrive at any time. The FAMS algorithm can dynamically split DAG tasks into unconstrained nodes, and then process the multiple copy task scheduling with calling the FASS algorithm to improve the reliability of multiple DAGs. The comparative experiments demonstrate that the proposed algorithms can take shorter time and higher resource utilization to process scheduling the same task sets, meanwhile, effectively reduce the earliest completion time while satisfying the reliability requirement.