Les bases de l'ordonnancement

Le problème de l’ordonnancement

Un programme pour systèmes embarqués doit accomplir un certain nombre de tâches de manière concurrente, ces tâches pouvant être périodiques ou événementielles. Chaque tâche peut être caractérisée par les spécifications temporelles suivantes:

C (computation time): le temps processeur le plus long consommé pour l’exécution de la tâche.
T (period): pour les tâches périodiques, la période de la tâche.
a (arrival time): moment auquel la tâche est prête pour exécution.
s (start time): moment auquel la tâche débute effectivement son exécution.
f (finishing time): moment auquel la tâche termine son exécution.
D (deadline): moment auquel la tâche doit avoir complété son exécution.

Ces spécifications temporelles sont illustrées dans le diagramme ci-dessous:

Pour les tâches apériodiques, a et D définissent le moment auquel la tâche est prête pour exécution et le délai pour accomplir cette tâche. Une tâche événementielle ou apériodique ne spécifie évidemment pas de période pour la tâche.

Pour les tâches périodiques, les spécifications temporelles peuvent être visualisées dans le diagramme ci-dessous:

Pour les tâches périodiques, D est souvent égal à T, ce qui signifie que l’exécution de la tâche doit simplement être terminée avant le début de la prochaine période.

Exercice Les bases de l’ordonnancement/1

Soit un programme qui contient deux tâches périodiques avec les spécifications temporelles suivantes: C1=400ms, D1=500ms, T1=1000ms, C2=500ms, D2 = 1000ms, T2=1000ms. Esquissez le diagramme temporel d’une période complète de 1000ms, en indiquant toutes les caractéristiques temporelles (C, T, a, s, f, D) pour les deux tâches.

Lorsque les spécifications temporelles de toutes les tâches constituant un programme sont définies, le problème d’ordonnancement revient à définir un calendrier des tâches (schedule) qui permet de respecter ces contraintes temporelles. Cette problématique est très importante pour tous les systèmes informatiques et également pour les systèmes embarqués. C’est également une problématique complexe qui déborde largement du cadre de ce cours. Nous allons traiter les cas les plus simples, en ne considérant la plupart du temps que T et C et en débutant par l’ordonnancement manuel.

L’ordonnancement manuel de tâches périodiques

La méthode que nous avons utilisée jusqu’ici pour organiser les tâches de nos programmes est celle de l’ordonnancement manuel, qui est une approche très commune dans la programmation des systèmes embarqués. Dans les problèmes abordés jusqu’ici, nous n’avons que peu considéré les paramètres des tâches si ce n’est dans certains cas la période. Nous allons maintenant traiter le cas plus général, en commençant par une application qui ne contient que des tâches périodiques. Dans ce cas, les programmes générés appliquent le modèle dit super-loop, de la forme générale (démontrée pour trois tâches)

task1() {
  // task 1 code
}
task2() {
  // task 2 code
}
task3() {
  // task 3 code
}
while (true) {
  wait1(); // may not be necessary
  task1();
  wait2(); // may not be necessary
  task2();
  wait3(); // may not be necessary
  task3();
}

Afin de créer une application qui respecte les contraintes temporelles des tâches, le programmeur doit établir une table cyclique des temps. Cette table aura un cycle de répétition et le cycle de répétition le plus court est défini comme le plus petit multiple commun des périodes de toutes les tâches (PPMC). Le PPMC détermine donc la taille de la table des tâches. Il est important de noter qu’afin de respecter les contraintes de toutes les tâches et de réaliser la table selon le PPMC, il peut être nécessaire de partager une tâche en sous-tâches.

Un exemple de table cyclique de tâches pour les quatre tâches suivantes est illustrée ci-dessous:

Gear: \(C = 100\,\mathsf{ms}\), \(T = 800\,\mathsf{ms}\)
Count: \(C = 200\,\mathsf{ms}\), \(T = 400\,\mathsf{ms}\)
Reset: \(C = 100\,\mathsf{ms}\), \(T = 800\,\mathsf{ms}\)
Display: \(C = 300\,\mathsf{ms}\), \(T = 1600\,\mathsf{ms}\)

table cyclique

Dans ce cas, la durée du cycle est de \(1600\,\mathsf{ms}\). Notez que nous avons dû subdiviser la tâche Display en trois sous-tâches de \(100\,\mathsf{ms}\). Nous avons aussi dû ajouter une tâche wait de \(100\,\mathsf{ms}\) pour terminer correctement le cycle.

Exercice Les bases de l’ordonnancement/2

Vous devez établir la table des tâches pour le problème ci-dessous et réalisez le programme à l’aide d’un modèle super-loop.

Votre programme comporte deux tâches avec les paramètres T1=1000ms, C1=50ms, _T2=1500ms et C2=50ms. La tâche consiste à inverser une LED donnée et le code de la fonction réalisant la tâche est

void task(Led& led) {
    led.Toggle();
    HAL_Delay(50);
}

Dans ce code, la fonction HAL_Delay est utilisée afin de simuler un temps de calcul C=50ms.

Etablissez la table des tâches et réalisez le programme à l’aide d’une super boucle. Si la table des tâches comporte des temps d’attente, vous devez réaliser ces temps d’attente en appelant la méthode vTaskDelay(), qui au contraire de HAL_Delay() réalise une attente passive et permet au système d’éventuellement accomplir d’autres tâches.

Malgré ces limitations, les avantages de la méthode d’ordonnancement statique cyclique existent:

le comportement du programme est très prédictible et permet ainsi la réalisation de systèmes avec des contraintes temporelles strictes.
le système ne souffre d’aucun problème de famine de ressources (resource starvation) et ainsi les tâches seront toujours desservies en respectant les contraintes.

Cette approche présente également des limitations:

la table des temps n’est pas toujours facile à construire. Le partage en sous-tâches peut être complexe et plus la taille de la table grandit, plus le problème devient complexe.
la table des tâches est statique et le programme exécute toujours le même ordonnancement. Il n’est ainsi pas possible de réaliser un comportement dynamique tenant compte de conditions externes ou de priorités de tâches différentes.
si le système ne supporte pas le traitement de tâches événementielles (interruptions), alors le programme doit continuellement vérifier le statut des périphériques qui pourraient générer des événements. Cela contribue à un gaspillage des ressources du CPU et crée une consommation d’énergie excessive. Ce problème peut être corrigé en permettant le traitement de tâches événementielles.

Exercice Les bases de l’ordonnancement/3

Trouvez au moins un avantage et un inconvénient supplémentaire inhérent à un système réalisant un ordonnancement statique cyclique.