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

periodic tasks. At time t =0, the processor is assigned to task τ 1 , which is the
highest-priority task according to RM. At time t =1, τ 1 completes its execution and
the processor is assigned to PS. However, since no aperiodic requests are pending, the
server suspends itself and its capacity is used by periodic tasks. As a consequence, the
request arriving at time t =2cannot receive immediate service but must wait until the
beginning of the second server period ( t =5). At this time, the capacity is replenished
at its full value ( C s =2) and used to serve the aperiodic task until completion. Note
that, since the capacity has been totally consumed, no other aperiodic requests can be
served in this period; thus, the server becomes idle.

The second aperiodic request receives the same treatment. However, note that since
the second request only uses half of the server capacity, the remaining half is discarded
because no other aperiodic tasks are pending. Also note that, at time t =16, the third
aperiodic request is preempted by task τ 1 , and the server capacity is preserved.

5.3.1 SCHEDULABILITY ANALYSIS

We first consider the problem of guaranteeing a set of hard periodic tasks in the pres-
ence of soft aperiodic tasks handled by a Polling Server. Then we show how to derive
a schedulability test for firm aperiodic requests.

The schedulability of periodic tasks can be guaranteed by evaluating the interference
introduced by the Polling Server on periodic execution. In the worst case, such an
interference is the same as the one introduced by an equivalent periodic task having
a period equal to T s and a computation time equal to C s . In fact, independently of
the number of aperiodic tasks handled by the server, a maximum time equal to C s is
dedicated to aperiodic requests at each server period. As a consequence, the processor
utilization factor of the Polling Server is U s = C s /T s , and hence the schedulability of
a periodic set with n tasks and utilization U p can be guaranteed if

U p + U s ≤ U lub ( n +1) .

If periodic tasks (including the server) are scheduled by RM, the schedulability test
becomes

n

C i
T i

+ C s ( n +1)[2 1 / ( n +1)

T s ≤

− 1] .

i =1

Note that more Polling Servers can be created and execute concurrently on different
aperiodic task sets. For example, a high-priority server could be reserved for a subset
of important aperiodic tasks, whereas a lower-priority server could be used to handle
less important requests. In general, in the presence of m servers, a set of n periodic