SKEDSOFT

Schedulability of Fixed-Priority Systems Containing Deferrable Server(s): You may question the need of a background server in the above example. The schedule in Figure 7–3 may lead us to wonder whether we can get the same improved response by making the execution budget of the server bigger, for example, let it be 1.5 instead of 1.0. As it turns out, if we were to make the server budget bigger, the task (6.5, 0.5) would not be schedulable.

This fact is shown by Figure 7–4. Suppose that an aperiodic job with execution time 3.0 or more arrives to an empty aperiodic job queue at time t0, 1 unit of time before the replenishment time of the server (3, 1). At t0, the server has 1 unit of budget. The server begins to execute from time t0. Its budget is replenished at t0 1, and it continues to execute as shown. Suppose that a job of each of the periodic tasks is released at time t0. For this combination of release

times, the task with period 3.5 would not complete in time if the budget of the server were bigger than 1.0. Since we cannot be sure that this combination of release times can never occur, the budget of the server must be chosen based the assumption that this combination can occur. This consideration limits the size of the server. This example illustrates the condition under which a critical instant of a periodic task occurs in a system containing a deferrable server when all tasks have fixed priorities and the deferrable server has the highest priority. Lemma 7.1 [LeSS, StLS] stated below follows straightforwardly from Theorem 6.5.

LEMMA . In a fixed-priority system in which the relative deadline of every independent, preemptable periodic task is no greater than its period and there is a deferrable server (ps , es) with the highest priority among all tasks, a critical instant of every periodic task Ti occurs at time t0 when all the following are true.
1. One of its jobs Ji,c is released at t0.
2. A job in every higher-priority task is released at the same time.
3. The budget of the server is es at t0, one or more aperiodic jobs are released at t0, and they keep the server backlogged hereafter.
4. The next replenishment time of the server is t0 es .

Figure 7–5 shows the segment of a fixed-priority schedule after a critical instant t0. Task TDS is the deferrable server (ps , es). As always, the other tasks are indexed in decreasing order of their priorities. As far as the job Ji,c that is released at t0 is concerned, the demand for processor time by each of the higher-priority tasks in its feasible interval (ri,c, ri,c Di ] is the largest when (1) and (2) are true. When (3) and (4) are true, the amount of processor time consumed by the deferrable server in the feasible interval of Ji,c is equal to es (Di − es)/ps    es , and this amount the largest possible.

Time-Demand Analysis Method. We can use the time-demand method to determine whether all the periodic tasks remain schedulable in the presence of a deferrable server (ps , es). For a job Ji,c in Ti that is released at a critical instant t0, we add the maximum amount es (t − e_s)/p_s ]   es of processor time demanded by the server at time t units after t0 into the right-hand side of Eq. (6.18). Hence, the time-demand function of the task Ti is given by

when the deferrable server (ps , es) has the highest priority.
To determine whether the response time of Ti ever exceeds its relative deadline Di in the case of Dk ≤ pk for all k = 1, 2, . . . , i , we check whether wi (t) ≤ t is satisfied at any of the values of t that are less than or equal to Di . Again, we only need to check at values of t that are integer multiples of pk for k = 1, 2, . . . , i −1 and at Di . In addition, since wi (t) also increases at the replenishment times of the server at or before the deadline of Ji,c (i.e., at es , es ps , es 2ps , . . . es (Di − es)/psps ), we also need to check whether wi (t) ≤ t at these values of t . The response time of Ti is always equal to or less than Di if the time supply t ever becomes equal to or larger than the time demand wi (t) at any of these values of t . It is also easy to modify the time-demand analysis method for periodic tasks whose response times are longer than the respective periods to account for the effect of a deferrable server. When the server has the highest priority, we add the time demand of the server (which is equal to es (t − es)/ps    es ) to the expression of wi, j (t) given by Eq. (6.19). Figure 7–6 shows the time-demand functions of T1 and T2 in the system shown in Figure 7–3. To determine whether T2 is schedulable, we must check whether wi (t) ≤ t at 1 and