Static Scheduling of Monoprocessor Real-Time Systems composed of Hard and Soft Tasks
The IEEE International Workshop on Electronic Design, Test and Applications (DELTA 2004), Perth, Australia, January 28-30, 2004, pp. 115-120
In this paper we address the problem of static scheduling of real-time systems that include both hard and soft tasks. We consider that hard as well as soft tasks are periodic and that there exist 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 an execution order for tasks 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 present an algorithm for finding the optimal schedule and also different heuristics that find near-optimal solutions at reasonable computational cost. The proposed algorithms are evaluated using a large number of synthetic examples.
Copyright note for papers published by the IEEE Computer Society:
Copyright IEEE. Personal use of this material is permitted. However,
permission to reprint/republish this material for advertising or
promotional purposes or for creating new collective works for resale
or redistribution to servers or lists, or to reuse any copyrighted
component of this work in other works, must be obtained from the IEEE.
[AEP04] Luis Alejandro Cortes, Petru Eles, Zebo Peng, "Static Scheduling of Monoprocessor Real-Time Systems composed of Hard and Soft Tasks", The IEEE International Workshop on Electronic Design, Test and Applications (DELTA 2004), Perth, Australia, January 28-30, 2004, pp. 115-120