On-line scheduling policies for a class of IRIS (increasing reward with increasing service) real-time tasks

We consider a real-time task model where a task receives a ''reward'' that depends on the amount of service received prior to its deadline. The reward of the task is assumed to be an increasing function of the amount of service that it receives, i.e., the task has the property that it receives increasing reward with increasing service (IRIS). We focus on the problem of on-line scheduling of a random arrival sequence of IRIS tasks on a single processor with the goal of maximizing the average reward accrued per task and per unit time. We describe and evaluate several policies for this system through simulation and through a comparison with an unachievable upper bound. We observe that the best performance is exhibited by a two-level policy where the top-level algorithm is responsible for allocating the amount of service to tasks and the bottom-level algorithm, using the earliest deadline first (EDF) rule, is responsible for determining the order in which tasks are executed. Furthermore, the performance of this policy approaches the theoretical upper bound in many cases. We also show that the average number of preemptions of a task under this two-level policy is very small.