Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /mnt/tanenbaum/sd4/projets/AlgoTR/_includes/path.php on line 15

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /mnt/tanenbaum/sd4/projets/AlgoTR/_includes/path.php on line 15

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /mnt/tanenbaum/sd4/projets/AlgoTR/_includes/path.php on line 15

Deprecated: preg_replace(): The /e modifier is deprecated, use preg_replace_callback instead in /mnt/tanenbaum/sd4/projets/AlgoTR/_includes/path.php on line 15

Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Time 

Presentation 

Article

N.C. Audsley

Younès.

L'assignation de priorité est parmi les sujets les plus étudiés dans la communauté de l'ordonnancement temps réel.
Les premiers travaux qui se sont intéressés à ce problème sont ceux de Liu et Layland qui ont proposé les deux fameuses politiques d'assignation de priorité Deadline Monotonic (DM) et Rate Monotonic (RM). Ils ont aussi prouvé que RM est optimal pour les systèmes de taches non concrets à échéance sur requête et DM pour ceux à échéance contrainte.
Ces deux politiques d'assignation de priorité ne sont pas optimales pour les systèmes de taches concrets.
Dans ce papier Audsley nous propose un algorithme d'assignation de propriété qui est optimal pour tous les systèmes de taches.
Cet algorithme explore de manière intelligente l'espace des assignations possibles, ce qui lui permet d'éviter une bonne partie de possibilités et de converger rapidement. L'assignation d'Audsley repose sur la propriété suivante : l'ordre des taches plus prioritaire ne change pas la faisabilité des taches moins prioritaires.
 
L'article fournit tous les calculs nécessaires pour le fonctionnement de l’algorithme d'assignation de priorités, à savoir :
  • un test pour savoir si on peut atteindre un scénario d'activation synchrone de toutes les taches en partant d'une activation quelconque,
  • un algorithme de calcul de temps réponse de tous les jobs activés durant la période d'étude (bornée par deux fois l'hypere-period),
  • un test de faisabilité qui teste si tous les jobs activés pendant la période d'étude respectent leurs échéances.