Bases d'ordonnancement pour STR

Les termes techniques utilisés ici sont identifiés et définis dans le glossaire proposé aux pages ≈5..8 de STR – Volume 00.

Ce qui suit est un bref des bases propres à la question de l'ordonnancement des STR. Vos notes de cours (si vous suivez un cours avec moi, à tout le moins, mais en général je présume) vont plus loin, et la littérature va évidemment beaucoup plus loin.

Périodicité des tâches et contraintes TR

Les tâches d'un STR peuvent être catégorisées par leur périodicité. Dans la littérature, on trouve essentiellement trois grandes familles de périodicités, soit celles des tâches périodiques, apériodiques et sporadiques. Chacune de ces familles est associée à un groupe de contraintes particulières (ce qui, dans la littérature, est plus implicite qu'explicite).

Tâches périodiques Tâches apériodiques Tâches sporadiques

Une tâche est dite périodique si le temps entre le début de chacune de ses occurrences est égal à sa période et si son échéance correspond à la fin de sa période.

Dans un STR, les tâches périodiques sont souvent des tâches TR au sens strict.

Une tâche périodique est donc assujettie à une contrainte de constance, par définition, et à une contrainte de brièveté – une telle tâche peut se compléter avant son échéance, mais pas après. L'affichage dans un jeu devant afficher images par secondes, avec une image affichée à chaque seconde précisément, s'inscrirait dans ce créneau.

Une tâche est dite apériodique si elle s'amorce à intervalles irréguliers. Dans un STR, il est fréquent que les tâches apériodiques soient des tâches TR au sens usuel plutôt qu'au sens strict du terme.

Les tâches apériodiques peuvent être assujetties à des contraintes de régularité, quoique ce ne soit pas nécessaire (p. ex. : une tâche associée à l'occurrence d'un événement physique peut être apériodique si l'événement l'est aussi), et sont typiquement soumises à une contrainte (souple) de brièveté, car dans le cas contraire on ne parlerait pas de tâche TR. Il est possible qu'une contrainte d'immédiateté soit aussi associée à une telle tâche.

Certaines tâches morcelées peuvent s'inscrire dans ce créneau : parfois, un système peut avoir de telles opérations à réaliser, et parfois pas, mais quand il y en a à faire, ces tâches doivent se terminer (ou s'interrompre, si elles ne sont pas terminées mais doivent se poursuivre ultérieurement) dans un délai maximal fixé par les conditions du STR dont elles font partie.

Une tâche est dite sporadique si elle est apériodique tout en demeurant TR au sens strict. Une contrainte particulière de toute tâche sporadique est que le temps minimal entre deux occurrences de celle-ci doit être connu au préalable (ce qui permet de planifier en vue du pire cas).

Le traitement d'un événement physique aux occurrences irrégulières mais dans un délai maximal d'exécution connu a priori (immédiateté et brièveté, dans un contexte TR strict) serait un exemple d'une tâche entrant dans cette catégorie. Pensez par exemple à une réaction à la pression d'une touche sur un piano : on ne sait pas au préalable quand le pianiste jouera, mais quand une touche est pressée, le son doit jouer immédiatement.

Ordonnancement de STR limités à des tâches périodiques

Le problème propre aux STR, qui sont d'abord et avant tout des systèmes, n'est pas tant celui de déterminer ou d'implémenter une tâche TR particulière mais bien d'ordonnancer un ensemble de tâches TR de manière à ce que toutes leurs contraintes soient respectées (TR strict) ou encore de manière à ce que les contraintes des tâches TR strictes soient respectées tout en minimisant les cas (et les conséquences) où les contraintes des tâches TR usuelles ne le seraient pas.

Nous couvrirons les ordonnanceurs TR tenant compte des tâches apériodiques ou sporadiques dans un document ultérieur, ceux-ci étant plus complexes, mais nous jetterons ici un bref coup d'oeil sur la question de l'ordonnancement d'un ensemble de tâches se limitant à des tâches périodiques (constantes et brèves).

Notez qu'on pourrait penser que la question de l'ordonnancement de tâches strictement périodiques serait chose simple, et ce l'est bien sûr parfois, mais le problème général comporte quelques caractéristiques amusantes qui méritent qu'on leur porte attention.

