Algorithme de Peterson pour unités de traitement

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 Peterson, de Gary L. Peterson.

La version de base de cet algorithme (présentée ici) permet la synchronisation de deux unités d'exécution (threads, processus) partageant 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. Celle présentée par la présente est quant à elle une version généralisée à unités d'exécution.

Intuition générale : c'est une approche courtoise, où une unité d'exécution offre le passage aux autres, puis attend que l'une des autres lui rende la pareille ou qu'elles choisissent de ne pas accéder à cette section critique

Le principe

Référez-vous pour l'essentiel à la version à deux unités d'exécution. La mécanique est similaire.

Détails spécifiques à l'algorithme de Peterson pour unités de traitement

Cette version de l'algorithme de Peterson utilise deux états partagés, placés dans  etats_synchro à droite :

  • Un tableau d'entiers, un par unité de traitement, représentant par un numéro d'étape l'acte de chercher à entrer dans la zone critique, et
  • Un autre tableau d'entiers, un par unité de traitement ici aussi, représentant la plus récente unité d'exécution à utiliser un numéro d'étape donné

Puisque cet algorithme fait correspondre les numéros d'unités de traitement et les numéros d'étapes, une valeur hors des bornes légales pour un numéro d'étape ( dans ce cas-ci) a été utilisé pour indiquer une étape non choisie.

 
#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
{
public:
   enum { NTHREADS = 2 };
private:
   int in_stage_[NTHREADS],
       last_process_[NTHREADS];
public:
   etats_synchro()
   {
      fill(begin(in_stage_), end(in_stage_), -1);
      fill(begin(last_process_), end(last_process_), 0);
   }
   int in_stage(int n) const noexcept
   {
      assert(0 <= n && n < NTHREADS);
      return in_stage_[n];
   }
   void in_stage(int n, int id) noexcept
   {
      assert(0 <= n && n < NTHREADS);
      in_stage_[n] = id;
   }
   void in_stage_reset(int n) noexcept
   {
      assert(0 <= n && n < NTHREADS);
      in_stage_[n] = -1;
   }
   int last_process(int n) const noexcept
   {
      assert(0 <= n && n < NTHREADS);
      return last_process_[n];
   }
   void last_process(int n, int id) noexcept
   {
      assert(0 <= n && n < NTHREADS);
      assert(0 <= id && id < NTHREADS);
      last_process_[n] = id;
   }
};

L'algorithme lui-même est implémenté par la fonction peterson_n(), à 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.

Sa mécanique va comme suit :

 
template <class T>
   void peterson_n(T && oper, etats_synchro &etats, bool &fin)
   {
      auto id = oper.id;
      while (!fin)
      {
         oper.avant_partie_critique();
         //
         // Tenter d'entrer dans la section critique
         //
         for (int j = 0; j < etats_synchro::NTHREADS; ++j)
         {
            etats.in_stage(id, j);
            etats.last_process(j, id);
            // wait while process k is in a higher-numbered stage than process i and
            // process i was the last to enter stage j
            for (int k = 0; k < etats_synchro::NTHREADS; ++k)
               if (k != id)
                  while (etats.in_stage(k) >= etats.in_stage(id) &&
                         etats.last_process(j) == id)
                     ;
         }
         oper.partie_critique();
         etats.in_stage_reset(id);
         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{[&] {
         peterson_n(prod, etats, fin);
      }},
      thread{[&] {
         peterson_n(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 !