Start Fair Queuing

In [7], a proportional share scheduler is used to subdivide the CPU bandwidth between various application classes: the proposed algorithm, Start Fair Queuing (SFQ), is similar to WFQ but defines the virtual time in a different manner and schedules the requests in order of increasing virtual start time. The virtual time v(t) is defined as follows:

$$v(t) = \left \{ \begin{array}{l r} 0 & \mbox{ if } t = 0 \\ ... ...{if request } q_i^k \mbox{ is executing}\\ \end{array}\right.$$

SFQ guarantees an allocation error bound of 2H_i,j, so it is near-optimal. Moreover, SFQ calculates v(t) in a simpler way (introducing less overhead) and does not need the virtual finish time of a request to schedule it, so it does not require any a priori knowledge on the request execution time (F(q_i^k) can be calculated at the end of q_i^k execution).

SFQ provides a lag bound $\max_t\{lag_i(t)\}=Q_i+F_i\sum Q_j$ which depends on the number of active tasks. The algorithm is not P-fair [2] and it is difficult to provide some form of hard deadline guarantee.