Un ensemble de tâches périodiques peut être connu a priori, par exemple dans le cas d'un système embarqué déployé sur un ordinateur de type industriel. Dans un tel cas, les paramètres d'exécution des tâches à ordonnancer seront aussi connus a priori, ce qui permet de parler d'ordonnancement de tâches périodiques statiques – pas que les tâches soient statiques, mais bien que leurs paramètres d'exécution de soient.

Si les éléments d'un ensemble de tâches périodiques varient à travers le temps, l'ordonnancement variera aussi, et il est possible que certains ensembles ne puissent pas être ordonnancés. Ceci explique que les ordonnancements de tâches périodiques soient souvent basés sur des paramètres connus a priori, et puissent même être générés de manière statique.

Tâches périodiques

Un ensemble de tâches périodiques peut s'exprimer sous la forme de telle sorte que pour . Dans cette notation, est le temps de calcul associé à la tâche et est sa période.

On comprendra que de manière générale, avec , le paramètre est une contrainte que l'ordonnanceur devra respecter (contrainte de constance) alors que le paramètre , qui décrit le pire cas pour le temps de calcul requis lors d'une exécution de , est un paramètre que la tâche s'engage à respecter.

On travaillera généralement avec des valeurs entières de et par souci de simplicité. De même, s'il y a des composantes incompressibles mais externes à dans l'exécution de (par exemple, une latence au démarrage), on inclura souvent ces paramètres dans l'évaluation de à moins que cela ne dénature le processus et qu'il soit important de considérer ces particularités de manière distinctes des paramètres d'exécution de .

Le temps que représente sera souvent estimé de manière exacte ou, au pire, raisonnablement pessimiste, du fait que dans un STR strict :

On peut représenter le profil d'exécution d'un ordonnancement de tâches TR comme un tableau dans lequel chaque case représente un moment discret dans l'exécution de l'une des tâches de cet ordonnancement. Dans un ordonnancement correct de  :

Cycles majeur et mineur

Deux paramètres clés des ordonnancements périodiques sont ce qu'on nomme son cycle majeur et son cycle mineur. Ces cycles sont des paramètres importants pour l'ordonnanceur, par pour les tâches elles-mêmes.

Cycle majeur Cycle mineur

Le cycle majeur d'un ordonnancement de tâches périodiques est le plus petit intervalle d'unités de temps menant à un cycle complet d'exécution pour toutes les tâches impliquées.Cela signifie qu'il n'y a pas lieu de prévoir un ordonnancement plus long que la longueur du cycle majeur pour l'ensemble des tâches impliquées : en pratique, ce cycle se répétera, tout simplement.

Exprimé autrement, il s'agit de la plus petite période à l'intérieur de laquelle toutes les tâches d'un ensemble donné se seront exécutées au moins une fois.

On peut dire que le cycle majeur d'un ensemble de tâches est la période de l'ensemble examiné de manière globale.

Calculer le cycle majeur d'un ensemble équivaut à évaluer le plus petit commun multiple (PPCM) des périodes des tâches de cet ensemble.

Le cycle mineur d'un ordonnancement de tâches périodiques, quant à lui, est le plus petit intervalle de temps au bout duquel une « décision » doit nécessairement être prise par l'ordonnanceur – le plus petit intervalle de temps susceptible de mener au passage d'une tâche à l'autre dans un ordonnancement donné.

Évidemment, le mot « décision » est quelque peu abusif ici, du fait que l'ordonnancement, une fois déterminé, sera typiquement fixe (pouvant même être statique, tel qu'indiqué plus haut), mais l'idée est que le début d'un cycle mineur est un point sensible pour le lancement d'une tâche périodique. Connaître le cycle mineur permet de construire un ordonnancement de manière plus efficace, en réduisant les moments candidats à provoquer un lancement de tâche.

En pratique, une tâche en exécution ne peut chevaucher le moment où on passe d'un cycle mineur à un autre. Les débuts de cycle mineurs sont aussi des débuts de tâches.

Calculer le cycle mineur d'un ensemble équivaut à évaluer le plus grand commun diviseur (PGCD) des périodes des tâches de cet ensemble.

Taux d'occupation

Le taux d'occupation d'une tâche dans un ordonnanceur donné est la partie d'un cycle majeur que le temps de calcul de occupera. Ce taux s'évalue comme suit :

