Ordonnancement de tâches temps réel avec suspension.

Frédéric Ridouard
LISI/ENSMA - Poitiers



Les systèmes temps-réel utilisent bien souvent un modèle de tâche 
simplifié. Dans la majorité des applications, les tâches sont 
représentées par un unique bloc d’exécution. Mais certaines tâches 
ont besoin au cours de leur exécution d’effectuer des opérations 
externes (comme par exemple des opérations d’entrée/sortie) et 
ainsi doivent se suspendre. Ce sont des tâches dites à suspension. 
Nous montrons que le problème d’ordonnancement de tâche à suspension 
est un problème NP-Difficile au sens fort. Nous démontrons également 
qu’il n’existe aucun algorithme optimal qui soit polynomial ou même 
pseudo-polynomial en temps de calculs pour choisir la prochaine tâche 
à s’exécuter. Et, nous démontrons la faiblesse de politiques 
classiques d’ordonnancement bien connues comme EDF (Earliest Deadline 
First), RM (Rate Monotonic), DM (Deadline Monotonic) et LLF (Least 
Laxity First) même sur des instances de tâches avec une charge 
processeur faible, proche de zéro.