Task Scheduling Based on Heterogeneous Priority and Critical Task Duplication
Lei Li, Wei Pan, Dejian Li, Guojin Liu, Tiancong Huang · 2023
Efficient task scheduling algorithms can reduce the overall task scheduling length and improve the efficiency of task execution in heterogeneous environments. However, most task scheduling algorithms ignore the heterogeneity of tasks when calculating the task scheduling order, so they are not suitable for heterogeneous environments. And a large number of free slots are generated to increase the scheduling length in the processor selection phase. So we present a task scheduling algorithm based on heterogeneous priority and critical task duplication by combining static table scheduling algorithm and task duplication algorithm with the main goal of minimizing task scheduling length. In priority calculation phase, we integrate the computation cost variance and node out degree to reveal the heterogeneity of task cost and data transmission. In the processor selection phase, if duplicating the critical parent task of current task can reduce its actual start time, we duplicate the critical parent task to the processor on which current task is scheduled for the purpose of reducing its overall scheduling length ultimately. We evaluate our method over the randomly generated graphs and some simulation comparison charts. Experimental results show that the proposed algorithm outperforms the other three comparison algorithms.