51

IV. Problème du producteur-consommateur

1. Spécification du problème
Deux procédures Produire, Consommer sont mises respectivement à la disposition du
producteur et du consommateur pour réaliser les opérations de production et de
consommation de message. La communication des messages entre le producteur et le
consommateur associé se fait par l’intermédiaire d’un buffer.
Contraintes du problème
- vis-à-vis du producteur:
Tout message produit (émis) non encore consommé est mémorisé en attendant d’être
prélevé. Du fait de la capacité limitée du buffer (n messages au plus), la différence entre le
nombre de productions et celui des consommations ne peut dépasser n. Dans le cas
contraire, le producteur doit attendre qu’il y ait au moins une place libre dans le buffer.
- Vis-à-vis du consommateur:
Tout message produit n’est consommé qu’une fois et une seule. S’il n’y a pas de nouveaux
messages produits, le consommateur doit attendre.
Pour le respect de ces contraintes, les procédures produire et consommer doivent alors être
synchronisées.
Parmi les outils possibles servant à réaliser la spécification du problème, les compteurs de
synchronisation sont d’un usage relativement simple.

Définition des compteurs:

Soit une procédure p réentrante, on définit:
Aut(p) : nombre d’exécutions de p autorisées depuis l’Initialisation;
Term(p) : nombre de terminaisons de p depuis le début;
Ces compteurs étant initialisés à 0; on en déduit:
1- ils sont monotones et croissants;
2-  p : Aut(p)  Term(p);
3- Aut(p) - Term(p) = Act(p) : nombre d’exécution de p en cours;
Dans le cas qui nous concerne:
Term(produire) : indique le nombre de messages émis par le producteur, et
Term(consommer) : indique le nombre de messages réellement consommés.
Une émission de message n’est possible que si le producteur n’ait pas une avance de n
messages (par rapport au consommateur), et une consommation n’est possible que s’il y a des
messages produits et non encore retirés.
Dans la suite, on utilisera le terme de prod pour produire et cons pour consommer
(abréviation), d’où:
Condition (prod)  Aut(prod) < Term(cons) + n avec  signifie équivalent
 52
 Aut(prod) - Term(cons) < n
Condition(cons)  Aut(cons) < Term(prod)
 Aut(cons) - Term(prod) < 0

Invariant du problème:
Aut(prod) - Term(cons)  n
et Aut(cons) - Term(cons)  0
 p, on a: Aut(p)  Term(p) d’où
0  Term(prod) - Aut(cons)  Aut(prod) - Term(cons)  n

Si les exécutions sont considérées comme atomiques, c’est-à-dire on ne s’intéresse pas au

début et à la fin d’exécution d’une procédure, on peut écrire: Aut = Term
C’est-à-dire, on ne s’intéresse qu’au nombre de fois qu’une procédure s’est exécutée. Si on
désigne par exec ce nombre, on peut écrire: exec = Aut = Term.
D’où l’invariant:
0  exec(prod) - exec(cons)  n  le nombre de messages émis (nombre d’exécutions de
produire) et non encore retirés varie entre 0 et n.

2. Mise en œuvre centralisée

Var buffer : array[0..n-1] of msg;
in, out : 0..n-1 init 0;
% in et out désignent les prochains emplacements vide et plein du buffer. %
debprod, finprod, debcons, fincons : 0.. init 0;
Le contrôle nécessaire à l’exécution correcte d’une procédure p est:
- Attente de la condition associée à P
- Mise à jour de la variable de contrôle debp
- Action sur le buffer (production ou consommation)
- Mise à jour de la variable de contrôle finp

Prodcons.Monitor:
begin
var buffer : array[0.. n-1] of msg;
in, out : 0..n-1 init 0;
debprod, finprod, debcons, fincons : 0.. init 0;
prod, cons : condition;
procédure produire(m:msg);
begin
if debprod - fincons  n then Wait(prod) endif;
 53
debprod := debprod + 1;
buffer[in] := m;
in := (in + 1) mod n
finprod := finprod + 1;
if debcons - finprod < 0 then Signal(cons) endif
end
procédure consommer(m:msg);
begin
if debcons - finprod  0 then Wait(cons) endif
debcons := debcons + 1;
m := buffer[out];
out := (out + 1) mod n;
fincons := fincons + 1;
if debprod - fincons < n then Signal(prod) endif
end
End monitor

Remarque: in  finprod mod n

out  fincons mod n
On peut borner les compteurs en introduisant les variables nbvide et nbplein initialisées
respectivement à n et 0, et qui ont pour valeurs:
nbplein := finprod - debcons
nbvide := n + fincons - debprod.

3. Mise en oeuvre répartie

Parmi les caractéristiques qui distinguent un système distribué d’un système centralisé est
l’absence de mémoire commune pouvant servir de moyens de communication entre processus
(comme c’est le cas dans un système centralisé). Cette caractéristique impose donc une
communication inter-processus par voie de messages, et provoque une incapacité pour un
processus du système distribué à observer un état global de ce système. Comme conséquence
de cette situation particulière, des techniques de contrôle spécialement adaptées au contexte
des systèmes distribués sont alors nécessaires.
Le problème du producteur-consommateur étant fréquemment utilisé dans la conception du
modèle de coopération client-serveur et protocoles, il est donc intéressant de pouvoir le
présenter de manière pédagogique et selon diverses techniques.

Comme indiquée dans la mise en oeuvre centralisée précédente, on utilisera la technique des
compteurs et modules de contrôle.
 54
L’énoncé abstrait du problème étant identique au précédent, le système producteur-
consommateur doit assurer à tout instant l’invariant suivant I1: “il existe au plus n messages
produits et non consommés”.

3.1 Expression des conditions de production et de consommation

