Tests « d'ordonnançabilité »

Prudence : document en construction, et structure en émergence...

Pour un résumé des symboles typiques pour les éléments clés des différents tests « d'ordonnançabilité » que vous trouverez dans la littérature, vous pouvez vous référer à ceci (version PDF) ou à cette version HTML.

Ce qui suit implémente concrètement certains des tests « d'ordonnançabilité » vus en classe. Notez que le terme « ordonnançabilité » n'est pas français, mais que je l'utiliserai à titre de néologisme pour le terme anglais Schedulability, que l'on retrouve abondamment dans la littérature des STR.

Nous donnerons à « ordonnançable » le sens de « qui peut être ordonnancé », et nous donnerons à « ordonnançabilité » le sens de « caractère de ce qui est ordonnançable ». Notez que j'omettrai les guillemets pour écrire ordonnançabilité tout simplement à partir de ce point, dans le but d'alléger la présentation.

Tests d'ordonnançabilité

Un ordonnanceur TR est souvent appelé à déterminer s'il est possible d'ordonnancer un ensemble de tâches TR, tout comme il est appelé à réaliser cet ordonnancement. Alors que la mise en place d'un ordonnancement complet peut être coûteux, il est souvent possible de tester l'ordonnançabilité d'un ensemble de tâches à coût plus raisonnable.

Pour cette raison, nous examinerons ici la question des tests d'ordonnançabilité.

Rôle d'un test d'ordonnançabilité

Un test d'ordonnançabilité nous permettra de statuer si un ensemble de tâches peut être ordonnancé ou encore s'il ne le peut pas. Dans le contexte d'un STR, est ordonnançable un ensemble de tâches pour lequel il existe un ordonnancement tel que les moments de lancement de chacune sont respectées (ce qui équivaut au respect des périodes quand les tâches sont périodiques) et pour lequel chaque tâche pourra s'exécuter dans le respect de ses contraintes.

Un test d'ordonnançabilité peut être...

Suffisant

Un test est suffisant si, lorsqu'il indique qu'un ensemble de tâches est ordonnançable, alors il l'est. Cependant, si un tel test conclut par la négative, cela ne signifie pas que l'ensemble n'est pas ordonnançable, seulement que nous ne pouvons conclure de manière affirmative à partir dudit test. Essentiellement, un test suffisant ne donne pas de faux positifs

Nécessaire

Un test est nécessaire si, lorsqu'il est échoué, nous savons que l'ensemble de tâces auquel il a été appliqué n'est pas ordonnançable. S'il est réussi, toutefois, la capacité d'ordonnancer l'ensemble de tâches n'est pas garantie

Exact

Un test est exact s'il est à la fois nécessaire et suffisant. En pratique, réaliser un test d'ordonnançabilité qui soit exact est souvent prohibitif (Intractable, au sens anglais du terme) sur le plan des coûts de calcul

Durable

Dans un STR, par la force des choses, on trouve typiquement des tests d'ordonnançabilité quelque peu pessimistes. Sachant cela, un test est durable (Sustainable) s'il continue à bien prédire l'ordonnançabilité d'un système de tâches quand les conditions d'exécution de ce dernier s'améliorent

Description sommaire d'une tâche

Pour l'ensemble de ce qui suit, nous aurons besoin d'être en mesure de représenter une tâche. étant donné les démonstrations faites plus bas, je me suis limité à une représentation qui convienne à des tâches périodiques, et il est probable que des ajustements soient requis pour couvrir aussi les tâches apériodiques ou sporadiques.

Dans une optique d'économie de code et dans le respect du principe DRY, nous utiliserons une implémentation CRTP des opérateurs d'ordonnancement.

L'idée ici est de pouvoir classer des objet en ordre croissant ou décroissant, les trier ou les organiser de diverses manières tout en évitant une part de redondance dans le code. Le mot « ordonnancement » tel qu'utilisé ici n'a pas de lien direct avec la question de l'ordonnançabilité et des tests sur lesquels nous nous penchons dans ce document.

 
#ifndef RELATION_H
#define RELATION_H
namespace relation {
   template <class T>
      struct ordonnancement {
         friend bool operator<=(const T &a, const T &b) {
            return !(b < a);
         }
         friend bool operator>(const T &a, const T &b) {
            return b < a;
         }
         friend bool operator>=(const T &a, const T &b) {
            return !(a < b);
         }
      };
}
#endif

