The first known Proportional Share scheduling algorithm is Weighted
Fair Queuing (WFQ) [4], which emulates the behavior of a GPS
system using the concept of virtual time. The virtual time v(t)
is defined by increments as follows:
Each request qik is assigned a virtual start time S(qik) and a
virtual finish time F(qik) defined as follows:
where ri,k is the time at which request qik is generated and
Qi,k is the request dimension (required execution time). Since
Qi,k is not known a priori, it is assumed equal to the maximum value
Qi.
Tasks' requests are scheduled in order of increasing virtual finish time:
in the virtual time domain, each request will finish before its virtual
finish time.
In static systems, where all the tasks are always active, WFQ provides
fairness by bounding the allocation error. However, it presents the
following problems:
it needs a frequent recalculation of v(t), increasing runtime
overhead;
it does not perform well in dynamic systems (when a task activates
or blocks, the fairness of the schedule is compromised);
it assumes each requests size equal the maximum value (scheduling
quantum): in a real situation this assumption is not correct;