\[ occupation(\gamma,T_i)=\frac{(\frac{cycle majeur(\gamma)}{P_i})C_i}{(cycle majeur(\gamma) )} \]

Ce taux est un nombre rationnel dans l'intervalle , bien entendu. Notez que le numérateur est nécessairement entier puisque par définition, divise . Le taux global d'occupation d'un ordonnanceur est la somme des taux d'occupation de ses tâches :

\[ occupation(\gamma)=\sum_{i=0}^n{occupation(\gamma,T_i)} \]

Pour réduire les erreurs sur les réels, on évaluera typiquement l'occupation de manière discrète, et on ne divisera par qu'au moment d'évaluer le taux d'occupation souhaité.

Tests « d'ordonnançabilité »

Faute d'un meilleur terme, nous utiliserons le néologisme « ordonnançabilité » pour indiquer la possibilité d'ordonnancer un ensemble de tâches. Une part importante de la littérature des ordonnanceurs dans les STR porte sur la détermination de tests efficaces d'ordonnançabilité pour un ensemble de tâches donné.

Un test d'ordonnançabilité est dit :

Pour bien des problèmes, identifier un test exact est Intractable au sens anglais du terme : soit indécidable, soit démesurément complexe sur le plan algorithmique.

Un test d'ordonnançabilité est typiquement appliqué au pire cas des tâches pour un système donné. Un test est durable (Sustainable) s'il continue à bien prédire l'ordonnançabilité d'un système de tâches quand les conditions s'améliorent. Pour les ordonnancements périodiques, fixés a priori, la durabilité est implicite, mais pour des ordonnancements aux paramètres plus complexes, cette caractéristique est un tenir-compte important.

Exemples concrets

Une condition nécessaire mais pas suffisante d'ordonnançabilité pour un ensemble de tâches périodiques est que :

\[occupation(\gamma) \le 1 \]

Si l'on retire le diviseur du calcul de l'occupation d'une tâche, le test d'ordonnançabilité ci-dessus devient une comparaison avec le cycle majeur de plutôt qu'avec la constante . Il est parfois plus simple de procéder ainsi.

Exemple 00 : soit l'ensemble de tâches périodiques suivant :

\[ \gamma={(P=5,C=5) } \] \[ cycle majeur(\gamma)=5 \] \[ cycle mineur(\gamma)=5 \] \[ occupation(\gamma)=1 \]

Cet ensemble est banal. Une seule tâche y occupe la totalité du temps de calcul : pensez à une boucle infinie qui fait le travail entier d'un STR et qui consomme la totalité du temps disponible sur « son » processeur. L'ensemble est ordonnançable de manière triviale (au sens mathématique du terme).

Exemple 01 : soit l'ensemble de tâches périodiques suivant :

\[ \gamma={(P=6,C=4) } \] \[ cycle majeur(\gamma)=6 \] \[ cycle mineur(\gamma)=6 \] \[ occupation(\gamma)*0,667 ou \frac{2}{3} \]

Cet ensemble est aussi banal. Une seule tâche doit s'y exécuter. Deux tiers du processeur seulement y sont accaparés. L'ensemble est ordonnançable de manière triviale et le taux d'occupation est de .

Exemple 02 : soit l'ensemble de tâches périodiques suivant :

\[ \gamma={(P=25,C=10),(P=25,C=8),(P=50,C=5),(P=50,C=4),(P=100,C=2) } \] \[ cycle majeur(\gamma)=100 \] \[ cycle mineur(\gamma)=25 \] \[ occupation(\gamma)=0,92 \]

Il est possible de construire un ordonnancement pour . En effet :

0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 4 4
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 3 3 3 3 * * *
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 2 2 2 2 2 * *
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 3 3 3 3 * * *

La représentation ci-dessus montre le cycle majeur (taille 100) et quatre cycles mineurs (chacun de taille 25), un par ligne. Chaque tâche apparaît comme une case identifiée par la mention (p. ex. : occupe les cases marquées , occupe les cases marquées ). Les cases marquées sont des cases disponibles.

Il est simple de vérifier ici que les périodes et les temps de calcul de chaque tâche sont respectés.

Exemple 03 : soit l'ensemble de tâches périodiques suivant :

\[ \gamma={(P=5,C=6)} \] \[ cycle majeur(\gamma)=5 \] \[ cycle mineur(\gamma)=5 \] \[ occupation(\gamma)=1,2 ou \frac{6}{5} \]