Pour les besoins de la démonstration, nous aurons recours à une représentation des tâches à ordonnancer qui est telle que chaque tâche connaît son WCET, la période à laquelle elle doit être démarrée (rythme constant) et sa priorité.

Cette représentation ne convient donc pas à un algorithme d'ordonnancement TR qui dépendrait de l'échéance (du Deadline) des tâches plutôt que de la priorité et de la période – on peut penser ici à l'algorithme EDF par exemple.

Pour réaliser un ordonnancement respectant le principe de Rate Monotonicity dans un système à base de priorités, il importe que l'ordre de priorité des tâches d'un ensemble soit l'inverse de celui de leurs périodes (plus courte période, plus haute priorité). La fonction rate_monotonic_priorities() que vous voyez à droite prend une séquence de ce qu'on présume être des Tache<T> pour un certain type T et s'assure que cette contrainte soit respectée.

Ceci permet de valider, pour certains des tests décrits plus bas, que le test en question soit applicable pour un ensemble de tâches donné.

L'opérateur de projection sur un flux n'a qu'une utilité diagnostique.

 
#ifndef TACHE_H
#define TACHE_H
#include "relation.h"
#include <ostream>
#include <type_traits>
#include <iterator>
#include <algorithm>
template <class T>
   class Tache : relation::ordonnancement<Tache<T>> {
   public:
      using value_type = T;
   private:
      value_type wcet_;
      value_type periode_;
      value_type priorite_;
   public:
      Tache(value_type periode, value_type wcet, value_type priorite)
         : wcet_{ wcet }, periode_{ periode }, priorite_{ priorite }
      {
      }
      value_type priorite() const {
         return priorite_;
      }
      value_type wcet() const {
         return wcet_;
      }
      value_type periode() const {
         return periode_;
      }
      bool operator<(const Tache &t) const {
         return priorite() < t.priorite();
      }
   };
template <class>
   struct est_tache : std::false_type {
   };
template <class T>
   struct est_tache<Tache<T>> : std::true_type {
   };
template <class T>
   static constexpr const bool est_tache_v = est_tache<T>();
template <class It>
   bool rate_monotonic_priorities(It debut, It fin) {
      using namespace std;
      static_assert(est_tache<value_type>::value);
      sort(debut, fin); // ordre croissant de priorites
      return is_sorted(debut, fin, [](const auto &a, const auto &b) {
         return a.periode() > b.periode();
      });
   }
template <class T>
   std::ostream& operator<<(std::ostream &os, const Tache<T> &t) {
      return os << "{p:" << t.priorite() << ", P:" << t.periode() << ", C:" << t.wcet() << "}";
   }
#endif

Quelques tests d'ordonnançabilité tirés de la littérature

Examinons maintenant l'implémentation de quelques tests d'ordonnançabilité tirés directement de la littérature portant sur les STR et sur les ordonnanceurs inéquitables. Nous séparerons l'implémentation de chaque test de son code client (du code de test, dans ce cas-ci.

Pour l'ensemble des tests ci-dessous, supposez que les inclusions et les directives using à droite ont été faites. Ceci permettra d'alléger l'écriture. J'ai choisi d'y aller avec du code C++ 11, aussi dans un souci d'allègement de l'écriture.

Quelques a priori

Pour les tests d'ordonnançabilité couverts ici, par souci de simplicité, nous présumerons :

  • Que l'exécution se fait sur un seul processeur
  • Que le WCET est connu a priori pour chaque tâche
  • Que le temps associé au changement de contexte d'une tâche à l'autre est négligeable
  • Que les tâches sont indépendantes les unes des autres
  • Que l'ensemble des tâches à examiner est fermé, et
  • Que l'échéance d'une tâche est égale à sa période

