Performance Of Bandwidth-preserving Server Algorithms
Performance of Bandwidth-Preserving Server Algorithms
Because no job of any accepted sporadic task is rejected by the scheduler, it is possible for a sporadic task to overload the processor. For this reason, the scheduler must provide firewall protection not only to tasks and jobs that have hard deadlines, but also to each existing sporadic task so the performance guarantee of the task will not be violated when other sporadic tasks misbehave. The bandwidth-preserving server algorithms described in earlier sections are designed to provide such protection and, therefore, are ideally suited for scheduling sporadic tasks with soft deadlines.
We focus here on systems which use a bandwidth-preserving server to execute each sporadic task. During an acceptance test, the scheduler can use an appropriate schedulability test to determine the maximum schedulable size of the server chosen to execute the new task. Hence, whether a new sporadic task is acceptable is reduced to the question of whether its required performance can be achieved when its server has the maximum schedulable size. This question can be answered by analyzing the new sporadic task alone without regard to other tasks.
We now ask what is the maximum response time of jobs in a sporadic task that is executed by a constant utilization, total bandwidth, or WFQ server in a deadline-driven system. Clearly, the size ˜ u of the server must at least be equal to the average utilization u (i.e., the ratio of the average execution time to the average interarrival time) of the sporadic task S. Queueing theory tells us that even when ˜ u = u, the average response time of the jobs in S is unbounded if their execution times and interarrival times are not otherwise constrained.
(e, p, p, I)-Constrained Sporadic Tasks. Suppose that the sporadic task fits the FeVe model: S = (e, p, p, I ), and u = e/p. Specifically, we suppose that the number of jobs in S released in any interval of length I is never more than I /p. (In the remainder of this section, by jobs, we mean jobs in S and will omit this reminder most of the time.) If the server size ˜ u is equal to u and the server is schedulable, the response time of every job is never more than p if their interarrival times are at least p. Because their interarrival times can be smaller than p, their response times can be larger than p. The question we want to answer here is how large their response times can be when the jobs are executed in FIFO order. Corollary 7.7 tells us as long as the total server size is no greater than 1, we can answer this question without regard to jobs executed by other servers. To find the maximum possible response time W of all jobs in S, we look at a busy interval of the server that begins at the arrival time t0 of the first of a bursty sequence of X jobs. By their arrivals being bursty, we mean that the interarrival times of these X jobs are all
equal to the minimum possible value p. Because S meets the (e, p, p, I ) constraint, X ≤ I /p. The solid line in Figure 7–23 shows the number of arrivals of jobs in S as a function of time from t0, and the dotted line in the figure shows the number of completions of these jobs. The vertical difference between the two lines at any time gives the number of jobs waiting to be executed at the time. It is evident that the response time of the Xth job in the busy interval is larger than the response times of all other jobs executed in the busy interval.
To find the response time of the Xth job (and hence the maximum response time of the sporadic task S), we note that immediately before the release time of the Xth job in S, there are no more than (X − 1) − (X − 1)p/p jobs waiting to be completed. Since it may take the server p units of time to complete each job, maximum response time of the Xth job is bounded from above by
The upper bound W for the case of p < p is loose because we obtain the expression above by replacing the floor function x by its lower bound x − 1. However, it differs from the tight bound by no more than p because the maximum response time can be as large as p I (1 − p/p), which is obtained by replacing x by x.
(1/p, I/p)-Leaky Bucket Constrained Tasks. An important special case is when the sporadic task S models the transmission of a packet stream over a network. In this case, the maximum execution time of all jobs is the time required to transmit a maximum size packet. For simplicity, we let this time be 1. Suppose that the task S = (1, p, p, I ) also satisfies the (1/p, I /p) leaky bucket constraint.
In this case, the largest response time occurs when the leaky bucket is full at the beginning t0 of a busy interval of the server. Starting from t0, one job with execution time 1 is removed from the bucket every p units of time, while it is being filled at the rate of one job every p units of time. At the time the Xth job is ready for transmission, the bucket is empty. In other words,
which gives us
The above observations allow us to conclude that the maximum response time of all jobs in S is bounded from above by
