|
L'algorithme d'Eisenberg et de McGuire utilise deux états partagés,
placés dans le singleton
etats_synchro présenté à droite :
- Un tableau d'états, un par unité de traitement, où
l'entrée à un indice donné indique l'état
actuel de l'unité de traitement correspondante; et
- Un entier représentant un tour (à qui le tour d'entrer
dans la section critique?).
Le singleton à droite encapsule les états derrière
une façade de services essentiels, le tout dans une optique de
lisibilité et de robustesse.
|
#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:
enum Etat { VEUT_ENTRER, EST_DEDANS, EST_IDLE };
Etat fanion_[NTHREADS];
int tour_;
public:
etats_synchro()
: tour_{} // peu importe
{
fill(begin(fanion_), end(fanion_), EST_IDLE);
}
void veut_entrer(int n) noexcept
{
assert(0 <= n && n < NTHREADS);
fanion_[n] = VEUT_ENTRER;
}
void entre(int n) noexcept
{
assert(0 <= n && n < NTHREADS);
fanion_[n] = EST_DEDANS;
}
bool est_idle(int n) const noexcept
{
assert(0 <= n && n < NTHREADS);
return fanion_[n] == EST_IDLE;
}
void devient_idle(int n) noexcept
{
assert(0 <= n && n < NTHREADS);
fanion_[n] = EST_IDLE;
}
bool est_dedans(int n) const noexcept
{
assert(0 <= n && n < NTHREADS);
return fanion_[n] == EST_DEDANS;
}
int tour() const noexcept
{ return tour_; }
void tour(int n) noexcept
{
assert(0 <= n && n < NTHREADS);
tour_ = n;
}
static int prochain(int n)
{
assert(0 <= n && n < NTHREADS);
return (n + 1) % NTHREADS;
}
};
|
|
L'algorithme est implémenté par la fonction
eisenberg_mcguire(), à 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. Ce code va comme suit :
- L'unité d'exécution
désireuse d'accéder à la zone critique l'indique
- Par la suite, supposant que les autres unités d'exécution
aient priorité sur elle, elle itère de manière cyclique en examinant les
états des autres unités de traitement, jusqu'à ce qu'elle ait fait un
tour complet sans trouver qui que ce soit d'actif
- Elle indique ensuite qu'elle est dans la zone critique, ce qui est
un mensonge, puis vérifier qu'elle y est bel et bien seule
- Tout cela se répète tant que l'unité d'exécution
active n'est pas en mesure d'affirmer qu'elle seule peut entrer dans la
zone critique (donc que c'est son tour ou que tous les autres candidats
sont dormants)
Une fois le travail critique terminé, l'unité active cherche
à déterminer le prochain candidat à s'exécuter,
puis retombe officiellement en état dormant. Il est possible, si
tous les autres candidats sont dormants, que la main revienne tout de
suite à l'unité de traitement active.
|
template <class T>
void eisenberg_mcguire(T && oper, etats_synchro &etats, bool &fin)
{
auto id = oper.id;
while (!fin)
{
oper.avant_partie_critique();
int j;
do
{
etats.veut_entrer(id); // j'annonce mes couleurs
// j'attends que quelqu'un, en tournant en sens "horaire" par rapport
// a moi, constate que tous les autres sont "idle". Ils ont priorite
// sur moi pour le moment
j = etats.tour();
while (j != id)
if (etats.est_idle(j))
j = etats.tour();
else
j = etats_synchro::prochain(j);
// j'annonce que je suis dans la section critique; c'est un mensonge!
etats.entre(id);
// je vérifie si je suis bel et bien seul dedans
for (j = 0 ; j < etats_synchro::NTHREADS && ((j == id) || !etats.est_dedans(j)); ++j)
;
// si la recherche a échoué et c'est mon tour
} while (!( (j >= etats_synchro::NTHREADS) &&
((etats.tour() == id) || (etats.est_idle(etats.tour())))));
// youppi, c'est à moi!!!
etats.tour(id);
oper.partie_critique();
// je trouve le prochain voisin qui n'est pas "idle", en sens "horaire" a partir de "tour",
// et je décide que c'est _son_ tour. Initialement, c'est mon tour, alors si tout le monde
// est idle, alors ca restera mon tour...
j = etats_synchro::prochain(etats.tour());
while (etats.est_idle(j))
j = etats_synchro::prochain(j);
etats.tour(j);
etats.devient_idle(id); // J'annonce que je suis "idle"
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{[&] {
eisenberg_mcguire(prod, etats, fin);
}},
thread{[&] {
eisenberg_mcguire(cons, etats, fin);
}}
};
char c; cin >> c; fin = true;
for(auto &thr : th)
thr.join();
clog.rdbuf(nullptr);
}
|
