Chapitre 6 : Terminaison
Pierre Gançarski*
Novembre 2003
Département d'informatique
UFR de Mathématique et Informatique
Université Louis Pasteur – Strasbourg
Table des matières
2 - Cas d'un
graphe en anneau uni-directionnel
2.1 - Principe de
l'algorithme (Dijstra et Van Gasten - 1983)
4.2 - Le principe
de l'algorithme de Misra (1983)
* Pierre.Gancarski@dpt-info.u-strasbg.fr
1 - Introduction
Soit un ensemble de n tâches
interdépendantes au sein d'une application. Ces n tâches
ou processus sont répartis sur une graphe de communication. Chaque processus en
cours d'exécution, exécute un algorithme séquentiel et échange des messages
avec les autres processus via le graphe de communication.
Le problème est le suivant : l'arrêt de tous les
processus correspond-il à l'arrêt définitif de l'application ou n'est-ce qu'un
état transitoire? (c'est-à-dire un message peut être en transit et provoquer le
redémarrage d'un, puis de tous les processus) ?
Définitions
-
Un processus est soit actif soit inactif : il est actif
s'il exécute du code, il est inactif s'il n'a rien à faire;
-
Seuls les processus actifs peuvent envoyer des messages ;
-
Un processus ne peut passer d'un état inactif à un état
actif que sur réception d'un message : à tout message correspond du code a
exécuter. Par contre, il peut passer de l'état actif à inactif à tout moment
(il a fini son code) ;
-
Tous les processus sont actifs au lancement de
l'application.
Un deuxième problème auquel nous ne nous intéresserons
pas, c'est de savoir si les processus ont "bien terminés"
c'est-à-dire de savoir si le résultat est satisfaisant localement (chaque
processus a bien fait le calcul prévu : cette estimation est en général faite
par le processus lui-même) et globalement (le résultat global est bien le
résultat recherché).
Hypothèses
-
Tout processus qui ne reçoit plus de message se termine
dans un temps fini.
-
Le réseau est FIFO
2 - Cas d'un graphe en anneau uni-directionnel
Les processus sont "ordonnés" sur le réseau par
ordre croissant de leur numéro.
2.1 - Principe
de l'algorithme (Dijstra et Van Gasten - 1983)
On utilise un jeton à deux états Termine ou État_Transitoire. Le
processus Po qui veut déterminer si l'application est
terminée, émet le jeton dans l'état Terminé. Si
celui-ci lui revient dans le même état, l'application est terminée. Sinon (donc
le jeton revient dans l'état État _Transitoire), il faut relancer la
détection de la terminaison.
2.2 - L'algorithme
Chaque processus Pi maintient les deux variables locales
suivantes
-
couleur i = Blanc
ou Noir initialisé à Blanc
-
etat i = Actif ou Inactif initialisé à Actif
Initialement, le jeton est à l'état Terminé en Po qui lance la détection dès que
son état passe à Inactif en transmettant
le jeton à P1
- État du
processus et transmission du jeton
Lorsque Pi reçoit un message, il passe à
l'état Actif
Un processus Actif ne
transmet pas le jeton, il le transmettra dès qu'il deviendra inactif.
Lorsqu'il a fini de calculer, il passe à l'état Inactif.
Lorsqu'il envoie un message vers un processus Pj tel que
j < i, il passe à l'état Noir.
Pourquoi ?
Parce qu'il se peut que le processus Pj soit
ré-activé par ce message APRÈS que Pj ait transmis le jeton à l'état État_Transitoire. Donc,
si Pi transmet un jeton Termine et que tous les processus Pk>i
sont inactifs, alors le jeton arrivera en Po dans l'état Termine. Donc
si Pi se contentait de transmettre le jeton en signalant qu'il est
inactif, rien ne préviendrait Po du réveil de Pj. D'où lorsque Pi recevra
le jeton, dès qu'il sera inactif, il transmettra le jeton dans l'état Etat_Transitoire (en
fait, cela revient à ce que Pi demande un nouveau tour). Puis il pourra
repasser à Blanc.
D'où, un processus Inactif
transmet le jeton d'état
-
identique à l'état du jeton reçu si il est dans l'état Blanc
- Etat_Transitoire si il est dans l'état Noir, puis passe à l'état Blanc.
- Détection
de la terminaison
Si le jeton revient en Po avec l'état
-
Terminé alors FIN : Terminaison Détectée.
-
Etat_Transitoire ou si Po
est actif, alors dès que Po redevient inactif, il remet le jeton à l'état Terminé et
devient Blanc. Puis il relance la détection en transmettant le
jeton à P1.
3 - Cas d'un arbre couvrant
Rappel : lorsque l'on est en phase
d'initialisation des calculs, seuls les pères peuvent transmettre des demandes
vers les fils directs.
|
Pour un sommet Pi de l'arborescence, posons
etat i,local (Pi)= |
1 si Pi a
fini son code |
et Dp; ensemble des |
|
0 sinon |
descendant de Pi à qui Pi a transmis une demande.
Soit etat i(Pj) la vision qu'a le processus Pi
de l'état du processus Pj
|
Alors etat i (Pi) = |
etat i,local
(Pi) si Di=0 |
|
etat i,local
(Pi) x PPj Î Di etat
i (Pj) sinon |
Lorsque l'on est en phase de calcul : tous les calculs ont été initiés, il suffit alors que chaque processus transmette la vision de son état dès que celui-ci est égal à 1, pour qu'un noeud puisse calculer son état. D'où
En phase d'initialisation
-
etato(Po) = 0
-
chaque fois qu'un message part d'un processus Pi vers
un fils Pj
Pi remet
tati (Pj) à 01,
Di = Di U { j } puis Pi "attend" l'état de Pj pour
recalculer son propre état ;
Pi
remet etatj,local(Pj) et etatj(Pj) à 0, passe à l'état
Actif et exécute son code.
En phase de détection
-
dès que etati4o(Pi4o) = 1, Pi transmet 1 à son
père
-
dès que etato(Po) = 1, l'application est terminée.
4 - Cas général
4.1 - Introduction
On suppose que le le graphe de communication est
fortement connexe (c'est-à-dire que tout processus Pi peut envoyer un message à
tout Po<j¹i<n
: pas nécessairement directement mais en passant
éventuellement en passant
d'autres processus). Dans ce cas, la théorie des graphes
nous assure qu'il existe un circuit2 C qui
comprend chaque noeud (au moins une fois) du graphe du réseau.
On va utiliser un jeton pour trouver le nombre nb de
processus visités suivant le circuit C qui soient restés inactifs entre deux
passages de ce jeton.
Il est donc évident que l'application sera terminée
lorsque nb = taille(C), où taille(C) est la taille du circuit en nombre
de visites de processus (peut être supérieur à n car on peut passer
plusieurs fois par un même processus).
Exemples
On trouvera par exemple pour l'exemple de gauche taille(C)
= 9, alors que celui de droite nous donne, par exemple, taille(C) = 8
4.2 - Le
principe de l'algorithme de Misra (1983)
Posons
- succ(Pi) successeur de Pi donné par le
circuit3 C
- Pour chaque processus Pi les quatre variables locales
suivantes :
-
couleuri =
Blanc ou Noir initialisé à Blanc
-
etati = Actif
ou Inactif initialisé à Actif
-
jeton_presenti = Vrai ou Faux initialisé à Faux sauf pour Pk,
k choisi aléatoirement
-
nbi = entier initialisé à 0
- État
d'un processus
- Lorsque Pi reçoit
un message, il passe à l'état actif par : etati = Actif
- Chaque fois qu'il envoie un message, il mémorise ce
fait par : couleuri = Noir. Ainsi, indirectement,
il mémorise qu'il est possible qu'il ait réveillé un processus.
- Lorsqu'il a fini de calculer, il passe à l'état inactif
par : etati = Inactif
- Lorsqu'il reçoit le jeton, il effectue : nbi = nb et
jet on_presenti = Vrai
puis
s'il est Inactif :
- soit il
détecte la terminaison : FIN
- soit
il doit retransmettre le jeton
s'il est Actif : il ne le
transmettra que lorsqu'il redeviendra inactif.
- Transmission
du jeton
Si Pi est Inactif (ou si Pi passe à Inactif)
avec jeton presenti = Vrai alors
/* Pi transmet le jeton */
si couleuri = Noir4
alors /*on recommence la
détection */
nbi = 1
sinon /* on
incrémente le nombre de processus inactifs déjà visité */
nbi=nbi+1
couleuri = Blanc
jeton_presenti = Faux envoyer(jeton,
nb = nbi) à succ(Pi)
- Détection
de la terminaison
si nb = taille(C) et couleuri = Blanc alors Terminaison
Détectée