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

C

i

Major
Tasks

C i+1

ε

ε ε ε

Associated

Tasks

ε ε ε

Figure 9.9 Task sequence generated by the adversary.

Note that the sequence of tasks generated by the adversary is constructed in such a
way that the player can schedule at most one task within its deadline (either a major
task or an associated task). Clearly, since task values are equal to their computation
times, the player never abandons a major task for an associated task because it would
accumulate a negligible value; that is, . On the other hand, the values of the major
tasks (that is, their computation times) are chosen by the adversary to minimize the
resulting competitive factor. To find the worst-case sequence of values for the major
tasks, let

J 0 ,J 1 ,J 2 ,...,J i ,...,J m
be the longest sequence of major tasks that can be generated by the adversary and,
without loss of generality, assume that the first task has a computation time equal to
C 0 =1. Now, consider the following three cases.

Case 0 . If the player decides to schedule J 0 , the sequence terminates with J 1 . In this
case, the cumulative value gained by the player is C 0 , whereas the one obtained by the
adversary is ( C 0 + C 1 − ). Note that this value can be accumulated by the adversary

either by executing all the associated tasks, or by executing J 0 and all associated tasks
started after the release of J 1 . Being arbitrarily small, it can be neglected in the
cumulative value. Hence, the ratio among the two cumulative values is

C 0
C 0 + C 1

1
1+ C 1

1
k .

ϕ 0 = = =

If 1 /k is the value of this ratio ( k> 0), then C 1 = k − 1.

Case 1 . If the player decides to schedule J 1 , the sequence terminates with J 2 . In this
case, the cumulative value gained by the player is C 1 , whereas the one obtained by the
adversary is ( C 0 + C 1 + C 2 ). Hence, the ratio among the two cumulative values is

C 1
C 0 + C 1 + C 2

1
k + C 2

k −

ϕ 1 = = .