Choosing preemption points to minimize typical running times
Choosing preemption points to minimize typical running times
复制标题
选择抢占点以最小化典型运行时间
DOI：
10.1145/3356401.3356407
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Fisher, Nathan
中科院分区：
文献类型：
--
作者：
Baruah, Sanjoy;Fisher, Nathan
考虑在程序中选择“有效抢占点”的问题——代码中允许抢占的点——以最小化总体运行时间。针对该问题提出的现有解决方案基于工作负载模型，其中假定在代码中的特定点执行抢占所需的持续时间以及在抢占点之间非抢占式执行代码所需的时间的最坏情况已知上限。由于这些解决方案都是基于最坏情况的假设，因此倾向于以保守的方式选择有效的抢占点；因此，在大多数典型的运行时环境下，程序的整体执行时间可能会过长。我们考虑一个更通用的工作负载模型，其中假设抢占持续时间和非抢占代码执行持续时间的“典型”值以及上限是已知的；给定这些信息，我们以最小化典型总体运行时间的方式推导抢占点的最佳放置算法（同时，如果需要，继续保证最坏情况总体运行时间的上限）。离线解决方案（其中所有抢占点在运行时之前选择）和在线解决方案（其中一些抢占点的选择是在运行时期间进行的，因此可以利用先前抢占的实际持续时间和已执行的代码段的执行的知识）并被证明是最佳的。
The problem of selecting "effective preemption points" in a program --- points in the code at which to permit preemption --- in order to minimize overall running time is considered. Prior solutions that have been proposed for this problem are based on workload models in which worst-case known upper bounds are assumed for the duration needed to perform preemptions at particular points in the code, and of the time needed to non-preemptively execute the code between preemption points. Since these solutions are based on worst-case assumptions, they tend to select effective preemption points in a conservative manner; consequently the overall execution time of the program may be needlessly large under most typical run-time circumstances. We consider a more general workload model in which "typical" values, as well as upper bounds, are assumed to be known for the preemption durations and the non-preemptive code-execution durations; given such information, we derive algorithms for the optimal placement of preemption points in a manner that minimizes the typical overall running time (while continuing to guarantee, if needed, upper bounds on the worst-case over-all running time). Both off-line solutions (in which all preemption points are selected prior to run-time) and on-line solutions (where the selection of some of the preemption points is made during run-time and therefore can exploit knowledge of the actual durations of prior preemptions and of the executions of already executed pieces of code) are presented and proved optimal.
登录
查看更多内容
DOI：
10.1145/1274858.1274863
发表时间：
2007-09
期刊：
ACM Trans. Embed. Comput. Syst.
影响因子：
--
作者：
J. Staschulat;R. Ernst
通讯作者：
J. Staschulat;R. Ernst
用于抢占式调度的可扩展精度缓存分析
影响因子：
3.7
作者：
J. Staschulat;R. Ernst
通讯作者：
R. Ernst
DOI：
10.1145/334012.334025
发表时间：
2000-05
期刊：
Proceedings of the Eighth International Workshop on Hardware/Software Codesign. CODES 2000 (IEEE Cat. No.00TH8518)
影响因子：
--
作者：
H. Tomiyama;N. Dutt
通讯作者：
H. Tomiyama;N. Dutt
影响因子：
1.3
作者：
S. Altmeyer;Robert I. Davis;Claire Maiza
通讯作者：
S. Altmeyer;Robert I. Davis;Claire Maiza
在基于缓存的实时系统中使用首选抢占点
DOI：
10.1109/ipds.1995.395820
发表时间：
1995
期刊：
Proceedings of 1995 IEEE International Computer Performance and Dependability Symposium
影响因子：
--
作者：
Jonathan Simonson;J. Patel
通讯作者：
J. Patel