Earliest Eligible Virtual Deadline First

In [16], the authors propose a scheduling algorithm, called Earliest Eligible Virtual Deadline First (EEVDF), that provides a bound on the lag experimented by each task.

EEVDF defines the virtual time as WFQ and schedules the requests by virtual finish times (in this case called virtual deadlines), but uses the virtual start time (called virtual eligible time) to decide whether a task can be scheduled (i.e. is eligible): if the virtual eligible time is greater than the actual virtual time, the request is not eligible. Virtual start and finish times are defined as follows:

$$\begin{eqnarray*}S(q_i^k) & = & \max\{v(r_{i,k}),S(q_i^{k-1}) + \frac{Q_{i,k-1}}{w_i}\} \\ F(q_i^k) & = & S(q_i^k) + \frac{Q_{i,k}}{w_i}. \\ \end{eqnarray*}$$

When a task activates or blocks , v(t) is adjusted in order to maintain the fairness in dynamic systems.

The lag bound guaranteed by EEVDF algorithm is Q, which is the minimum lag bound. For this reason, EEVDF is said to be optimal. EEVDF can also schedule dynamic task sets and can use fractional and non uniform quantum size, so it can be used in a real operating system. To the best knowledge of the authors, EEVDF is the only algorithm that provides a fixed lag bound.

If the lag is bounded, real-time execution can be obtained by maintaining the share of each real-time task constant:

$$f_i(t) = \frac{C_i + \max_t\{lag_i(t)\}}{D_i}.$$