Algorithme de Peterson

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 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. Une version généralisée à $n$ unités de traitement existe aussi.

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

Le principe

Le principe de cet algorithme va comme suit :

Deux unités d'exécution, munies d'identifiants entiers $i,j$ distincts l'un de l'autre

Une demande d'entrée dans la section critique repose sur deux états, soit une demande d'accès (booléen) et un identifiant entier de l'unité ayant accès à la section critique

Une unité d'exécution, avant d'entrer dans la section critique, donne le privilège d'accès à l'autre et lui donne une opportunité d'entrer

L'accès à la section critique n'est obtenu que lorsque l'autre signale ne pas vouloir y accéder

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

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

Un tableau de booléens, un par unité de traitement, où l'entrée à un indice donné est une indication que l'unité de traitement à cet indice souhaite entrer dans la zone jugée critique, et
Un entier représentant un tour, pour savoir à qui le tour d'entrer dans la section critique

L'algorithme demande occasionnellement de connaître l'identité de l'autre unité de traitement. 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 rappelle l'algorithme de Dekker, tout en étant un peu plus simple et, surtout, plus général (étant applicable à la synchronisation de plus de deux unités de traitement).

#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 noexcept
      { return tour_; }
   void tour(int n) noexcept
      { tour_ = n; }
   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 Peterson est implémenté par la fonction peterson(), à 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.

On remarquera qu'il repose sur un double signal d'intention :

L'unité d'exécution active indique son intention d'entrer dans la zone jugée critique; et
L'unité d'exécution active indique son souhait que ce soit à son tour d'agir.

Par la suite, l'accès à la zone jugée critique ne se fait que quand l'autre unité de traitement (dans cette version, il n'y en a que deux) ne signalera plus son intention d'être dans la section critique ou quand ce ne sera plus le tour de l'autre unité de traitement de s'exécuter.

template <class T>
   void peterson(T && oper, etats_synchro &etats, bool &fin)
   {
      auto id = oper.id;
      while (!fin)
      {
         //
         // Notez que l'ordre est important. Dans sa forme traditionnelle, cet
         // algorithme ne fonctionne pas sur une architecture contemporaine
         //
         etats.fanion(id, true); // je veux entrer
         etats.tour(etats_synchro::autre_que(id)); // je donne une opportunite au voisin d'abord
         oper.avant_partie_critique();
         while (etats.fanion(etats_synchro::autre_que(id)) && // j'attends que le voisin me donne priorite
                etats.tour() == etats_synchro::autre_que(id))
            ;
         oper.partie_critique();
         etats.fanion(id, false);
         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(prod, etats, fin);
      }},
      thread{[&] {
         peterson(cons, etats, fin);
      }}
   };
   char c; cin >> c; fin = true;
   for(auto &thr : th)
      thr.join();
   clog.rdbuf(nullptr);
}