Probabilistic Deadline Miss Analysis of Real-Time Systems Using Regenerative Transient Analysis

Quantitative evaluation of real-time systems demands for analysis frameworks that go beyond worst-case assumptions, since some parameters could be better characterized by a random variable than by a deterministic value. On the one hand, this opens notable issues on the safe estimation of probabilistic parameters starting from real measurements. On the other hand, this also requires modeling formalisms and solution techniques that can encompass stochastic temporal parameters with a non-Markovian distribution, thus breaking the limits of Markovian approaches. We propose a framework for modeling and evaluating periodic real-time tasks that may have a probabilistic Worst Case Execution Time (pWCET) and are scheduled by a fixed-priority non-preemptive policy. The methodology leverages the Extreme Value Theory (EVT) for the derivation of the pWCET of tasks by means of Erlang distributions. Evaluation is performed through regenerative transient analysis based on the method of stochastic state classes, supporting the derivation of quantitative measures on the time by which a deadline is missed. The approach is experimented on a case study including tasks with a pWCET derived from benchmarks and real system execution.