Schedulability and optimization analysis for non-preemptive static priority scheduling based on task utilization and blocking factors
Schedulability and optimization analysis for non-preemptive static priority scheduling based on task utilization and blocking factors
复制标题
基于任务利用率和阻塞因素的非抢占式静态优先级调度的可调度性及优化分析
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Wen
中科院分区：
文献类型：
--
作者：
G. V. D. Brüggen;Jian;Wen
对于实时任务集，允许抢占通常被认为对于确保可调度性很重要，因为它允许高优先级任务几乎立即分配给处理器。然而，抢占式调度也引入了一些额外的开销，并且对于某些硬件组件可能不允许，这激发了非抢占式或有限抢占式调度的需求。我们提出了一种针对非抢占式（NP）固定优先级调度的安全充分的可调度性测试，如果给出根据优先级和周期的任务顺序，则可以验证线性时间内截止单调（DM-NP）和速率单调（RM-NP）调度的可调度性。与最早截止时间优先 (EDF-NP) 相比，该测试得出 DM-NP 和 RM-NP 的加速因子上限比之前已知的更好，从而缩小了下限和上限之间的差距。我们改进了我们的测试，产生了阻塞时间的有趣属性，这些属性允许仅在满足某些条件的情况下考虑抢占情况的可调度性来确定可调度性。此外，我们根据最大阻塞时间上限与执行时间的比率 γ > 0，提出了 RM-NP 的利用率界限，显着改善了之前的结果。
For real time task sets, allowing preemption is often considered to be important to ensure the schedulability, as it allows high-priority tasks to be allocated to the processor nearly immediately. However, preemptive scheduling also introduces some additional overhead and may not be allowed for some hardware components, which motivates the needs of non-preemptive or limited-preemptive scheduling. We present a safe sufficient schedulability test for non-preemptive (NP) fixed priority scheduling that can verify the schedulability for Deadline Monotonic (DM-NP) and Rate Monotonic (RM-NP) scheduling in linear time, if task orders according to priority and period are given. This test leads to a better upper bound on the speedup factor for DM-NP and RM-NP in comparison to Earliest Deadline First (EDF-NP) than previously known, closing the gab between lower and upper bound. We improve our test, resulting in interesting properties of the blocking time that allow to determine schedulability by only considering the schedulability of the preemptive case if some conditions are met. Furthermore, we present a utilization bound for RM-NP, based on the ratio γ > 0 of the upper bound of the maximum blocking time to the execution time, significantly improving previous results.