Bases d'ordonnancement pour STR

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

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 $\gamma=\{T_0,T_1,\cdots,T_n\}$ de telle sorte que $T_i=(P_i,C_i)$ pour $i=0..n$. Dans cette notation, $C_i$ est le temps de calcul associé à la tâche $T_i$ et $P_i$ est sa période.

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

On travaillera généralement avec des valeurs entières de $P$ et $C$ par souci de simplicité. De même, s'il y a des composantes incompressibles mais externes à $T$ dans l'exécution de $T$ (par exemple, une latence au démarrage), on inclura souvent ces paramètres dans l'évaluation de $C$ à 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 $T$.

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

• Si $T$ sous-estime $C$ a priori, il est possible que l'ordonnancement de $T$ dans $\gamma$ soit possible mais que l'exécution du STR résultant soit fautive puisqu'il arrivera que $T$ ne respecte pas sa contrainte de brièveté, trop ambitieuse, ce qui entraînera un échec de l'exécution du système dans son ensemble, alors que
• Si $T$ surestime $C$ a priori, il est possible que l'ordonnancement de $T$ dans $\gamma$ ne soit pas possible, donc que le système résultant ne puisse être généré ou déployé, alors qu'un estimé plus près de la réalité aurait pu mener à un STR correct

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 $\gamma=\{T_0,T_1,\cdots,T_n\}$ :

• L'exécution de $T_i$ doit démarrer (ce qu'on nomme le Release de $T_i$ ) à chaque début de chaque intervalle $P_i$. Ainsi, si une tâche $T=(10,2)$ est démarrée au moment $3$, elle sera aussi démarrée aux moments $13,23,33,\cdots$ de par sa période de $10$
• L'exécution de $T_i$ doit se poursuivre pour une durée $C_i$. Bien que $C_i$ soit un estimé du pire cas pour une exécution de $T_i$, l'ordonnanceur doit s'assurer que ce pire cas puisse être rencontré, donc doit faire comme si $T_i$ s'exécutera effectivement pour une durée $C_i$ à chaque démarrage. Pour une tâche $T=(10,2)$ démarrée au moment $3$, les moments $13,14,23,24,33,34,\cdots$ lui seront consacrés dans l'ordonnancement planifié du fait que son paramètre $C$ est $2$

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.

Taux d'occupation

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

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

Pour réduire les erreurs sur les réels, on évaluera typiquement l'occupation de manière discrète, et on ne divisera par $cycle majeur(\gamma)$ 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 :

• Suffisant si, quand le test est positif, cela signifie que les échéances et les contraintes de toutes les tâches seront rencontrées
• Nécessaire si, quand le test est négatif, cela signifie qu'au moins une des tâches ne rencontrera pas ses contraintes, et
• Exact s'il est à la fois nécessaire et suffisant

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 $\gamma$ est que :

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 $\gamma$ plutôt qu'avec la constante $1$. Il est parfois plus simple de procéder ainsi.

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

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 $\gamma$ est ordonnançable de manière triviale (au sens mathématique du terme).

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

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 $\gamma$ est ordonnançable de manière triviale et le taux d'occupation est de $\frac{2}{3}$.

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

Il est possible de construire un ordonnancement pour $\gamma$. 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 $T_i$ apparaît comme une case identifiée par la mention $i$ (p. ex. : $T_0$ occupe les cases marquées $0$, $T_1$ occupe les cases marquées $1,\cdots$). 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 :

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 $100%$. L'ensemble $\gamma$ 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 :

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

Ici, l'occupation totale de $\gamma$ est inférieure à $100%$ puisque

Pourtant, l'ensemble $\gamma$ n'y est pas ordonnançable. Ceci se constate par construction d'un ordonnancement possible pour $\gamma$. 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 $\gamma$ :

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

L'ordonnancement d'une première tâche (ici, $T_0:{P=6,C=4}$ ) mène à un remplissage partiel de ce tableau. Ainsi, une fois $T_0$ ordonnancée, nous aurons :

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

Il reste ensuite à ordonnancer $T_1$ , or $T_1$ a un temps d'exécution de $3$ , et il ne reste aucun espace pour une tâche de cette durée dans l'ordonnanceur. Conséquemment, $\gamma={(P=6,C=4),(P=12,C=3)}$ 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 $pgcd(m,n)$ pour deux entiers $m$ et $n$ :

#include <cassert>
constexpr int pgcd_(int m, int n) {
   return !n? m : pgcd_(n, m % n);
}
constexpr 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 $m$ et $n$ sont statiques :

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

Notez que $pgcd(0,0)$ est considéré ici comme indéfini, mais qu'il existe des écoles de pensées à ce sujet : certains admettent $pgcd(0,0)=0$ 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 $ppcm(m,n)$ pour deux entiers $m$ et $n$ :

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

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

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

Comme dans le cas du $pgcd$, $ppcm(0,0)$ 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.

• Une implémentation standard du PGCD : http://en.cppreference.com/w/cpp/numeric/gcd
• Une implémentation standard du PPCM : http://en.cppreference.com/w/cpp/numeric/lcm