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.

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)).