Static Scheduling of Monoprocessor Real-Time Systems composed of Hard and Soft Tasks
2003 (English)Report (Other academic)
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.
Place, publisher, year, edition, pages
Linköping, Sweden: ESLAB, IDA, Linköpings Universitet , 2003.
static scheduling, real-time systems, hard tasks, soft tasks, utility function
IdentifiersURN: urn:nbn:se:liu:diva-23334Local ID: 2765OAI: oai:DiVA.org:liu-23334DiVA: diva2:243648