Heuristic Use of Singularities fro On-Line Scheduling of Real-Time Mandatory/Reward-Based Optional Systems

R. M. SANTOS; J. URRIZA; J. SANTOS; J. OROZCO

Viena

Conferencia; 14th Euromicro Conference on Real-Time Systems; 2002

IEEE Computer Society Press

The paper addresses the problem of on-line scheduling of mandatory/reward-based systems in which tasks have a hard real-time mandatory part and an optional part with a non-decreasing reward function associated to its execution. Four methods, generically called SH, are proposed. They are based on the detection of singularities, special instants that appear along the execution of the system. By applying some heuristic rules, the singularities and some of the following slots are used to process optional parts. To the best of the authors´ knowledge, papers published up to now on the subject of reward maximization require the functions to be continuously differentiable. Moreover, they cannot be executed on-line. On the contrary, the only requirement of the SH methods is that the functions are computable at every instant. After the system is proved to be schedulable by any of the available exact test off-line techniques, SH methods can be executed on-line. Their performance is evaluated using simulations performed on a synthetic set of tasks proposed in one of the outstanding papers on the subject and on sets of tasks randomly generated. The results are analysed and explained. The main conclusionis that , in all cases, the SH methods outperform the Best Incremental Return, often used as a yardstick.