Efficient Computation of Deadline-Miss Probability and Potential Pitfalls
Kuan-Hsun Chena, Niklas Ueterb, Georg von der Brüggenc and Jian-Jia Chend
Department of Informatics, TU Dortmund University, Germany
akuan-hsun.chen@tu-dortmund.de
bniklas.ueter@tu-dortmund.de
cgeorg.von-der-brueggen@tu-dortmund.de
djian-jia.chen@tu-dortmund.de
ABSTRACT
In soft real-time systems, applications can tolerate rare deadline misses. Therefore, probabilistic arguments and analyses are applicable in the timing analyses for this class of systems, as demonstrated in many existing researches. Convolutionbased analyses allow to derive tight deadline-miss probabilities, but suffer from a high time complexity. Among the analytical approaches, which result in a significantly faster runtime than the convolution-based approaches, the Chernoff bounds provide the tightest results. In this paper, we show that calculating the deadline-miss probability using Chernoff bounds can be solved by considering an equivalent convex optimization problem. This allows us to, on the one hand, decrease the runtime of the Chernoff bounds while, on the other hand, ensure a tighter approximation since a larger variable space can be searched more efficiently, i.e., by using binary search techniques over a larger area instead of a sequential search over a smaller area. We evaluate this approach considering synthesized task sets. Our approach is shown to be computationally efficient for large task systems, whilst experimentally suggesting reasonable approximation quality compared to an exact analysis.
Keywords: Deadline miss probability, Soft real-time systems.