L'indépendance des tâches implique un lancement (Release) à un moment précis de toutes les tâches. Ce moment est l'instant critique du système.

 
#ifndef TESTS_ORDONNANCEMENT_H
#define TESTS_ORDONNANCEMENT_H
#include <utility>
#include <iterator>
#include <algorithm>
#include <numeric>
#include <cassert>
namespace tests_ordonnancement {

Liu et Layland (1973)

Ce test opère sur des ensembles de tâches à priorités fixées a priori.

Le seuil évalué par seuil() converge vers pour de grandes valeurs de . Ainsi, toute liste de tâches dont le taux d'utilisation est inférieur ce seuil sera ordonnançable avec une telle approche.

Le test va comme suit (voir ceci pour un rappel du sens des symboles utilisés) :

\[ \sum_{i=1}^N{\left(\frac{C_i}{T_i}\right)} \leq N\left(2^\frac{1}{N}-1\right)\]

Il est suffisant mais pas nécessaire; par exemple, pour l'ensemble de tâches suivant :

...on obtient un seuil de valeur et un test , or bien que le test soit faux, cet ensemble s'avère ordonnançable.

Vous verrez ici comment ce test est mis en application.

 
   struct liu_layland_1973 {
      static constexpr const char * nom = "Liu et Layland, 1973";
      template <class It>
         static double seuil(It debut, It fin) {
            auto N = distance(debut, fin);
            //
            // SEUIL converge vers 69,3% pour de grands N. Ergo, toute liste de tâches
            // dont le taux d'utilisation est inférieur à 69,3% sera ordonnançable avec
            // une approche à priorité fixe
            //
            return static_cast<double>(N) * (pow(2.0, 1.0 / static_cast<double>(N)) - 1.0);
         }
      static constexpr const char* applicabilite = R"(
Ce test s'applique dans le cas ou les taches sont periodiques, ne partagent pas de ressources,
et ou l'echance de chaque tache est egale a sa periode. Les priorites doivent etre statiques
et les priorites doivent etre choisies de maniere a ce que les taches de plus courte periode
soient les plus prioritaires. Le temps d'un changement de contexte est presume negligeable
)";
      template <class It>
         std::pair<double, bool> operator()(It debut, It fin) const {
            using namespace std;
            using value_type = typename iterator_traits<It>::value_type;
            const auto somme = accumulate(debut, fin, 0.0, [](double cumul, value_type t) {
               return cumul +
                  (static_cast<double>(t.wcet()) /
                  static_cast<double>(t.periode()));
            });
            return { somme, somme <= seuil(debut, fin) };
         }
      };

Bini (2007)

Tout comme Lui et Layland (1973), ce test est suffisant sans être nécessaire, et opère sur des ensembles de tâches à priorités fixes. Il est toutefois un peu plus simple à calculer.

Le test va comme suit (voir ceci pour un rappel du sens des symboles utilisés) :

\[ \prod_{i=1}^N{\left(\left(\frac{C_i}{T_i}\right)+1\right)} \leq 2 \]

Vous verrez ici comment ce test est mis en application.

 
   struct bini_2007 {
      static constexpr const char * nom = "Bini, 2007";
      template <class It>
         static constexpr double seuil(It, It) {
            return 2.0;
         }
      static constexpr const char* applicabilite = R"(
Ce test s'applique dans le cas ou les taches sont periodiques, ne partagent pas de ressources,
et ou l'echance de chaque tache est egale a sa periode. Les priorites doivent etre statiques
et les priorites doivent etre choisies de maniere a ce que les taches de plus courte periode
soient les plus prioritaires. Le temps d'un changement de contexte est presume negligeable
)";
      template <class It>
         std::pair<double, bool> operator()(It debut, It fin) const {
            using namespace std;
            auto produit = accumulate(debut, fin, 1.0, [](double cumul, const Tache<int> &t) {
               return cumul *
                  ((static_cast<double>(t.wcet()) /
                  static_cast<double>(t.periode())) + 1.0);
            });
            return { produit, produit <= seuil(debut, fin) };
         }
   };
}
#endif

Raffinements possibles

Certains raffinements sont possibles pour réaliser des tests d'ordonnançabilité.

L'un d'entre eux repose sur la capacité de grouper des tâches en familles. Les tâches d'une même famille ont alors en commun d'avoir des périodes qui sont des multiples l'une de l'autre; les considérer en groupe permet de réduire le nombre de cas distincts à examiner.

