Architecture Logique des Systèmes Distribués M. & Z.

ALIOUAT 47

Gestion d’un parking de stationnement de véhicules

On considère un parking d’automobiles à N places de stationnement, où les voitures,

représentant des processus, sont en compétition pour l’accès à des places (ressources) de
parking.
Chaque processus Pi i  [1, P] peut être représenté par les événements suivants: E : Entrée,
P:parking, S:sortie.
Une expression abstraite de synchronisation du système est:
Le nombre de places libres NBPLIBRES dans le parking doit être toujours tel que : 0 
NBPLIBRES  N. Autrement dit, NBPLIBRES = N - aut(E) + term(S) où aut(E) = nombre de
franchissement de E ou compteur d’événement E et term(S) = nombre de franchissement de S
ou compteur événements S. Les Points de Synchronisation(PdS) du système sont l’entrée e dans
le parking et la sortie s. Si on note #E = aut(E) et #S = term(S), on a alors :
NBPLIBRES = N - #E + #S
d’où 0  N - #E + #S, on peut écrire: #E - #S  N (1) : Expression abstraite du problème.
Pour mettre en œuvre (1), on enregistre les compteurs #E et #S dans les variables respectives E
et S. Le contrôleur de synchronisation (gardien) doit respectivement effectuer, aux points de
synchronisation e et s, les actions suivantes:
i : attendre E - S < N; faire E := E + 1
ii : S := S + 1
Lorsque plusieurs processus arrivent simultanément au point e, le contrôleur doit garantir la
cohérence des opérations i en imposant leur exécution en exclusion mutuelle. Il en sera
également de même, et pour les mêmes raisons, pour le point s. On remarquera que les
opérations en i et ii sont indépendantes d’ou la possibilité de les exécuter de manière simultanée.
Autrement dit, les accès en entrées et les accès en sorties (du parking) des véhicules peuvent se
faire en parallèle.
On remarquera également que si on s’intéresse au nombre de places libres dans le parking
représenté par l’expression NPLIBRES = N - E + S, les accès en entrée et en sortie ne peuvent
plus se réaliser simultanément, puisque les actions du contrôleur deviendraient:
iii : attendre NPLIBRES > 0; faire NPLIBRES := Y - 1
iv : NPLIBRES := NPLIBRES + 1
Les actions iii et iv précédentes doivent donc être sérialisées, c’est à dire que l’exclusion
mutuelle doit porter sur l’ensemble des opérations effectuées aux PdS e et s.

On constate que la mise en œuvre du problème dépend étroitement de la spécification (modèle)

de départ. Dans le cas qui nous concerne, on peut représenter le contrôleur des actions iii et iv
par un processus qui est appelé par les processus véhicules pour exécuter ces actions une seule à
la fois (exclusion mutuelle). Par contre, le contrôleur qui se chargerait des actions i et ii peut
être constitué de deux contrôleurs indépendants l’un sérialisant les actions i et l’autre les actions
ii. Naturellement, ils doivent coopérer puisqu’ils se partagent la variable S.
 Architecture Logique des Systèmes Distribués M. & Z. ALIOUAT 47

Mise en oeuvre
Si on considère un environnement centralisé, les événements E et S seront enregistrés dans les
variables E et S ou bien dans la variable NPLIBRES.
Exemple d’implémentation à l’aide de moniteurs.
[Link] E
begin
var nplibres : integer; S
condition attendre; Parking fig. 1
procedure entrer
begin
if nplibres  0 then wait(attendre);
nplibres : nplibres – 1;
end
procedure sortir
begin
nplibres := nplibres + 1;
signal (attendre);
end
% Initialisation %
nplibres := N;
endmonitor

program main
parbegin
entrer, sortir ....
parend
Remarque : L’exclusion mutuelle des procédures entrer et sortir impliquent que les véhicules
ne peuvent entrer et sortir simultanément par le même accès.
On peut souhaiter la solution avec un modèle qui se prête mieux à des accès distincts en entrée
et sortie, solution qu’on peut adapter à un environnement distribué.
[Link]
begin
var E, S : integer;
condition attendre;
procedure entrer
begin
if E – S ≥ N then wait(attendre)
endif
E := E + 1
 Architecture Logique des Systèmes Distribués M. & Z. ALIOUAT 47
end
procedure sortir
begin
S := S + 1;
Signal (attendre);
end
% Initialisation %
N := max, E := S:= 0;
endmonitor

A l’aide des modules de contrôle:

