Les machines d'état

Une autre technique pour orchestrer plusieurs tâches avec un calendrier donné consiste à utiliser des machines d’état cadencées à une fréquence précise.

Si on reprend l’exemple du chapitre précédent avec une LED qui doit clignoter avec une période de 1000ms (LED1) et une autre avec une période de 1500ms (LED2).

Pour la LED1, on pourrait faire une machine d’état cadencée à 500ms qui inverse la LED à chaque deuxième tick :

Machine d'état pour la LED1

Et pour la LED2, on fait aussi une machine d’état cadencée à 500ms, mais qui inverse la LED à chaque troisième tick :

Machine d'état pour la LED2

On peut généraliser le machine d’état pour inverser la LED tous les $n$ ticks avec un compteur $i$ :

Machine d'état généralisée

On peut implémenter cette technique en C++ avec une classe abstraite pour représenter une machine d’état:

class StateMachine {
   public:
    virtual void Tick() = 0;
};

Une machine d’états pour inverser l’état des LEDs tous les $n$ ticks peut être implémentée ainsi :

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

class Led : public StateMachine {
   public:
    Led(PinName pin, int n) : led_(pin, kLedOff), n_{n}, state_{0} {}
    void Tick() override
    {
        state_++;
        if (state_ == n_) {
            led_   = !led_;
            state_ = 0;
        }
    }

   private:
    DigitalOut led_;
    int n_;
    int state_;
};

Pour un système composé de plusieurs machines d’états, on peut stocker ces machines dans un vecteur :

#include <vector>

class System {
   public:
    void AppendStateMachine(StateMachine* state_machine)
    {
        stateMachines_.push_back(state_machine);
    }
    void Tick()
    {
        for (const auto& s : stateMachines_) {
            s->Tick();
        }
    }

   private:
    vector<StateMachine*> stateMachines_;
};

Le programme principal est le suivant :

int main()
{
    System system;
    system.AppendStateMachine(new Led(LED1, 2));
    system.AppendStateMachine(new Led(LED2, 3));

    Ticker clock;
    clock.attach(callback(&system, &System::Tick), 500ms);
    while (true) {
        ThisThread::sleep_for(Kernel::wait_for_u32_forever);
    }
}

Note

On aurait aussi pu implémenter le System comme une classe dérivée de StateMachine mais ça n’apporte pas grand-chose ici.

On cadence le système avec une période $p$ égal au plus grand diviseur commun des périodes $T_{i}$ de toutes les machines d’états:

p = gcd T_{i}

Pour que le système fonctionne, nous devons encore nous assurer que toutes les tâches peuvent terminer pendant la période $p$ . Si le temps pour effectuer la tâche $i$ est égal à $C_{i}$ , le système fonctionne si:

max C_{i} \leq p

Si cette dernière condition n’est pas remplie, on doit fractionner les tâches, ou alors choisir des périodes $T_{i}$ qui donnent un plus grand diviseur commun.

Exercice

Exercice Les machines d’état/1

Considérons le code que nous venons d’écrire pour faire clignoter les LEDs. Si on remplace le programme principal par le suivant :

int main()
{
    System system;
    system.AppendStateMachine(new Led(LED1, 60));
    system.AppendStateMachine(new Led(LED2, 45));
    system.AppendStateMachine(new Led(LED3, 30));
    system.AppendStateMachine(new Led(LED4, 15));

    Ticker clock;
    clock.attach(callback(&system, &System::Tick), 15ms);
    while (true) {
        ThisThread::sleep_for(Kernel::wait_for_u32_forever);
    }
}

Quelle est la période de clignotement de chacune des 4 LEDs ?

Ce programme n’est pas optimal. Identifiez sa principale faiblesse et corrigez-la.

Solution

La LED1 change d’état toutes les $60 \cdot 15 m s = 900 m s$ . La période est donc de $900 \cdot 2 = 1800 m s$ .
La période de la LED2 est de $45 \cdot 15 \cdot 2 = 1350 m s$ .
La période de la LED3 est de $30 \cdot 15 \cdot 2 = 900 m s$ .
La période de la LED4 est de $15 \cdot 15 \cdot 2 = 450 m s$ .

Le plus grand diviseur commun n’est pas $15$ , mais $15 \cdot 15 = 225 m s$ . On pourrait donc mettre le programme en veille plus longtemps avec le code suivant :

int main2()
{
    System system;
    system.AppendStateMachine(new Led(LED1, 4));
    system.AppendStateMachine(new Led(LED2, 3));
    system.AppendStateMachine(new Led(LED3, 2));
    system.AppendStateMachine(new Led(LED4, 1));

    Ticker clock;
    clock.attach(callback(&system, &System::Tick), 225ms);
    while (true) {
        ThisThread::sleep_for(Kernel::wait_for_u32_forever);
    }
}