Aller au contenu

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:

Tâche

Les spécifications temporelles d'une tâche

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:

Tâche périodique

Tâche périodique

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.

Solution

Tâche
Période avec les spécifications temporelles

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 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(DigitalOut& led) {
    led = !led;
    wait_us(50000);
}
Dans ce code, la fonction wait_us 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 ThisThread::sleep_for(), qui au contraire de wait_us réalise une attente passive et permet au système d’éventuellement accomplir d’autres tâches.

Solution
superloop_two_leds.cpp (solution)
#include "mbed.h"

static constexpr int kLedOn  = 0;
static constexpr int kLedOff = 1;

void task(DigitalOut& led) {
    led = !led;
    wait_us(50000);
}

int main()
{
    DigitalOut led1(LED1, kLedOff);
    DigitalOut led2(LED2, kLedOff);

    while (true) {
        task(led1);
        ThisThread::sleep_for(350ms);
        task(led2);
        ThisThread::sleep_for(550ms);
        task(led1);
        ThisThread::sleep_for(850ms);
        task(led2);
        ThisThread::sleep_for(50ms);
        task(led1);
        ThisThread::sleep_for(950ms);
    }
}

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

Solution

Avantages:

  • un ordonnanceur n’est pas requis et l’overhead lié à son utilisation est ainsi supprimé (temps de calcul, context switch).

Inconvénients:

  • si les résultats d’une tâche dépendent de conditions externes, le délai maximal permettant de traiter la tâche avec de nouvelles conditions externes est le cycle de répétition de la tâche. Un exemple pour un tel délai est une tâche qui doit être effectuée en tenant compte de la valeur obtenue d’un capteur.
  • la scalabilité d’un tel système n’est pas optimale. Ajouter une nouvelle tâche est complexe et devient de plus en plus complexe avec chaque tâche ajoutée.

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 Les bases de l’ordonnancement/4

Analyser le programme ci-dessous. Que peut-il se passer dans l’exécution du programme suivant concernant le traitement de la pression du bouton?

button_polling.cpp
#include "mbed.h"

int main()
{
    DigitalOut led1(LED1);
    DigitalIn button(PA_0);

    while (true) {
        ThisThread::sleep_for(2s);
        if (button)
        {
            led1 = !led1;
        }
    }
}
Solution

Si la pression sur le bouton ne dure pas assez longtemps, alors l’événement ne sera pas détecté pas le programme.

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 Les bases de l’ordonnancement/5

Modifier l’exemple de code de l’exercice 4 afin que la pression sur le bouton soit traitée selon le principe d’interruption. Observez la différence de comportement de l’application entre les deux solutions.

Solution
button_interrupt.cpp (solution)
#include "mbed.h"

static constexpr int kLedOn  = 0;
static constexpr int kLedOff = 1;

volatile bool buttonPressed = false;
void buttonISR() {
    buttonPressed = true;
}

int main()
{
    DigitalOut led1(LED1, kLedOn);

    InterruptIn button(PA_0);
    button.fall(&buttonISR);

    while (true) {
        ThisThread::sleep_for(2s);
        if (buttonPressed)
        {
            led1 = !led1;
            buttonPressed = false;
        }
    }
}

Comme démontré dans l’exercice 5, 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.