Total Bandwidth Server Algorithm

Total Bandwidth Server Algorithm: To motivate the total bandwidth server algorithm [SpBu], let us return to the example in Figure 7–13. Suppose that A3 were to arrive at time 14 instead. Since 14 is before the current server deadline 15, the scheduler must wait until time 15 to replenish the budget of the constant utilization server. A3 waits in the interval from 14 to 15, while the processor idles! Clearly, one way to improve the responsiveness of the server is to replenish its budget at time 14. This is exactly what the total bandwidth server algorithm does.

Specifically, the total bandwidth server algorithm improves the responsiveness of a constant utilization server by allowing the server to claim the background time not used by periodic tasks. This is done by having the scheduler replenish the server budget as soon as the budget is exhausted if the server is backlogged at the time or as soon as the server becomes backlogged. We now show that a constant utilization server works correctly if its budget is replenished in this aggressive manner. In particular, we can change the replenishment rules as follows and get a total bandwidth server. You can see that the rules of a total bandwidth server are even simpler than the rules of a constant utilization server. Replenishment Rules of a Total Bandwidth Server of size ˜ us
R1 Initially, es = 0 and d = 0.
R2 When an aperiodic job with execution time e arrives at time t to an empty aperiodic job queue, set d to max(d, t) e/ ˜ us and es = e.
R3 When the server completes the current aperiodic job, the job is removed from its queue.
(a) If the server is backlogged, the server deadline is set to d e/ ˜ us, and es = e.
(b) If the server is idle, do nothing.

Comparing a total bandwidth server with a constant utilization server, we see that for a given set of aperiodic jobs and server size, both kinds of servers have the same sequence of deadlines, but the budget of a total bandwidth server may be replenished earlier than that of a constant utilization server. As long as a total bandwidth server is backlogged, it is always ready for execution. In the above example, this means that the server’s budget is replenished at 6.9 and, if A3 were to arrive at 14, at 14, and the deadline of the server is 15 and 23.5, respectively, A3 would be completed at time 17.5 if it were executed by a total bandwidth server but would be completed at 19 by a constant bandwidth server.

Clearly, a total bandwidth server does not behave like a sporadic task with a constant instantaneous utilization. To see why it works correctly, let us examine how the server affects periodic jobs and other servers when its budget is set to e at a time t before the current server deadline d and its deadline is postponed to the new deadline d = d e/ ˜ us . In particular, we compare the amount of processor time demanded by the server with the amount of time demanded by a constant utilization server of the same size ˜ us before the deadline di,k of a periodic job Ji,k whose deadline is later than the server’s new deadline d. (We do not need to consider periodic jobs with deadlines earlier than d because they have higher priorities than the server.) If the job Ji,k is ready at t , then the amounts of time consumed by both servers are the same in the interval from t to di,k. If Ji,k is not yet released at t , then the time demanded by the total bandwidth server in the interval (ri,k , d] is less than the time demanded by the constant utilization server because the total bandwidth server may have executed before ri,k and has less budget in this interval. In any case, the total bandwidth server will not cause a job such as Ji,k to miss its deadline if the constant utilization server will not. By a similar argument, we can show that a total bandwidth server will not cause another server to become unschedulable if a constant utilization server of the same size will not.

We state the correctness of constant utilization and total bandwidth server algorithms in the following corollaries so we can refer to them later. In the statement of the corollaries, we use the expression “a server meets its deadline” (or “a server is schedulable,” as we said in the last paragraph). By this, we mean that the budget of the server is always consumed by the deadline set at the time when the budget was replenished. If we think of the server as a sporadic task and each replenishment of the budget of e units as the release of a sporadic job that has this execution time and the corresponding deadline, then every job in this sporadic task completes in time.