L'ordonnancement coopératif

L’ordonnancement coopératif

L’ordonnancement coopératif (aussi appelé parfois non préemptif) peut être représenté dans la figure ci-dessous:

L’ordonnancement coopératif est un algorithme dans lequel les tâches cèdent volontairement l’utilisation du CPU aux autres tâches, quand elles ont terminé ou doivent attendre qu’une ressource soit disponible. L’avantage d’un tel algorithme est qu’il est très simple à réaliser au niveau de l’ordonnanceur - en fait, un ordonnanceur n’est même pas requis puisque l’ordonnancement des tâches est effectué dans le programme lui-même et donc à charge du développeur. Le désavantage principal de cette approche est qu’une tâche peut utiliser le CPU de manière excessive et ainsi empêcher d’autres tâches d’être exécutées en respectant leurs contraintes temporelles.

Réalisation avec une `super-loop`

La réalisation la plus commune d’un algorithme coopératif est la réalisation à l’aide d’une super-loop comme déjà présenté. Dans cette boucle, les tâches sont exécutées les unes après les autres, comme schématisé dans le pseudo-code ci-dessous:

task1() {
  // task 1 code
}
task2() {
  // task 2 code
}
task3() {
  // task 3 code
}
while (true) {
  task1();
  task2();
  task3();
}

Dans ce modèle, si les tâches doivent communiquer entre elles, elles peuvent le faire par l’utilisation de variables globales. Dans la mesure où chaque tâche est exécutée jusqu’à ce qu’elle soit terminée (run to completion), aucun mécanisme de synchronisation n’est requis. Pour que ce modèle fonctionne, il est important que les contraintes suivantes soient respectées:

Une tâche ne peut pas bloquer l’exécution du programme, par exemple en attendant sur la disponibilité d’une ressource sans libérer le CPU.
Le temps d’exécution d’une tâche doit être limité afin de permettre à chaque tâche de s’exécuter dans un délai acceptable. Si nécessaire, les tâches trop longues doivent être découpées en sous-tâches.
Une tâche doit soit s’exécuter jusqu’à sa fin ou relâcher le CPU lorsqu’elle doit attendre sur une ressource non disponible.
Si une tâche a été interrompue, elle doit pouvoir reprendre son exécution à son point d’interruption.

La forme la plus simple d’un algorithme coopératif est celle où toutes les tâches sont exécutées jusqu’à leur fin (run to completion), en étant éventuellement partagées en sous-tâches si cela s’avère nécessaire. Dans ce cas, un tel algorithme devient un algorithme d’ordonnancement statique cyclique: l’ordonnancement est statique (les périodes d’exécution et les temps d’exécution sont connus par le programmeur) et est exécuté dans un cycle sans fin. Cela correspond donc à notre désormais fameuse super-loop.

Réalisation à l’aide d’un `Ticker`

l’ordonnancement coopératif peut également être réalisé à l’aide d’un Ticker, qui devra mettre à jour l’état d’exécution d’une tâche en fonction de la période d’exécution d’une tâche. Dans ce cas, l’ordonnancement est réalisé selon le pseudo-code ci-dessous:

ticker_function() {
    // code for updating the run status of each task
}
// initialize ticker with short interrupt time

while (true) {
  // execute each task with run status set to true  
}

Exercice

Exercice L’ordonnancement coopératif/1

Écrivez un programme qui permet de faire clignoter les quatres LEDs de votre cible avec des intervalles de 1000ms, 1500ms, 2000ms et 3000ms. Le programme doit utiliser le schéma indiqué ci-dessus et utiliser un Ticker comme introduit dans Timer. Afin de réaliser cet exercice, vous devez utiliser les variables déclarées ci-dessous:

static constexpr uint32_t NBR_OF_TASKS = 4;
static DigitalOut leds[NBR_OF_TASKS] = { DigitalOut(LED1, kLedOff), DigitalOut(LED2, kLedOff), DigitalOut(LED3, kLedOff), DigitalOut(LED4, kLedOff)};
static constexpr std::chrono::milliseconds taskPeriods[NBR_OF_TASKS] = { 1000ms, 1500ms, 2000ms, 3000ms };
static std::chrono::milliseconds elapsedTimeTask[NBR_OF_TASKS] = { 0ms };
static bool runTask[NBR_OF_TASKS] = { false };
static std::chrono::milliseconds tickerPeriod = 1ms;

Solution

ticker_four_leds.cpp (solution)

#include "mbed.h"

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

static constexpr uint32_t NBR_OF_TASKS = 4;
static DigitalOut leds[NBR_OF_TASKS] = { DigitalOut(LED1, kLedOff), DigitalOut(LED2, kLedOff), DigitalOut(LED3, kLedOff), DigitalOut(LED4, kLedOff)};
static constexpr std::chrono::milliseconds taskPeriods[NBR_OF_TASKS] = { 1000ms, 1500ms, 2000ms, 3000ms };
static std::chrono::milliseconds elapsedTimeTask[NBR_OF_TASKS] = { 0ms };
static bool runTask[NBR_OF_TASKS] = { false };
static std::chrono::milliseconds tickerPeriod = 1ms;

static Timer timer;
static std::chrono::microseconds lastTimeTask[NBR_OF_TASKS] = { 0ms };

