luico_rtcsa05

Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks

Luis Alejandro Cortes Author homepage
 
Petru Eles Author homepage
Zebo Peng Author homepage

11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), Hong Kong, August 17-19, pp. 422-428

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


Related files:
luico_rtcsa05.camera.pdf, Adobe Acrobat portable document
luico_rtcsa05.camera.ps, postscript document

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.


[AEP05] Luis Alejandro Cortes, Petru Eles, Zebo Peng, "Quasi-Static Scheduling for Multiprocessor Real-Time Systems with Hard and Soft Tasks", 11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'05), Hong Kong, August 17-19, pp. 422-428
( ! ) perl script by Giovanni Squillero with modifications from Gert Jervan   (v3.1, p5.2, September-2002-)
Last modified on Monday December 04, 2006 by Gert Jervan