计算机科学与探索 ›› 2017, Vol. 11 ›› Issue (5): 833-841.DOI: 10.3778/j.issn.1673-9418.1609039

• 理论与算法 • 上一篇    下一篇

可靠性感知周期任务能耗管理调度算法

张忆文+,王  成   

  1. 华侨大学 计算机科学与技术学院,福建 厦门 361021
  • 出版日期:2017-05-01 发布日期:2017-05-04

Reliability-Aware Energy Management Scheduling Algorithm for Periodic Task

ZHANG Yiwen+, WANG Cheng   

  1. College of Computer Science and Technology, Huaqiao University, Xiamen, Fujian 361021, China
  • Online:2017-05-01 Published:2017-05-04

摘要: 针对EDF/DDM(earliest deadline first/dynamic deadline modify)算法不能利用空闲时间降低能耗的不足,提出了能够回收空闲时间的静态节能(static saving energy,SSE)算法。针对SSE算法没有考虑系统可靠性问题,在证明可靠性感知资源受限周期任务调度问题是NP难之后,提出两种启发式算法:最长执行时间优先算法(longest execution time first,LETF)算法和最短执行时间优先算法(shortest execution time first,SETF)算法。仿真实验表明所提出的LETF算法和SETF算法的能耗均低于EDF/DDM算法的能耗。此外,SETF算法和LETF算法的出错率比EDF/DDM算法低,是EDF/DDM算法的97%和76%,系统可靠性得到提高。

关键词: 能耗, 可靠性感知, 资源受限, 实时调度

Abstract: Aiming at the shortcoming of the EDF/DDM (earliest deadline first/dynamic deadline modify) algorithm which can't use the slack time to reduce the energy consumption, this paper proposes the SSE (static saving energy) algorithm which can reclaim the slack time. But, it ignores that the processor speed has a negative effect on the system reliability. This paper proves that the problem of reliability-aware resource-constrained low-power periodic task scheduling is NP-hard. Furthermore, this paper presents two heuristic algorithms: LETF (longest execution time first) algorithm and SETF (shortest execution time first) algorithm. The simulation results show that the energy consumption of the LETF algorithm and the SETF algorithm is lower than that of the EDF/DDM algorithm. In addition, the probability of failure of the LETF algorithm and the SETF algorithm is 97% and 76% lower than that of the EDF/DDM algorithm, respectively. It means that the system reliability is improved.

Key words: energy consumption, reliability-aware, resource constrained, real-time scheduling