Algorithmes pour implémenter une section critique – généralités

Divers algorithmes ont été proposés pour implémenter des sections critiques dans le but d'assurer une synchronisation ponctuelle entre deux (parfois entre n) unités de traitement.

J'en ai implémenté quelques-uns pour vous, tous à partir d'une gamme d'outils communs (voir l'encadré à droite pour une liste des implémentations proposées). Notez que les implémentations classiques sont pratiquement toujoures exprimées en pseudocode; celles que j'ai réalisé pour vous sont en C++ 11 (aux threads près, qui dépendent de la plateforme).

Ce que vous trouverez ici est une liste des outils d'ordre général, communs à toutes ces implémentations. Les détails de chaque algorithme apparaissent sur leurs pages respectives.

Détails d'ordre général

Les divers exemples d'algorithmes de synchronisation présentés ici seront identiques à plusieurs égards, et différents du point de vue de l'algorithme, évidemment, de même que des états sur lesquels cet algorithme repose. Tel qu'indiqué plus haut, ce document se concentre sur les détails d'ordre général des implémentations qui vous sont proposées; pour ce qui est spécifique à chaque algorithme, référez-vous à la page appropriée.

Dans cette incarnation, les tâches n'auront pas de classe parent commune. J'ai procédé de manière moins intrusive, à partir de code générique. Toute tâche aura toutefois un identifiant entier unique pour faciliter l'affichage, le débogage et la prise en charge de certains aspects protocolaires dans les algorithmes qui en ont besoin.

Chaque algorithme comprendra :

• Un producteur, qui générera des données
• Un consommateur, qui consommera des données
• Un ensemble d'états partagés entre les threads gérant respectivement le producteur et le consommateur, pour l'implémentation de l'algorithme

Le producteur et le consommateur sont modélisés par des classes, mais sont identiques dans tous les exemples. Chacun effectuera dans sa section critique (nommée partie_critique() dans le code) une tâche qui requiert de la synchronisation. Le rôle de chaque algorithme sera de leur offrir cette synchronisation.

Les programmes de test sont aussi identiques, mais à un détail près, soit le nom de la fonction qui exécutera l'algorithme (j'ai utilisé le nom de l'algorithme dans chaque exemple).

Producteur

Dans sa partie critique, une instance de Producteur insérera du texte arbitraire dans l'objet contenant les données partagées. Pour les besoins de la cause, on utilisera un nombre pseudo-aléatoire d'instances d'un texte significatif choisi avec soin.

#ifndef PRODUCTEUR_H
#define PRODUCTEUR_H
#include <string>
#include <ostream>
#include <functional>

class Producteur
{
   std::string &donnees;
   std::function<int()> gen_work;
public:
   const int id;
   Producteur(int id, std::string &s, std::function<int()> gen_work)
      : id{ id }, donnees{ s }, gen_work{ gen_work }
   {
   }
   void avant_partie_critique();
   void partie_critique();
   void apres_partie_critique();
};
#endif

#include "Producteur.h"
#include <string>
#include <iostream>
#include <cassert>
using namespace std;

void Producteur::avant_partie_critique()
   { clog << "Prod (avant)\n"; }

void Producteur::partie_critique()
{
   auto netapes = gen_work();
   assert(netapes >= 0);
   clog << "Prod! (debut)\n";
   while (netapes--)
      donnees += "J'aime mon prof!\n";
   clog << "Prod! (fin)\n";
}

void Producteur::apres_partie_critique()
   { clog << "Prod (apres)\n"; }

Consommateur

Une instance de Consommateur affichera le contenu de l'objet contenant les données partagées, et videra cet objet.

#ifndef CONSOMMATEUR_H
#define CONSOMMATEUR_H
#include <string>
#include <ostream>
#include <cassert>

class Consommateur
{
   std::string &donnees;
   std::ostream &sortie;
public:
   const int id;
   Consommateur(int id, std::string &s, std::ostream &sortie)
      : id{id}, donnees{s}, sortie{sortie}
   {
      assert(sortie);
   }
   void avant_partie_critique();
   void partie_critique();
   void apres_partie_critique();
};
#endif

#include "Consommateur.h"
#include <string>
#include <iostream>
using namespace std;

void Consommateur::avant_partie_critique()
   { clog << "Cons (avant)\n"; }

void Consommateur::partie_critique()
{
   clog << "Cons debut!\n";
   sortie << donnees << endl;
   while (!donnees.empty())
      donnees = donnees.substr(0, donnees.size() - 1);
   // donnees_.clear();
   clog << "Cons fin!\n";
}

void Consommateur::apres_partie_critique()
   { clog << "Cons (apres)\n"; }