DYNAMIC PRIORITY SERVERS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 189

6.9 THE CONSTANT BANDWIDTH SERVER

In this section we present a novel service mechanism, called the Constant Bandwidth
Server (CBS), which efficiently implements a bandwidth reservation strategy. As the
DSS, the Constant Bandwidth Server guarantees that, if U s is the fraction of processor
time assigned to a server (i.e., its bandwidth), its contribution to the total utilization
factor is no greater than U s , even in the presence of overloads. Note that this prop-
erty is not valid for a TBS, whose actual contribution is limited to U s only under the
assumption that all the served jobs execute no more than the declared WCET. With
respect to the DSS, however, the CBS shows a much better performance, comparable
with the one achievable by a TBS.

The basic idea behind the CBS mechanism can be explained as follows: when a new
job enters the system, it is assigned a suitable scheduling deadline (to keep its de-
mand within the reserved bandwidth) and it is inserted in the EDF ready queue. If
the job tries to execute more than expected, its deadline is postponed (i.e., its priority
is decreased) to reduce the interference on the other tasks. Note that by postponing
the deadline, the task remains eligible for execution. In this way, the CBS behaves as
a work conserving algorithm, exploiting the available slack in an efficient (deadline-
based) way, thus providing better responsiveness with respect to non-work conserving
algorithms and to other reservation approaches that schedule the extra portions of jobs
in background, as proposed by Mercer, Savage, and Tokuda [MST93, MST94a].

If a subset of tasks is handled by a single server, all the tasks in that subset will share
the same bandwidth, so there is no isolation among them. Nevertheless, all the other
tasks in the system are protected against overruns occurring in the subset.

In order not to miss any hard deadline, the deadline assignment rules adopted by the
server must be carefully designed. The next section precisely defines the CBS al-
gorithm, and formally proves its correctness for any (known or unknown) execution
request and arrival pattern.

6.9.1 DEFINITION OF CBS

The CBS can be defined as follows:

A CBS is characterized by a budget c s and by an ordered pair ( Q s ,T s ), where Q s
is the maximum budget and T s is the period of the server. The ratio U s = Q s /T s
is denoted as the server bandwidth.

At each instant, a fixed deadline d s,k is

associated with the server. At the beginning d s, 0 =0.