ORDONNANCEMENT À MIGRATIONS RESTREINTES

Algorithme d’ordonnancement 

Travaux existants

À notre connaissance, l’approche FJΠ a été peu étudiée. Nous pouvons citer les travaux de Baruah et Carpenter. Ils ont proposé deux algorithmes dans [BC03],r-EDF basé sur EDF etr-PriD basé sur PriD [GFB03]. Ce travail a été étendu au modèle des architectures à processeurs uniformes par Funk et Baruah [FB05]. Un algorithme à migrations restreintes fondé sur EDF a été proposé par Anderson, Bud et Devi [ABD08], mais dans le cas d’un ordonnancement temps réel souple. Cette approche a aussi été utilisée par Dorin et al. pour proposer un algorithme de partitionnement des instances hors-ligne et un ordonnancement en ligne basé sur EDF [DMYGR10]. Tous ces travaux considèrent que l’algorithme d’attribution des priorités est EDF. Ha et Liu ont présenté une manière d’ordonnancer des instances avec un algorithme de la classe (FixedTaskPriorityFixedJobProcessor) [HL94]. Ils ont montré que cette approche d’ordonnancement n’était pas prédictible. Fisher a plus récemment proposé un une condition suffisante d’ordonnancement pour cet algorithme [Fis07]. Mais il n’a pas abordé la notion de prédictibilité. 

Laxité

Lorsque l’on parle d’ordonnancement avec laxité, il est tout naturel de penser à l’algorithme LLF [Leu89, DM89]. Nous considérons toutefois dans ce chapitre un algorithme de la classe d’ordonnancement FTP. La laxité est utilisée pour prendre des décisions d’ordonnancement aux instants d’activations des instances, c’est-à-dire à chaque début d’instance, et pas pendant son exécution comme avec LLF. Nous considérons le critère de laxité car nous nous intéressons à la robustesse, qui consiste à exploiter le temps pendant lequel le processeur est oisif pour permettre des déviations sur les paramètres temporels. Même si la valeur de laxité calculée à l’instant de l’activation de l’instance peut être amenée à diminuer au cours de son exécution, la connaissance de cette valeur peut permettre la mise en place d’un mécanisme similaire au vol de temps creux. Le vol de temps creux consiste à récupérer les temps d’oisiveté afin d’exécuter entre autres des traitements apériodiques. À l’instant de son activation t = ri,k, la laxité Li,k(t) de l’instance Ji,k sur le proces  instance ri di [e − i , e+ i ] J1 0 10 [5, 5] J2 0 10 [2, 6] J3 4 15 [8, 8] J4 0 20 [10, 10] J5 5 200 [100, 100] J6 7 25 [2, 2] TABLE 5.2 – Paramètres temporels des instances de l’exemple de la figure 5.1. seur πj est donnée par : Li,k(t) = Di − Ci − X Jj∈hp(πj ,Ji,k) e ∗ j (t) (5.1) Les valeurs données par l’équation 5.1 correspondent à la laxité dans le pire cas. La laxité Li,k(t) d’une instance Ji,k est une fonction décroissante qui décroît lorsqu’une instance de plus haute priorité que Ji,k est activée sur le même processeur.

Anomalies d’ordonnancement

La preuve de non prédictibilité de Ha et Liu est basée sur l’exemple donné par la figure 5.1. Leur algorithme d’ordonnancement fonctionne de la manière suivante. Lorsqu’une instance est activée, elle peut être soit démarrée sur un processeur libre, soit mise en attente de libération d’un processeur. Un processeur est considéré libre relativement au niveau de priorité de l’instance active si ce processeur n’exécute pas d’instance de priorité supérieure. Si la tâche nouvellement activée préempte une instance en cours d’exécution, cette dernière est alors mise en attente de libération du processeur sur lequel elle s’exécutait. Les paramètres temporels des 6 instances sont donnés dans la table 5.2. Il faut remarquer que l’instance J2 peut être exécutée pour une durée comprise entre 2 et 6 unités de temps. Toutes les autres instances ne peuvent être exécutées que pour une durée fixée (e − i = e + i ). Dans la figure 5.1(a), l’instance J2 est exécutée pour une durée e2 = 6, soit ∀i ∈ [1 − 6], ei = e + i . Dans la figure 5.1(b), e2 = 2 et ∀i ∈ [1 − 6], ei = e − i . Ces deux figures représentent donc l’ordonnancement dans le pire cas (figure 5.1(a)) et l’ordonnancement dans le meilleur cas (figure 5.1(b)) relativement aux coûts d’exécution des instances. Pour ces deux ordonnancements, aucune échéance n’est dépassée. Pourtant, dans la figure 5.1(c), l’instance J4 rate son échéance alors que l’instance J2 est exécutée pour une durée e2 = 3. Nous pouvons remarquer que ce phénomène se produit car le processeur π2 devient disponible à l’instant t = 4 car J4 est moins prioritaire que J3. J3 est alors admise sur π2, mais la laxité de J4 n’est plus suffisante pour lui permettre de terminer son exécution avant son échéance. Nous pouvons aussi remarquer que le meilleur cas pour J4 se produit lorsque J2 est exécutée pour e2 = 5 (figure 5.1(d)). Cet algorithme n’est donc pas prédictible.