void manage_tasks() {
    for (uint32_t taskIndex = 0; taskIndex < NBR_OF_TASKS; taskIndex++) {
        elapsedTimeTask[taskIndex] += tickerPeriod;
        if (elapsedTimeTask[taskIndex] >= taskPeriods[taskIndex]) {
            runTask[taskIndex] = true;
            elapsedTimeTask[taskIndex] = 0ms;
        }
    }
}

void task(uint32_t taskIndex) {
    auto elapsedTime = timer.elapsed_time();
    auto intervalTime = std::chrono::duration_cast<std::chrono::milliseconds>(timer.elapsed_time() - lastTimeTask[taskIndex]);
    printf("Task %ld executed at interval %lldms\n", taskIndex, intervalTime.count());
    lastTimeTask[taskIndex] = elapsedTime;

    leds[taskIndex] = ! leds[taskIndex];
    runTask[taskIndex] = false;
}

int main()
{
    Ticker scheduler;
    scheduler.attach(&manage_tasks, tickerPeriod);

    timer.start();

    while (true) {
        for (uint32_t taskIndex = 0; taskIndex < NBR_OF_TASKS; taskIndex++) {
            if (runTask[taskIndex]) {
                task(taskIndex);
            }
        }
    }
}

Cette manière de réaliser un ordonnancement coopératif des tâches s’apparente à un ordonnanceur run-to-completion dynamique. En effet, avec cette réalisation, chaque tâche est exécutée jusqu’à ce qu’elle soit terminée. Toutefois, en comparaison à la réalisation super-loop de l’exercice 1, l’ordonnancement d’une tâche est dynamique. Dans ce sens, ajouter une tâche est plus aisée et ne demande pas au programmeur de calculer les intervalles entre l’appel de chaque tâche. Le code de la solution affiche d’ailleurs les intervalles de temps entre l’exécution de chaque tâche. Vous pouvez ainsi vérifier que les périodes sont correctes.

Réalisation à l’aide d’une `EventQueue`

Le mécanisme réalisé ci-dessous s’apparente également à celui d’une EventQueue{target=blank} telle que mise à disposition par _Mbed OS. L’utilisation la plus simple de l’EventQueue permet d’ordonnancer des événements qui seront servis par un thread (en utilisant le mécanisme de l’event loop). La programmation de l’exercice 2 à l’aide d’une EventQueue est très simple et facilement lisible, comme démontré ci-dessous:

event_queue_four_leds.cpp (solution)

    #include "mbed.h"
    
    static constexpr int kLedOn  = 0;
    static constexpr int kLedOff = 1;
    
    // global variables used for tasks
    static constexpr uint32_t NBR_OF_TASKS = 4;
    static DigitalOut leds[NBR_OF_TASKS] = { DigitalOut(LED1, kLedOff), DigitalOut(LED2, kLedOff), DigitalOut(LED3, kLedOff), DigitalOut(LED4, kLedOff)};
    static constexpr std::chrono::milliseconds taskPeriods[NBR_OF_TASKS] = { 1000ms, 1500ms, 2000ms, 3000ms };
    
    void task(uint32_t taskIndex) {
        leds[taskIndex] = ! leds[taskIndex];
    }
    
    int main()
    {
        // Request the shared queue
        EventQueue* pEventQueue = mbed_event_queue();
    
        // Schedule all tasks on this queue
        for (uint32_t taskIndex = 0; taskIndex < NBR_OF_TASKS; taskIndex++) {
            pEventQueue->call_every(taskPeriods[taskIndex], task, taskIndex);
        }
    
        // serve the event queue
        pEventQueue->dispatch_forever();
    }

En rapport à l’API EventQueue, il est intéressant de noter les points:

L’API Mbed OS met à disposition deux instances d’EventQueue (voir Shared Event Queue. L’utilisation de ces instances permet de réduire l’utilisation de la mémoire allouée à cet usage.
L’API EventQueue est thread et ISR safe. Cela signifie que plusieurs threads peuvent utiliser une queue de manière concurrente et que les méthodes de la classe peuvent être appelées dans un contexte ISR.
Il existe plusieurs manières de servir les événements d’une EventQueue. Dans l’exemple ci-dessus, le code utilise la méthode dispatch_forever. Cette méthode sert les événements déposés sur la queue indéfiniment, à moins d’un appel à la méthode break_dispatch.

Exercice

Exercice L’ordonnancement coopératif/2

Instrumentez le code ci-dessus afin de démontrer que les périodes d’exécution des tâches sont bien correctes. Pour ce faire, vous devez utiliser un Timer et sauvegarder le temps d’exécution de chaque tâche.

Solution

event_queue_with_time.cpp (solution)

// you need to declare global variables like

static Timer timer;
static std::chrono::microseconds lastTimeTask[NBR_OF_TASKS] = { 0ms };

// add the following code in the task() function
    auto elapsedTime = timer.elapsed_time();
    auto intervalTime = std::chrono::duration_cast<std::chrono::milliseconds>(timer.elapsed_time() - lastTimeTask[taskIndex]);
    printf("Task %ld executed at interval %lldms\n", taskIndex, intervalTime.count());
    lastTimeTask[taskIndex] = elapsedTime;

// and don't forget to start your timer !

L'ordonnancement coopératif