On peut facilement exprimer les conditions de production et de consommation à l’aide des
compteurs.
debprod : nombre de débuts d’exécution de l’opération produire
finprod : ‘’ fins ‘’ ‘’
debcons: nombre de débuts d’exécution de consommer
fincons : ‘’ fins ‘’ ‘’

Comptabiliser les débuts et fins des opérations sont nécessaire car celles-ci n’ont pas une
durée d’exécution nulle.
On a: debprod  finprod et debcons  fincons
(Cp) debprod - fincons < n
(Cc) debcons - finprod < 0
à l’aide des deux prédicats (Cp) et (Cc), on peut remplacer l’invariant I1 par I2: l’opération
produire peut s’exécuter si et seulement si (Cp) est vrai; l’opération consommer peut
s’exécuter si et seulement si (Cc) est vrai.
Les prédicats (Cp) et (Cc) constituent une expression abstraite du problème.

3.2 Première mise en oeuvre

3.2.1 Distribution du système
On considère un système formé de deux sites: le site de production et le site de consommation
sur lesquels sont respectivement placés le processus producteur et le processus
consommateur. Ces sites sont connectés par un réseau de communication;
Puisqu’on considère qu’un processus par site on confondra dans la suite les termes site et
processus.
Les variables des contrôles (compteurs) modifiées par le producteur sont localisées sur le site
de production SP. Les variables modifiées par le consommateur sont situées sur le site de
consommation SC. Ainsi les processus ne peuvent modifier que les variables se trouvant sur
leur site. L’évaluation des conditions (Cc) et (Cp) implique la lecture des variables se trouvant
sur l’autre site.
Considérons le prédicat (Cp) fonction de debprod et fincons, la variable debprod n’est lue et
modifiée que par le producteur. la variable fincons est modifiée que par le consommateur et
est lue par le producteur. La valeur de fincons doit être transmise depuis le site de
consommation vers le site de production. En raison des délais de transmission, le producteur
 55
ne peut connaître à un instant donné la valeur exacte de fincons. Il doit se contenter d’une
copie de la valeur fincons en ‘retard’ sur la valeur exacte. Le même phénomène se produit
pour la lecture de finprod par le consommateur.

3.2.2 Régularité des conditions.

Lorsque le SC modifie fincons ( suite à une terminaison de l’opération de consommation), il
envoie la nouvelle valeur de cette variable à SP. Après un certain délai (délai de
transmission); SP reçoit cette valeur ‘retardée’ et la range dans la variable cfincons (copie
ancienne de fincons).
Sachant que par définition, le compteur fincons est positif et strictement croissant; et en
supposant que la transmission des valeurs, sous forme de message, entre SP et SC se fasse en
préservant le séquencement des messages, on peut écrire qu’à tout instant on a :
I3: cfincons  fincons ( à cause de la mise à jour retardée).
Soit le prédicat Cp’: debprod - cfincons < n
il en résulte que I3 et Cp’  Cp ce qui signifie que Cp’ peut être utilisée par le producteur
comme condition pour produire (I2 vérifié). En d’autres termes si Cp’ est vérifiée pour que le
producteur puisse produire, alors Cp l’est aussi; la réciproque n’est pas vraie ( Cp vrai  Cp’
vrai).
on remarque que l’utilisation de Cp’ peut provoquer un ralentissement de la production.
mettons Cp’ sous forme régulière, on obtient
Cp’’: cfincons - debprod > -n
Rappel de la régularité
Soit le prédicat E
(E) iCi  k où les Ci représentent des compteurs monotones croissants et k est un
entier relatif.
Le prédicat est dit régulier par rapport à un compteur C i , si son coefficient i est positif. Si
on considère le prédicat E’ tel que:
(E’) i ICi  k avec ICi  Ci
et si E est régulier alors E’ E.
Dans notre cas Cp’’ est régulier par rapport à cfincons et cfincons  fincons donc Cp’ Cp.
Il est donc valide d’utiliser Cp’ comme condition de production.
remarque : S’il n’y a pas perte de message, la transmission de la valeur de fincons n’est pas
nécessaire, un message de type “ fin de consommation ” suffit. Si par contre, des messages
peuvent se perdre, il est nécessaire que le consommateur transmette de temps à autre les
valeurs de fincons.

3.3.3. Mise en oeuvre possible.

Le site de production comporte un processus producteur Prod générant des messages et un
 56
contrôleur de production P chargé de les transmettre au site consommateur. Ce dernier se
compose d’un tampon ou buffer, d’un processus consommateur Cons, et d’un contrôleur de
consommation C chargé de recevoir les messages émis par P.

Producteur Consommateur

RDV RDV
Communication
Contrôleur P Contrôleur C
Asynchrone

Partie Production Partie Consommation

Figure 1. Structure du système producteur/consommateur

3.3.3.1. notation et convention d’écriture

Le langage utilisé dans la suite sera proche du langage CSP (Hoare 78).
La formulation se fera selon le schéma: condition  action ;
une condition est composée d’une conjonction d’expressions booléennes et éventuellement
d’une primitive de communication:
Dans une condition l’opérateur de conjonction est représenté par ‘;’.
Une condition est vraie lorsque toutes les expressions booléennes de la conjonction sont
vraies et que la communication spécifiée par la primitive de communication est possible.
Une alternative est une construction regroupant plusieurs branches: condition  action;
l’exécution d’une alternative comprend d’abord l’évaluation des conditions de chaque
branche. Le système choisit arbitrairement une des conditions évaluées à vrai et on exécute
l’action qui lui est associée. Une alternative répétitive est une alternative exécutée tant qu’une
des branches au moins a une condition à vrai.
Syntaxe:
[
condition  action
 ‘’  ‘’
....
]
La syntaxe de l’alternative répétitive est obtenue à partir de celle de l’alternative simple, en
faisant précéder le crochet d’une étoile: * [........?.] .
 57
