FIXED-PRIORITY SERVERS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 139

5.5 PRIORITY EXCHANGE

The Priority Exchange (PE) algorithm is a scheduling scheme introduced by Lehoczky,
Sha, and Strosnider [LSS87] for servicing a set of soft aperiodic requests along with
a set of hard periodic tasks. With respect to DS, PE has a slightly worse performance
in terms of aperiodic responsiveness but provides a better schedulability bound for the
periodic task set.

Like DS, the PE algorithm uses a periodic server (usually at a high priority) for ser-
vicing aperiodic requests. However, it differs from DS in the manner in which the
capacity is preserved. Unlike DS, PE preserves its high-priority capacity by exchang-
ing it for the execution time of a lower-priority periodic task.

At the beginning of each server period, the capacity is replenished at its full value. If
aperiodic requests are pending and the server is the ready task with the highest priority,
then the requests are serviced using the available capacity; otherwise C s is exchanged
for the execution time of the active periodic task with the highest priority.

When a priority exchange occurs between a periodic task and a PE server, the periodic
task executes at the priority level of the server while the server accumulates a capacity
at the priority level of the periodic task. Thus, the periodic task advances its execution,
and the server capacity is not lost but preserved at a lower priority. If no aperiodic re-
quests arrive to use the capacity, priority exchange continues with other lower-priority
tasks until either the capacity is used for aperiodic service or it is degraded to the pri-
ority level of background processing. Since the objective of the PE algorithm is to
provide high responsiveness to aperiodic requests, all priority ties are broken in favor
of aperiodic tasks.

Figure 5.14 illustrates an example of aperiodic scheduling using the PE algorithm. In
this example, the PE server is created with a period T s =5and a capacity C s =1.
Since the aperiodic time managed by the PE algorithm can be exchanged with all
periodic tasks, the capacity accumulated at each priority level as a function of time is
represented in overlapping with the schedule of the corresponding periodic task. In
particular, the first timeline of Figure 5.14 shows the aperiodic requests arriving in the
system, the second timeline visualizes the capacity available at PE's priority, whereas
the third and the fourth ones show the capacities accumulated at the corresponding
priority levels as a consequence of the priority exchange mechanism.

At time t =0, the PE server is brought at its full capacity, but no aperiodic requests
are pending, so C s is exchanged with the execution time of task τ 1 . As a result, τ 1
advances its execution and the server accumulates one unit of time at the priority level