Description de l’algorithme

Nous proposons l’algorithme r-SP_wl (r-SP faisant référence à r-EDF mais avec un ordonnancement FTP, aussi appelé Static-Priority (SP) dans l’état-de-l’art, et wl pour with laxity). Cet algorithme prend ses décisions d’ordonnancement lors de l’activation d’une instance en fonction de la laxité des instances actives. L’ordonnanceur doit stocker pour chaque instance ordonnancée sa valeur de laxité pour pouvoir la consulter et la mettre à jour. Nous considérons des tâches à échéances contraintes, ce qui implique qu’au plus une seule instance d’une même tâche peut être activée à l’instant t. Nous faisons l’hypothèse d’un ordonnanceur capable d’attribuer une priorité différente à chaque tâche. Nous utilisons alors une table d’association (à hachage parfait) pour associer une valeur de laxité à un niveau de priorité. En effet, une telle structure d’association permet d’obtenir la valeur associée en un temps constant.  Les instances sont admises sur un processeur à l’instant de leur activation. Une instance Ji,k peut être admise sur un processeur πj à l’instant t = ri,k si et seulement si : – la laxité de Ji,k est supérieure ou égale à 0. Li,k(t) ≥ 0 avec Li,k(t) donnée par l’équation (5.1) ; – la laxité des instances de priorité inférieure à Ji,k est supérieure ou égale à 0 après admission de Ji,k : ∀Jj ∈ lp(πj , Ji,k), Lj (t) − ei,k ≥ 0 (5.2) La condition donnée par l’équation (5.2) garantit qu’aucune instance de priorité inférieure à celle de l’instance Ji,k nouvellement admise ne dépassera son échéance. Nous noterons que cette phase d’admission consiste à garantir, qu’à l’instant t, l’instance ayant la plus petite valeur de laxité, parmi toutes les instances de priorité inférieure, en aura suffisamment pour ne pas dépasser son échéance. Cette opération consiste à vérifier la valeur de laxité de toutes les instances de priorité inférieure à celle de Ji,k. Pour un processeur πj , elle a une complexité linéaire en le nombre de tâches. Lorsqu’une instance Ji,k est activée ou admise, une entrée est ajoutée dans la structure de données pour stocker sa valeur de laxité telle que calculée par l’équation (5.1). Avant de calculer cette valeur, le coût d’exécution restant ej (ri,k) ∗ de toutes les instances Jj plus prioritaires que Ji,k doit être mis à jour. Le coût d’exécution restant des instances en cours d’exécution est décrémenté de la durée écoulée depuis le dernier instant d’ordonnancement. Quand plusieurs processeurs sont disponibles lors de l’admission d’une instance, notre algorithme admet celle-ci sur le processeur pour lequel la valeur de laxité minimale est la plus grande. La laxité minimale à l’instant t d’un processeur πj est donnée par minJi∈J(πj ) Li(t). Ce choix n’est pas optimal. Il permet néanmoins une bonne répartition des instances sur les différents processeurs dans le cas où le système n’est pas trop chargé. Cela a pour effet de pouvoir offrir plus de marge aux tâches. Notre algorithme d’ordonnancement étant un algorithme en ligne avec des migrations, il est difficile de calculer cette valeur de marge autrement qu’en déroulant l’ordonnancement sur une période d’étude. À la terminaison d’une instance, celle-ci est arrêtée et les ressources qu’elle a utilisées sont libérées. Il est important de noter que, d’après l’équation (5.1), la laxité d’une instance est calculée à partir de son WCET. Si cette instance Ji termine son exécution avant son WCET, l’ordonnanceur continue de considérer l’interférence de celleci sur les instances moins prioritaires jusqu’à ce que son WCET ait été virtuellement consommé. Il adoptera donc un comportement oisif en n’admettant pas d’instance supplémentaire qui ne l’aurait pas été dans le cas où Ji aurait été exécutée pour une durée égale à son WCET.