PERIODIC TASK SCHEDULING - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 104

According to the DM algorithm, each task is assigned a fixed priority P i inversely
proportional to its relative deadline D i . Thus, at any instant, the task with the shortest
relative deadline is executed. Since relative deadlines are constant, DM is a static
priority assignment. As RM, DM is normally used in a fully preemptive mode; that is,
the currently executing task is preempted by a newly arrived task with shorter relative
deadline.

The Deadline-Monotonic priority assignment is optimal 2 , meaning that, if a task set is
schedulable by some fixed priority assignment, then it is also schedulable by DM.

4.5.1 SCHEDULABILITY ANALYSIS

The feasibility of a task set with constrained deadlines could be guaranteed using the
utilization based test, by reducing tasks' periods to relative deadlines:
n

C i
D i ≤

n (2 1 /n

−

1) .

i =1

However, such a test would be quite pessimistic, since the workload on the processor
would be overestimated. A less pessimistic schedulability test can be derived by noting
that

the worst-case processor demand occurs when all tasks are released simultane-
ously; that is, at their critical instants;

for each task τ i , the sum of its processing time and the interference (preemption)
imposed by higher priority tasks must be less than or equal to D i .

Assuming that tasks are ordered by increasing relative deadlines, so that

i<j ⇐⇒ D i <D j ,

such a test can be expressed as follows:

∀ i :1 ≤ i ≤ nC i + I i ≤ D i , (4.16)

where I i is a measure of the interference on τ i , which can be computed as the sum of
the processing times of all higher-priority tasks released before D i :

D i
T j

C j .

i− 1

I i =

j =1

2 The proof of DM optimality is similar to the one done for RM and it can be found in [LW82].