非preemptive最早截止时间调度 [英] Non preemptive Earliest deadline first scheduling

问题描述

我工作的一个任务调度程序，我想用EDF调度。任务设置我需要安排只包含任务，期限等于其周期和任务，必须定期调度。我的问题是，一旦他们已经开始执行的任务不能中断。

I am working on a task scheduler and I would like to use EDF scheduling. The task set I need to schedule contains only tasks with deadlines equal to their periods and the tasks must be scheduled periodically. The problem I have is that the tasks cannot be interrupted once they have started execution.

我知道，EDF是当任务被安排在一个处理器上$ P $只有当pemptively所以我在想，如果有可能，我可能强加的任务任何测试或约束来验证我的任务的优化调度算法集可以使用非preemptive EDF调度。

I know that the EDF is an optimal scheduling algorithm only when when tasks are scheduled on a single processor preemptively so I was wondering if there might be any tests or constraints I might impose on the tasks to verify that my task set can be scheduled using a non-preemptive EDF.

任何帮助是极大的AP preciated。谢谢

Any help is greatly appreciated. Thank you

推荐答案

让e_i任务的执行时间我，P_i其周期和e_m = max_i（e_i）。然后，你能保证你的任务设置是可行的，如果

Let e_i the execution time of task i, P_i its period, and e_m=max_i(e_i). Then, you can guarantee that your task set is feasible, if

U = sum_i（（e_i + e_m）/ P_i）＆LT; = 1

U = sum_i ((e_i + e_m)/P_i) <= 1

理由：：您可能知道刘/ Layland标准sum_i（E_1 / P_i）LT = 1，非preamtable任务可以被看作是一个阻塞到更高优先级的任务。阻塞时间可以被认为是附加的执行时间。最坏的情况是，当一个更高优先级的任务准备好最长的（低优先级）任务开始后直接。

Justification: You probably know the Liu/Layland criterion sum_i(e_1/P_i) <= 1. A non-preamtable task can be seen as a blocking to a higher priority task. Blocking time can be considered as additional execution time. The worst case is when a higher priority tasks becomes ready directly after the longest (lower priority) task has started.

编辑： 我得出上述特设的条件。然而，这仅仅是一个足够的。对于更precise分析，人们必须考虑到，一个任务只能通过用啤酒相对截止期，即另一个任务具有较长时期，比照受阻，相对于所使用的模型，任务例如，[JL00] *，定理6.18。

I've derived the condition above ad hoc. However, it is a sufficient one only. For a more precise analysis, one have to consider that a task can only be blocked by another task with a lager relative deadline, i.e., with respect to the used model, tasks with a longer period, c.f. e.g., [JL00]*, Theorem 6.18.

因此​​，对于任务设置任务T_1，...，T_n用句P_1＆LT; P_2＆LT; ...＆LT; P_N， 可以计算

Thus, for a task set with tasks T_1, ..., T_n with periods P_1 < P_2 < ... < P_n, one can calculate

L'_i = e_i + max_{j=i...n}(e_j).

然后，所设定的任务是为可行

Then, the task set is feasible for

sum_i L'_i/P_i <= 1.

C.f。 [JL00]，非preemptive关键部分第8.3节。

C.f. [JL00], Section 8.3 on Nonpreemptive Critical Sections.

^{* [JL00]简W.S.刘，实时系统，prentice厅，2000}

这篇关于非preemptive最早截止时间调度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！