L'algorithme à droite est mais est typiquement fait offline, et a donc peu d'impact sur le temps d'exécution en pratique.

 
   template <class C, class It>
      C grouper_en_familles(It debut, It fin) {
         auto est_pertinente = [](const Tache<int> &t, It debut, It fin) {
            if (debut == fin) return true;
            for (; debut != fin; ++debut)
               if (t.periode() < debut->periode() && debut->periode() % t.periode() == 0)
                  return false;
            return true;
         };
         auto fusionner_famille = [](const Tache &t, It debut, It fin) {
            assert(debut != fin);
            auto occupation = accumulate(debut, fin, t.wcet(), [t](int so_far, const Tache<int> &tache) {
               return (t.periode() > tache.periode() && t.periode() % tache.periode() == 0) ?
                  so_far + tache.wcet() * t.periode() / tache.periode()  : so_far;
            });
            return { t.periode(), occupation, t.priorite() };
         };
         C resultat;
         auto temp = debut;
         for_each(debut, fin, [&](const Tache<int> &t) {
            if (est_pertinente(t, temp, fin))
               resultat.emplace_back(fusionner_famille(*debut, temp, fin));
         });
         return resultat;
      }
}
#endif

Appliquer un test d'ordonnançabilité – quelques exemples

Les tests eux-mêmes seront réalisés en passant un test d'ordonnançabilité générique à la fonction realiser_test() visible à droite. Ceci permettra de réduire la répétition de code.

 
#include "Tache.h"
#include "tests_ordonnancement.h"
#include <cassert>
#include <ostream>
#include <cassert>
#include <iterator>
#include <numeric>
#include <cmath>
#include <utility>
#include <vector>
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
using namespace tests_ordonnancement;
template <class T, class Op>
   void realiser_test(const char *expected_result, vector<T> v, Op test, bool grouper = false) {
      assert(rate_monotonic_priorities(begin(v), end(v)));
      cout << "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-\n"
           << "Taches a ordonnancer: ";
      copy(begin(v), end(v), ostream_iterator<T>{cout, " "});
      cout << '\n';
      if (grouper) {
         v = grouper_en_familles<vector<T>>(begin(v), end(v));
         cout << "Apres groupement en familles: ";
         copy(begin(v), end(v), ostream_iterator<T>{cout, " "});
         cout << '\n';
      }
      auto test_results = test(begin(v), end(v));
      cout << "Resultat attendu: " << expected_result << '\n';
      cout << "Test " << (test_results.second? "reussi" : "echoue")
           << ", score " << test_results.first
           << ", seuil " << Op::seuil(begin(v), end(v)) << endl << endl;
   }

Appliquer le test Liu et Layland (1973)

Trois exemples d'application du test Liu et Layland (1973) sont présentés à droite :

  • Le premier exemple est tel que le test échoue et donne les bons résultats
  • Le deuxième est trop pessimiste et mène à un faux négatif
  • Le troisième donne le bon résultat avec les mêmes données que le deuxième, ceci dû à un groupement en familles des tâches au préalable

 

 
void realiser_tests_liu_layland_1973() {
   using namespace tests_ordonnancement;
   cout << liu_layland_1973::nom << "\n\n"
        << liu_layland_1973::applicabilite << "\n\n";
   realiser_test(
      "echec (legitime)",
      vector<Tache<int>> { { 50, 12, 1 }, { 40, 10, 2 }, { 30, 10, 3 } },
      liu_layland_1973{}
   );
   realiser_test(
      "echec (faux negatif)",
      vector<Tache<int>> { { 80, 40, 1 }, { 40, 10, 2 }, { 20, 5, 3 } },
      liu_layland_1973{}
   );
   realiser_test(
      "succes (legitime)",
      vector<Tache<int>> { { 80, 40, 1 }, { 40, 10, 2 }, { 20, 5, 3 } },
      liu_layland_1973{}, true
   );
}

Appliquer le test Bini (2007)

Trois exemples d'application du test Bini (2007) sont présentés à droite :

  • Le premier exemple est tel que le test échoue et donne les bons résultats
  • Le deuxième est trop pessimiste et mène à un faux négatif
  • Le troisième donne le bon résultat avec les mêmes données que le deuxième, ceci dû à un groupement en familles des tâches au préalable
 
void realiser_tests_bini_2007() {
   using namespace tests_ordonnancement;
   cout << bini_2007::nom << "\n\n"
        << bini_2007::applicabilite << "\n\n";
   realiser_test(
      "echec (legitime)",
      vector<Tache<int>> { { 50, 12, 1 }, { 40, 10, 2 }, { 30, 10, 3 } },
      bini_2007{}
   );
   realiser_test(
      "echec (faux negatif)",
      vector<Tache<int>> { { 80, 40, 1 }, { 40, 10, 2 }, { 20, 5, 3 } },
      bini_2007{}
   );
   realiser_test(
      "succes (legitime)",
      vector<Tache<int>> { { 80, 40, 1 }, { 40, 10, 2 }, { 20, 5, 3 } },
      bini_2007{}, true
   );
}

Construire un test d'ordonnançabilité

Vous trouverez ici le détail de certains composants clés des tests d'ordonnançabilité.

Évaluer l'interférence maximale d'une tâche

La fonction evaluer_interference_maximale() évalue l'interférence maximale que subira une tâche dans un intervalle de temps donné. étant donné que les calculs débutent typiquement à l'instant critique pour un ordonnanceur donné, et que cet instant est typiquement considéré comme l'instant 0 pour les fins des calculs, le paramètre intervalle dans la fonction est dans .

Le nombre maximal de fois qu'une tâche pourra s'exécuter dans l'intervalle s'exprime comme :

\[ \left\lceil \frac{R_i}{T_j} \right\rceil \]

...où est, pour cette fonction, donné par un paramètre et où est la période de la tâche . On discute en fait des paramètres de la tâche en évaluant l'interférence causée par une autre tâche tout en ne connaissant a priori que la borne supérieure exclusive de l'intervalle.

De son côté, l'interférence maximale que peut entraîner une tâche dans un intervalle de temps donné est donné par :

\[ \left\lceil \frac{R_i}{T_j} \right\rceil C_j \] 
template <class T>
   T evaluer_interference_maximale(const Tache<T> &t, T intervalle) {
      const T nb_lancements_dans_intervalle =
         static_cast<T>(
            ceil(static_cast<double>(intervalle)/static_cast<double>(t.periode()))
         );
      return nb_lancements_dans_intervalle * t.wcet();
   }

Construire

L'ensemble contient les tâches de priorité supérieure à celle de ; le symbole signifie d'ailleurs ici Higher Priority Than. évidemment, la constitution de dépend directement de l'ensemble de tâches à ordonnancer, de même que de la priorité de la tâche elle-même..

La construction de cet ensemble est une tâche somme toute banale. On pourrait faire plus élégant en utilisant un algorithme comme std::partition(), si vous avez envie de vous amuser un peu.

 
template <class T, class It>
   vector<Tache<T>> construire_hp(const Tache<T> &t, It debut, It fin) {
      vector<Tache<T>> v;
      copy_if(debut, fin, back_inserter(v), [t](const Tache<T> &candidat) {
         return candidat.priorite() > t.priorite();
      });
      return v;
   }

Évaluer le temps de réponse d'une tâche

Le calcul du temps de réponse d'une tâche peut tenir compte des interférences (pour les tâches autres que la plus prioritaire d'entre toutes) ou ne pas en tenir compte (pour la tâche la plus prioritaire du lot).

L'équation décrivant ce calcul est donnée par :

\[ R_i = C_i + \sum_{j \in hp(i)} \left\lceil \frac{R_i}{T_j} \right\rceil C_j \]

Cette équation est plus facile à résoudre numériquement en commençant par la tâche la plus prioritaire (qui ne subit pas d'interférences d'autres tâches) et en « reculant » vers les tâches les moins prioritaires.

 
template <class T, class It>
   double evaluer_temps_reponse_v1
      (const Tache<T> &t, It debut, It fin, T intervalle) {
      auto v = construire_hp(t, debut, fin);
      return accumulate(begin(v), end(v), t.wcet(), [intervalle](double cumul, const Tache<T> &t) {
         return evaluer_interference_maximale(t, intervalle);
      });
   }
template <class T>
   double evaluer_temps_reponse_v0(const Tache<T> &t) {
      return t.wcet();
   }

Pour déterminer un intervalle réaliste pour chaque tâche , nous avons recours à une évaluation débutant par la dernière tâche (la plus prioritaire) et procédant à rebours, cumulant les résultats en cours de route.

 
template <class It, class T>
   T evaluer_terme_intervalle_realiste(T eval_avant, It debut, It fin) {
      return accumulate(debut, fin, T(), [&eval_avant](T cur, const Tache<int> &t) {
         return static_cast<T>(ceil(static_cast<double>(eval_avant)/
                                    static_cast<double>(t.periode())) *
                               static_cast<double>(t.wcet()));
      });
   }