Autre ensemble banal. Une seule tâche doit s'y exécuter, mais son temps de calcul excède sa période. Le taux d'occupation dépasse . L'ensemble n'est donc pas ordonnançable, ce qui est constaté encore une fois de manière triviale.

Exemple 04 : soit l'ensemble de tâches périodiques suivant :

\[ \gamma={(P=6,C=4),(P=12,C=3)} \] \[ cycle majeur(\gamma)=12 \] \[ cycle mineur(\gamma)=6 \]

Cet ensemble est moins banal que les précédents. Deux tâches y sont prévues, qu'on peut identifier par et le cycle majeur correspond à PPCM(12,6), donc , alors que le cycle mineur correspond à PGCD(12,6), donc .

Ici, l'occupation totale de est inférieure à puisque

\[ occupation(\gamma,T_0)=\frac{(\frac{12}{6})4}{12}=\frac{8}{12}=\frac{2}{3} \] \[ occupation(\gamma,T_1)=\frac{(\frac{12}{12})3}{12}=\frac{3}{12}=\frac{1}{4} \] \[ occupation(\gamma)=\frac{2}{3}+\frac{1}{4}=\frac{8}{12}+\frac{3}{12}=\frac{11}{12} \cong 0,91667 \]

Pourtant, l'ensemble n'y est pas ordonnançable. Ceci se constate par construction d'un ordonnancement possible pour . Avant ordonnancement, on peut représenter l'ordonnanceur comme un tableau d'unités d'exécution discrètes de même taille, la taille de ce tableau étant donnée par le cycle majeur de l'ensemble  :

+- cycle -+
|  mineur |
|         |
^         ^
* * * * * * * * * * * *
^                     ^
|                     |
+--- cycle  majeur ---+

L'ordonnancement d'une première tâche (ici, ) mène à un remplissage partiel de ce tableau. Ainsi, une fois ordonnancée, nous aurons :

0 0 0 0 * * 0 0 0 0 * *

Il reste ensuite à ordonnancer , or a un temps d'exécution de , et il ne reste aucun espace pour une tâche de cette durée dans l'ordonnanceur. Conséquemment, n'est pas ordonnançable.

Annexe – calculer pgcd(m,n)

Le calcul du plus grand commun diviseur de deux entiers intervient dans l'évaluation du cycle mineur d'un ensemble de tâches périodiques. À titre de rappel, voici une manière d'évaluer pour deux entiers et  :

#include <cassert>
int pgcd_(int m, int n) {
   return !n? m : pgcd_(n, m % n);
}
int pgcd(int m, int n) {
   assert(m || n);
   return pgcd_(m, n);
}

L'algorithme est récursif et peut donc « s'exécuter » à la compilation si et sont statiques :

constexpr int pgcd_(int m, int n) {
   return !n? (!m? throw illegal{} : m) : pgcd(n, m % n);
}

Notez que est considéré ici comme indéfini, mais qu'il existe des écoles de pensées à ce sujet : certains admettent comme un cas particulier alors que qu'autres l'estiment indéfini. J'ai l'impression que c'est une question de convenance plus que de pureté idéologique (j'ai entendu des arguments convaincants dans chaque camp) alors j'ai fait le choix un peu arbitraire ici de ne pas l'admettre, en sachant que c'est matière à débats.

Annexe – calculer ppcm(m,n)

Le calcul du plus petit commun multiple de deux entiers intervient dans l'évaluation du cycle mineur d'un ensemble de tâches périodiques. À titre de rappel, voici une manière d'évaluer pour deux entiers et  :

// ...
int ppcm_(int m, int n) {
   return (!m || !n)? 0 : m * n / pgcd(m, n);
}
int ppcm(int m, int n) {
   assert(m || n);
   return ppcm_(m, n);
}

Ici encore, l'algorithme est récursif (à travers ) et peut donc « s'exécuter » à la compilation si et sont statiques :

// ...
constexpr int ppcm(int m, int n) {
   return (!m || !n)? 0 : m * n / pgcd(m, n);
}

Comme dans le cas du , est considéré ici comme indéfini mais il s'agit à ma connaissance d'un choix, qui est matière à débats, plus que d'une position formelle dans la communauté des mathématiciennes et des mathématiciens.

Lectures complémentaires

Quelques liens pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !