一种面向节能的星载实时任务动态调度算法研究  

An Energy-Saving Oriented Dynamic Scheduling Algorithm for Space-Borne Real-Time Tasks

作　　者：李延祺 任海 白亮 邱源 张凤源 牛建伟[1] 李辉勇[1] LI Yanqi;REN Hai;BAI Liang;QIU Yuan;ZHANG Fengyuan;NIU Jianwei;LI Huiyong(Department of Computer Science and Engineering,Beihang University,Beijing 100191,China;Shanghai Aerospace Electronic Technology Institute,Shanghai 200082,China)

机构地区：[1]北京航空航天大学计算机学院,北京100191 [2]上海航天电子技术研究所,上海200082

出　　处：《上海航天》2019年第3期81-88,共8页Aerospace Shanghai

基　　金：上海航天科技创新基金项目(SAST2016097,SAST2017107)

摘　　要：星载嵌入式操作系统性能和任务能耗之间的平衡非常重要,采用合理的处理器和电压分配策略是一个重要手段。提出一系列基于计算概率的建模方法,用来解决星载实时嵌入式系统中对于具有数据依赖的非周期性任务的处理器和电压分配相关问题,并且能够确保所有的任务都能在时间约束下执行。首先设计一个处理器调度算法,将任务的有向无环图(DAG)映射到一组可变电压处理器上,然后使用动态编程算法为每个任务分配合适的电压。通过带有重启的局部搜索策略从候选解集中获取最优解,以解决局部最优陷阱问题。通过实验说明,所提出的算法与其他算法相比,在所有时间约束下具有更好的能效。The trade-off between system performance and energy efficiency (service time) is critical for the battery-based aerospace real-time embedded system. By adopting a probabilistic approach,this paper proposes a model and a set of algorithms to address the processor and voltage assignment with probability (PVAP) problem of data-dependent aperiodic tasks in real-time embedded systems,ensuring that all the tasks can be done under the time constraint with a guaranteed probability. A task directed acyclic graph (DAG) is adopted to model the PVAP problem. This paper first proposes a task-scheduling algorithm to map the task DAG onto a set of voltage-variable processors,and then uses the dynamic programming algorithm to assign a proper voltage to each task. Finally,to escape from local optima,a local search with restarts searches the optimal solution from candidate solutions by updating the objective function,until the task ends or the task deadline is reached. The test results show that compared with other algorithms,this algorithm has higher energy efficiency under all the time constraints.

关 键 词：概率调度 实时嵌入式系统 节能 实时任务调度 星载系统 

分 类 号：TP316.2[自动化与计算机技术—计算机软件与理论] TP309[自动化与计算机技术—计算机科学与技术]