Primitives de communication utilisées:
P!x : envoi d’un message x au processus avec rendez-vous;
P!!x : envoi d’un message x au processus P sans rendez-vous (émission asynchrone);
P?x : réception d’un message x venant de P avec rendez-vous;
P??x : réception d’un message x venant de P sans rendez-vous (réception asynchrone);
!?P : tes (sonde) booléen: !?P a la valeur vrai si le processus P est bloqué en attente de
communication. On l’utilise pour s’assurer que l’envoi du message P!x n’est pas
bloquant pour l’émetteur.
Les commentaires sont précèdes du double tiret ( --) et se terminent à la fin de la ligne, les
phrases entre les symboles < et > sont des macro-instructions.

3.3.3.2. Algorithme du contrôleur de production

Le producteur Prod transmet au contrôleur de production les messages destinés au
consommateur.
La communication entre Prod et son contrôleur P se fait par rendez-vous. Ainsi, Prod est
bloqué par P tant que le précédent message à produire n’a pu être inséré dans le tampon.
-- définition du processus P;
P::
-- Initialisation
debprod := 0 -- compteur du nombre d’opérations de production ayant débuté;
cfincons := 0 -- copie locale, utilisée par P, du compteur du nombre d’opérations de
consommation ayant terminé;
req_en_cours := faux -- booléen n’autorisant qu’au plus un seul message en attente de
-- production
*[
-- Accepter un message du producteur si ce n’est pas déjà fait :
non req_en_cours ; Prod ? message  req_en_cours := vrai
?
-- Si une production est prête et si la condition de production est vraie alors émettre la
-- production:
req_en_cours ; debprod - cfincons < n  debprod := debprod +1
C!!message
req_en_cours := faux
?
-- Attente du signal de fin de consommation venant du contrôleur de consommation et --
-- mettre à jour la copie cfincons
C ?? signal-fincons  cfincons := cfincons +1
]
 58

3.3.3.3. Algorithme du contrôleur de consommation

Le contrôleur C transmet au consommateur Cons les messages produits par Prod et reçus par
l’intermédiaire de P.
-- définition de processus C
C::
-- Initialisation
debcons := 0
cfinprod := 0
*[
-- Transmettre une production au processus consommateur si la condition de
-- consommation est vrai:
debcons - cfinprod < 0 ; !? Cons  debcons := debcons +1
< extraire un message du tampon >
Cons ? message
-- signaler la fin de l’opération de consommation afin que le contrôleur de
-- production puisse mettre à jour la variable cfincons:
P!!signal-fincons

-- attendre l’arrivée d’un message de production:
P?? message  cfinprod := cfinprod + 1
< mémoriser le message dans le tampon >
]

3.3.4. pertes de messages

Dans l’algorithme précédent, il est supposé implicitement que le système de transmission est
d’une fiabilité telle que tous les messages du type Signal-fincons émis par le contrôleur de
consommation C sont reçus convenablement au niveau du contrôleur de production P. Ces
messages permettent à P de contrôler les emplacements libres du tampon de C. La perte
définitive d ’un de ces messages implique l’occupation définitive d’un emplacement du
tampon; c’est à dire: un message occupe une place dans le tampon et attend (indéfiniment)
d’être consommé.
En fait, la perte de messages dans un réseau est un problème réel et pour en tenir compte, il
est important de transmettre la valeur de fincons (équivalent à debcons) au lieu d’un simple
signal Signal-fincons.
Pour ce faire, les algorithmes précédents doivent être modifiés comme suit:
- Remplacer la dernière branche de l’alternative répétition du contrôleur de production P par:
C??x  cfincons := x
 59
-- P reçoit de C la valeur de fincons.
- Ajouter dans l’algorithme du contrôleur de consommation une variable fincons initialement
nulle et incrémentée après chaque consommation, et remplacer l’émission P!! signal-fincons
par P!!fincons pour transmettre la valeur de fincons au contrôleur de production P.
Pour prévenir la perte possible de message (de données ou de contrôle) et le déséquencement
(l’arrivé des messages n’est pas l’ordre de leurs émissions), il suffit d’utiliser le protocole de
transmission de Stenning (76) [HDLC, par exemple)

Remarque: Pour éviter de manipuler des compteurs (monotones continuellement) croissants

pouvant éventuellement attendre des valeurs trop importantes, on peut leur substituer les
valeurs dans l’intervalle [0,N]:
Nbemplplein : nombre d’emplacements pleins du tampon;
Nbemplplein = debprod - cfincons
Nbemplvide : nombre d’emplacements vides du tampon
Nbemplvide = debcons - cfinprod + N

3.4 Seconde mise en forme : système multiproducteurs / uni-consommateur

Remplaçons dans le système précédent le producteur unique par M producteurs, on obtient
alors la mise en oeuvre suivante :
- les M processus producteurs sont en compétition pour l’accès à l’objet partagé constitué des
emplacements libres du tampon du consommateur. Les compteurs debprod et finprod sont
respectivement partagés en lecture/écriture et en écriture;
- la communication s’effectue entre les m producteurs et le consommateur qui les considère
comme une entité unique vis à vis de la coopération dans le système. Les problèmes
soulevés précédemment et les solutions apportées demeurent inchangés.

Ces deux parties du protocole de coopération Producteur/Consommateur sont bien distinctes;

leur mise en oeuvre et les réseaux qu’elles utilisent peuvent être différents.

Distribution d’une variable globale:

Répartir un objet partagé (global) en mise à jour (lecture/écriture) dans un système distribué
implique une exclusion mutuelle des accès aux objets.
C’est le cas de la variable debprod partagée entre les différents producteurs. Ainsi, tout
algorithme, destiné à garantir la cohérence d’un objet partagé dans un système réparti, doit
assurer les propriétés suivantes:
- Exclusion mutuelle lors des accès;
- Equité dans l’attribution du privilège de l’exclusion (absence de privation lors des
demandes de l’exclusion);
 60
