Equation 1 express that in a GPS system each
active task
executes at least with a rate equal to
As a consequence, the following properties hold:
executedi(t1,t2) | (t2-t1)Fi | (2) | |
executedi(t1,t2) | = | (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 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
and ,
the allocation error in the time
interval [t1,t2] can be defined as
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] executes for a time
;
in a real system this is
impossible because of the allocation error. The difference between the ideal
and the real schedule is the lag:
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
is