next up previous
Next: Parallelism between PSA and Up: Background on constant bandwidth Previous: Background on constant bandwidth

The Constant Bandwidth Server

Each aperiodic server with a bounded demanded bandwidth Bi can be used for realizing a Constant Bandwidth allocation, but CBS permits hard real-time guarantee if tasks' parameters are known. The CBS assigns each job an initial deadline, which is postponed each time the task is demanding more than the reserved bandwidth. The server is described by two parameters Qs and Ts, where Ts is the server period, Qs is the service time assigned to the task in each period, and $U_s = \frac{Q_s}{T_s}$ is the server demanded bandwidth. Deadlines are assigned to jobs as follows. When a new request arrives, the server checks whether the last assigned deadline can be used, otherwise it assigns to the request an initial deadline equal to ri,j + Ts. Each time the job executes for Qs time units, its scheduling deadline is postponed by Ts ( a complete description of the algorithm can be found in [1]).

If Ci and Ti are the Worst Case Execution Time and the minimum interarrival time of task $\tau_i$, using a CBS with parameters (Qs=Ci,Ts=Ti) a bandwidth $B_s=\frac{Q_s}{T_s}=\frac{C_i}{T_i}$ is reserved, hence it is guaranteed that the assigned deadline will not be postponed (hard guarantee), otherwise only a stochastic guarantee can be performed.

Using a CBS to implement Constant Bandwidth resource allocation, the following lemma can be proved (see [1]):

Lemma 1   If a task $\tau_i$ served by a CBS with parameters (Qs,Ts) is active in [t0,t] and d is a scheduling deadline assigned by the CBS (with $t_0 \leq d \leq t$), then

 \begin{displaymath}executed_i(d,t) \geq \left \lfloor \frac{t-d}{T_h} \right \rfloor Q_h.
\end{displaymath} (6)

Equation 6 expresses the demanded time when a CBS is used.

In [5,6] Deng and Liu use a similar mechanism to schedule multiple applications in an open environment, realizing the resource allocations with a Total Bandwidth Server (TBS) [13,14] or a similar aperiodic server (the Constant Utilization Server). The problem with these servers is that they cannot be used when tasks' WCETs are not known, so an error in the WCET estimation would compromise the correct behavior of the system.

The Resource Reservation abstraction [12] does not introduce the concept of reserved bandwidth, but it is similar to CBS in that it realizes a CBA. Like CBS, it allows to perform hard guarantee, but, being based on fixed priority (DM), it performs worse in overload situations (see Figure 1). In facts, when a task executes for Ci time units in its period Ti and does not complete(the reservation is depleted), the rest of the task is scheduled in background. Using dynamic priority, CBS schedules the "depleted tasks" by postponing deadlines.

  
Figure 1: Resource Reservation and Constant Bandwidth
\begin{figure}\centerline{\psfig{file=rrcfr.eps,width=10cm}}
\end{figure}


next up previous
Next: Parallelism between PSA and Up: Background on constant bandwidth Previous: Background on constant bandwidth

1999-02-16