7. Global Dynamic-Priority Scheduling of L&L Tasks

Here is an informal description of the technique; for further detail, please see [79, p. 116]. Let δ denote an arbitrarily small positive real number, and \([t,t+\delta]\) a time interval during which the processor shares assigned to the tasks do not change. Each task τ _i that is active during this interval needs to execute for an amount \(u_i\cdot\delta\). Considering the tasks sequentially in any order, we simply begin assigning them to the first processor starting at time-instant t until we have reached time-instant \(t+\delta\), at which point we would “wrap around” and proceed to the next processor beginning again at time-instant t, and so on until all the tasks have been assigned. If a task has only been assigned a part of its execution requirement upon a processor, we assign it the remainder of its execution requirement upon the next processor: the fact that \(u_i \le 1\) for each task guarantees that the allocation to a task upon two consecutive processors will not overlap in time.

Actually, the potentially tighter bound of \(\min(C_i/\text{gcd}(C_i,T_i), C_j/\text{gcd}(C_j,T_j))\) on the number of comparisons is easily seen to hold.