计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (14): 61-64.DOI: 10.3778/j.issn.1002-8331.1603-0186

• 理论与研发 • 上一篇    下一篇

星间实时关键数据一次容错调度算法

范玲玲1,2,林宝军2,3,陈  勇3   

  1. 1.中国科学院 上海微系统与信息技术研究所,上海 200050
    2.上海微小卫星工程中心,上海 201203
    3.中国科学院 光电研究院,北京 100094
  • 出版日期:2017-07-15 发布日期:2017-08-01

Key data between satellites once fault-tolerant scheduling algorithm

FAN Lingling1,2, LIN Baojun2,3, CHEN Yong3   

  1. 1.Shanghai Institute of Microsystem and Information Technology, Chinese Academy of Sciences, Shanghai 200050, China
    2.Shanghai Engineering Center for Microsatellites, Shanghai 201203, China
    3.Academy of Opto-Electronics, Chinese Academy of Sciences, Beijing 100094, China
  • Online:2017-07-15 Published:2017-08-01

摘要: 针对卫星实时系统中关键数据一次容错问题,首先,针对关键数据与非关键数据混合传输场景,建立系统模型,对系统的容错传输能力进行分析,得出混合数据一次容错传输条件;其次提出NP-PEDF-FT调度算法,通过在非抢占式EDF容错算法的基础上,利用截止期容错系数[λ]调整出错任务的截止期,实现全部关键数据的1次容错传输;同时加入数据传输队列监测功能,以保证关键数据在其截止期之前优先传输;最后对算法进行了仿真分析,比较NP-PEDF-FT、NP-EDF-FT、NP-DP-FT三种非抢占式容错调度策略,分析结果表明,NP-PEDF-FT算法关键数据丢包率较NP-EDF-FT算法平均降低31.6%,较NP-DP-FT算法平均降低86.4%。

关键词: 非抢占式, 关键数据, 容错, 调度, 截止期, 比较

Abstract: In this paper, in accordance with the need of key data in real-time satellite system fault tolerance, and the key data with a relatively small number and a long cycle, it puts forward NP-PEDF-FT algorithm to realize high performance schedule. This algorithm based on EDF fault tolerant algorithm, adjusts the deadline of the key data through fault tolerance coefficient[λ]. This algorithm adjusts the deadline of the key data as the original deadline multiplied by the coefficient [(1-λ)]  to the queue of the tasks to send again, when the key data once transmission errors. So it can realize once fault tolerance. Of course, the algorithm will not send again and abandon the task, when the common data once transmission errors. NP-PEDF-FT algorithm is better when the coefficient[λ]is equal to 0.6 through the simulation. It also simulates the NP-PEDF-FT algorithm, NP-EDF-FT algorithm and NP-DP-FT algorithm, and compares the packet loss probability. It turns out that the NP-PEDF-FT algorithm used in this paper has a better effect.

Key words: non-preemptive, key data, fault tolerance, scheduled, deadline, compare