Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems
Efficiently Approximating the Probability of Deadline Misses in Real-Time Systems
复制标题
有效地近似实时系统中错过最后期限的概率
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
K. Morik
中科院分区：
文献类型：
--
作者：
G. V. D. Brüggen;N. Piatkowski;Kuan;Jian;K. Morik
23 本文探讨了单处理器平台上一组受约束的截止日期零星 24 软实时任务的截止日期错过概率。我们探索两个方向来评估 prob-25 能力，即所分析的任务作业是否可以在测试 26 个时间点 t（或之前）完成其执行。一种方法是基于分析上限，该上限可以在多项式时间内有效地计算出来，但代价是每个测试点的精度损失，源自 28 个著名的 Hoeffding 不等式和著名的 Bernstein 不等式。另一种方法 29 利用一系列状态 30 空间缩减技术，在多项分布上有效地对概率进行卷积，即，在不损失任何精度的情况下进行修剪，并通过 31 统一等效类进行近似，但精度损失有限。我们在一系列评估中证明了我们方法的有效性 32。与33篇文献中基于卷积的方法不同，后者计算量要求高，并且仅适用于任务集
23 This paper explores the probability of deadline misses for a set of constrained-deadline sporadic 24 soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the prob-25 ability whether a job of the task under analysis can finish its execution at (or before) a testing 26 time point t. One approach is based on analytical upper bounds that can be efficiently com-27 puted in polynomial time at the price of precision loss for each testing point, derived from the 28 well-known Hoeffding’s inequality and the well-known Bernstein’s inequality. Another approach 29 convolutes the probability efficiently over multinomial distributions, exploiting a series of state 30 space reduction techniques, i.e., pruning without any loss of precision, and approximations via 31 unifying equivalent classes with a bounded loss of precision. We demonstrate the effectiveness 32 of our approaches in a series of evaluations. Distinct from the convolution-based methods in the 33 literature, which suffer from the high computation demand and are applicable only to task sets