HANDLING OVERLOAD CONDITIONS - Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications - page 304

ϕ on

1

0.75

0.5

0.25

load

0 1 2 3

Figure 9.10 Bound of the competitive factor of an on-line scheduling algorithm as a func-
tion of the load.

Note that for ρ =1+ , Equation (9.9) is satisfied for p = 4 / 27 0 . 385, whereas,

for ρ =2, the same equation is satisfied for p =0 . 25.

In summary, whenever the system load does not exceed one, the upper bound of the
competitive factor is obviously one. As the load exceeds one, the bound immediately
falls to 0.385, and as the load increases from one to two, it falls from 0.385 to 0.25. For
loads higher than two, the competitive factor limitation remains at 0.25. The bound on
the competitive factor as a function of the load is shown in Figure 9.10.

Baruah et al. [BR91] also showed that when using value density metrics (where the
value density of a task is its value divided by its computation time), the best that an
online algorithm can guarantee in environments with load ρ> 2 is
1
(1 + √ k ) 2 ,

where k is the important ratio between the highest and the lowest value density task in
the system.

In environments with a loading factor ρ , 1 <ρ ≤ 2, and an importance ratio k ,two

cases must be considered. Let q = k ( ρ − 1).If q ≥ 1, then no online algorithm can

achieve a competitive factor greater than

1
(1 + √ q ) 2 ,

whereas, if q< 1, no online algorithm can achieve a competitive factor greater than p ,
where p satisfies

qp ) 3 =27 p 2 .

4(1 −