Optimal Reward-Based Scheduling for Periodic Real-Time Tasks.
AbstractReward-based scheduling refers to the problem in which there is a reward associated with the execution of a task. In our framework, each real-time task comprises a mandatory and an optional part. The mandatory part must complete before the task's deadline, while a nondecreasing reward function is associated with the execution of the optional part, which can be interrupted at any time. Imprecise computation and Increased-Reward-with-Increased-Service models fall within the scope of this framework. In this paper, we address the reward-based scheduling problem for periodic tasks. An optimal schedule is one where mandatory parts complete in a timely manner and the weighted average reward is maximized. For linear and concave reward functions, which are most common, we 1) show the existence of an optimal schedule where the optional service time of a task is constant at every instance and 2) show how to efficiently compute this service time. We also prove the optimality of Rate Monotonic Scheduling (with harmonic periods), Earliest Deadline First, and Least Laxity First policies for the case of uniprocessors when used with the optimal service times we computed. Moreover, we extend our result by showing that any policy which can fully utilize all the processors is also optimal for the multiprocessor periodic reward-based scheduling. To show that our optimal solution is pushing the limits of reward-based scheduling, we further prove that, when the reward functions are convex, the problem becomes NP-Hard. Our static optimal solution, besides providing considerable reward improvements over the previous suboptimal strategies, also has a major practical benefit: Run-time overhead is eliminated and existing scheduling disciplines may be used without modification with the computed optimal service times.
Introduction
In a real-time system each task must complete and produce correct output by the specified deadline.
However, if the system is overloaded it is not possible to meet each deadline. In the past, several
techniques have been introduced by the research community regarding the appropriate strategy to use
in overloaded systems of periodic real-time tasks.
One class of approaches focuses on providing somewhat less stringent guarantees for temporal con-
straints. In [16], some instances of a task are allowed to be skipped entirely. The skip factor determines
how often instances of a given task may be left unexecuted. A best effort strategy is introduced in
[11], aiming at meeting k deadlines out of n instances of a given task. This framework is also known
as (n,k)-firm deadlines scheme. Bernat and Burns present in [3] a hybrid and improved approach to
provide hard real-time guarantees to k out of n consecutive instances of a task.
The techniques mentioned above tacitly assume that a task's output is of no value if it is not executed
completely. However, in many application areas such as multimedia applications [26], image and speech
processing [5, 6, 9, 28], time-dependent planning [4], robot control/navigation systems [12, 30], medical
decision making [13], information gathering [10], real-time heuristic search [17] and database query
processing [29], a partial or approximate but timely result is usually acceptable.
The imprecise computation [7, 19, 21] and IRIS (Increased Reward with Increased Service) [14, 15, 18]
models were proposed to enhance the resource utilization and graceful degradation of real-time systems
when compared with hard real-time environments where worst-case guarantees must be provided. In
these models, every real-time task is composed of a mandatory part and an optional part. The former
should be completed by the task's deadline to provide output of acceptable (minimal) quality. The
optional part is to be executed after the mandatory part while still before the deadline, if there are
enough resources in the system that are not committed to running mandatory parts for any task. The
longer the optional part executes, the better the quality of the result (the higher the reward).
The algorithms proposed for imprecise computation applications concentrate on a model that has
an upper bound on the execution time that could be assigned to the optional part [7, 21, 27]. The
aim is usually to minimize the (weighted) sum of errors. Several efficient algorithms are proposed to
solve optimally the scheduling problem of aperiodic imprecise computation tasks [21, 27]. A common
assumption in these studies is that the quality of the results produced is a linear function of the precision
consequently, the possibility of having more general error functions is usually not addressed.
An alternative model allows tasks to get increasing reward with increasing service (IRIS model)
[14, 15, 18] without an upper bound on the execution times of the tasks (though the deadline of the
task is an implicit upper bound) and without the separation between mandatory and optional parts [14].
A task executes for as long as the scheduler allows before its deadline. Typically, a nondecreasing concave
reward function is associated with each task's execution time. In [14, 15] the problem of maximizing the
total reward in a system of aperiodic independent tasks is addressed. The optimal solution with static
task sets is presented, as well as two extensions that include mandatory parts and policies for dynamic
task arrivals.
Note that the imprecise computation and IRIS models are closely related, since the performance
metrics can be defined as duals (maximizing the total reward vs. minimizing the total error). Similarly,
a concave reward function corresponds to a convex error function, and vice versa. We use the term
"Reward-based scheduling" to encompass scheduling frameworks, including Imprecise Computation and
IRIS models, where each task can be logically decomposed into a mandatory and optional subtask. A
nondecreasing reward function is associated with the execution of each optional part.
An interesting question concerns the types of reward functions that represent realistic application
areas. A linear reward function [19, 21] models the case where the benefit to the overall system increases
uniformly during the optional execution. Similarly, a concave reward function [14, 15, 18, 26] addresses
the case where the greatest increase/refinement in the output quality is obtained during the first portions
of optional executions. Linear and general concave functions are considered as the most realistic and
typical in the literature since they adequately capture the behavior of many application areas like
image and speech processing [5, 6, 9, 28], multimedia applications [26], time-dependent planning [4],
robot control/navigation systems [30], real-time heuristic search [17], information gathering [10] and
database query processing [29]. In this paper, we show that the case of convex reward functions is an
NP-Hard problem and thus focus on linear and concave reward functions. Reward functions with 0/1
constraints, where no reward is accrued unless the entire optional part is executed, or as step functions
have also received some interest in the literature. Unfortunately, this problem has been shown to be
NP-Complete in [27].
Periodic reward-based scheduling remains relatively unexplored, since the important work of Chung,
Liu and Lin [7]. In that paper, the authors classified the possible application areas as "error non-
cumulative" and "error cumulative". In the former, errors (or optional parts left unexecuted) have
no effect on the future instances of the same task. Well-known examples of this category are tasks
which receive, process and transmit periodically audio, video or compressed images [5, 6, 9, 26, 28]
and information retrieval tasks [10, 29]. In "error cumulative" applications, such as radar tracking, an
optional instance must be executed completely at every (predetermined) k invocations. The authors
further proved that the case of error-cumulative jobs is an NP-Complete problem. In this paper, we
restrict ourselves to error non-cumulative applications.
Recently, a QoS-based resource allocation model (QRAM) has been proposed for periodic applications
[26]. In that study, the problem is to optimally allocate several resources to the various applications
such that they simultaneously meet their minimum requirements along multiple QoS dimensions and the
total system utility is maximized. In one aspect, this can be viewed as a generalization of optimal CPU
allocation problem to multiple resources and quality dimensions. Further, dependent and independent
quality dimensions are separately addressed for the first time in this work. However, a fundamental
assumption of that model is that the reward functions and resource allocations are in terms of utilization
of resources. Our work falls rather along the lines of Imprecise Computation model, where the reward
accrued has to be computed separately over all task instances and the problem is to find the optimal
service times for each instance and the optimal schedule with these assignments.
Aspects of the Periodic Reward-Based Scheduling Problem
The difficulty of finding an optimal schedule for a periodic reward-based task set has its origin on two
objectives that must be simultaneously achieved, namely:
i. Meeting deadlines of mandatory parts at every periodic task invocation.
ii. Scheduling optional parts to maximize the total (or average) reward.
These two objectives are both important, yet often incompatible. In other words, hard deadlines of
mandatory parts may require sacrificing optional parts with greatest value to the system.
The analytical treatment of the problem is complicated by the fact that, in an optimal schedule,
optional service times of a given task may vary from instance to instance which makes the framework
of classical periodic scheduling theory inapplicable. Furthermore, this fact introduces a large number
of variables in any analytical approach. Finally, by allowing nonlinear reward functions to better
characterize the optional tasks' contribution to the overall system, the optimization problem becomes
computationally harder.
In [7], Chung, Liu and Lin proposed the strategy of assigning statically higher priorities to mandatory
parts. This decision, as proven in that paper, effectively achieves the first objective mentioned above
by securing mandatory parts from the potential interference of optional parts. Optional parts are
scheduled whenever no mandatory part is ready in the system. In [7], the simulation results regarding
the performance of several policies which assign static or dynamic priorities among optional parts are
reported. We call the class of algorithms that statically assign higher priorities to mandatory parts
Mandatory-First Algorithms.
In our solution, we do not decouple the objectives of meeting the deadlines of mandatory parts and
maximizing the total (or average) reward. We formulate the periodic reward-based scheduling problem
as an optimization problem and derive an important and surprising property of the solution for the
most common (i.e., linear and concave) reward functions. Namely, we prove that there is always an
optimal schedule where optional service times of a given task do not vary from instance to instance.
This important result immediately implies that the optimality (in terms of achievable utilization) of
any policy which can fully use the processor in case of hard-real time periodic tasks also holds in the
context of reward-based scheduling (in terms of total reward) when used with these optimal service
times. Examples of such policies are RMS-h (Rate Monotonic Scheduling with harmonic periods) [20],
EDF (Earliest Deadline First) [20] and LLF (Least Laxity First) [24]. We also extend the framework to
homogeneous multiprocessor settings and prove that any policy which can fully utilize all the processors
is also optimal for scheduling periodic reward-based tasks (in terms of total reward) on multiprocessors
environments.
Following these existence proofs, we address the problem of efficiently computing optimal service
times and provide polynomial-time algorithms for linear and/or general concave reward functions. Note
that using these optimal and constant optimal service times has also important practical advantages: (a)
The runtime overhead due to the existence of mandatory/optional dichotomy and reward functions is
removed, and (b) existing RMS with harmonic periods), EDF and LLF schedulers may be used without
any modification with these optimal assignments.
The remainder of this paper is organized as follows: In Section 2, the system model and basic
definitions are given. The main result about the optimality of any periodic policy which can fully utilize
the processor(s) is obtained in Section 3. In Section 4, we first analyze the worst-case performance
of Mandatory-First approaches. We also provide the results of experiments on a synthetic task set to
compare the performance of policies proposed in [7] against our optimal algorithm. In Section 6, we show
that the concavity assumption is also necessary for computational efficiency by proving that allowing
convex reward functions results in an NP-Hard problem. Then, we examine whether the optimality of
identical service times still holds if the model is modified by dropping some fundamental assumptions
(Section 5). We present details about the specific optimization problem that we use in Section 7. We
conclude by summarizing our contribution and discussing future work.
System Model
We first develop and present our solution for uniprocessor systems, then we show how to extend it to
the case of homogeneous multiprocessor systems.
We consider a set T of n periodic real-time tasks . The period of T i is denoted by P i ,
which is also equal to the deadline of the current invocation. We refer to the j th invocation of task T i
All tasks are assumed to be independent and ready at
Each task T i consists of a mandatory part M i and an optional part O i . The length of the mandatory
part is denoted by m i ; each task must receive at least m i units of service time before its deadline in order
to provide output of acceptable quality. The optional part O i becomes ready for execution only when
the mandatory part M i completes, it can execute as long as the scheduler allows before the deadline.
Associated with each optional part of a task is a reward function R which indicates the reward
accrued by task T ij when it receives t ij units of service beyond its mandatory portion. R is of the
(1)
where f i is a nondecreasing, concave and continuously differentiable function over nonnegative real
numbers and is the length of the entire optional part O i . We underline that f
the benefit of task T ij can not decrease by allowing it to run longer. Notice that the reward function
R i (t) is not necessarily differentiable at Note also that in this formulation, by the time the
task's optional execution time t reaches the threshold value the reward accrued ceases to increase.
Clearly, the reward of executing an optional part O i for an amount of time will be the same as
the reward for executing for Therefore, it is not beneficial to execute O i for more than
time units.
A function f(x) is concave if and only if for all x; y and 0 - ff -
ff)f(y). Geometrically, this condition means that the line joining any two points of a concave curve
may not be above the curve. Examples of concave functions are linear functions (kx
functions (ln[kx decay functions (c th root functions (x 1=k ). Note
that the first derivative of a nondecreasing concave function is nonincreasing. Having nondecreasing
concave reward functions means that while a task T i receives service beyond its mandatory portion M i ,
its reward monotonically increases. However, its rate of increase decreases or remains constant with
time. The concavity assumption implies that the early portions of an optional execution are not less
important than the later ones, which adequately captures many application areas mentioned in the
introduction. We mostly concentrate on linear and, in general, concave reward functions.
A schedule of periodic tasks is feasible if mandatory parts meet their deadlines at every invocation.
Given a feasible schedule of the task set T, the average reward of task T i is defined as:
where P is the hyperperiod, that is, the least common multiple of P is the service time
assigned to the j th instance of optional part of task T i . That is, the average reward of T i is computed
over the number of its invocations during the hyperperiod P, in an analogous way to the definition of
average error in [7] 1 .
The average weighted reward of a feasible schedule is then given by:
We note that the results we prove easily extend to the case in which one is interested in maximizing the total reward
where w i is a constant in the interval (0,1] indicating the relative importance of optional part O i .
Although this is the most general formulation, it is easy to see that the weight w i can always be
incorporated into the reward function f i (), by replacing it by w Thus, we will assume that all
weight (importance) information are already expressed in the reward function formulation and that
REWW is simply equal to
Finally, a schedule is optimal if it is feasible and it maximizes the average weighted reward.
A Motivating Example:
Before describing our solution to the problem, we present a simple example which shows the performance
limitations of any Mandatory-First algorithm. Consider two tasks where
5. Assume that the reward functions associated with optional parts are linear
Furthermore, suppose that k 2 associated with the reward accrued
by T 2 is negligible when compared to k 1 , i.e. k 1 AE k 2 . In this case, the "best" algorithm among
"Mandatory-First" approaches should produce the schedule shown in Figure 1.00000000000011111111111100000000000000000000001111111111111111111111

Figure

1: A schedule produced by Mandatory-First Algorithm
Above, we assumed that the Rate Monotonic Priority Assignment is used whenever more than one
mandatory task are simultaneously ready, as in [7]. Yet, following other (dynamic or static) priority
schemes would not change the fact that the processor will be busy executing solely mandatory parts
Mandatory-First approach. During the remaining idle interval [5,8], the best
algorithm would have chosen to schedule O 1 completely (which brings most benefit to the system) for 1
time unit and O 2 for 2 time units. However, an optimal algorithm would produce the schedule depicted
in

Figure

2.
As it can be seen, the optimal strategy in this case consisted of delaying the execution of M 2 in order
to be able to execute 'valuable' O 1 and we would still meet the deadlines of all mandatory parts. By
doing so, we would succeed in executing two instances of O 1 , in contrast to any Mandatory-First scheme
which can execute only one instance of O 1 . Remembering that k 1 AE k 2 , one can conclude that the
reward accrued by the 'best' Mandatory-First scheme may only be around half of that accrued by the
optimal one, for this example. Also, observe that in the optimal schedule, the optional execution times
of a given task did not vary from instance to instance. In the next section, we prove that this pattern
O 2

Figure

2: An optimal schedule
is not a mere coincidence. We further perform an analytical worst-case analysis of Mandatory-First
algorithms in Section 4.
3 Optimality of Full-Utilization Policies for Periodic Reward-Based
Scheduling
We first formalize the Periodic Reward-Based Scheduling problem. The objective is clearly finding
values to maximize the average reward. By substituting the average reward expression
given by (2) in (3), we obtain our objective function:
maximize
The first constraint that we must enforce is that the total processor demand of mandatory and
optional parts during the hyperperiod P may not exceed the available computing capacity, that is:
Note that this constraint is necessary, but by no means sufficient for feasibility of the task set
with values. Next, we observe that optimal t ij values may not be less than zero, since
negative service times do not have any physical interpretation. In addition, the service time of an
optional instance of T i does not need to exceed the upperbound of reward function R i (t), since the
reward accrued by T i ceases to increase after Hence, we obtain our second constraint set:
The constraint above allows us to readily substitute f i () for R i () in the objective function. Finally,
we need to express the "full" feasibility constraint, including the requirement that mandatory parts
complete in a timely manner at every invocation. Note that it is sufficient to have one feasible schedule
with the involved fm i g and optimal values:
There exists a feasible schedule with fm i g and ft ij g values
We express this constraint in English and not through formulas since the policy or algorithm producing
this schedule including optimal t ij assignments need not be specified at this point.
To re-capture all the constraints, the periodic reward-based scheduling problem, which we denote
by REW-PER, is to find values so as to:
maximize
subject to
There exists a feasible schedule with fm i g and ft ij g values (7)
Before stating our main result, we underline that if
it is not possible to schedule
mandatory parts in a timely manner and the optimization problem has no solution. Note that this
condition is equivalent to
? 1, which indicates that the task set would be unschedulable, even
if it consisted of only mandatory parts. Hence, thereafter, we suppose that
there exists at least one feasible schedule.
Theorem 1 Given an instance of Problem REW-PER, there exists an optimal solution where the optional
parts of a task T i receive the same service time at every instance, i.e.
Furthermore, any periodic hard-real time scheduling policy which can fully utilize the processor (EDF,
LLF, RMS-h) can be used to obtain a feasible schedule with these assignments.
Proof:
Our strategy to prove the theorem will be as follows. We will drop the feasibility condition (7)
and obtain a new optimization problem whose feasible region strictly contains that of REW-PER.
Specifically, we consider a new optimization problem, denoted by MAX-REW, where the objective
function is again given by (4), but only the constraint sets (5) and (6) have to be satisfied. Note
that the new problem MAX-REW does not a priori correspond to any scheduling problem, since the
feasibility issue is not addressed. We then show that there exists an optimal solution of MAX-REW
. Then, we will return to REW-PER and demonstrate the existence
of a feasible schedule (i.e. satisfiability of (7)) under these assignments. The reward associated with
MAX-REW's optimal solution is always greater than or equal to that of REW-PER's optimal solution,
for MAX-REW does not consider one of the REW-PER's constraints. This will imply that this specific
optimal solution of the new problem MAX-REW is also an optimal solution of REW-PER.
Now, we show that there exists an optimal solution of MAX-REW where
be an optimal solution to
also an optimal solution to
MAX-REW.
ffl We first show that ft 0
values satisfy the constraints (5) and (6), if already satisfy them.
Since
i the constraint (5) is not violated by the transformation. Also,
by assumption,
i , which is arithmetic mean of
is necessarily less than or equal to max j
the constraint set (6) is not violated
either by the transformation.
ffl Furthermore, the total reward does not decrease by this transformation, since
). The proof of this statement is presented in the Appendix.
Using Claim 1, we can commit to finding an optimal solution of MAX-REW by setting t
n. In this case,
. Hence, this
version of MAX-REW can be re-written as:
maximize
subject to
Finally, we prove that the optimal solution t automatically satisfies
the feasibility constraint (7) of our original problem REW-PER. Having equal optional service times
for a given task greatly simplifies the verification of this constraint. Since t
satisfy (9), we can write
equivalently,
- 1.
This implies that any policy which can achieve 100% processor utilization in classical periodic
scheduling theory (EDF, LLF, RMS-h) can be used to obtain a feasible schedule for tasks, which have
now identical execution times at every instance. Hence, the "full feasibility" constraint (7)
of REW-PER is satisfied. Furthermore, this schedule clearly maximizes the average reward since ft i g
values maximize MAX-REW whose feasible region encompasses that of REW-PER.
Corollary 1 Optimal t i values for the Problem REW-PER can be found by solving the optimization
problem given by (8), (9) and (10).
The details of the solution of this concave optimization problem are presented in Section 7.
3.1 Extension to Multiprocessors
The existence proof of identical service times can be easily extended to homogeneous multiprocessors.
The original formulation of REW-PER needs to be modified in order to reflect the multiprocessor
environment. Note that the objective function (4), the lower and upper bound constraints (6) on
optional service times and the full feasibility constraint (7) can be kept as they are. However, with k
processors, the system can potentially have a task set whose total utilization is k instead of 1. Hence,
we need to change the first constraint accordingly.
By doing so, we obtain the formulation of periodic imprecise computation problem for k processors,
denoted as MULTI-REW:
maximize
subject to
There exists a feasible schedule on k processors with fm i g and ft ij g values (14)
Following exactly the same line of reasoning depicted in Theorem 1, we can infer the following:
Theorem 2 Given an instance of Problem MULTI-REW, there exists an optimal solution where the
optional parts of a task T i receive the same service time at every instance, i.e.
Furthermore, any scheduling policy which can achieve full utilization on k processors can be used to
obtain a feasible schedule with these assignments.
An example of such full-utilization policies for multiprocessors is provided by Mancini et al. in [23]. We
note that the PFair scheduling policy [2] which can also achieve full-utilization, assumes that all the
periods are multiples of the slot length and hence it can not be used in this context.
Corollary 2 Optimal t i values for the Problem MULTI-REW can be found by solving the following
optimization problem:
maximize
subject to
Again, the details of the solution of this concave optimization problem are given in Section 7.
4 Evaluation and comparison with other approaches
We showed through the example in Section 2 that the reward accrued by any Mandatory-First scheme
may only be approximately half of that of the optimal algorithm. We now prove that, under worst-case
scenario, the ratio of the reward accrued by a Mandatory-First approach to the reward of the
optimal algorithm approaches zero.
Theorem 3 There is an instance of periodic reward-based scheduling problem where the ratio
Reward of the best mandatory\Gammafirst scheme
Reward of the optimal scheme
r for any integer r - 2.
Proof: Consider two tasks T 1 and T 2 such that P 2
r
which implies that
r (r\Gamma1)
This setting suggests that during any period of T 1 , a scheduler has the choice of executing (parts
in addition to M 1 .
Note that under any Mandatory-First policy, the processor will be continuously busy executing
mandatory parts until Furthermore, the best algorithm among Mandatory-First
policies should use the remaining idle times by scheduling O 1 entirely (since
2units of O 2 . The resulting schedule is shown in Figure 3.m 1
Figure

3: A schedule produced by Mandatory-First Algorithm
The average reward that the best mandatory-first algorithm (MFA) can accrue is therefore:
r
However, an optimal algorithm (shown in Figure 4) would choose delaying the execution of M 2 for
units of time, at every period of T 1 . By doing so, it would have the opportunity of accruing the
reward of O 1 at every instance.m 1
om
r
r
r
r
r

Figure

4: An optimal schedule
The total reward of the above schedule is:
r
The ratio of rewards for the two policies turns out to be (for any r - 2)
RMFA
ROPT
=r
r
=r
which can be made as close as possible to 0 by appropriately choosing r.Theorem 3 gives the worst-case performance ratio of Mandatory-First schemes. We also performed
experiments with a synthetic task set to investigate the relative performance of Mandatory-First schemes
proposed in [7] with different types of reward functions and different mandatory/optional workload
ratios.
The Mandatory-First schemes differ by the policy according to which optional parts are scheduled
when there is no mandatory part ready to execute. Rate-Monotonic (RMSO) and Least-Utilization (LU)
schemes assign statically higher priorities to optional parts with smaller periods and least utilizations
respectively. Among dynamic priority schemes are Earliest-Deadline-First (EDFO) and Least-Laxity-
First (LLFO) which consider the deadline and laxity of optional parts when assigning priorities. Least
Attained Time (LAT) aims at balancing execution times of optional parts that are ready, by dispatching
the one that executed least so far. Finally, Best Incremental Return (BIR) is an on-line policy which
chooses the optional task contributing most to the total reward, at a given slot. In other words, at every
slot BIR selects the optional part O ij such that the difference f is the largest (here t ij
is the optional service time O ij has already received and \Delta is the minimum time slot that the scheduler
assigns to any optional task). However, it is still a sub-optimal policy since it does not consider the
laxity information. The authors indicate in [7] that BIR is too computationally complex to be actually
implemented. However, since the total reward accrued by BIR is usually much higher than the other
five policies, BIR is used as a yardstick for measuring the performance of other algorithms.
We have used a synthetic task set comprising 11 tasks whose total (mandatory
is 2.3. Individual task utilizations vary from 0.03 to 0.6. Considering exponential, logarithmic and linear
reward functions as separate cases, we measured the reward ratio of six Mandatory-First schemes with
respect to our optimal algorithm. The tasks' characteristics (including reward functions) are given in
the Table below. In our experiments, we first set mandatory utilization to 0 (which corresponds to the
case of all-optional workload), then increased it to 0.25, 0.4, 0.6, 0.8 and 0.91 subsequently.
7 90
9

Figures

5 and 6 show the reward ratio of six Mandatory-First schemes with respect to our optimal
algorithm as a function of mandatory utilization, for different types of reward functions. A common
pattern appears: the optimal algorithm improves more dramatically with the increase in mandatory
utilization. The other schemes miss the opportunities of executing "valuable" optional parts while
constantly favoring mandatory parts. The reward loss becomes striking as the mandatory workload
increases. Figures 5.a and 5.b show the reward ratio for the case of exponential and logarithmic reward
functions, respectively. The curves for these strictly concave reward functions are fairly similar:
BIR performs best among Mandatory-First schemes, and its performance decreases as the mandatory
utilization increases; for instance the ratio falls to 0.73 when mandatory utilization is 0.6. Other algorithms
which are more amenable to practical implementations (in terms of runtime overhead) than
BIR perform even worse. However, it is worth noting that the performance of LAT is close to that of
BIR. This is to be expected, since task sets with strictly concave reward functions usually benefit from
"balanced" optional service times.
Utilization
OPT
Reward Ratio with
Respect to Optimal
RMSO LLFO
EDFO
(a)
LLFO
RMSO EDFO
LU
Reward Ratio with
Respect to Optimal
OPT
Mandatory

Figure

5: The Reward Ratio of Mandatory-First schemes: strictly concave reward functions (a) Exponential
(b) Logarithmic functions
Reward Ratio with
Respect to Optimal
Utilization
OPT0.800.600.500.201.00
LLFO
RMSO
EDFO
LU

Figure

The Reward Ratio of Mandatory-First schemes: linear reward functions

Figure

6 shows the reward ratio for linear reward functions. Although the reward ratio of Mandatory-
First schemes again decreases with the mandatory utilization, the decrease is less dramatic than in the
case of concave functions (see above). However, note that the ratio is typically less than 0.5 for the
five practical schemes. It is interesting to observe that the (impractical) BIR's reward now remains
comparable to that of optimal, even in the higher mandatory utilizations: the difference is less than
15%. In our opinion, the main reason for this behavior change lies on the fact that, for a given task,
the reward of optional execution slots in different instances does not make a difference in the linear
case. In contrast, not executing the "valuable" first slot(s) of a given instance creates a tremendous
effect for nonlinear concave functions. The improvement of the optimal algorithm would be larger for a
larger range of k i values (where k i is the coefficient of the linear reward function). We note that even
the worst-case performance of BIR may be arbitrarily bad with respect to the optimal one for linear
functions, as Theorem 3 suggests.
Further considerations on the optimality of identical service times
We underline that Theorem 1 was the key to eliminate (potentially) an exponential number of unknowns
thereby to obtain an optimization problem of n variables. One is naturally tempted to ask
whether the optimality of identical service times is still preserved if some fundamental assumptions
of the model are relaxed. Unfortunately, attempts to reach further optimality results for extended /
different models remain inconclusive as the following propositions suggest.
Proposition 1 The optimality of identical service times no longer holds if the Deadline = Period
assumption is relaxed.
Proof:
We will prove the statement by providing a counter-example. Assume that we allow the deadline of
a task to be less than its period. Consider the following two tasks:
Further, assume that the deadline of T 2 is D while the deadline of T 1 coincides with
its period, i.e. d 8. Note that the tight deadline of T 2 makes it impossible to schedule any optional
after which we are able to schedule O 1 for 3 units. This optimal schedule is shown in

Figure

7. On the other hand, if one commits to identical service times per instance, it is clear that we
may not schedule any optional part, since we could not execute O 1 in the first instance of T 1 (Figure
8).Next, suppose that the deadlines are equal to the periods, but we have to adopt a static priority
scheduling policy. It was already mentioned in Section 3, that if the periods are harmonic, then we
can use RMS without compromising optimality. But, in the general case where the periods are not
necessarily harmonic, this is not true even if we are investigating the 'best' schedule within the context
of a given static priority assignment.
Proposition 2 In the general case, the optimality of identical service times no longer holds if we
commit to a static priority assignment.
d
O 110
Figure

7: The optimal schedule0
Figure

8: Best schedule with identical service times
Proof:
Again, consider the following task set:
As we have only two tasks, we will consider the cases where T 1 or T 2 has higher priority and show
that in every case, the reward of the optimal schedule differs from the one obtained with identical service
times per instance assumption.
Case higher priority: It is easy to see that we can construct a schedule which fully
utilizes the timeline during the interval [0; lcm(6; This schedule is also immediately
optimal since the reward function is linear (observe that hence we do not receive any reward
for executing O 2 ). But, we remark that we can not execute O 1 for more than 1 unit on its first instance
in any feasible schedule - without violating the deadline of T 2 . Therefore, we would have ended up
with a lower reward after executing 1 unit of O 1 at each instance, if we had committed to identical
service times (Figure 9)b.
Case 2 - T 2 has higher priority: The optimality is still compromised if T 2 has higher priority.
While the optimal schedule (Figure 10a) fully utilizes the timeline, the best schedule with t

Figure

remains suboptimal.
We remark that the Proposition 2 has also implications for Q-RAM model [26], since it points to the
impossibility of achieving optimality with identical service times by using a static priority assignment.0000000000001111111111110000000000001111111111110000000000001111111111110000000000001111111111110163 242 6
6 81
O 1
O 1
O
O 1
O 1
O
O 1(a)
(b)

Figure

has the higher priority (a) The optimal schedule (b) The best schedule with identical
service times
O
O
MO 15OMM 1
O
O
MO 15OMM 1
O
M5OMM
19 2118O O 111
(a)
(b)

Figure

has the higher priority (a) The optimal schedule (b) The best schedule with identical
service times
The final proposition in this section illustrates that the optimality of identical service times is also
sensitive to the concavity of reward functions.
Proposition 3 The optimality of identical service times no longer holds if the concavity assumption
about the reward functions is relaxed.
Proof:
Consider two harmonic tasks without mandatory parts whose parameters are given in the following
table:
Note that t 2 should be assigned its maximum possible value (i.e., the upper bound 6), since the
marginal return of F 2 is larger than F 1 everywhere. An optimal schedule maximizing the average
reward for these two tasks is depicted in Figure 11.00000000000000000011111111111111111111111100000000000000000000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000011111111111111111111111111111111111111111111111111111111111111111O
O 2
O 12 8
Figure

11: An optimal schedule
The sum of the average rewards in the optimal schedule is 2:6 However, if we
commit ourselves to the equal service times per instances, we can find no better schedule than the one
shown in Figure 12, whose reward is only
It is not difficult to construct a similar example for the tasks with 0-1 constraints as well, which
implies that even the number of variables to deal with (the t ij 's) may be prohibitively large in these
problems.
O 1 O 1O513
O 2

Figure

service times
6 Periodic Reward-Based Scheduling Problem with Convex Reward
Functions is NP-Hard
As we mentioned before, maximizing the total (or average) reward with 0/1 constraints case had already
been proven to be NP-Complete in [21]. Similarly, in section 5 we showed that, if the reward functions
are convex, the optimality of identical service times is not preserved. In this section, we show that, in
fact convex reward functions result in an NP-Hard problem, even with identical periods.
We now show how to transform the SUBSET-SUM problem, which is known to be NP-Complete,
to REW-PER with convex reward functions.
SUBSET-SUM: Given a set of positive integers and the integer M, is there a set
SA ' S such that
We construct the corresponding REW-PER instance as follows. Let
Now consider a
set of n periodic tasks with the same period M and mandatory parts m 8i. The reward function
associated with T i is given by:
strictly convex and increasing function on nonnegative real numbers.
Notice that f i (t i ) can be re-written as t i Also we underline that having the same
periods for all tasks implies that REW-PER can be formulated as:
maximize
subject to
Let us denote by MaxRew the total reward of the optimal schedule. Observe that for
the quantity t i Otherwise, at either of the boundary values 0 or s i ,
MaxRew - WM .
Now, consider the question: "Is MaxRew equal to WM ?". Clearly, this question can be answered
quickly if there is a polynomial-time algorithm for REW-PER where reward functions are allowed to be
convex. Furthermore, the answer can be positive only when
and each t i is equal to either 0
or s i . Therefore, MaxRew equal to WM , if and only if there is a set SA ' S such that
which implies that REW-PER with convex reward functions is NP-Hard.
7 Solution of Periodic Reward-Based Scheduling Problem with Concave
Reward Functions
Corollaries 1 and 2 reveal that the two optimization problems whose solutions provide optimal service
times for uniprocessor and multiprocessor systems share a common form:
maximize
subject to
where d (the 'slack' available for optional executions) and b 1 are positive rational numbers.
In this section, we present polynomial-time solutions for this problem, where each f i is a nondecreasing,
concave and differentiable 2 function.
First note that, if the available slack is large enough to accommodate every optional part entirely
(i.e., if
then the choice t clearly maximizes the objective function due to the
nondecreasing nature of reward functions.
Otherwise, the slack d should be used in its entirety since the total reward never decreases by doing
so (again due to the nondecreasing nature of the reward functions). In this case, we obtain a concave
optimization problem with lower and upper bounds, denoted by OPT-LU. An instance of OPT-LU
is specified by the set of nondecreasing concave functions g, the set of upper bounds
and the available slack d. The aim is to:
maximize
subject to
2 In the auxiliary optimization problems which will be introduced shortly, the differentiability assumption holds as well.
Special Case of Linear functions: We address separately the case when F comprises solely linear
functions, since the time complexity can be considerably reduced by using this information. Note that
for a function f i increase t i by \Delta then total reward increases by k i \Delta. However by
doing so, we make use of b i \Delta units of slack (d is reduced by b i \Delta due to (22)). Hence, the "marginal
return" of task T i per slack unit is w
. Now consider another function f
. If should be always favored with respect to T i since the marginal return
of f j is strictly greater than f i everywhere. Repeating the argument for every pair of tasks, we can
obtain the following optimal strategy.
We first order the functions according to their marginal returns w
the function with the largest marginal return, f 2 the second and so on (ties are broken arbitrarily). If
d, then we set t and we are done (we are using the entire slack for T 1 , since transferring
service time to any other task would not increase the total reward). If b 1 then we set t
and d is reduced accordingly Next, we repeat the same for the next "most valuable"
. After at most n iterations, the slack d is completely consumed. We note that this solution
is analogous to the one presented in [26]. The dominant factor in the time complexity comes from the
initial sorting procedure, hence in the special case of all-linear functions, OPT-LU can be solved in time
O(n log n).
When F contains nonlinear functions then the procedure becomes more involved. In the next two
subsections, we introduce two auxiliary optimization problems, namely Problem OPT (which considers
only the equality constraint) and Problem OPT-L (which considers only the equality and lower bound
constraints), which will be used to solve OPT-LU.
7.1 Problem OPT: Case of the Equality Constraint
An instance of the problem OPT is characterized by the set of nondecreasing concave
functions and the slack d:
maximize
subject to
As it can be seen, OPT does not take into account the lower and upper bound constraints of Problem
OPT-LU. The algorithm which returns the solution of Problem OPT, is denoted by "Algorithm OPT".
When F is composed solely of non-linear reward functions, the application of Lagrange multipliers
technique [22] to the Problem OPT, yields:b i
where - is the common Lagrange multiplier and f 0
is the derivative of the reward function f i . The
quantity 1
actually represents the marginal return contributed by T i to the total reward,
which we will denote as w i (t i ). Observe that since f i non-decreasing and concave by assumption,
both
non-increasing and positive valued. Equation (25) implies that the marginal
returns
should be equal for all reward functions in the optimal solution g.
Considering that the equality
should also hold, one can obtain closed formulas in most of
the cases which occur in practice. The closed formulas presented below are obtained by this method.
ffl For logarithmic reward functions of the form f
and
ffl For exponential reward functions of the form f
and
ffl For "k th root" reward functions of the form f
and
When it is not possible to find a closed formula, following exactly the approach presented in [14, 15,
18], we solve - in the equation
is the inverse function of 1
(we assume the existence of the derivative's inverse function whenever f i is nonlinear, complying with
[14, 15, 18]). Once - is determined, t is the optimal solution.
We now examine the case where F is a mix of linear and nonlinear functions. Consider two linear
functions f t. The marginal return of f
and that
of f j is w
then the service time t i should be definitely zero, since
marginal return of f i is strictly less than f j everywhere. After this elimination process, if there are
linear functions with the same (largest) marginal return w max then we will consider them as a
single linear function in the procedure below and evenly divide the returned service time t max among
values corresponding to these p functions.
Hence, without loss of generality, we assume that f n is the only linear function in F. Its
marginal return is w
We first compute the optimal distribution of slack d among
tasks with nonlinear reward functions f . By the Lagrange multipliers technique, w
and thus w 1 (t
at the optimal solution t
.
Now we distinguish two cases:
. In this case, t
is the optimal solution to OPT. To see this,
first remember that all the reward functions are concave and nondecreasing, hence w
This implies that transferring some service
time from another task T i to T n would mean favoring the task which has the smaller marginal
reward rate and would not be optimal.
. In this case, reserving the slack d solely to tasks with nonlinear reward functions means
violating the best marginal rate principle and hence is not optimal. Therefore, we should increase
drops to the level of w not beyond. Solving
assigning any remaining slack d\Gamma
bn to t n (the service
time of unique task with linear reward function) clearly satisfies the best marginal rate principle
and achieves optimality.
7.2 Problem OPT-L: Case of Lower Bounds
In this section we present a solution for problem OPT-L and we improve on this solution in Section 7.2.1.
An instance of Problem OPT-L is characterized by the set F=ff 1 of nondecreasing concave
reward functions, and the available slack d:
maximize
subject to
To solve OPT-L, we first evaluate the solution set SOPT to the corresponding problem OPT and
check whether all inequality constraints are automatically satisfied. If this is the case, the solution
set SOPT \GammaL of Problem OPT-L is clearly the solution SOPT . Otherwise, we will construct SOPT \GammaL
iteratively as described below.
A well-known result of nonlinear optimization theory states that the solution SOPT \GammaL of Problem
OPT-L should satisfy so-called Kuhn-Tucker conditions [22, 25]. Furthermore, Kuhn-Tucker conditions
are also sufficient in the case of concave reward functions [22, 25]. For Problem OPT-L, Kuhn-Tucker
conditions comprise Equations (27), (28) and:
are Lagrange multipliers. The necessary and sufficient character of Kuhn-Tucker
conditions indicates that any 2n+ 1 tuple which satisfies conditions (27)
through (31) provides optimal t i values for OPT-L.
One method of solving the optimization problem OPT-L is to find a solution to the 2n+1 equations
(27), (29) and (30) which satisfies constraint sets (28) and (31). Iteratively solving the 2n+ 1 nonlinear
equations is a complex process which is not guaranteed to converge. In this paper, we follow a different
approach. Namely, we use the Kuhn-Tucker conditions (29), (30) and (31) to prove some useful properties
of the optimal solution. Our method is based on carefully using the properties that we derive in
order to refine the solution of the optimization problem OPT.
violates some inequality constraints given by (28) then 9i
Proof: Assume to the contrary that 8i - In this case Kuhn-Tucker conditions reduce to the
equality constraint (27), the set of inequality constraints (28) plus the Lagrangian condition given in (25).
On the other hand, SOPT , which is the solution of OPT, should satisfy (27) and the Lagrangian condition
(25). In other words, solving OPT is always equivalent to solving a set of non-linear equations which
are identical to Kuhn-Tucker conditions of OPT-L except inequality constraints, by setting 8i -
Hence, if there were a solution to OPT-L where 8i - then that solution would be returned by the
algorithm solving OPT and would not violate inequality constraints. However, given that the solution
SOPT failed to satisfy all the inequality constraints we reach a contradiction. Therefore, there exists at
least one Lagrange multiplier - i which is strictly greater than 0.Claim 3 9j
Proof: For the sake of contradiction, assume that 8j - j ? 0. In this case Equation (30) enforces
that 8i t were true,
will be equal to 0, leaving the slack d totally unutilized.
In this case, this clearly would not be the optimal solution due to the nondecreasing nature of reward
functions.In the rest of the paper, we use the expression "the set of functions" instead of "the set of indices
of functions" unless confusion arises. Let:
Remember that 1
is the marginal return associated with f x (t x ) and is denoted by w x (t x ). In-
formally, \Pi contains the functions f x 2 F with the smallest marginal returns at the lower bound 0,
Lemma 1 If SOPT violates some inequality constraints then, in SOPT \GammaL , t
Proof: Assume that 9m 2 \Pi such that t m ? 0. In this case, Equation (30) implies that the
corresponding we know that 9j such that - j ? 0. By Equation (30), t Using
Equation (29), we can writeb m
the concavity property of f m suggests that 1
(0). But in this case we
contradicting the assumption that m 2 \Pi. Hence -m ? 0 and by
Equation 0.In view of Lemma 1, we present the algorithm to solves Problem OPT-L in Figure 13 .
Algorithm OPT-L(F,d)
1 Evaluate the solution SOPT of the optimization
problem (without inequality constraints)
2 If all the inequality constraints are satisfied then SOPT \GammaL =SOPT ; exit
3 Compute \Pi from equation
6 goto Step 1

Figure

13: Algorithm to solve Problem OPT-L
Complexity: The time complexity COPT (n) of Algorithm OPT is O(n) (If the mentioned closed
apply, then the complexity is clearly linear. Otherwise the unique unknown - can be solved
in linear time under concavity assumptions, as indicated in [14, 15, 18]). Lemma 1 immediately implies
the existence of an algorithm which sets t re-invokes Algorithm OPT for the
remaining tasks and slack (in case that some inequality constraints are violated by SOPT ). Since the
number of invocations is bounded by n, the complexity of the algorithm which solves OPT-LU is O(n 2 ).
7.2.1 Faster Solution for Problem OPT-L
In this section, we present a faster algorithm of time complexity O(n \Delta log n), to solve OPT-L. We will
make use of the new (faster) algorithm in the final solution of OPT-LU.
Consider Algorithm OPT-L depicted in Fig. 13. Let F k be the set of functions passed to OPT during
the k th iteration of Algorithm OPT-L, and \Pi k be the set of functions with minimum marginal returns
at the lower bounds (minimum w i (0) values) during the k th iteration (Formally, \Pi
by f 0
y be the number of distinct w i (0) values among functions in F,
and m   - n   be the iteration number where Algorithm OPT returns a solution set which satisfies the
constraint set given by (28) for the remaining t i values. Note that the elements of \Pi
be produced in O(n \Delta log n) time during the preprocessing phase. Clearly, Algorithm OPT-L sequentially
sets returns a solution which does not violate
the constraint set for the remaining unknowns at the (m   ) th iteration.
A tempting idea is to use binary search in the range [1; n   ] to locate the critical index m   in a faster
way. However, to justify the correctness of such a procedure one needs to prove that if one had further
set invoked subsequently the algorithm OPT, then
SOPT obtained in this way would have still satisfied the constraint set given by (28). Notice that if
this property does not hold, then it is not possible to determine the "direction" of the search by simply
testing SOPT at a given index i, since we must be assured that there exists a unique index m   such that:
setting invoking OPT does not provide a solution SOPT which
satisfies the inequality constraints whenever 1 -
setting invoking OPT does provide a solurion SOPT which satisfies
the inequality constraints whenever m
The first of these properties follows directly from the correctness of Algorithm OPT-L. It turns
out that the second property also holds for concave objective functions as proven below. Hence, the
time complexity COPT \GammaL (n) may be reduced to O(n \Delta log n) by using a binary search like technique.
Algorithm FAST-L which solves Problem OPT-L in time O(n \Delta log n) is shown in Figure 14.
7.2.2 Correctness proof of the Fast Algorithm
We begin by introducing the following additional notation regarding the k th iteration of Algorithm
OPT-L.
assigned to the optional part of task T i by OPT during the k th iteration of
Algorithm OPT-L
solution produced by OPT during the k th iteration of Algorithm OPT-L
0g: the set of indices for which the solution SOPT;k violates inequality constraints.
Clearly, Algorithm OPT-L successively sets t
returns a solution which does not violate any constraints for functions in Fm   at the (m   ) th iteration.
Algorithm FAST-L uses binary search to determine the critical index m   efficiently. The correctness of
Algprithm OPT-L assures that 8 invoking OPT
Algorithm FAST-L(F,d)
Evaluate SOPT of the corresponding Problem OPT
2 If all the constraints are satisfied then SOPT \GammaL =SOPT ; exit
3 Enumerate the functions in F according to the nondecreasing order
of w j (0) values and construct the sets \Pi
6 Evaluate SOPT by invoking OPT(\Pi m+1 [
7 if a constraint is violated
9 else f
Evaluate SOPT by invoking
12 if a constraint is violated
14 else f

Figure

14: Fast Algorithm for Problem OPT-L
would yield a non-empty violating set V y for the remaining tasks. Finally, Proposition 4 establishes
that 8 y - m   \Gamma 1, V y will always remain empty after setting t
and invoking OPT, since this would leave even more slack for the remaining tasks. In the algorithm
FAST-L, a specific index m is tested at each iteration to check whether it satisfies the property
and ;. If this is the case, then since there is only one index m   satisfying this
property. However, in case that Vm 6= ; then we can infer that and the next probe is
determined in the range (m; n   ). Finally, if both then we restrict the search in
the range (0;
Proposition 4 Suppose that, during the execution of Algorithm OPT-L, SOPT;k does not violate some
inequality constraints (i.e., . Then the th invocation of
Algorithm OPT for the remaining tasks yields SOPT;k+1 such that t i;k+1 - t i;k for all
(which implies that V k+1 is still empty).
Proof: Note that t i;k - 0 8 by assumption. Based on the optimality property of
subproblems, if the k th invocation of Algorithm OPT yields an optimal solution, it will also generate
the optimal distribution of d \Gamma
among functions in F k \Gamma \Pi k . However,
the th invocation provides optimal distribution of d among functions in F k \Gamma \Pi k as well
(by setting t Thus, two successive invocations of Algorithm OPT can be written as:
maximize
subject to
and
maximize
subject to
Hence the proof will be complete if we show that 8i 2 F
Any solution SOPT;k should satisfy first-order necessary conditions for Lagrangian [22]:
The necessary conditions (34) giveb c
b d
For the sake of contradiction, assume that 9w 2 F
there must be some y 2 F k \Gamma \Pi k such that t y;k+1 ? t y;k . We distinguish two cases:
1. f w is nonlinear, that is, its derivative is strictly decreasing. Since f y is also concave, we can
by f 0
by f 0
are clearly inconsistent with
Equations (35) and (36). This can be easily seen by substituting w for c and y for d in Equations
(35) and (36), respectively.
2. f w is linear, which implies that f 0
j. In this case, to satisfy Equations (35)
and
y should be also linear of the form f y
bw . Hence, two functions
have the same marginal return
by But remembering our assumption from Section
7.1 that Algorithm OPT treats all linear functions of the same marginal return "fairly" (that is,
assigns them the same amount of service time), we reach a contradiction since t w;k was supposed
to be greater than t y;k .
Complexity: At most O(log n) probes are made during binary search and at each probe Algorithm
OPT is called twice. Recall that Algorithm OPT has the time complexity O(n). The initial cost of
sorting the derivative values is O(n log n). Hence the total complexity is COPT \GammaL
log log n), which is O(n \Delta log n).
7.3 Combining All Constraints: Solution of Problem OPT-LU
An instance of Problem OPT-LU is characterized by the set F= ff of nondecreasing,
differentiable, and concave reward functions, the set O= of upper bounds on the length
of optional execution parts, and available slack d:
maximize
subject to
We recall that
in the specification of OPT-LU.
We first observe the close relationship between the problems OPT-LU and OPT-L. Indeed, OPT-LU
has only an additional set of upper bound constraints. It is not difficult to see that if SOPT \GammaL satisfies
the constraints given by Equation (39), then the solution SOPT \GammaLU of problem OPT-LU is the same
as SOPT \GammaL . However, if an upper bound constraint is violated then we will construct the solution
iteratively in a way analogous to that described in the solution of Problem OPT-L.
contains the functions f x 2 F with the largest
marginal returns at the upper bounds, w x (o x ).
The algorithm ALG-OPT-LU (see Figure 15) which solves the problem OPT-LU is based on the
successive invocations of FAST-L. First, we find the solution SOPT \GammaL of the corresponding problem
OPT-L. We know that this solution is optimal for the simpler problem which does not take into account
upper bounds. If the upper bound constraints are automatically satisfied, then we are done. However,
if this is not the case, we set t \Gamma. Finally, we update the sets F, O and the slack d before
going through the next iteration.
Correctness: Most of the algorithm is self-explanatory in view of the results obtained in previous
sections. However, Line 5 of ALG-OPT-LU requires further elaboration. In addition to constraints
(38), (39) and (40), the necessary and sufficient Kuhn-Tucker conditions for Problem OPT-LU can be
expressed as:
Algorithm OPT-LU(F,O,d)
3 Evaluate SOPT \GammaL by invoking Algorithm FAST-L
4 if all upper bound constraints are satisfied then
set F=F\Gamma\Gamma
9 set O=O\Gammafo x jx 2 \Gammag

Figure

15: Algorithm to solve Problem OPT-LU
are Lagrange multipliers.
violates upper bound constraints given by Equation (39) then 9i -
Proof: Assume that 8i -
In this case, Kuhn-Tucker conditions (42) and (44) vanish. Also
conditions (38), (40), (41), (43) and (45) become exactly identical to Kuhn-Tucker conditions of Problem
OPT-L. Thus, SOPT \GammaL returned by Algorithm FAST-L is also equal to SOPT \GammaLU if and only if it satisfies
the extra constraint set given by (39).Claim 5 8i
Proof: Assume that 9i such that -
In this case, (42) and (43) force us to choose
which implies that this is contrary to our assumption that
the specification of the problem.
Now we are ready to justify line 5 of the algorithm:
violates upper bound constraints given by (39) then , in SOPT \GammaLU , t
\Gamma.
Proof: We will prove that the Lagrange multipliers -
are all non-zero, which will imply
(by (42)) that t We know that 9j such that
5. Using (41) we can
which gives (since t
necessarily less than or equal to , we can deduce 1
contradicts our assumption that m 2 \Gamma.Complexity: Notice that the worst case time complexity of each iteration is equal to that of
Algorithm FAST-L, which is O(n \Delta log n). Observe that the cardinality of F decreases by at least 1
after each iteration. Hence, the number of iterations is bounded by n. It follows that the total time
complexity COPT \GammaLU (n) is O(n 2 \Delta log n).
8 Conclusion
In this paper, we have addressed the periodic reward-based scheduling problem. We proved that when
the reward functions are convex, the problem is NP-Hard. Thus, our focus was on linear and concave
reward functions, which adequately represent realistic applications such as image and speech processing,
time-dependent planning and multimedia presentations. We have shown that for this class of reward
there exists always a schedule where the optional execution times of a given task do not change
from instance to instance. This result, in turn, implied the optimality of any periodic real-time policy
which can schedule a task set of utilization k on k processors. The existence of such policies is well-known
in real-time systems community: RMS (with harmonic periods), EDF and LLF for uniprocessor
systems, and in general, any scheduling policy which can fully utilize a multiprocessor system. We have
also presented polynomial-time algorithms for computing the optimal service times. We believe that
these efficient algorithms can be also used in other concave resource allocation/QoS problems such as
the one addressed in [26].
We underline that besides clear and observable reward improvement over previously proposed sub-optimal
policies, our approach has the advantage of not requiring any runtime overhead for maximizing
the reward of the system and for constantly monitoring the timeliness of mandatory parts. Once optimal
optional service times are determined statically by our algorithm, an existing (e.g., EDF) scheduler does
not need to be modified or to be aware of mandatory/optional semantic distinction at all. In our opinion,
this is another major benefit of having pre-computed and optimal equal service times for a given task's
invocations in reward-based scheduling.
In addition, Theorem 1 implies that as long as we are concerned with linear and concave reward
functions, the resource allocation can be also made in terms of utilization of tasks without sacrificing
optimality. In our opinion, this fact points to an interesting convergence of instance-based [7, 21] and
utilization-based [26] models for the most common reward functions.
About the tractability issues regarding the nature of reward functions, the case of step functions
was already proven to be NP-Complete ([21]). By efficiently solving the case of concave and linear
reward functions and proving that the case of convex reward functions is NP-Hard, efficient solvability
boundaries in (periodic or aperiodic) reward-based scheduling have been reached by our work (assuming
Finally, we have provided examples to show that the theorem about the optimality of identical
service times per instance no longer holds, if we relax some fundamental assumptions such as the
deadline/period equality and the availability of the dynamic priority scheduling policies. Considering
dynamic aperiodic task arrivals and investigating good approximation algorithms for intractable cases
such as step functions and error cumulative jobs can be major avenues for reward-based scheduling.



--R

A Polynomial-time Algorithm to solve Reward-Based Scheduling Prob- lem
Fairness in periodic real-time scheduling

Solving time-dependent planning problems
Scalable Video Coding using 3-D Subband Velocity Coding and Multi-Rate Quan- tization
Scalable Video Data Placement on Parallel Disk data arrays.
Scheduling periodic jobs that allow imprecise results.
Algorithms for Scheduling Real-Time Tasks with Input Error and End-to-End Deadlines
An extended imprecise computation model for time-constrained speech processing and generation

A dynamic priority assignment technique for streams with (m
Architectural foundations for real-time performance in intelligent agents
Reasoning under varying and uncertain resource constraints
Efficient On-Line Processor Scheduling for a Class of IRIS (Increasing Reward with Increasing Service) Real-Time Tasks

Algorithms and Complexity for Overloaded Systems that Allow Skips.


Imprecise Results: Utilizing partial computations in real-time systems
Scheduling Algorithms for Multiprogramming in Hard Real-time Environment
Algorithms for scheduling imprecise computations.
Linear and Nonlinear Programming
Scheduling Algorithms for Fault-Tolerance in Hard-Real-Time Systems
Fundamental Design Problems of Distributed systems for the Hard Real-Time Environment
Classical Optimization: Foundations and Extensions
A Resource Allocation Model for QoS Management.
Algorithms for scheduling imprecise computations to minimize total error.
Image Transfer: An end-to-end design
Producing monotonically improving approximate answers to relational algebra queries.
Anytime Sensing
--TR

--CTR
R. M. Santos , J. Urriza , J. Santos , J. Orozco, New methods for redistributing slack time in real-time systems: applications and comparative evaluations, Journal of Systems and Software, v.69 n.1-2, p.115-128, 01 January 2004
Hakan Aydin , Rami Melhem , Daniel Moss , Pedro Meja-Alvarez, Power-Aware Scheduling for Periodic Real-Time Tasks, IEEE Transactions on Computers, v.53 n.5, p.584-600, May 2004
Shaoxiong Hua , Gang Qu , Shuvra S. Bhattacharyya, Energy reduction techniques for multimedia applications with tolerance to deadline misses, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
Xiliang Zhong , Cheng-Zhong Xu, Frequency-aware energy optimization for real-time periodic and aperiodic tasks, ACM SIGPLAN Notices, v.42 n.7, July 2007
Melhem , Nevine AbouGhazaleh , Hakan Aydin , Daniel Moss, Power management points in power-aware real-time systems, Power aware computing, Kluwer Academic Publishers, Norwell, MA, 2002
Melhem , Daniel Moss, Maximizing rewards for real-time applications with energy constraints, ACM Transactions on Embedded Computing Systems (TECS), v.2 n.4, p.537-559, November
Jeffrey A. Barnett, Dynamic Task-Level Voltage Scheduling Optimizations, IEEE Transactions on Computers, v.54 n.5, p.508-520, May 2005
Lui Sha , Tarek Abdelzaher , Karl-Erik rzn , Anton Cervin , Theodore Baker , Alan Burns , Giorgio Buttazzo , Marco Caccamo , John Lehoczky , Aloysius K. Mok, Real Time Scheduling Theory: A Historical Perspective, Real-Time Systems, v.28 n.2-3, p.101-155, November-December 2004
deadline scheduling;real-time systems;reward maximization;periodic task scheduling;imprecise computation