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.
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.
[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. |
|
