sch_rep03

Static Scheduling of Monoprocessor Real-Time Systems composed of Hard and Soft Tasks

Luis Alejandro Cortes Author homepage
 
Petru Eles Author homepage
Zebo Peng Author homepage

Technical Report, Embedded Systems Lab, Dept. of Computer and Information Science, Linköping University, April 2003.

ABSTRACT
In this report we address the problem of static scheduling of real-time systems that include both hard and soft tasks. We consider systems in which both hard and soft tasks are periodic, and our analysis take into account the data dependencies among tasks. In order to capture the relative importance of soft tasks and how the quality of results is affected when missing a soft deadline, we use utility functions associated to soft tasks. Thus our objective is to find a schedule that maximizes the total utility and at the same time guarantees hard deadlines. We use the expected duration of tasks for evaluating utility functions whereas we use the maximum duration of tasks for ensuring that hard deadlines are always met. We show that the problem we study in this report is NP-complete and we present an algorithm that finds the optimal schedule as well as different heuristics that find near-optimal solutions at reasonable computational cost.


Related files:
sch_rep03.pdfAdobe Acrobat portable document
sch_rep03.ps.gzpostscript document, compressed (with gzip)


[AEP03] Luis Alejandro Cortes, Petru Eles, Zebo Peng, "Static Scheduling of Monoprocessor Real-Time Systems composed of Hard and Soft Tasks", Technical Report, Embedded Systems Lab, Dept. of Computer and Information Science, Linköping University, April 2003.
( ! ) perl script by Giovanni Squillero with modifications from Gert Jervan   (v3.1, p5.2, September-2002-)
Last modified on Monday December 04, 2006 by Gert Jervan