template <class It>
   int evaluer_intervalle_realiste(It debut, It fin) {
      assert (debut != fin);
      vector<Tache<int>> v(debut, fin);
      sort(begin(v), end(v), greater<Tache<int>>{});
      vector<int> omega;
      omega.push_back(v.front().wcet());
      for (auto p = next(begin(v)); p != end(v); ++p) {
         auto courant = evaluer_terme_intervalle_realiste(omega.back(), next(p), end(v));
         if (courant == omega.back()) return courant;
         omega.push_back(courant);
      }
      return v.front().periode() + 1; // échec
   }

Enfin, le programme principal applique ces quelques tests à des ensembles de tâches donnés.

 
int main() {
   realiser_tests_liu_layland_1973();
   realiser_tests_bini_2007();
   {
      vector<Tache<int>> v{ Tache<int>{ 50, 12, 1 }, Tache<int>{ 40, 10, 2 }, Tache<int>{ 30, 10, 3 } };
      cout << "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-" << endl;
      cout << "Evaluer temps de reponse, v0 (calcul de base)" << endl;
      for(const auto &t : v)
         cout << "Tache : " << t << "; WCET: "
              << evaluer_temps_reponse_v0(t) << endl;
      const int periode_max =
         accumulate(next(begin(v)), end(v), v.front().periode(), [](int so_far, const Tache<int> &t) {
            return max(so_far, t.periode());
         });
      cout << "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-" << endl;
      cout << "Evaluer temps de reponse, v1 (inclure interference), [0..Ri) avec Ri == "
           << periode_max << endl;
      for(const auto &t : v)
         cout << "Tache : " << t << "; WCET: "
              << evaluer_temps_reponse_v1(t, begin(v), end(v), periode_max) << endl;
      cout << "-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-" << endl;
      //
      // La question: trouver Ri (periode_max n'est qu'un estimé pessimiste)
      //
      const int intervalle_realiste =
         evaluer_intervalle_realiste(v.begin(), v.end());
      cout << "Evaluer temps de reponse, v2 (avec interference), [0..Ri) avec Ri == "
           << periode_max << endl;
      for(const auto & t : v)
         cout << "Tache : " << t << "; WCET: "
              << evaluer_temps_reponse_v1(t, begin(v), end(v), periode_max) << endl;
   }
}

À l'exécution, nous obtenons ce qui suit.

Liu et Layland, 1973


Ce test s'applique dans le cas ou les taches sont periodiques, ne partagent pas de ressources,
et ou l'echance de chaque tache est egale a sa periode. Les priorites doivent etre statiques
et les priorites doivent etre choisies de maniere a ce que les taches de plus courte periode
soient les plus prioritaires. Le temps d'un changement de contexte est presume negligeable


-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Taches a ordonnancer: {p:1, P:50, C:12} {p:2, P:40, C:10} {p:3, P:30, C:10}
Resultat attendu: echec (legitime)
Test echoue, score 0.823333, seuil 0.779763

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Taches a ordonnancer: {p:1, P:80, C:40} {p:2, P:40, C:10} {p:3, P:20, C:5}
Resultat attendu: echec (faux negatif)
Test echoue, score 1, seuil 0.779763

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Taches a ordonnancer: {p:1, P:80, C:40} {p:2, P:40, C:10} {p:3, P:20, C:5}
Apres groupement en familles: {p:1, P:80, C:80}
Resultat attendu: succes (legitime)
Test reussi, score 1, seuil 1

Bini, 2007


Ce test s'applique dans le cas ou les taches sont periodiques, ne partagent pas de ressources,
et ou l'echance de chaque tache est egale a sa periode. Les priorites doivent etre statiques
et les priorites doivent etre choisies de maniere a ce que les taches de plus courte periode
soient les plus prioritaires. Le temps d'un changement de contexte est presume negligeable