[Link]
begin
procedure sortir;
procedure entrer;
queue sortir/entrer;
condition(entrer): act(entrer) act(sortir) = 0
and aut(entrer) - term(sortir) < N;
condition(sortir): act(sortir) + act(entrer) = 0;
endmdc
Mise en oeuvre en environnement réparti:
Considérons deux issues désignées respectivement site e et site s
Les événements e (entrée) et s (sortie) ne sont pas observables sur les deux sites. Pour mettre en
oeuvre l’expression abstraite (1), on
peut envisager deux solutions possibles:
- Le contrôle est centralisé (approche à décision E S
centralisée dans un environnement réparti).
Cette solution évidente, consiste à mettre dans un site les
variables et le code nécessaire à la synchronisation. Parking fig.2
Le contrôle est alors réalisé par un processus contrôleur unique, auquel les autres processus
localisés sur les autres sites (site e et s par exemple) envoient des messages (demande d’entrée et
demande de sortie). On retrouve alors une situation identique à celle d’un système centralisé.

Faiblesse de la solution: La fiabilité du système repose sur celle du processus contrôleur.

Si une panne affecte ce dernier, soit que le système s’arrête, soit des mesures de reprise ont été
prévues, il y a lieu alors de reconfigurer le système (désigner un autre contrôleur).
Manque de parallélisme d’où attente éventuelle à l’entrée comme à la sortie.

- Le contrôle est distribué:

Dans ce cas, il faut répartir le contrôle sur M sites, ce qui revient à considérer M processus
 Architecture Logique des Systèmes Distribués M. & Z. ALIOUAT 44
contrôleurs, un sur chaque site. Trois types de solutions sont alors examinés:
1. Répartition des variables de l’expression abstraite de synchronisation entre les contrôleurs.
2. Décomposition de ces variables en M composantes (une composante sur chaque site).
3. Duplication des variables (un exemplaire sur chaque site) et en assurer la cohérence.

a) Répartition des variables.

Considérons un parking à deux accès: un accès en entrée site 1 et l’autre en sortie site 2 (figure
2.). Un contrôleur (gardien 1) de l’accès du site 1 comptabilise les entrées E de véhicules sur
son site, un autre contrôleur comptabilise les sorties S de son site 2. Pour autoriser un véhicule à
entrer dans le parking, le gardien 1 doit d’abord vérifier l’expression:
E - S < N (2)
Il connaît exactement la valeur de E, mais la valeur de S qui se trouve sur le site 2 n’est connue
que du gardien 2. Il peut alors la lui transmettre pour permettre l’évaluation de (2). Compte tenu
des délais (non nuls) de transmission, le gardien 1 recevra une valeur de S en retard par rapport à
la valeur courante. Cette valeur S’est une image retardée de S.
Le gardien 1 ne peut donc évaluer que l’expression: E - S’ < N (3)
Or, on a: S’S, on peut donc affirmer que si (3) est vérifiée, (1) l’est aussi.
Le comportement du gardien 1 sera:
cycle Attendre S’, si E - S’ < N alors E := E + 1 (autoriser un accès) finsi fcycle
Les actions du gardien 2 seraient:
cycle attendre une demande de sortie faire S := S +1, envoyer (S) fcycle

b) Décomposition d’une variable

Admettons que le parking comporte M accès fonctionnant tous en entrée/sortie. On peut écrire:
E = E1 + E2 + ....... Em-1 + Em
S = S1 + S2 + .... Sm-1 + Sm
Les Ei et Si représentent le nombre d’entrée et de sortie de véhicules enregistrées sur le site i
par le gardien N° i. La résolution du problème nécessite alors la gestion de 2m compteurs.
Chaque site i ne connaissant que deux compteurs Ei et Si, il a besoin, pour vérifier l’expression
de synchronisation, de se faire envoyer par les autres sites les 2m-2 compteurs restants. Cela
représenterait un flux de messages important qui pourrait nuire à la fluidité des communications.

Une autre façon de résoudre le problème consisterait à distribuer les places de stationnement
entre les différents contrôleurs: chaque contrôleur i disposerait d’un nombre de places libres à
gérer qu’on appelle un crédit Ci. Durant l’évolution du système, la répartition initiale de places
libres se modifie, et certains gardiens peuvent amenés à refuser des accès dans le « parking
virtuel » qu’il gère, alors qu’il puisse exister des places libres ailleurs (chez d’autres gardiens).
Pour affaiblir cet inconvénient, on peut procéder à une redistribution périodique de crédits. Cela
consiste à ce que chaque gardien i envoie périodiquement à son successeur gardien (i+1)mod m
un crédit Ni. On a initialement le nombre de places libres:
 Architecture Logique des Systèmes Distribués M. & Z. ALIOUAT 47
