Schedulability analysis of applications with stochastic task execution times
Schedulability analysis of applications with stochastic task execution times
复制标题
DOI：
10.1145/1027794.1027797
复制
发表时间：
2004-11
期刊：
影响因子：
--
通讯作者：
Sorin Manolache;P. Eles;Zebo Peng
中科院分区：
文献类型：
--
作者：
Sorin Manolache;P. Eles;Zebo Peng
在过去的十年中，对于软实时系统内的大型应用类别，考虑固定（最坏情况）任务执行时间的模型的局限性已得到认可。一种更现实的模型考虑具有给定概率分布的不同执行时间的任务。考虑这样一个具有指定任务执行时间概率分布函数的模型，系统的一个重要性能指标是任务和任务图的预期截止期错过率。本文提出了一种以解析方式获取该指标的方法。我们的目标是在所需的分析时间和内存方面保持较低的分析成本，同时尽可能考虑一般类别的目标应用模型。对于建模为任务图集的应用程序，做出了以下主要假设：任务是周期性的，任务执行时间具有给定的广义概率分布函数，任务执行截止期是给定的且任意的，调度策略实际上可以属于任何类别的非抢占式调度策略，并且系统允许设计人员提供的同一任务图的最大并发实例数量。实验表明了所提出的技术对于单处理器系统的有效性。
In the past decade, the limitations of models considering fixed (worst-case) task execution times have been acknowledged for large application classes within soft real-time systems. A more realistic model considers the tasks having varying execution times with given probability distributions. Considering such a model with specified task execution time probability distribution functions, an important performance indicator of the system is the expected deadline miss ratio of the tasks and of the task graphs. This article presents an approach for obtaining this indicator in an analytic way. Our goal is to keep the analysis cost low, in terms of required analysis time and memory, while considering as general classes of target application models as possible. The following main assumptions have been made on the applications that are modeled as sets of task graphs: the tasks are periodic, the task execution times have given generalized probability distribution functions, the task execution deadlines are given and arbitrary, the scheduling policy can belong to practically any class of non-preemptive scheduling policies, and a designer supplied maximum number of concurrent instantiations of the same task graph is tolerated in the system. Experiments show the efficiency of the proposed technique for monoprocessor systems.