Hardware Reference
In-Depth Information
4.5
DEADLINE MONOTONIC
The algorithms and the schedulability bounds illustrated in the previous sections rely
on the assumptions A1, A2, A3, and A4 presented at the beginning of this chapter. In
particular, assumption A3 imposes a relative deadline equal to the period, allowing an
instance to be executed anywhere within its period. This condition could not always
be desired in real-time applications. For example, relaxing assumption A3 would
provide a more flexible process model, which could be adopted to handle tasks with
jitter constraints or activities with short response times compared to their periods.
The Deadline Monotonic (DM) priority assignment weakens the “period equals dead-
line” constraint within a static priority scheduling scheme. This algorithm was first
proposed in 1982 by Leung and Whitehead [LW82] as an extension of Rate Mono-
tonic, where tasks can have relative deadlines less than or equal to their period (i.e.,
constrained deadlines
).
Specifically, each periodic task
τ
i
is characterized by four
parameters:
A phase Φ
i
;
A worst-case computation time
C
i
(constant for each instance);
A relative deadline
D
i
(constant for each instance);
A period
T
i
.
These parameters are illustrated in Figure 4.14 and have the following relationships:
⎧
⎨
C
i
≤
T
i
r
i,k
=Φ
i
+(
k
D
i
≤
−
1)
T
i
⎩
d
i,k
=
r
i,k
+
D
i
.
T
i
C
i
τ
i
D
i
d
i
Figure 4.14
Task parameters in Deadline-Monotonic scheduling.
Search WWH ::
Custom Search