Non preemptive Earliest deadline first scheduling

Question

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.

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.

Any help is greatly appreciated. Thank you

Answer 1

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) <= 1

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.

EDIT: 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.

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], Section 8.3 on Nonpreemptive Critical Sections.

^{* [JL00] Jane W.S. Liu, Real-Time Systems, Prentice Hall, 2000}