The analysis of deadline monotonic schedulability is similar to that given above for the EDF case, with a few critical differences.
Sketch of proof:
The full analysis is given in [5]. We first consider the
case where , and then consider the special case where
.
Looking at Figure 5, one can see that
is
maximized for
when
and
.
For the case it is not possible to have
.
Since
is the problem job, it must have a deadline at the
end of the busy window. Instead of the situation
in Figure 5, for
the densest
packing of jobs is as shown in Figure 6.
That is, the difference for this case
is that the length
of the tail is
instead of
.
The number of periods of spanning the busy
window in both is
, and the
maximum contribution of the head is
. All differences are
accounted for by the fact that
instead of
.
The above lemma leads to the following DM schedulability test.
The proof is given in [5]. It is similar to that of Theorem 12, but using the appropriate lemmas for DM scheduling.
Corollary 19 is proved by repeating the proof of
Theorem 18, adapted to fit the definition of .
If we assume the deadline of each task is equal to its period the schedulability condition of Corollary 19 for deadline monotone scheduling becomes a lower bound on the minimum achievable utilization for rate monotone scheduling.
The proof, which is given in [5], is similar to that of Theorem 18.
Analogously to
Funk, Goossens, and Baruah[7],
Andersson, Baruah, and Jonsson[2]
defined a periodic task set
to be a light system on
processors if it satisfies the following properties:
They then proved the following theorem.
The above result is a special case of our
Corollary 20. If we take
,
it follows that the system
of tasks is schedulable to meet deadlines if
Baruah and Goossens[6] proved the following similar result.
This is a slightly weakened special case of our Corollary 20.
For , it follows
that the system of tasks is schedulable to meet deadlines if