Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks
2003 (English)Report (Other academic)
We address in this report the problem of scheduling for multiprocessor real-time systems comprised of hard and soft tasks. We use utility functions associated to soft tasks that capture their relative importance and how the quality of results is influenced when a soft deadline is
missed. The problem is thus finding a task execution order that maximizes the total utility and guarantees meeting the hard deadlines. We consider time intervals rather than fixed execution times for tasks. On the one hand, a single static schedule computed off-line is too pessimistic. On the other hand, a purely on-line approach, which computes a new schedule every time a task completes considering the actual conditions, incurs an overhead that is unacceptable due to the high complexity of the problem. We propose a quasi-static solution where a number of schedules are computed at design-time, letting only for run-time the selection of a particular schedule based on the actual execution times. We propose an exact algorithm as well as heuristics that tackle the time and memory complexity of the problem. We evaluate our approach through synthetic examples and a realistic application.
Place, publisher, year, edition, pages
Linköping, Sweden: Embedded Systems Lab, IDA, Linköping University , 2003.
quasi-static scheduling, real-time systems, hard tasks, soft tasks
IdentifiersURN: urn:nbn:se:liu:diva-23311Local ID: 2739OAI: oai:DiVA.org:liu-23311DiVA: diva2:243625