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

All periodic tasks τ i : i =1 ,...,n have hard deadlines and their schedulability
must be guaranteed off line.

All aperiodic tasks J i : i =1 ,...,m do not have deadlines and must be sched-
uled as soon as possible, but without jeopardizing the schedulability of the peri-
odic tasks.

Each periodic task τ i has a period T i , a computation time C i , and a relative
deadline D i equal to its period.

All periodic tasks are simultaneously activated at time t =0.

Each aperiodic task has a known computation time but an unknown arrival time.

Some of the assumptions listed above can easily be relaxed to handle periodic tasks
with arbitrary phasing and relative deadlines different from their periods. Shared re-
sources can also be included in the model assuming an access protocol like the Stack
Resource Policy [Bak91]. In this case, the schedulability analysis has to be conse-
quently modified to take into account the blocking factors due to the mutually ex-
clusive access to resources. For some algorithms, the possibility of handling firm
aperiodic tasks is also discussed.

The rest of the chapter is organized as follows. In the next two sections, we discuss
how two fixed-priority service algorithms - namely, the Priority Exchange and the
Sporadic Server algorithms - can be extended to work under the EDF priority assign-
ment. Then, we introduce three new aperiodic service algorithms, based on dynamic
deadline assignments, that greatly improve the performance of the previous fixed-
priority extensions. One of these algorithms, the EDL server, is shown to be optimal,
in the sense that it minimizes the average response time of aperiodic requests.

6.2 DYNAMIC PRIORITY EXCHANGE SERVER

The Dynamic Priority Exchange (DPE) server is an aperiodic service technique pro-
posed by Spuri and Buttazzo [SB94, SB96] that can be viewed as an extension of the
Priority Exchange server [LSS87], adapted to work with a deadline-based scheduling
algorithm. The main idea of the algorithm is to let the server trade its runtime with the
runtime of lower-priority periodic tasks (under EDF this means a longer deadline) in
case there are no aperiodic requests pending. In this way, the server runtime is only
exchanged with periodic tasks but never wasted (unless there are idle times). It is sim-
ply preserved, even if at a lower priority, and it can be later reclaimed when aperiodic
requests enter the system.