- Absence d’interblocage entre sites.

3.5 Méthode de réalisation de l’exclusion mutuelle

3.5.1 Jeton circulant
Dans la technique du jeton circulant, le privilège de l’exclusion mutuelle est représenté par la
possession d’un jeton. Ce jeton est mise en oeuvre par un message de contrôle qui circule en
un exemplaire unique dans le système. Ce jeton véhicule les variables à répartir en
garantissant l’exclusion mutuelle. Dans le cas qui nous concerne, la variable transportée sera
debprod et le jeton circulera parmi l’ensemble des processus. Puisque cette circulation de
jeton dépend de la topologie du réseau qui interconnecte les différents sites (de production) et
la possession du jeton implique l’acquisition du privilège; le trajet suivi par le jeton doit donc
assurer l’équité dans l’attribution de l’exclusion mutuelle. Il semblerait que l’algorithme qui
assura un routage équitable du jeton serait de faire circuler ce dernier sur un anneau virtuel.
Quelles seraient alors les conséquences du choix d’une topologie en anneau virtuel reliant les
différents sites producteurs (ce qui sera examiné dans la suite).

3.5.2. Structure du système

On considère les m processus producteurs P1, P2, ..., Pm répartis sur un anneau, comme
l’indique la figure 2, ci-après.
L’obtention de l’exclusion mutuelle, par les producteurs, se fera selon l’ordre (statique) de
passage du jeton sur l’anneau, chaque site obtient le privilège, l’algorithme assure donc la
propriété d’Equité et l’absence d’interblocage.
Tout producteur Pi (1  i  m) doit recevoir de manière régulière la valeur fincons.
Bien qu’il soit possible de transmettre la copie via un réseau distinct de l’anneau qui relie les
producteurs, on utilisera, pour simplifier, le service de transport offert par le jeton. Ainsi, le
site de consommation sera inséré dans l’anneau.

Entité de production Entité de

Pi-1 Pi Conso-
Mation

P3 C

P2 P1

Figure 2. Structure d’un système multi-producteur/uniconsommateur

 61

3.5.3 Première solution possible

On va faire transporter par le jeton les compteurs suivants:
- debprod par lequel sera assurée l’exclusion mutuelle;
- cfincons fournirait à chaque producteur une copie retardée du compteur original fincons;
L’algorithme exécuté par chaque producteur Pi est:
lorsque Pi reçoit le jeton et désire produire, il évalue son prédicat d’autorisation de production,
à l’aide des variables transportées par le jeton.
Si la condition est satisfaite, P i produit et met à jour debprod. P i ne peut produire plus d’un
message: il transmet ensuite le jeton à son successeur sur l’anneau. Il lui transmet ainsi le
privilège et cfincons (copie ou image de fincons).
Chaque site a une vision équitable du jeton sans toutefois que celle-ci ne soit utilisée
équitablement.
En effet, le producteur situé immédiatement après le consommateur sur l’anneau sera servi le
premier, puis transmet l’information au second qui peut se servir etc ...
Dans le cas plus favorable (tampon entièrement vide) seuls les n premiers producteurs
désirant produire pourront le faire. Si le nombre total m de producteurs du système est
supérieur à N, les m-n derniers peuvent être en situation de privation si les n premiers veulent
tous produire quand le jeton passe.

3.5.4 Une solution équitable

Pour assurer une Équité dans le service on peut agir comme suit:
- soit ordonner les requêtes de production et les servir dans cet ordre;
- soit assurer une coopération directe entre le consommateur et un producteur.
En effet, la famine possible qui peut se produire entre les producteurs est due à une méthode
(technique) de transmission de cfincons favorisant les producteurs situés sur l’anneau proches
du consommateur;
Si tous les producteurs (avaient pris ou prennent) connaissance équitablement de la valeur de
fincons, leur vision de l’état du système serait identique (au retard de transmission près).
Cette solution met en cause la topologie du réseau de communication producteur/
consommateur.
Une solution n’exigeant pas la modification de la topologie du réseau est de compléter
l’ordre statique dans lequel le jeton visite les processus par un ordre dynamique sur les
requêtes; Équité est assurée en servant en priorité les requêtes les plus anciennes.
Chaque requête de production se voit attribuer un numéro, qui est son rang dans la séquence
des requêtes émises. le compteur Comptereq servant à les estampiller est partagé en
lecture/écriture par les producteurs. Ce compteur est diffusé et protégé par l’intermédiaire du
jeton (il y est placé).
 62
Chaque producteur Pi ne peut avoir au plus qu’une requête en attente. Son numéro d’ordre
sera mémorisé dans la variable locale rangi. Le comportement d’un producteur pour
contribuer à l’ordonnancement dynamique des requêtes est alors le suivant:
le jeton transporte maintenant trois compteurs: debprod, cfincons, comptereq. Ces variables
ne peuvent être manipulées que par le possesseur du jeton (les variables locales de P i seront
indicées par i).
lorsque le producteur Pi reçoit le jeton et désire produire, il prend son rang dans la file des
requêtes (qui n’a pas d’existence physique) après avoir incrémenté le compteur comptereq. Le
code exécuté est donc:
comptereq := compte+ 1
rangi := comptereq

[Intuitivement, le producteur Pi aura un comportement équitable s’il ne se sert que lorsque le

nombre de places libres nlibres est supérieur au nombre de requêtes en attente plus
anciennes que la sienne (nlibres représente le nombre de places libres tel que le perçoit le
possesseur du jeton )].
Le producteur possédant le jeton détient les variables debprod et cfincons et a ainsi
connaissance du nombre nreqprio. des requêtes prioritaires (i.e situées avant la sienne). En
effet:
nreqprioi = rangi - debprod - 1
nlibres = n - (debprod - cfincons)
La condition de production assurant l’équité est locale au producteur et s’écrit:
(Ce) nlibres > nreqprioi
[cette expression suppose que le possesseur du jeton prend son rang avant de tester Ce].
La valeur nreqprio, représente le nombre de requêtes plus prioritaires que la sienne. La
condition (Ce) implique Cp’; en effet:

