Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems
share
This paper explores the probability of deadline misses for a set of constrained-deadline sporadic soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the prob-ability whether a job of the task under analysis can finish its execution at (or before) a testing time point t. One approach is based on analytical upper bounds that can be efficiently computed in polynomial time at the price of precision loss for each testing point, derived from the well-known Hoeffding’s inequality and the well-known Bernstein’s inequality. Another approach convolutes the probability efficiently over multinomial distributions, exploiting a series of statespace reduction techniques, i.e., pruning without any loss of precision, and approximations viaunifying equivalent classes with a bounded loss of precision. We demonstrate the effectivenessof our approaches in a series of evaluations. Distinct from the convolution-based methods in theliterature, which suffer from the high computation demand and are applicable only to task setswith a few tasks, our approaches can scale reasonably without losing much precision in terms ofthe derived probability of deadline misses.
READ FULL TEXT