An exact stochastic analysis of priority-driven periodic real-time systems and its approximations

This paper describes a stochastic analysis framework for general priority-driven periodic real-time systems. The proposed framework accurately computes the response time distribution of each task in the system, thus making it possible to determine the deadline miss probability of individual tasks, even for systems with a maximum utilization factor greater than 1. The framework is uniformly applied to general priority-driven systems, including xed-priority systems (such as Rate Monotonic) and dynamic-priority systems (such as Earliest Deadline First), and can handle tasks with arbitrary relative deadlines and execution time distributions. In the framework, both an exact method and approximation methods to compute the response time distributions are presented and compared in terms of analysis accuracy and complexity. We prove that the complexity of the exact method is polynomial in terms of the number of jobs in a hyperperiod of the task set and the maximum length of the execution time distributions, and show that the approximation methods can signicantly reduce the complexity without loss of accuracy