|
Published Articles >> Table of Contents >> Abstract
25th IEEE International Real-Time Systems Symposium (RTSS'04)
pp. 47-56
Negative Results for Scheduling Independent Hard Real-Time Tasks with Self-Suspensions
Frederic Ridouard, LISI-ENSMA
Pascal Richard, LISI-ENSMA
Francis Cottet, LISI-ENSMA
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/REAL.2004.35
Send link to a friend
| Abstract |
|
In most real-time systems, tasks use remote operations that are executed upon dedicated processors. External operations introduce self-suspension delays in the behavior of tasks. This paper presents several negative results concerning scheduling independent hard real-time tasks with self-suspensions. Our main objective is to show that well-known scheduling policies such as fixed-priority or Earliest Deadline First are not efficient to schedule such task systems. We prove the scheduling problem to be NP-hard in the strong sense, even for synchronous task systems with implicit deadlines. We also show that scheduling anomalies can occur at run-time: reducing the execution requirement or the suspension delay of a task can lead the task system to be infeasible under EDF. Lastly, we present negative results on the worst-case performances of well-known scheduling algorithms (EDF, RM, DM, LLF, SRPTF) to maximize tasks completed by their deadlines.
|
 Additional Information
|
Citation:
Frederic Ridouard, Pascal Richard, Francis Cottet,
"Negative Results for Scheduling Independent Hard Real-Time Tasks with Self-Suspensions,"
rtss,
pp. 47-56,
25th IEEE International Real-Time Systems Symposium (RTSS'04),
2004
|
|
