Algorithme de Dekker

L'article suppose que vous avez lu la présentation générale des algorithmes de synchronisation classiques, de même que Algos-Section-Critique-General.html qui explique la démarche d'ensemble, présente les risques et décrit les classes Producteur et Consommateur qui sont réinvesties ici.

Le code qui suit est une implémentation de l'algorithme de Dekker, qu'on attribue au mathématicien néerlandais Theodorus Dekker. Cet algorithme permet la synchronisation de deux unités d'exécution (threads, processus) partageant une zone de mémoire, sans avoir recours à des outils de synchronisation comme ceux que l'on trouve dans les systèmes d'exploitation contemporains. Ce serait le premier algorithme du genre, historiquement.

Intuition générale : chaque unité d'exécution annonce son intention d'entrer dans la section critique. Si une situation ambiguë survient, un système de tour donne à l'une des unités d'exécution priorité sur l'autre

Le principe

Le principe de cet algorithme va comme suit :

Détails spécifiques à l'algorithme de Dekker

L'algorithme de Dekker utilise deux états partagés, placés dans etats_synchro à droite :

  • Un entier représentant un tour (à qui le tour d'accéder à la section critique?), et
  • Un tableau contenant un booléen par unité d'exécution

Remarquez le recours à des assertions dynamiques pour valider les indices. Déboguer un algorithme parallèle peut être complexe et ardu; ne négligez pas ces précieux outils!

L'algorithme demande occasionnellement de connaître l'identité de l'autre unité d'exécution. Ce service est statique (offert directement par la classe). L'algorithme demande aussi de passer d'un tour à l'autre, logique cyclique qu'implémente le service prochain_tour().

Cet algorithme a sans doute inspiré (au moins en partie) l'algorithme de Peterson.

 
#include "Producteur.h"
#include "Consommateur.h"
#include <cassert>
#include <algorithm>
#include <iostream>
#include <string>
#include <fstream>
#include <thread>
#include <random>
using namespace std;
class etats_synchro
{
   enum { NTHREADS = 2 };
   bool fanion_[NTHREADS];
   int tour_;
public:
   etats_synchro()
      : tour_{}
   {
      fill(begin(fanion_), end(fanion_), false);
   }
   int tour() const
      { return tour_; }
   bool fanion(int n) noexcept
   {
      assert(0 <= n && n < NTHREADS);
      return fanion_[n];
   }
   void fanion(int n, bool val) noexcept
   {
      assert(0 <= n && n < NTHREADS);
      fanion_[n] = val;
   }
   static int autre_que(int n) noexcept
      { return (n + 1) % NTHREADS; }
   void prochain_tour() noexcept
      { tour_ = autre_que(tour()); }
};

L'algorithme de Dekker est implémenté par la fonction dekker(), à droite, exécutée dans un thread distinct. Le code clé de cet algorithme est celui qui gère l'entrée dans la section jugée critique, de même que celui qui en gère la sortie.

En gros :

  • Le thread en cours indique son intention d'entrer dans la section
  • Tant que l'autre thread signale aussi sa présence dans cette zone charnière, le thread en cours examine l'indicateur de tour pour voir si ça semble être à son tour de procéder. Si ce n'est pas le cas, il signale qu'il n'est plus en train d'essayer d'entrer dans la zone et attend patiemment son tour, puis signale à nouveau son intention d'entrer
  • Lorsque le thread en cours arrive au stade où son intention a été signalée, où l'autre thread n'est plus en train de signaler son intention d'être dans la zone critique, et où cela semble être le tour du thread actif de procéder, alors il exécute le code associé à la section jugée critique, puis signale à l'autre thread que c'est maintenant à son tour et signale ensuite qu'il quitte lui-même la zone critique

La mécanique de la répétitive d'entrée dans la zone critique fait en sorte qu'il arrive assez fréquemment que les circonstances mènent une même unité de traitement accède à la zone critique plusieurs fois consécutives. C'est la vie.

 
template <class T>
   void dekker(T && oper, etats_synchro &etats, bool &fin)
   {
      auto id = oper.id;
      while (!fin)
      {
         oper.avant_partie_critique();
         etats.fanion(id, true); // je veux entrer
         while (etats.fanion(etats_synchro::autre_que(id))) // quelqu'un d'autre y est?
         {
            if (etats.tour() != id) // ce n'est pas a mon tour?
            {
               etats.fanion(id, false); // je retire ma demande
               while (etats.tour() != id) // j'attends mon tour
                  ;
               etats.fanion(id, true); // je reitere ma demande
            }
         }
         oper.partie_critique();
         etats.prochain_tour(); // on laisse la place a un autre
         etats.fanion(id, false); // je n'y suis plus
         oper.apres_partie_critique();
      }
   }

Sans grande surprise, le programme principal lance les diverses unités de traitement souhaitées, assure leur identification correcte et leur supplée le booléen qu'elles partageront et qui jouera pour elles le rôle d'un signal de fin, puis attend la fin des threads et nettoie les ressources attribuées au préalable.

 
int main()
{
   etats_synchro etats;
   random_device rd;
   mt19937 prng{ rd() };
   auto gen_work = [&]() -> int {
      uniform_int_distribution<int> de(1,50);
      return de(prng);
   };
   ofstream sortie{"out.txt"};
   clog.rdbuf(sortie.rdbuf());
   bool fin = {};
   int id = {};
   string transit;
   Producteur prod{ id++, transit, gen_work };
   Consommateur cons{ id++, transit, sortie };
   thread th[] = {
      thread{[&] {
         dekker(prod, etats, fin);
      }},
      thread{[&] {
         dekker(cons, etats, fin);
      }}
   };
   char c; cin >> c; fin = true;
   for(auto &thr : th)
      thr.join();
   clog.rdbuf(nullptr);
}

Valid XHTML 1.0 Transitional

CSS Valide !