(Ce) n - ( debprod - cfincons ) > rangi - debprod - 1

 rangi - cfincons  n
avant que le producteur ne produise, rangi > deprod d’où
(Ce2) rangi - cfincons  n  debprod - cfincons < n
c.à.d Ce2  Cp’
Ceci démontre qu’on peut adopter Ce2 comme condition de production. Lorsqu’un producteur
Pi a pris son rang, son expression rangi - cfincons est monotone décroissante. En effet, chaque
tour de jeton sur l’anneau le fait passer sur le site de consommation qui fait croître la valeur
de cfincons alors que la variable rangi reste constante. Un producteur verra dons sa requête de
production autorisée au bout d’un temps fini. le service est donc équitable et cette Equité est
linéaire puisque le temps qui s’écoule entre le dépôt d’une requête et sa satisfaction est
 63
proportionnel au nombre de producteurs.
En effet, de la relation rang i - debprod  m (il y a moins de m producteurs avec requêtes
prioritaires) et debprod - cfincons  n (invariant du système) on déduit:
rangi - cfincons  n + m (la valeur extrême est atteinte lorsque toutes les places du tampon
sont occupées et que tous les producteurs désirent produire).
Un producteur ayant une requête en attente ne peut pas produire une seconde fois tant que la
production précédente n’est pas terminée. Un producteur attendra donc au maximum m tours
de jeton sur l’anneau à condition que le consommateur consomme au moins un message par
tour de jeton; la variable cfincons n’augmente dans ce cas que d’une unité lors du passage du
jeton sur le site de consommation.
On remarque que lors d’un tour du jeton les producteurs dont la condition de production est
vraie produisent selon l’ordre de passage du jeton; l’ordre de service n’est donc pas
nécessairement l’ordre de prise de rang.
toutes les techniques de contrôle distribué employant le concept de jeton circulant doivent
faire face au problème de perte de ce jeton.

3.5.5 Algorithme de contrôle

A partir des conditions de production et de consommation présentées précédemment, on
obtient un algorithme où chaque contrôleur de production P i possède deux variables
booléennes req_en_cours et rang-pris. Req_en_cours est vraie lorsque le contrôleur de
production sait que le producteur qui lui est associé désire produire. La variable rang-pris vaut
vraie lorsque le contrôleur a pris son rang dans la file des contrôleurs désirant produire tout
en ayant req_en_cours = vrai.

3.5.5.1 Algorithme d’un contrôleur de production

Pi::
req_en_cours := faux
*[
-- accepter un message du producteur si ce n’est déjà fait:
non req_en_cours ; prod ?message  req_en_cours := vrai
rang-pris := faux
?
-- accepter le jeton venant du prédécesseur sur l’anneau:
i > 1;Pi-1? jeton (debprod, cfincons, comptereq) 
-- Définition de l’opération <utiliser jeton>
?
-- Si le producteur désire produire et si la prise de rang n’a pas encore été faite alors prendre
 64
-- son rang:
req_en_cours ; non rang-pris  comptreq := comptereq + 1
rang := comptereq
rang-pris := vrai

?
-- Si le rang a été pris et si la condition de production est vrai alors produire:
rang-pris ; rang - cfincons  n  debprod := debprod + 1
C !! message
req_en_cours := faux
rang-pris := faux

-- transmettre le jeton au successeur sur l’anneau:

?
i < m  Pi+1 ! jeton (debprod, cfincons, comptereq)
?
i = m  C! jeton (debprod, cfincons, comptereq)  < utiliser jeton >
?
i = 1 ; C? jeton (debprod, cfincons, comptereq)  < utiliser jeton >
]

3.5.5.2 Algorithme du contrôleur de consommation

C::
cfinprod := 0
fincons := 0
debcons := 0
*[
-- Accepter le jeton venant du dernier contrôleur de production sur l’anneau et fournir
-- une copie à jour du compteur fincons au premier contrôleur sur l’anneau en lui
-- transmettant le jeton:
Pm ? jeton (debprod, cfincons, comptereq) 
P1 ! jeton ( debprod, fincons, comptereq )

-- Accepter un message venant d’un contrôleur de production:
Pi ?? message  cfinprod := cfinprod + 1
< insérer le message dans le tampon >

-- Si la condition de consommation est vraie et si le consommateur désire consommer alors
 65
-- lui envoyer un message de production:
debcons - cfinprod < 0 ;!? Cons  debcons := debcons + 1
< extraire un message du tampon >
Cons ! message
fincons := fincons + 1
-- la mise à jour de la copie cfincons se fera lors de la transmission du jeton par le contrôleur
-- de consommation.
]
Remarque: la mise à jour de la copie cfincons n’est pas ici aussi explicite que pour les
algorithmes examinés dans la partie précédente 3. Ici on qu’une seule copie du compteur
fincons et elle est transportée par le jeton. Cette copie n’est remise à jour qu’au moment du
passage du jeton dans le contrôleur de consommation. Initialement le jeton est détenu par le
contrôleur C qui le lance sur l’anneau avec:
debprod = fincons = comptereq = 0

5.5.6 Cas de pannes

