Affiliations: Laboratoire d'Informatique Scientifique et
Industrielle, École Nationale de Mécanique et d'Aérotechnique,
Téléport 2 – BP 40109 F-86961 Chasseneuil Futuroscope Cedex, France
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 and to minimize the maximum response time of
tasks.
