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

6.4 TOTAL BANDWIDTH SERVER

Looking at the characteristics of the Sporadic Server algorithm, it can be easily seen
that, when the server has a long period, the execution of the aperiodic requests can be
delayed significantly. This is due to the fact that when the period is long, the server is
always scheduled with a far deadline. And this is regardless of the aperiodic execution
times.

There are two possible approaches to reduce the aperiodic response times. The first
is, of course, to use a Sporadic Server with a shorter period. This solution, however,
increases the run-time overhead of the algorithm because, to keep the server utilization
constant, the capacity has to be reduced proportionally, but this causes more frequent
replenishments and increases the number of context switches with the periodic tasks.

A second approach, less obvious, is to assign a possible earlier deadline to each ape-
riodic request. The assignment must be done in such a way that the overall processor
utilization of the aperiodic load never exceeds a specified maximum value U s . This is
the main idea behind the Total Bandwidth Server (TBS), a simple and efficient aperi-
odic service mechanism proposed by Spuri and Buttazzo [SB94, SB96]. The name of
the server comes from the fact that, each time an aperiodic request enters the system,
the total bandwidth of the server is immediately assigned to it, whenever possible.

In particular, when the k th aperiodic request arrives at time t = r k , it receives a
deadline

d k =max( r k ,d k− 1 )+ C k
U s

,

where C k is the execution time of the request and U s is the server utilization factor
(that is, its bandwidth). By definition d 0 =0. Note that in the deadline assignment
rule the bandwidth allocated to previous aperiodic requests is considered through the
deadline d k− 1 .

Once the deadline is assigned, the request is inserted into the ready queue of the sys-
tem and scheduled by EDF as any other periodic instance. As a consequence, the
implementation overhead of this algorithm is practically negligible.

Figure 6.6 shows an example of an EDF schedule produced by two periodic tasks with
periods T 1 =6, T 2 =8and execution times C 1 =3, C 2 =2, and a TBS with

utilization U s =1 U p =0 . 25. The first aperiodic request arrives at time t =3and

is serviced with deadline d 1 = r 1 + C 1 /U s =3+1 / 0 . 25 = 7. Being d 1 the earliest
deadline in the system, the aperiodic request is executed immediately. Similarly, the
second request, which arrives at time t =9, receives a deadline d 2 = r 2 + C 2 /U s =
17, but it is not serviced immediately, since at time t =9there is an active periodic

−