Intractability Issues in Mixed-Criticality Scheduling
Intractability Issues in Mixed-Criticality Scheduling
复制标题
混合关键调度中的棘手问题
DOI：
10.4230/lipics.ecrts.2018.11
复制
发表时间：
2018
影响因子：
3.7
通讯作者：
Sanjoy Baruah
中科院分区：
文献类型：
--
作者：
Kunal Agrawal;Sanjoy Baruah
在寻求开发混合关键度调度算法时，遇到来自两个来源的挑战。首先，混合关键度调度本质上是一个在线问题，因为调度决策必须在没有获得最佳决策所需的所有信息的情况下做出-这些信息只会随着时间的推移而被揭示。第二，许多基本的混合临界可扩展性分析问题在计算上是难以处理的-在很强的意义上是NP-难的-但我们希望使用多项式或伪多项式运行时间的算法来解决这些问题。虽然这两个方面的棘手性传统上是单独研究的理论计算机科学文献中，他们被认为是在一个综合的方式在混合关键调度理论。在这项工作中，我们试图分离出固有的在线的影响，并计算棘手的，整体棘手的混合关键调度问题。加速因子被广泛用作混合关键度调度算法有效性的定量度量;最近关于这样做的适当性有一点争论。我们在这里提供了一些额外的角度来看这个问题：我们试图更好地了解其适当性，以及它在这方面的局限性，分别研究如何在线性质的一些mixedcriticality问题，和他们的计算复杂性，有助于加速因子的两个广泛研究的混合临界调度算法。2012 ACM主题分类计算机系统组织→实时系统
In seeking to develop mixed-criticality scheduling algorithms, one encounters challenges arising from two sources. First, mixed-criticality scheduling is an inherently an on-line problem in that scheduling decisions must be made without access to all the information that is needed to make such decisions optimally – such information is only revealed over time. Second, many fundamental mixed-criticality schedulability analysis problems are computationally intractable – NP-hard in the strong sense – but we desire to solve these problems using algorithms with polynomial or pseudo-polynomial running time. While these two aspects of intractability are traditionally studied separately in the theoretical computer science literature, they have been considered in an integrated fashion in mixed-criticality scheduling theory. In this work we seek to separate out the effects of being inherently on-line, and being computationally intractable, on the overall intractability of mixed-criticality scheduling problems. Speedup factor is widely used as quantitative metric of the effectiveness of mixed-criticality scheduling algorithms; there has recently been a bit of a debate regarding the appropriateness of doing so. We provide here some additional perspective on this matter: we seek to better understand its appropriateness as well as its limitations in this regard by examining separately how the on-line nature of some mixedcriticality problems, and their computational complexity, contribute to the speedup factors of two widely-studied mixed-criticality scheduling algorithms. 2012 ACM Subject Classification Computer systems organization → Real-time systems