-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Taches a ordonnancer: {p:1, P:50, C:12} {p:2, P:40, C:10} {p:3, P:30, C:10}
Resultat attendu: echec (legitime)
Test echoue, score 2.06667, seuil 2

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Taches a ordonnancer: {p:1, P:80, C:40} {p:2, P:40, C:10} {p:3, P:20, C:5}
Resultat attendu: echec (faux negatif)
Test echoue, score 2.34375, seuil 2

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Taches a ordonnancer: {p:1, P:80, C:40} {p:2, P:40, C:10} {p:3, P:20, C:5}
Apres groupement en familles: {p:1, P:80, C:80}
Resultat attendu: succes (legitime)
Test reussi, score 2, seuil 2

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Evaluer temps de reponse, v0 (calcul de base)
Tache : {p:1, P:50, C:12}; WCET: 12
Tache : {p:2, P:40, C:10}; WCET: 10
Tache : {p:3, P:30, C:10}; WCET: 10
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Evaluer temps de reponse, v1 (inclure interference), [0..Ri) avec Ri == 50
Tache : {p:1, P:50, C:12}; WCET: 20
Tache : {p:2, P:40, C:10}; WCET: 20
Tache : {p:3, P:30, C:10}; WCET: 10
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Evaluer temps de reponse, v2 (avec interference), [0..Ri) avec Ri == 50
Tache : {p:1, P:50, C:12}; WCET: 20
Tache : {p:2, P:40, C:10}; WCET: 20
Tache : {p:3, P:30, C:10}; WCET: 10

Test d'ordonnançabilité pour algorithme EDF

Un test d'ordonnançabilité pour EDF remonte aussi à Liu et Layland (1973). Ce test suppose que , donc que l'échéance d'une tâche est égale à sa période, et va comme suit (voir ceci pour un rappel du sens des symboles utilisés) :

\[ \sum_{i=1}^N{\left(\frac{C_i}{T_i}\right)} \leq 1\]

La simplicité de ce test est appréciable : ici, dans la mesure où le taux d'utilisation est inférieur à , le critère d'ordonnançabilité est rencontré.

Le test d'ordonnançabilité ci-dessus est exact pour EDF alors que l'équivalent est seulement suffisant pour FPS. On sait par contre que tout ordonnancement valide avec un algorithme FPS serait aussi valide avec EDF.

 
struct test_liu_layland_1973_edf {
   template <class It>
      pair<double, bool> operator()(It debut, It fin) const {
         using value_type = typename
            iterator_traits<It>::value_type;
         auto N = distance(debut, fin);
         auto somme = accumulate(debut, fin, 0.0, [](double cumul, value_type t) {
            return cumul + (static_cast<double>(t.wcet()) /
                            static_cast<double>(t.periode()));
         });
         return { somme, somme <= 1 };
      }
};

Charge du système avec ordonnancement selon l'algorithme EDF

Il est possible, avec EDF, d'évaluer la charge du système à un instant par (voir ceci pour un rappel du sens des symboles utilisés) :

\[ h(t)=\sum_{i=1}^N{\lfloor \frac{t+T_i-D_i}{T_i}\rfloor C_i} \]

Pour EDF, en pratique, on mesurera la charge du système aux moments correspondant aux échéances des tâches, et non pas de manière continue. Notez que cet exemple ne profite pas des avancées de C++ 11 avec <chrono>.

Il existe aussi une limite analytique à partir de laquelle il n'est plus pertinent d'évaluer la charge d'un système ordonnancé à partir de cette stratégie (à tout le moins s'il n'y a pas de nouvelles tâches qui s'ajoutent à l'ensemble devant être ordonnancé), que je n'ai pas le temps de détailler pour le moment (désolé!).

 
//
// Ici, il faut utiliser une version « enrichie » du type Tache
// en lui ajoutant une echeance (ici un clock_t par souci de
// simplicité)
//
struct charge_systeme_edf {
   template <class It>
      double operator()(clock_t temps, It debut, It fin) {
         using value_type = typename
            iterator_traits<Itt>::value_type;
         auto N = distance(debut, fin);
         return accumulate(debut, fin, 0.0, [&temps](double cumul, value_type t) {
            return cumul + floor(
               (
                   static_cast<double>(temps) + 
                   static_cast<double>(t.periode()) -
                   static_cast<double>(t.echeance())
               ) / static_cast<double>(t.periode())
            ) * static_cast<double>(t.wcet());
         });
      }
};

Voilà!

Valid XHTML 1.0 Transitional

CSS Valide !