Y =  Yi = N (4)
et on a constamment: Y = N - E + S = (Yi + Ni) (5)
Le gardien N°i, avant de transmettre un crédit Ni à son successeur, diminue son quota Yi de Ni
places. Lorsque le message qui transporte le crédit Ni arrive au gardien N° j, celui-ci augmente
son quota de places libres de Ni par : Yj := Yj + Ni
Lorsqu’un véhicule arrive à l’accès N°i, le gardien l’autorise à y entrer si Yi > 0; dans le cas
contraire, il doit attendre l’un des deux événements suivants:
˗ Sortie d’un véhicule de l’accès i et Yi devient Yi:= Yi + 1,
˗ Arrivée d’un message transportant un crédit Nk émis par le voisin K:= (i-1) mod m, et Yi
devient Yi:= Yi + Nk.²

Maintien de la cohérence d’une variable partagée

Les gardiens du parking peuvent coopérer en utilisant de manière exclusive la variable Y
représentant le nombre de places libres. Une solution simple consiste à organiser les différents
gardiens en anneau virtuel : chaque gardien j est alors relié à son prédécesseur immédiat (i-
1)mod m qui lui transmet les messages, et son successeur immédiat k=(i+1) mod m auquel il en
envoie. Un agent circulant sur l’anneau allant de gardien à gardien et transportant la valeur de Y.
Lorsque l’agent arrive au niveau d’un accès i où attend un véhicule, avec une valeur de Y > 0, le
gardien i laisse alors entrer un véhicule et met à jour Y par Y : = Y – 1
Les sorties des véhicules devraient se faire en présence de l’agent circulant et sa variable Y.
Toutefois, le gardien peut autoriser les véhicules à sortir et mémoriser le nombre de sorties S
qui sera utilisé pour mettre à jour Y (Y : = Y + S) lorsque l’agent sera présent.
Cette solution simple qui garantit la cohérence de la variable Y comporte certains inconvénients
en particulier :
- Manque de parallélisme, puisque les entrées ne se feront qu’au niveau d’un accès à la fois -
et en présence de l’agent et de sa variable Y
- La vitesse à laquelle s’effectueront les entrées, dépend de la vitesse de circulation de l’agent
sur l’anneau.
- Lorsque l’agent circulant disparaît, il faut pouvoir le remplacer. L’agent représente ici le
jeton circulant, et en cas de perte il faut le régénérer.
- Possibilité de famine : l’ordre d’entrer dans le parking est défini par l’agent et est différent
de l’ordre d’arrivée des véhicules aux différents accès. Si l’agent arrive toujours au niveau
d’un accès de N° i avec Y = 0, les véhicules en attente dans cet accès risquent d’attendre
indéfiniment. Pour éviter cette privation, il faut que les entrées des véhicules se fassent selon
un certain ordre strict global. Cet ordre sera réalisé en utilisant le mécanisme d’estampillage
et servira à garantir l’exclusion mutuelle de l’utilisation de Y. Ainsi, chaque véhicule
arrivant devant un accès (en entrée ou sortie) sera muni d’une estampille. Il n’est plus alors
utile de faire circuler un agent pour transporter l’exemplaire unique de Y pour en assurer la
cohérence. Un protocole de communication entre gardiens est nécessaire de sorte que le
gardien de N° I+1 sache que le gardien de N°I a terminé. Pour ce faire, on peut utiliser un
Architecture Logique des Systèmes Distribués M. & Z. ALIOUAT 47
protocole à diffusion, et la variable Y se trouve dupliquée sur chaque site. Dés qu’un accès
est autorisé, le gardien diffuse à tous les autres le rang du véhicule et l’opération effectuée
sur Y. Le gardien ayant le N° d’ordre suivant serait alors autorisé à effectuer une opération.
Pour les opérations de sorties peuvent ne pas être ordonnées : à chaque demande de sortie,
un gardien laisse le véhicule quitter le parking et diffuser à tous les sites l’opération :
Incrémenter Y (faire Y := Y+1)
Les exemplaires de la variable Y n’ont pas exactement la même valeur mais ils restent
cohérents. Si un gardien N°I autorise l’entrée d’un véhicule, parce que c’est son tour, il met
à jour sa variable Yi : Yi := Yi – 1 et diffuse le message (décrémenter, n° d’ordre). Au
même moment, un autre gardien N° j a pu laisser sortir un véhicule et a fait : Incrémenter
Yj, diffuser un message (incrémenter).
Dans ce cas, Yi aura subie successivement une décrémentation et une incrémentation ; pour
Yj ce sera l’inverse. Les autres exemplaires de Y auront subits soit une incrémentation soit
une décrémentation. Ces deux opérations étant commutatives, il n’est pas obligatoire de les
ordonnées, mais ce n’est pas toujours vrai.