Sporadic Servers

SPORADIC SERVERS
We have just seen that a deferrable server may delay lower-priority tasks for more time than a period task with the same period and execution time. This section describes a class of bandwidth-preserving servers, called sporadic servers [SpSL, GhBa], that are designed to improve over a deferrable server in this respect. The consumption and replenishment rules of sporadic server algorithms ensure that each sporadic server with period ps and budget es never demands more processor time than the periodic task (ps , es) in any time interval. Consequently, we can treat the sporadic server exactly like the periodic task (ps , es) when we check for the schedulability of the system. A system of periodic tasks containing a sporadic server may be schedulable while the same system containing a deferrable server with the same parameters is not.

For example, we mentioned earlier that it is not possible to make the execution time of the deferrable server in Figure 7–3 larger than 1.0 when the system is scheduled ratemonotonically. In contrast, if we replace the deferrable server by a sporadic server, we can increase the server execution time to 1.25, while keeping its period at 3.0, or decrease its period to 2.5, while keeping its execution time at 1.0. You may want to convince yourself that a sporadic server with these sets of parameters will be able to complete the aperiodic job at 6.25 and 6.0, respectively, instead of 6.5 accomplished by the deferrable server in Figure 7–3. With slight abuse of the notation, we will sometimes refer to a sporadic server with period ps and budget es as the periodic task Ts = (ps , es) and say that a server job is released when the server becomes eligible. Different kinds of sporadic servers differ in their consumption and replenishment rules. More complicated rules allow a server to preserve its budget for a longer time, replenish the budget more aggressively, and, in a deadline-driven system, execute at a higher priority. By using different rules, you can trade off the responsiveness of the server for the overhead in its implementation.

Sporadic Server in Fixed-Priority Systems: We first confine our attention to fixed-priority systems. For the moment, we assume that there is only one sporadic server in a fixed-priority system T of n independent, preemptable periodic tasks. The server has an arbitrary priority πs . (If the server has the same priority as some periodic task, the tie is always broken in favor of the server.) We use TH to denote the subset of periodic tasks that have higher priorities than the server. We say that the system T of periodic tasks (or the higher-priority subsystem TH) idles when no job in T (or TH) is ready for execution; T (or TH) is busy otherwise. By definition, the higher-priority subsystem remains busy in any busy interval of TH. Finally, a server busy interval is a time interval which begins when an aperiodic job arrives at an empty aperiodic job queue and ends when the queue becomes empty again.

Since our focus here is on the consumption and replenishment rules of the server, we assume that we have chosen the parameters ps and es and have validated that the periodic task (ps , es) and the system T are schedulable according to the fixed-priority algorithm used by the system. When doing the schedulability test, we assume that the relative deadline for consuming the server budget is finite but arbitrary. In particular, we allow this deadline to be larger than ps . During an interval when the aperiodic job queue is never empty, the server behaves like the periodic task (ps , es) in which some jobs may take longer than one period to complete.
We state below the consumption and replenishment rules that define a simple sporadic server. In the statement, we use the following notations. (Their names may not make sense for now. We will return shortly to explain why they are called by these names and to discuss the rationales behind the consumption and replenishment rules.)

• t_r denotes the latest (actual) replenishment time.
• t _f denotes the first instant after tr at which the server begins to execute.
• t_e denotes the latest effective replenishment time.
• At any time t , BEGIN is the beginning instant of the earliest busy interval among the latest contiguous sequence of busy intervals of the higher-priority subsystem TH that started before t . (Two busy intervals are contiguous if the later one begins immediately after the earlier one ends.)
• END is the end of the latest busy interval in the above defined sequence if this interval ends before t and equal to infinity if the interval ends after t .

The scheduler sets tr to the current time each time it replenishes the server’s execution budget. When the server first begins to execute after a replenishment, the scheduler determines the latest effective replenishment time te based on the history of the system and sets the next replenishment time to t_e ps . (In other words, the next replenishment time is ps units away from t_e, as if the budget was last replenished at te and hence the name effective replenishment time.) Simple Sporadic Server. In its simpliest form, a sporadic server is governed by the following consumption and replenishment rules. We call such a server a simple sporadic server. A way to implement the server is to have the scheduler monitor the busy intervals of TH and maintain information on BEGIN and END.

• Consumption Rules of Simple Fixed-Priority Sporadic Server: At any time t after tr , the server’s execution budget is consumed at the rate of 1 per unit time until the budget is exhausted when either one of the following two conditions is true. When these conditions are not true, the server holds its budget.
C1 The server is executing.
C2 The server has executed since tr and END < t .

• Replenishment Rules of Simple Fixed-Priority Sporadic Server:
R1 Initially when the system begins execution and each time when the budget is replenished, the execution budget = es, and tr = the current time.
R2 At time t f , if END = t f , te = max(tr , BEGIN). If END < t f , te = t f . The next replenishment time is set at te ps .
R3 The next replenishment occurs at the next replenishment time, except under the following conditions. Under these conditions, replenishment is done at times stated below.
(a) If the next replenishment time te ps is earlier than t f , the budget is replenished as soon as it is exhausted.
(b) If the system T becomes idle before the next replenishment time te ps and becomes busy again at tb, the budget is replenished at min(te ps , tb).

Rules C1 and R1 are self-explanatory. Equivalently, rule C2 says that the server consumes its budget at any time t if it has executed since tr but at t , it is suspended and the higher-priority subsystem TH is idle. Rule R2 says that the next replenishment time is ps units after tr (i.e., the effective replenishment time te is tr ) only if the higher-priority subsystem TH has been busy throughout the interval (tr , t f ). Otherwise, te is later; it is the latest instant at which an equal or lower-priority task executes (or the system is idle) in (tr , t f ). Figure 7–8 gives an illustrative example. Initially the budget of the server (5, 1.5) is 1.5. It is scheduled rate-monotonically with three periodic tasks: T1 = (3, 0.5), T2 = (4, 1.0), and T3 = (19, 4.5). They are schedulable even when the aperiodic job queue is busy all the time. 1. From time 0 to 3, the aperiodic job queue is empty and the server is suspended. Since it has not executed, its budget stays at 1.5. At time 3, the aperiodic job A1 with execution time 1.0 arrives; the server becomes ready. Since the higher-priority task (3, 0.5) has a job ready for execution, the server and the aperiodic job wait.