Plusieurs problèmes se posent lorsqu’une panne affecte un producteur P i. Dans pareil cas, les
producteurs actifs doivent continuer leur exécution normale. Pour permettre cette continuité
de service, il est nécessaire de reconstituer l’anneau des producteurs (reconfiguration de
l’anneau).
- Le producteur défaillant ayant réservé une place dans le tampon en incrémentant le
compteur comptereq, tous les producteurs recevant le jeton après P i respectent cette
réservation en ne produisant pas s’il reste qu’une seule entrée libre dans le tampon. Pour
annuler cette réservation on peut informer le consommateur de la panne de P i et lui faire
simuler la consommation d’un message issu de Pi:
Il suffit d’incrémenter cfincons, ce qui a pour effet d’augmenter d’une unité le nombre de
places libres dans le tampon.

3.6 Distribution par duplication

3.6.1 Principe
Au lieu de transporter le compteur debprod au moyen d’un jeton, il est possible de le
dupliquer sur chaque site de production. Un problème majeur surgit alors: celui de garantir la
cohérence des copies multiples. Cette cohérence comporte deux aspects:
1- Cohérence des copies multiples en lecture; en l’absence de message en transit dans le
réseau les copies doivent être identiques.
2- Cohérence lors des accès conflictuels à une variable globale partagée en écriture.

Une méthode classique pour obtenir 1) est de diffuser à tous les sites la valeur d’une copie
 66
locale lorsque son propriétaire vient de la modifier. Cette méthode est conditionnée par
l’existence d’un réseau permettant la diffusion (à l’aide d’un bus ou maillage complet).
- Pour réaliser 2) on utilise la technique courante de l’estampillage des messages par une
horloge logique (Lamport 78) et la gestion d’une file d’attente des demandes de modification.
On applique les hypothèses usuelles de transmission sur le réseau à savoir: - délai fini (non-
perte) et le non deséquencement des messages.

3.6.2 Structure du système

Soit un système comporta:
- Une partie consommation constituée d’un contrôleur C et d’un consommateur Cons;
- La partie production comprend m couples formés chacun d’un contrôleur de production Pi et
d’un producteur prodi associé. Les Pi communiquent au moyen d’un réseau complètement
maillé, sans perte ni désequencement des messages. Un autre réseau (en étoile) relie chaque
Pi au contrôleur C, avec la propriété de non perte de messages.
L’algorithme exécuté par un contrôleur Pi doit assurer quatre fonctions:
- Cohérence de la mise à jour des copies: on emploie l’estampillage et la diffusion des mises à
jour (la diffusion assure que tout site reçoit les modifications et l’estampillage qu’il est
possible de les considérer dans le même ordre sur tous les sites);
- Gestion de l’exclusion mutuelle sur la variable debprod; il s’agit de la fonction coopération
entre les producteurs (protocole PPP);
- Coopération avec le contrôleur de consommation (protocole PCP);
- Coopération avec le producteur prodi associé à Pi.

L’algorithme exécuté par le contrôleur C doit assurer deux fonctions:

- Coopération avec Pi (protocole PCP);
- Coopération avec le consommateur Cons.

3.6.3 Algorithme de contrôle

Les algorithmes de contrôle à exécuter par les sites de production seront basés sur
l’algorithme d’exclusion mutuelle de Lamport [Lamport 78] pour réaliser le protocole PPP;
les principes en sont les suivants [Raynal 84].
Lorsqu’un site désire l’exclusion mutuelle, il envoie à tous les autres sites un messages de
requête req portant une estampille, qui est la valeur de son horloge logique locale au moment
de l’émission du message. Chaque site gère une copie de la file des requêtes en attente, qui
contient un message par site producteur. Cette file locale est mise à jour lors de la réception
d’un message req; elle est maintenue triée selon les valeurs d’estampilles croissantes.
Afin que les différentes copies de la file des requêtes soient identiques, un site recevant un
message req répond par un message d’acquittement acq.
 67
Sachant que les messages ne sont pas déséquencés, la réception par P i d’un message acq
émis par Pj et estampillé par la valeur d implique qu’aucune requête d’estampille inférieur à d
et provenant de Pj n’est en transit dans le réseau. Ainsi toute arrivée de message acq d’un site
Pj, alors qu’il n’y a pas de message req du même site, conduit à mettre à jour la file locale.
L’exclusion mutuelle est obtenue par le site qui constate qu’il a reçu de tous les autres sites du
système des message req ou acq portant des estampilles plus grandes que celle de sa requête:
sa requête est en tête de sa file locale des requêtes en attente.
Lorsqu’un site relâche l’exclusion mutuelle, il envoie un message rel à tous les autres sites.
Tous les messages portent une estampille et lors de la réception d’un message l’horloge
logique locale est mise à jour de manière à permettre d’ordonner totalement les messages du
système à partir de leur estampille.
Relativement au protocole PCP, les comportements des sites sont analogues au cas précédent.

3.6.3.1 Contexte d’un contrôleur de production

- Variables locales à Pi:
debprod : copie locale du compteur, distribuée selon le protocole PPP;
cfincons : copie locale du compteur, distribuée selon le protocole PCP;
req_en_cours : booléen, variable d’état du processus
tab_req : msg[1..m],file des requêtes, distribuée selon la technique de Lamport;
h : horloge locale, utilisée dans le protocole PPP pour la cohérence des copies;
- Fonctions:
Premier(t,i) : predicat valant vrai si la plus vieille requête figurant dans la file t appartient à
Pi;
req_reçue(t,i) : predicat valant vrai si t[i] contient une requête;
- Procédures:
mise_à_jour(h_locale,h_distante) -- met à jour l’horloge locale h_locale lors de la réception
-- d’un message:
h_locale := max(h_locale, h_distante) +1;
diffuser(x,i) : -- envoie le message x à tous les Pj , j  i, et met à jour tab_req[i];
-- les messages sont envoyés au moyen d’une primitive de
-- communication asynchrone.

3.6.3.2 Algorithme d’un contrôleur de production

Pi ::
h := 0;
tab_req := 0;
debprod := 0;
cfincons := 0;
 68
