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

The idle times of the EDL algorithm can be precomputed off-line and the server can
use them to schedule aperiodic requests, when there are any, or to advance the exe-
cution of periodic tasks. In the latter case, the idle time advanced can be saved as
aperiodic capacity at the priority levels of the periodic tasks executed.

The idea described above is used by the algorithm called Improved Priority Exchange
(IPE) [SB94, SB96]. In particular, the DPE server is modified using the idle times of
an EDL scheduler. There are two main advantages in this approach. First, a far more
efficient replenishment policy is achieved for the server. Second, the resulting server
is no longer periodic, and it can always run at the highest priority in the system. The
IPE server is thus defined in the following way:

The IPE server has an aperiodic capacity, initially set to 0.

At each instant t = e i + kH , with 0 0, a replenishment of Δ i

units of time is scheduled for the server capacity; that is, at time t = e 0 the server
will receive Δ 0

≤ i ≤ p and k ≥

units of time (the two arrays E and D have been defined in the

previous section).

The server priority is always the highest in the system, regardless of any other
deadline.

All other rules of IPE (aperiodic requests and periodic instances executions, ex-
change and consumption of capacities) are the same as for a DPE server.

The same task set of Figure 6.8 is scheduled with an IPE server in Figure 6.9.

Note that the server replenishments are set according to the function ω EDL
τ

, illustrated

in Figure 6.7.

When the aperiodic request arrives at time t =8, one unit of time is immediately
allocated to it by the server. However, other two units are available at the priority
level corresponding to the deadline 12, due to previous deadline exchanges, and are
allocated right after the first one. The last one is allocated later, at time t =12,
when the server receives a further unit of time. In this situation, the optimality of the
response time is kept. As we will show later, there are only rare situations in which
the optimal EDL server performs slightly better than IPE. That is, IPE almost always
exhibits a nearly optimal behavior.