A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults

被引:75
|
作者
Han, CC [1 ]
Shin, KG [1 ]
Wu, J [1 ]
机构
[1] Univ Michigan, Dept Elect Engn & Comp Sci, Real Time Comp Lab, Ann Arbor, MI 48109 USA
关键词
real-time systems; deadline mechanisms; notification time; primary; alternate; backwards-RM algorithm; CAT algorithm; EIT algorithm;
D O I
10.1109/TC.2003.1183950
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
A hard real-time system is usually subject to stringent reliability and timing constraints since failure to produce correct results in a timely manner may lead to a disaster. One way to avoid missing deadlines is to trade the quality of computation results for timeliness and software fault tolerance is often achieved with the use of redundant programs. A deadline mechanism which combines these two methods is proposed to provide software fault tolerance in hard real-time periodic task systems. Specifically, we consider the problem of scheduling a set of real-time periodic tasks each of which has two versions: primary and alternate. The primary version contains more functions (thus more complex) and produces good quality results, but its correctness is more difficult to verify because of its high level of complexity and resource usage. By contrast, the alternate version contains only the minimum required functions (thus simpler) and produces less precise, but acceptable results and its correctness is easy to verify. We propose a scheduling algorithm which 1) guarantees either the primary or alternate version of each critical task to be completed in time and 2) attempts to complete as many primaries as possible. Our basic algorithm uses a fixed priority-driven preemptive scheduling scheme to preallocate time intervals to the alternates and, at runtime, attempts to execute primaries first. An alternate will be executed only 1) if its primary fails due to lack of time or manifestation of bugs or 2) when the latest time to start execution of the alternate without missing the corresponding task deadline is reached. This algorithm is shown to be effective and easy to implement. this algorithm is enhanced further to prevent early failures in executing primaries from triggering failures in the subsequent job executions, thus improving efficiency of processor usage.
引用
收藏
页码:362 / 372
页数:11
相关论文
共 50 条
  • [31] Boosting adaptivity of fault-tolerant scheduling for real-time tasks with service requirements on clusters
    Zhu, Xiaomin
    He, Chuan
    Ge, Rong
    Lu, Peizhong
    JOURNAL OF SYSTEMS AND SOFTWARE, 2011, 84 (10) : 1708 - 1716
  • [32] QoS-Aware Fault-Tolerant Scheduling for Real-Time Tasks on Heterogeneous Clusters
    Zhu, Xiaomin
    Qin, Xiao
    Qiu, Meikang
    IEEE TRANSACTIONS ON COMPUTERS, 2011, 60 (06) : 800 - 812
  • [33] An adaptive scheme for fault-tolerant scheduling of soft real-time tasks in multiprocessor systems
    Al-Omari, R
    Somani, AK
    Manimaran, G
    JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2005, 65 (05) : 595 - 608
  • [34] Supervisory control for fault-tolerant scheduling of real-time multiprocessor systems with aperiodic tasks
    Park, Seong-Jin
    Cho, Kwang-Hyun
    INTERNATIONAL JOURNAL OF CONTROL, 2009, 82 (02) : 217 - 227
  • [35] Real-time scheduling in a generic fault-tolerant architecture
    Wellings, AJ
    Beus-Dukic, L
    Powell, D
    19TH IEEE REAL-TIME SYSTEMS SYMPOSIUM, PROCEEDINGS, 1998, : 390 - 398
  • [36] Fault-Tolerant Scheduling for Hybrid Real-Time Tasks Based on CPB Model in Cloud
    Han, Haoran
    Bao, Weidong
    Zhu, Xiaomin
    Feng, Xiaosheng
    Zhou, Wen
    IEEE ACCESS, 2018, 6 : 18616 - 18629
  • [37] Fault-Tolerant Scheduling for Real-Time Tasks on Multiple Earth-Observation Satellites
    Zhu, Xiaomin
    Wang, Jianjiang
    Qin, Xiao
    Wang, Ji
    Liu, Zhong
    Demeulemeester, Erik
    IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, 2015, 26 (11) : 3012 - 3026
  • [38] Fault-tolerant scheduling in distributed real-time systems
    Satyanarayana, NV
    Mall, R
    Pal, A
    2001 INTERNATIONAL CONFERENCE ON COMPUTER NETWORKS AND MOBILE COMPUTING, PROCEEDINGS, 2001, : 275 - 280
  • [39] Fault-Tolerant Scheduling in Homogeneous Real-Time Systems
    Krishna, C. M.
    ACM COMPUTING SURVEYS, 2014, 46 (04)
  • [40] Fault-tolerant scheduling in distributed real-time systems
    Thai, ND
    PARALLEL PROCESSING AND APPLIED MATHEMATICS, 2004, 3019 : 125 - 130