next up previous
Next: Weighted Fair Queuing Up: Background on proportional share Previous: Background on proportional share

The ideal model

The objective of the PSA model is to emulate a fluid flow system (in which each task is treated as an infinitely divisible fluid) on a discrete quantum-based allocation system. The ideal scheduling model is the Generalized Processor Sharing (GPS) presented in [10,11]. It can be thought as the limiting form of a Weighted Round Robin policy: each task $\tau_i$ is assigned a weight wi, which determines the minimum bandwidth sharing of the task. Given a task set $\Gamma = \{ \tau_1, ..., \tau_n \}$, if executedi(t1,t2) is the execution time of task $\tau_i$ in an interval [t1,t2], the n tasks share the resource as follows:

 \begin{displaymath}\forall \tau_i \mbox{ active in } [t_1,t_2],
\frac{executed_...
...ed_j(t_1,t_2)} \geq \frac{w_i}{w_j}
\mbox{ } j = 1, 2, ..., n
\end{displaymath} (1)

Equation 1 express that in a GPS system each active task $\tau_i$ executes at least with a rate equal to

\begin{displaymath}F_i = \frac{w_i}{\sum_{\tau_j \in \Gamma} w_j}.\end{displaymath}

The actual execution rate varies with time and is defined as the share of task $\tau_i$:

\begin{displaymath}f_i(t) = \frac{w_i}
{\sum_{\tau_j \in \Gamma_a(t)} w_j}\end{displaymath}

where $\Gamma_a(t)$ is the set of tasks which are active at time t.

As a consequence, the following properties hold:

executedi(t1,t2) $\textstyle \geq$ (t2-t1)Fi (2)
executedi(t1,t2) = $\displaystyle \int_{t_1}^{t_2} f_i(t)dt.$ (3)

In a Proportional Share system, the resource is allocated in discrete time quanta of length Q. A task always acquires the resource at the beginning of a time quantum and can release it either at the end of the quantum (in this case a new request is posted) or before the end of the quantum (in this case the process blocks and must be explicitly re-activated). This is done by dividing each task $\tau_i$ in requests qik having maximum size Q.

Since the allocation is discrete in time, this approach generates an allocation error with respect to the ideal GPS model. Given two active tasks $\tau_i$ and $\tau_j$, the allocation error in the time interval [t1,t2] can be defined as

\begin{displaymath}\epsilon_{i,j} = \left \vert \frac{executed_i(t_1,t_2)}{w_i} - \frac{executed_j(t_1,t_2)}{w_j} \right \vert.\end{displaymath}

With this definition, the minimum theoretical error bound is $H_{i,j} = \frac{Q}{2}(\frac{1}{w_i} + \frac{1}{w_j})$.

Another way of measuring the allocation error of a task is given by the lag. In the ideal GPS system, in the interval [t1,t2] $\tau_i$executes for a time $\int_{t_1}^{t_2} f_i(t)dt$; in a real system this is impossible because of the allocation error. The difference between the ideal and the real schedule is the lag:

\begin{displaymath}lag_i(t_1) = \int_{t_0}^{t_1} f_i(t)dt - executed_i(t_0,t_1),\end{displaymath}

where t0 is the activation time of task $\tau_i$.

The goal of a Proportional Share algorithm is to reduce the allocation error experienced by tasks. To support some form of real-time execution it is important to guarantee that lagi(t) is bounded. In fact, if an upper bound for lagi(t) exists, the execution time accumulated by $\tau_i$ is

 \begin{displaymath}executed_i(t_0,t) \geq \int_{t_0}^t f(t)dt - max_t\{lag_i(t)\}.
\end{displaymath} (4)

Hence, a task $\tau_i$ having execution time Ci is guaranteed to complete within a (relative) deadline Di if

\begin{displaymath}executed_i(t_0, t_0+D_i) \geq C_i.\end{displaymath}


next up previous
Next: Weighted Fair Queuing Up: Background on proportional share Previous: Background on proportional share

1999-02-16