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

5.4 DEFERRABLE SERVER

The Deferrable Server (DS) algorithm is a service technique introduced by Lehoczky,
Sha, and Strosnider [LSS87, SLS95] to improve the average response time of aperiodic
requests with respect to polling service. As the Polling Server, the DS algorithm
creates a periodic task (usually having a high priority) for servicing aperiodic requests.
However, unlike polling, DS preserves its capacity if no requests are pending upon the
invocation of the server. The capacity is maintained until the end of the period, so
that aperiodic requests can be serviced at the same server's priority at anytime, as long
as the capacity has not been exhausted. At the beginning of any server period, the
capacity is replenished at its full value.

The DS algorithm is illustrated in Figure 5.7 using the same task set and the same
server parameters ( C s =2, T s =5) considered in Figure 5.3. At time t =1, when
τ 1 is completed, no aperiodic requests are pending; hence, the processor is assigned to
task τ 2 . However, the DS capacity is not used for periodic tasks, but it is preserved for
future aperiodic arrivals. Thus, when the first aperiodic request arrives at time t =2,
it receives immediate service. Since the capacity of the server is exhausted at time
t =4, no other requests can be serviced before the next period. At time t =5, C s is
replenished at its full value and preserved until the next arrival. The second request
arrives at time t =8, but it is not served immediately because τ 1 is active and has a

higher priority.

Thus, DS provides much better aperiodic responsiveness than polling, since it pre-
serves the capacity until it is needed. Shorter response times can be achieved by cre-
ating a Deferrable Server having the highest priority among the periodic tasks. An
example of high-priority DS is illustrated in Figure 5.8. Note that the second aperi-
odic request preempts task τ 1 , being C s > 0 and T s <T 1 , and it entirely consumes
the capacity at time t =10. When the third request arrives at time t =11, the capacity
is zero; hence, its service is delayed until the beginning of the next server period. The
fourth request receives the same treatment because it arrives at time t =16, when C s
is exhausted.

5.4.1 SCHEDULABILITY ANALYSIS

Any schedulability analysis related to the Rate-Monotonic algorithm has been done
on the implicit assumption that a periodic task cannot suspend itself, but must execute
whenever it is the highest-priority task ready to run (assumption A5 in Section 4.1).
It is easy to see that the Deferrable Server violates this basic assumption. In fact,
the schedule illustrated in Figure 5.8 shows that DS does not execute at time t =0,