DYNAMIC PRIORITY SERVERS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 180

EDL

ω (t)

+3

+1 +1 +1 +3

3

4

IPE

0 2 4 6 8 10 12 14 16 18 20 22 24

3

τ

1

0 6 12 18 24

3

τ

2

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

Figure 6.9 Improved Priority Exchange server example.

6.6.1 SCHEDULABILITY ANALYSIS

In order to analyze the schedulability of an IPE server, it is useful to define a trans-
formation among schedules similar to that defined for the DPE server. In particular,
given a schedule σ produced by the IPE algorithm, we build the schedule σ in the

following way:

Each execution of periodic instances during deadline exchanges (that is, increase
in the corresponding aperiodic capacity) is postponed until the capacity decreases.

All other executions of periodic instances are left as in σ .

In this case, the server is not substituted with another task. Again σ is well defined
and is invariant; that is, it does not depend on σ but only on the periodic task set.
Moreover, σ is the schedule produced by EDL applied to the periodic task set (com-
pare Figure 6.7 with Figure 6.9). The optimal schedulability is stated by the following
theorem:

Theorem 6.6 (Spuri, Buttazzo) Given a set of n periodic tasks with processor uti-
lization U p and the corresponding IPE server (the parameters of the server depend on
the periodic task set), the whole set is schedulable if and only if

U p ≤ 1

(the server automatically allocates the bandwidth 1 − U p to aperiodic requests).