• 中国计算机学会会刊
  • 中国科技核心期刊
  • 中文核心期刊

Computer Engineering & Science

Previous Articles     Next Articles

An improved primary/backup scheduling algorithm
based on simulated annealing algorithm

ZHU Yong-chao1,ZHOU Chuan1,CUI Yu-wei2,GUO Jian1,WU Yi-fei1   

  1. (1.School of Automation,Nanjing University of Science and Technology,Nanjing 210094;
    2.AVIC Xi’an Flight Automatic Control Research Institute,Xi’an 710077,China)

     
  • Received:2018-09-18 Revised:2019-01-25 Online:2019-09-25 Published:2019-09-25

Abstract:

Aiming at the priority constraint oriented task scheduling in heterogeneous distributed systems, we propose an improved primary/backup scheduling algorithm based on simulated annealing algorithm called SAPB. The task  model is presented by a directed acyclic graph (DAG) and the proposed algorithm schedules two copies (primary and backup) of each task. For task sorting, we adopt the  HEFT task sorting method to avoid the limitation of the task model description in primary/backup scheduling strategies such as eFRD. In task processor selection stage, the simulated annealing algorithm is used to search the solution with higher reliability under the condition of meeting the deadline and it considers preparing one more backup copy to solve the likely scheduling failure caused by task priority constraints when scheduling backup copies have fewer processors. Finally, the simulation experiments based on randomly generated DAGs are carried out. The results show that the proposed algorithm outperforms the eFRD in terms of the schedulability of backup copies and system reliability.
 

Key words: heterogeneous distributed system, simulated annealing, directed acyclic graph (DAG), primary/backup copy, task scheduling