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: Ordonnancement de tâches périodiques

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 une problématique 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: Super-loop et ordonnancement manuel

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 toutefois 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, 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: Ordonnancement statique cyclique

L’ordonnancement manuel et le traitement de tâches événementielles

Un des désavantages d’une réalisation d’ordonnancement manuel qui ne traite que des tâches périodiques est que le programme doit continuellement vérifier le statut des périphériques qui pourraient générer des événements. Cela génère un gaspillage de ressource CPU, limite la possibilité d’optimiser la consommation du CPU et n’évite pas de manquer certains événements. Si on considère un cycle de répétition de plusieurs secondes, il est en effet facile d’imaginer que le programme aura des difficultés à par exemple traiter correctement tous les événements liés à la pression d’un bouton.

Exercice: Détection d’évenement par polling

Si vous avez répondu à la question de l’exercice précédent, vous comprenez qu’il est donc indispensable de traiter les tâches événementielles selon le principe d’interruption, également dans le cas d’un ordonnancement manuel. La structure générale d’un programme avec ordonnancement manuel est modifiée de la façon suivante afin de pouvoir traiter des tâches événementielles:

...
volatile bool deviceARequest = false;
void deviceAEvent() {
  deviceARequest = true;
}

while (true) {
  ...
  if (deviceARequest) {
      executeDeviceARequest();
  }
  ... 
  if (deviceBRequest) {
      executeDeviceARequest();
  }

}

Dans cette forme générale, deviceXRequest représente une variable qui sera mise à jour dans une routine ISR et executeDeviceXRequest représente le traitement de la tâche événementielle.

Exercice: Détection d’évenement par interruption

Comme démontré dans l’exercice précédent, un tel mécanisme permet de déférer le traitement de la tâche selon la table des événements. Il assure que la tâche événementielle sera toujours traitée. Par contre, le délai de traitement de la tâche dépend de la table d’ordonnancement des tâches. Accomplir le traitement de la tâche dans le contexte ISR n’est pas une solution à ce problème, puisque les routines ISR doivent en principe être courtes et que certaines tâches ne peuvent pas être accomplies dans un contexte ISR. Les autres inconvénients de l’ordonnancement statique subsistent également.