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

t t

1 2

Figure 6.5 Computational demand of a periodic task in [ t 1 ,t 2 ] .

Note that as long as the server capacity is greater than zero, all pending aperiodic
requests are executed with the same deadline. In Figure 6.4 this happens at time t =
14, when the last two aperiodic requests are serviced with the same deadline d s =20.

6.3.1 SCHEDULABILITY ANALYSIS

To prove the schedulability bound for the Dynamic Sporadic Server, we first show that
the server behaves like a periodic task with period T s and execution time C s .

Given a periodic task τ i , we first note that in any generic interval [ t 1 ,t 2 ] such that τ i
is released at t 1 , the computation time scheduled by EDF with deadline less than or
equal to t 2 is such that (see Figure 6.5)

t 2 − C i .

t 1

C i ( t 1 ,t 2 ) ≤

T i

The following Lemma shows that the same property is true for DSS.

Lemma 6.1 In each interval of time [ t 1 ,t 2 ] , such that t 1 is the time at which DSS
becomes ready (that is, an aperiodic request arrives and no other aperiodic requests
are being served), the maximum aperiodic time executed by DSS in [ t 1 ,t 2 ] satisfies the
following relation:

t 2 − C s .

t 1

C ape ≤

T s

Proof. Since replenishments are always equal to the time consumed, the server
capacity is at any time less than or equal to its initial value. Also, the replenishment
policy establishes that the consumed capacity cannot be reclaimed before T s units of
time after the instant at which the server has become ready. This means that, from the
time t 1 at which the server becomes ready, at most C s time can be consumed in each
subsequent interval of time of length T s ; hence, the thesis follows.