Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks
2005 (English)In: 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA05,2005, Hong Kong: IEEE Computer Society Press , 2005, 422- p.Conference paper (Refereed)
We address in this paper the problem of scheduling for multiprocessor real-time systems with hard and soft tasks. Utility functions are associated to soft tasks to capture their relative importance and how the quality of results is affected when a soft deadline is missed. The problem is to find a task execution order that maximizes the total utility and guarantees the hard deadlines. In order to account for actual execution times, we consider time intervals for tasks rather than fixed execution times. A single static schedule computed off-line is pessimistic, while a purely on-line approach, which computes a new schedule every time a task completes, incurs an unacceptable overhead. We propose therefore a quasi-static solution where a number of schedules are computed at design time, leaving for run-time only 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
Hong Kong: IEEE Computer Society Press , 2005. 422- p.
real-time systems, quasi-static scheduling, hard tasks, soft tasks
IdentifiersURN: urn:nbn:se:liu:diva-28504DOI: 10.1109/RTCSA.2005.72Local ID: 13653ISBN: 0-7695-2346-3OAI: oai:DiVA.org:liu-28504DiVA: diva2:249314
11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications RTCSA05