L’ORDONNANCEMENT ÉVÈNEMENTIEL TEMPS-RÉEL PEUT-IL ÊTRE DÉTERMINISTE

De l’origine du non-déterminisme

Les systèmes à ordonnancement évènementiel ne sont pas prévisibles. Ce point a été évoqué dans l’introduction de ce chapitre. Ce non-déterminisme trouve sa source dans le principe même de l’ordonnancement par priorité utilisé classiquement dans les systèmes temps-réel évènementiels. La première section de cette partie revient plus en détail sur ce point.

Où l’on analyse l’origine du non-déterminisme comportemental

Les systèmes temps-réel évènementiels, tels qu’ils sont classiquement implémentés, reposent sur un ordonnancement préemptif à priorités. Chaque tâche se voit attribuer une priorité d’exécution qui lui permet d’être exécutée préférentiellement aux tâches de niveau inférieur, éventuellement en interrompant l’exécution de celles-ci.

Raisonnons sur le cas simple à trois tâches présenté figure 6. La tâche B consomme des données produites par les tâches A et C. Elle est synchronisée sur la tâche A ; la relation entre C et B est supposée non bloquante. Les priorités respectives de ces trois tâches sont définies de la façon suivante : la tâche A est la plus prioritaire, vient ensuite la tâche B, puis la tâche C. Examinons le cas de figure où la tâche C est activée avant la tâche A. La durée d’activation de la tâche C n’étant pas constante1 , deux cas peuvent se présenter : dans le premier cas, la tâche C se termine avant l’activation de la tâche A ; dans le second cas, la tâche C n’est pas terminée lorsque la tâche A est activée, elle est donc préemptée par cette dernière, puis par la tâche B. Figure 6. Trois tâches dans un système évènementiel ordonnancé par priorités. La conséquence de cette indétermination d’exécution sur la tâche B est immédiate : dans le premier cas la tâche B exploitera les données issues de la dernière exécution de la tâche C ; dans le second cas la tâche B exploitera les données de l’occurrence d’exécution précédente. Dans un ordonnancement temporel, il est prévu dès la conception une durée d’exécution pour chaque tâche. La figure 7 présente schématiquement ce mécanisme d’ordonnancement pour les trois tâches précédentes Où l’on fixe la durée apparente d’exécution des tâches

– Le temps logique d’exécution

C’est ce que proposent Ghosal [33] et Liu [53]. Pour résoudre le problème du nondéterminisme comportemental, ils fixent la durée apparente d’exécution de chaque tâche du système depuis l’origine de son activation. Ghosak appelle cette durée le temps logique d’exécution (LET1 ) tandis que Liu la nomme plus simplement échéance (deadline). Les deux concepts sont cependant très similaires. Pour l’un comme pour l’autre, trois règles capitales régissent l’ordonnancement des tâches : • Lorsqu’une tâche est activée par un évènement, les données qu’elle exploite sont immédiatement échantillonnées, même si la tâche n’est pas immédiatement exécutée. Le décompte de l’échéance ou du LET commence à cet instant.

• Entre cet instant et l’expiration de l’échéance, la tâche doit être exécutée intégralement, quelque soit sa durée effective d’exécution et les préemptions qu’elle subit. • A l’issue de l’échéance, et seulement à cet instant, les données produites par la tâche sont mises à disposition des autres tâches du système. Figure 8. Le temps logique d’exécution (LET). Source [33]. Vu de l’extérieur, la tâche considérée semble donc avoir débuté à sa date d’activation et s’être achevée à l’issue de l’échéance. Figure 9. Ordonnancement à échéance. Source [53]. Ghosal met en œuvre des mécanismes d’échantillonnage des données1 qui garantissent l’isolation du contexte d’exécution de la tâche pendant le LET.