Stochastic analysis of real-time systems under preemptive priority-driven scheduling

摘要

Exact stochastic analysis of most real-time systems under preemptive priority-driven scheduling is unaffordable in current practice. Even assuming a periodic and independent task model, the exact calculation of the response time distribution of tasks is not possible except for simple task sets. Furthermore, in practice, tasks introduce complexities such as release jitter, blocking in shared resources, etc., which cannot be handled by the periodic independent task set model. In order to solve these problems, exact analysis must be abandoned for an approximated analysis. However, in the real-time field, approximations must not be optimistic, i.e. the deadline miss ratios predicted by the approximated analysis must be greater than or equal to the exact ones. In order to achieve this goal, the concept of pessimism needs to be mathematically defined in the stochastic context, and the pessimistic properties of the analysis carefully derived. This paper provides a mathematical framework for reasoning about stochastic pessimism, and obtaining mathematical properties of the analysis and its approximations. This framework allows us to prove the safety of several proposed approximations and extensions. We analyze and solve some practical problems in the implementation of the stochastic analysis, such as the problem of the finite precision arithmetic or the truncation of the probability functions. In addition, we extend the basic model in several ways, such as the inclusion of shared resources, release jitter or non-preemptive sections.