On Probabilistic Timing Analysis of Fault-Tolerant Real-Time Systems Experiencing Random Errors

The inherent intractability of probabilistic timing and schedulability analysis of real-time and embedded systems in exact cases has been well discussed in the literature. This has prompted the search for efficient solutions which give meaningful results in practical situations. As many real-time systems are exposed to errors which are random in nature (e.g., due to EMI), it is prudent to consider stochastic schedulability analysis in which the impacts of such errors upon timing are considered. However, work in this area has progressed slowly: in this paper, progress is presented as follows. New schedulability conditions are derived for Earliest Deadline First (EDF)-scheduled periodic and/or sporadic task sets experiencing Binomially distributed random error arrivals, leading to job faults and re-execution attempts. A new analytic model for tightly bounding the impacts of errors over a section of the EDF workload is first presented, and subsequently used to derive an accurate and tractable probabilistic schedulability and timing analysis procedure. The analysis is sufficient to verify that task deadlines are met with a pre-specified upper tail probability R >> 0.5. An example illustrates its application and efficiency. The paper is concluded by highlighting areas of future work.