req_en_cours := faux;
*[
-- Accepter une requête venant de Pj et la mémoriser:
Pj ?? req-prod (hj)  tab_req[j] := < req-prod, hj >
mise à jour(hi,hj)
-- envoyer à Pj un accusé de réception:
Pj !! acq(hi)
?
-- Accepter un accusé de réception venant de Pj et le mémoriser lorsque Pj n’a pas de requête
-- en cours:
Pj ?? acq(hj)  [non req_reçue[tab_req,j]  tab_req[j] := <acq,hj>
mise_à_jour(hi,hj)
?
-- Accepter un message de fin de requête venat de Pj
Pj ?? rel(hj)  debprod := debprod +1 -- mise à jour de la copie locale
tab_req[i] := <rel,hj>
mise_à_jour(hi,hj)
?
-- Partie concernant le dialogue entre le contrôleur de production et le producteur:
-- Accepter un message de production venant de producteur si ce n’est pas déjà fait:
non req_en_cours ; prodi ? message  req_en_cours := vrai;
-- Envoyer un message de requête à tous les autres contrôleurs:
diffuser(req-prod(hi),i);

-- Si la requête de Pi est la 1ère de la file des requêtes et si la condition de production est
-- vraie alors envoyer un message de production au contrôleur de consommation et envoyer
-- aux autres contrôleurs un message signalant que la requête de Pi a été satisfaite:
premier(tab_req,i);(debprod - cfincons) < n  debprod := debprod +1
-- Emission asynchrone:
C!!message
diffuser(rel(hi),i)
req_en_cours := faux

-- Réception asynchrone:
C??req-cons(cfincons)  skip -- Mise à jour de cfincons
]

3.6.3.3 Algorithme du contrôleur de consommation

 69
C::
-- Variables locales à C:
debcons, fincons, cfinprod: entier positif ou nul
-- initialisation
debcons := 0 -- Compteur local
cfinprod := 0 -- Copie du compteur finprod, mise à jour lors de la réception d’un message
-- consommable
*[
-- Protocole avec le consommateur:
-- Si la condition de consommation est vraie alors envoyer un message de production au
-- consommateur:
debcons - cfinprod < 0;!?cons  debcons := debcons +1
<Extraire un message du tampon>
Cons!message
-- Gestion explicite du compteur
fincons := fincons +1
-- Diffuser de manière asynchrone la nouvelle valeur du compteur fincons afin que
-- chaque contrôleur de production puisse mettre à jour sa variable locale cfincons:
 k [1..m];Pk!!req_cons(fincons)
?
-- Protocole avec les producteurs:
-- Réception asynchrone d’un message de production venant de l’un des contrôleurs de
-- production:
 j [1..m];Pj??message  <Mémorisation du message dans le tampon>
cfinprod := cfinprod +1
]

Remarque:
l’ordre de service est l’ordre d’obtention de l’exclusion mutuelle; ceci donne au service les
propriétés d’équité et d’absence d’interblocage que possède l’algorithme d’exclusion mutuelle
de Lamport utilisé [Lamport 78].

3.6.4 Cas des pannes

Avant d’obtenir l’exclusion mutuelle chaque contrôleur de production attend que tous les
autres contrôleurs aient répondu à son message de requête. En conséquence, la panne d’un
contrôleur bloque la production de tout le système. Pour remédier à ce défaut, on peut utiliser
le protocole suivant: lorsque le réseau détecte la panne d’un site P i il diffuse un message
 70
spécial en-pannei, qui informe tous les contrôleurs de production afin que ceux-ci n’attendent
pas de réponse de Pi. Lorsque le site Pi est à nouveau opérationnel, il doit se réinsérer dans le
système en diffusant un message réparéi puis attendre que chaque site Pj du système lui est
répondu soit par un message reqi si Pj a une requête en attente, soit par le message relj sinon
[Cornafion 81].

3.7 Distribution par éclatement

3.7.1 Une solution statique
La méthode précédente de distribution par duplication utilisait des variables locales reliées
par des contraintes globales. Il est possible de diminuer fortement ces contraintes en divisant
les places du tampon entre chaque site de production: on parle alors de distribution par
éclatement de variable. Chaque contrôleur de production reçoit un certain quota de places
libres ni qui lui sont ainsi allouées d’une manière statique. La compétition entre les
producteurs est nulle car ils ne se partagent aucune ressource.
Nous divisons donc n et le compteur fincons en m parties:
n = ni; fincons =  finconsi
Le compteur finconsi contient le nombre d’opérations de consommation ayant consommé une
production venant de Pi et ayant terminé. Chaque contrôleur de production P i utilise la
condition de production suivante:
(Cpi) debprodi - ifinconsi < ni
où ifinconsi est une copie locale à P i du compteur finconsi. Montrons que l’emploi de Cpi
comme condition de production est valide, c’est-à-dire que:
( i  debprodi - ifinconsi < ni)  debprod - fincons < n
Comme chaque contrôleur de production ne produit que si sa condition de production est
vraie, on a nécessairement debprodi - ifinconsi  ni pour tout i. Comme nous avons ifinconsi
 finconsi, s’il existe k te que Cpk soit vraie alors nous avons aussi:
 i  k, debprodi - finconsi  ni  debprodk - finconsk < nk

 (i k
debprodi + debprodk) - ( 
i k
finconsi + finconsk) < ( 
i k
ni + nk)
Etant donné que debprod =  debprodi, finconsi =  finconsi, n = ni cette dernière
condition s’écrit:
debprod - fincons < n
Nous venons de montrer que si un contrôleur de production trouve sa condition Cpi vraie
alors la condition globale de production est vraie. La réciproque n’est pas vraie: le tampon
peut contenir des entrées libres alors qu’aucun contrôleur de production n’a sa condition de
production vraie. La cause de ce problème est le décalage entre fincons i et ifinconsi, du fait du
retard dans la transmission. Ce problème a été déjà rencontré. De plus, en raison du caractère
 71
statique de l’allocation des places, un producteur peut épuiser son quota de places libres (et
donc voir sa condition de production devenir fausse), alors qu’il existe encore des places
libres dans le tampon, mais elles sont allouées à d’autres producteurs. L’allocation statique
offre par contre l’avantage d’augmenter le degré de parallélisme du système grâce à l’absence
de partage d’objet entre les producteurs. Ceux-ci n’ont pas à communiquer entre eux. Le
graphe des communications entre les processus du système est un graphe en étoile, le
contrôleur de consommation en occupant le centre.

3.7.1.1 Algorithme d’un contrôleur de production

Pi::
-- variables locales à Pi:
quota : entier positif ou nul -- variable contenant ni
debprod, cfincons : entier positif ou nul
-- initialisation :
C?allocation(quota) -- Réception du quota initial
debprod := 0
cfincons := 0
*[
-- Dialogue avec le producteur client; si le service ’transmettre une production au
-- consommateur’ est possible, il est effectué immédiatement:
debprod - cfincons < quota ; prodi?message  C!!message
debprod := debprod + 1
?
C?signal_fincons  cfincons := cfincons + 1
]

L’algorithme du consommateur utilise une fonction fournisseur qui prend en argument un

message et rend comme résultat l’identité du processus ayant émis ce message.

3.7.1.2 Algorithme du contrôleur de consommation

C::
-- Variables locales à C:
tampon : ...
debprod, cfinprod : entier positif ou nul
quota : entier positif ou nul
nbprivilégiés : 0..m-1 -- La division du nombre de places du tampon par le nombre
-- de producteurs donne un reliquat qui est réparti sur les nbprivilégiés premiers processus,
 72
-- qui reçoivent chacun une place supplémentaire.
-- initialisation
quota := n div m
nbprivilégiés := n mod m
debcons := 0
cfinprod := 0
-- Allocation d’un quota de places libres à chaque contrôleur de production
-- N.B. : [1..0] signifiera ici que cette instruction n’a aucun effet.
i  [1..nbprivilégiés];Pi!allocation(quota +1)
i  [nbprivilégiés +1..m];Pi!allocation(quota)
*[
--Si la condition de consommation est vraie alors consommer un message:
debcons - cfinprod < 0;!?Cons  debcons := debcons +1
<Extraire un message du tampon>
Cons!message
-- Signaler la consommation du message au producteur qui l’a émis, afin qu’il
-- puisse mettre à jour sa variable cfincons:
j := fournisseur(message)
Pj!!signal_fincons
?
-- Accepter tout message de production venant d’un contrôleur de production:
i  [1..m];Pi?message  cfinprod := cfinprod +1
<Ranger le message reçu dans le tampon>
]

Remarque:
L’absence de compétition entre les producteurs, le caractère statique de l’allocation du
tampon impliquent que l’équité de l’algorithme dépend uniquement de l’équité de
l’algorithme d’allocation statique. Nous avons choisi dans notre exemple un algorithme
d’équi-répartition.

3.7.2 Une solution mixte

Pour atténuer le caractère trop statique de l’algorithme que nous venons de voir nous devons
permettre aux places libres inutilisées de circuler entre les contrôleurs de production en leur
permettant de coopérer. Nous pouvons considérer que les algorithmes de répartition par
éclatement et les algorithmes de répartition par partage tels que ceux des parties 5 et 6
constituent deux politiques extrêmes: le tampon est partagé entre les producteurs, soit
 73
statiquement, soit dynamiquement. Si nous utilisons simultanément les deux techniques nous
pouvons à la fois améliorer le degré de parallélisme et rendre l’allocation moins statique.
Nous pouvons poser n = ns + nd où ns est le nombre de places du tampon gérées au moyen
de la technique d’éclatement de ressources (allocation statique) et nd est le nombre de places
gérées selon la technique vue à la partie 5. On définit:
ns = nsi ; fincons = finconsi + finconsd;
debprod = debprodsi + debprodd
L’algorithme d’allocation dynamique s’applique à un ensemble de producteurs
communiquant à l’aide d’un anneau. La condition de production du processus Pi s’écrit:
(Cpi) (condition de production dans le tampon alloué statiquement) (Cps)
 (condition de production dans le tampon dynamiquement) (Cpd)
C’est-à-dire:
(Cpi) (debprodsi - ifinconsi < nsi)  (rangi - ifinconsd  nd)
Afin d’augmenter le parallélisme, on utilisera de préférence le tampon alloué statiquement, dit
tampon local lorsque Cps et Cpd seront simultanément vraies; le consommateur consommera
de préférence dans le tampon local. Il n’y a pas d’interaction entre les deux techniques (pas de
variables partagées) donc la mise en parallèle des deux algorithmes est valide. Ceux-ci sont
tous deux équitables, l’algorithme résultant de la mise en parallèle l’est donc aussi.

3.7.3. Cas des pannes

Lorsqu’un site de production tombe en panne, son quota de places libres alloué statiquement
n’est plus utilisé. Pour remédier à ce défaut, on peut affecter ces places au tampon global
dynamique, ce qui permet de bien répartir entre les producteurs les entrées devenues
inutilisées. Lorsqu’un producteur quitte l’état de panne, il doit récupérer son quota de places
allouées statiquement. Pour ce faire, il doit acquérir des places libres du tampon global.
 74
Annexe
Architectures possibles du problème producteur-consommateur

1. site A site C

Prod Cons

site B

Tampon

Compteurs observables sur les sites:

site A : debprod
site B : finprod, fincons
site C : debcons
2.
site A site B
prod cons

tampon
Compteurs observables sur les sites:
Site A: debprod, finprod, fincons
Site B: debcons, cfinprod
75