Schedulability Of Fixed-priority Systems Containing Deferrable Server(s)
4, which are the replenishment times of the server before the deadline 6.5 of the first job in T2, in addition to 3.5, which is the period of T1, and 6.5. As expected, both tasks are schedulable according to this test.
Because of Lemma, we can also determine the schedulability of the fixed-priority periodic tasks by examining a segment of the schedule immediately after a critical instant of the periodic tasks. (The schedule in Figure 7–4 is an example.) Similarly, using the expression of wi (t) given by Eq. (7.1), we can find the maximum response time of each periodic task when scheduled together with a deferrable server by solving the equation wi (t) = t iteratively.
Schedulable Utilization. There is no known schedulable utilization that assures the schedulability of a fixed-priority system in which a deferrable server is scheduled at an arbitrary priority. The only exception is the special case when the period ps of the deferrable server is shorter than the periods of all periodic tasks and the system is scheduled rate-monotonically. In particular, the following theorem gives the schedulable utilization of a special class of systems [LeSS, StLS].
THEOREM 7.2. Consider a system of n independent, preemptable periodic tasks whose periods satisfy the inequalities ps < p1 < p2 < · · · < pn < 2ps and pn >
ps es and whose relative deadlines are equal to their respective periods. This system is schedulable rate-monotonically with a deferrable server (ps , es) if their total utilization is less than or equal to
where us is the utilization es/ps of the server.
The proof is similar to that of Theorem 6.5 and is left to you as an exercise (Problem 7.7). When the server’s period is arbitrary, we can use the schedulable utilization URM(n) given by Eq. (6.10) to determine whether each periodic task Ti is schedulable if the periodic tasks and the server are scheduled rate-monotonically and the relative deadlines of the periodic tasks are equal to their respective periods. To see how, we focus on the feasible interval (ri,c, ri,c Di ] of a job Ji,c in any periodic task Ti that has a lower priority than the server. As far as this job is concerned, the server behaves just like a periodic task (ps , es), except that the server may execute for an additional es units of time in the feasible interval of the job. We can treat these es units of time as additional “blocking time” of the task Ti : Ti is surely schedulable if
where Ui is the total utilization of the i highest-priority tasks in the system.
As an example, consider a deferrable server with period 4 and execution budget 0.8. It is scheduled rate-monotonically with three preemptable periodic tasks T1 = (3, 0.6), T2 = (5.0, 0.5), and T3 = (7, 1.4). T1 has a higher priority than the server and is not affected by the server. To determine whether T2 is schedulable, we compute U2 us es/p2. The value of this expression is 0.66. Since it is less than URM(3) = 0.757, we know that T2 is schedulable. To check whether T3 is schedulable in the same manner, we find that U us es/p3 = 0.814 exceeds the schedulable utilization of the RM algorithm for four tasks. This sufficient but not necessary test says that the task T3 may not be schedulable. However, if we use the right-hand side of Eq. (7.1) as the time-demand function of T3 and do a time-demand analysis, we will find that T3 is in fact schedulable.
Deferrable Server with Arbitrary Fixed Priority. You recall that any budget of a deferrable server that remains unconsumed at the end of each server period is lost. For this reason, when the server is not scheduled at the highest priority, the maximum amount of processor time it can consume (and hence is demanded) depends not only on the release times of all the periodic jobs relative to replenishment times of the server, but also on the execution times of all the tasks. For some combinations of task and server parameters, the time demand of the server in a time interval of length t may never be as large as es (t − es)/ps es , the terms we included in the right-hand side of Eq. (7.1). However, these terms do give us an upper bound to the amount of time demanded by the server and allows us to account for the effect of the server on the schedulability of lower-priority tasks correctly if not accurately. From this observation, we can conclude that in a system where the deferrable server is scheduled at an arbitrary priority, the time-demand function of a task Ti with a lower-priority than the server is bounded from above by the expression of wi (t) in Eq. (7.1). Using this upper bound, we make the time-demand analysis method a sufficient schedulability test for any fixed-priority system containing one deferrable server.
A system may contain several aperiodic tasks. We may want to use different servers to execute different aperiodic tasks. By adjusting the parameters and priorities of the servers, the response times of jobs in an aperiodic task may be improved at the expense of the response times of jobs in other aperiodic tasks. It is easy to see that when there is more than one deferrable server, we can take the effect of each server into account by including its processortime demand in the computation of the time-demand function of each lower-priority periodic task in the same manner. Specifically, the time-demand function wi (t) of a periodic task Ti with a lower priority than m deferrable servers, each of which has period ps,k and execution budget es,k, is given by
