摘要： 随着计算机技术的发展与用户需求的不断提升，多有向无环图（DAG）共享一组异构计算资源的问题受到广泛的关注。但由于实际任务的复杂多变，多个DAG之间存在一定的差异，导致多DAG调度策略存在公平性问题。为此，提出一种改进的启发式公平调度算法IFairness。在选择待调度DAG阶段采用一种新的评判指标DAG完成度，代替原Fairness算法中的剩余Makespan作为DAG选择依据，在计算每个DAG的滞后程度阶段，采用"向后看"一步的原则，解决某些DAG在初期得不到调度的问题。仿真结果表明，与原Fairness算法相比，IFairness算法不公平程度降低了7.28%，资源利用率提升了11.97%，有效提高了调度算法的公平性及资源利用率。

关键词: 多有向无环图, 公平性, 启发式, 完成度, 资源利用率

Abstract: With the development of computer technology and the continuous improvement of user needs,the problem of multiple Directed Acyclic Graph(DAG) sharing the same group of heterogeneous computing resources has attracted wide attention.However,due to the complexity and change of the actual tasks,there are certain differences between multiple DAG,which lead to the fairness problem of multiple DAG scheduling strategies.Therefore,this paper proposes an improved heuristic fair scheduling algorithm,IFairness.In selecting the DAG phase to be scheduled,a new evaluation index DAG completion degree is adopted,which replaces the remaining Makespan in the original Fairness algorithm as the DAG selection basis.In the calculation phase of the lag degree of each DAG,the principle of "looking forward one step" is adopted to solve the problem that some DAG cannot be scheduled at the initial stage.Simulation results show that compared with the original Fairness algorithm,the unfairness degree of the IFairness algorithm is reduced by 7.28%,and the resource utilization rate is improved by 11.97%,which effectively improves the fairness and resource utilization rate of the scheduling algorithm.

Key words: multiple Directed Acyclic Graph(DAG), fairness, heuristic, completion degree, resource utilization rate

中图分类号: 

• TP393