Synchronisation des processus
Correction
2ième Année Informatique et Mathématiques Appliquées
Novembre 2001
1 Exclusion mutuelle
On considère le problème de l'exclusion mutuelle dans le contexte
d'une architecture multi-processeurs. On suppose que chaque processeur peut exécuter
une instruction atomique inc(x) qui renvoie la valeur courante
de la variable x et incrémente ensuite celle-ci de façon indivisible.
Soit sous forme d'un triplet de Hoare :
{ S=k } x = inc(S) { x=k /\ S=k+1 }
On suppose que le nombre de processus existant en parallèle ne peut
dépasser une borne fixée N.
Pour l'algorithme des opérations Entrer et
Sortir, on propose d'utiliser un compteur (appelé séquenceur)
global S de type entier
et une variable globale Gagnant de type entier :
int S = 0 ; Gagnant = 0 ;
Le principe de la solution consiste à autoriser le processus qui possède le numéro
gagnant à entrer en exclusion. L'algorithme de l'opération Entrer
est donc le suivant :
int Entrer() {
int monTour = inc(S) ;
while ( monTour != Gagnant ) do { } ;
return (monTour) ;
}
Questions - Réponses
-
Préciser l'invariant garanti par cette solution et sur lequel repose
la propriété d'exclusion mutuelle.
Réponse
La propriété d'exclusion mutuelle repose sur le fait que la variable
séquenceur fournit, à chaque requête d'entrée, un numéro différent, ce qui
peut s'exprimer par :
invariant pour tout i,j :1..N :: Pi.monTour = Pj.monTour => i=j
- Donner l'algorithme de l'opération Sortir.
Réponse
Les numéros fournis par la variable séquenceur
étant consécutifs, la primitive Sortir consiste simplement à incrémenter
la variable globale Gagnant. Une exception est levée en cas d'appel erroné
(appel de la part d'un processus qui n'est pas celui en exclusion mutuelle).
void Sortir(int monTour) throws SortieErronée {
if (monTour != Gagnant) throw SortieErronée ;
Gagnant += 1 ;
}
On remarquera qu'il n'est pas nécessaire d'utiliser l'instruction inc
puisque la primitive Sortir ne peut être exécutée que par un seul processus
à la fois, celui en exclusion mutuelle.
- Le compteur S croît indéfiniment. Trouver une solution
utilisant un séquenceur borné.
Réponse
L'instruction inc incrémente un mot mémoire de taille finie définissant
un intervalle [0..2p[. Une incrémentation de la valeur maximale provoque
un débordement et l'on peut alors assurer au niveau matériel l'écriture
de la valeur 0. En masquant le débordement, on a alors un compteur « modulo »
2p. En général, p vaut 16 ou 32 bits, soit une valeur nettement supérieure
au nombre maximum de processus. On a donc bien N < 2p. On peut donc
utiliser un tel compteur borné. La primitive Sortir doit
bien entendu compter aussi modulo 2p. On préfère dans ce cas éviter
d'avoir recours au masquage du débordement en programmant explicitement
le comptage modulo 2p.
void Sortir(int monTour) throws SortieErronée {
if (monTour != Gagnant) throw SortieErronée ;
if (Gagnant == Integer.MAX_VALUE) Gagnant = 0 ;
else Gagnant += 1 ;
}
Attention :
Une telle approche pour compter modulo 2p avec la
variable S ne peut être
utilisée car la non atomicité de la lecture (du test) et de l'écriture ne garantit
plus l'unicité des numéros obtenus. Qui plus est, l'accès en parallèle par plusieurs
processus en lecture/écriture à la variable S ne garantit même plus que la valeur lue soit
la dernière valeur écrite.
2 Mécanisme de sémaphore
Un sémaphore est utilisé comme compteur de ressources critiques réutilisables.
Un processus ayant exécuté plusieurs opérations P pour obtenir
des ressources s'arrête inopinément (pour cause de déroutement par exemple).
Questions - Réponses
-
Quelle est la conséquence de cet événement
sur le schéma d'allocation des ressources ?
Réponse
Les ressources que le processus a obtenu grâce aux opérations P
ne seront pas libérées grâce aux opérations correspondantes V
qu'aurait dû exécuter le processus. Par conséquent, ces ressources vont
rester inaccessibles aux autres processus.
- Proposer une solution pour éviter cette anomalie. On supposera
qu'un traitement spécifique peut être exécuté par le noyau de gestion
des processus lors de la terminaison anormale du processus.
Réponse
Une ressource critique ne pouvant être utilisée que par un seul processus,
on suppose que chaque ressource allouée pointe le sémaphore qui la gère.
Si l'on conserve une liste des ressources allouées aux processus (dans
le descripteur de ce processus), le noyau peut alors parcourir
la liste des ressources allouées et pour chaqu'une d'elle obtenir
le nom du sémaphore. Une opération V peut alors être exécutée
forçant ainsi la libération de la ressource.
3 Moniteurs de Hoare : Groupes de processus
On considère un système de processus parallèles qui accèdent durant leur
exécution à une ressource commune. Les processus sont répartis dans
des groupes numérotés de 1 à N et tout processus appartient au moins à un groupe. À titre
d'exemple, le système peut se composer de 5 processus répartis dans
3 groupes selon le schéma suivant :
g1 = {p1,p3,p5}, g2 = {p2,p4}, g3 = {p1,p2, p3}
La modélisation des processus peut se faire de façon classique en distinguant
3 états caractéristiques, tout processus pouvant exécuter de façon
répétitive les transitions suivantes :
-
De l'état passif, un processus peut passer dans l'état
demandeur[g] lorsqu'il souhaite accéder à la ressource en tant que membre d'un groupe g;
- De l'état demandeur[g], il entrera dans l'état utilisateur[g]
lorsque le droit d'accès lui aura été accordé au titre d'utilisateur appartenant au groupe g;
- De l'état utilisateur[g], il retournera dans l'état passif
lorsqu'il libérera l'accès à la ressource.
La figure (1) illustre le graphe de transitions modélisant
ce comportement des processus.
Figure 1 : Graphe de transitions des processus
Pour désigner les attributs d'un processus, on utilise la notation pointée Pi.attr.
Par exemple, Pi.etat désignera l'état courant du processus.
On utilisera le prédicat Pi.u[g] identique à (Pi.etat=utilisateur[g]).
Synchronisation
La ressource commune peut être accédée par les processus à condition de vérifier la propriété
de sûreté suivante :
Exclusivité de groupe
À tout instant, la ressource ne peut être utilisée
que par les processus d'un même groupe courant, avec pour conséquence, qu'un processus ne peut utiliser
simultanément la ressource en tant que membre de deux groupes différents.
invariant pour tout i,j :: Pi.u[g] /\ Pj.u[g'] => g = g'
Pour garantir cette propriété, tout accès à la ressource nécessite de passer par le protocole suivant :
processus P[i] {
... ;
Exclusivité.Obtenir(g) ;
/* utiliser la ressource en tant que membre du groupe g */
Exclusivité.Libérer() ;
...
}
On se propose de garantir la règle d'exclusivité de groupe en implantant les
opérations Obtenir(groupe g) et Libérer() dans un moniteur de Hoare.
L'interface de ce moniteur est la suivante :
moniteur Exclusivité {
/* obtenir le droit d'accès */
void Obtenir ( int g ) ;
/* libérer l'accès */
void Libérer () ;
}
On introduit les variables d'état (en précisant leur valeur initiale) et conditions suivantes :
-
int np = 0 : compte le nombre de processus utilisant la ressource au titre
du groupe courant ;
- int gc = 0 : indique le groupe courant utilisateur si (gc != 0) ;
- condition accès[1..N] : un tableau de N variables conditions.
On propose la solution suivante pour l'opération Obtenir(int g) :
void Obtenir( int g) {
if (g != gc) wait(accès[g]) ;
if (np == 0) gc = g ;
np += 1 ;
signal(accès[g]) ;
}
Questions - Réponses
-
Corriger la condition de blocage de l'opération Obtenir(int g),
celle proposée étant fausse ;
Réponse
L'opération Obtenir est non bloquante si la ressource est libre ou
si le groupe demandeur appartient au groupe courant possédant la ressource.
Cette précondition s'exprime donc par :
Pre(Obtenir) = (np = 0) \/ (g = gc)
La condition de blocage est donc :
Pre(Obtenir) = (np > 0) /\ (g != gc)
On remplace donc la première instruction conditionnelle par :
if ((np > 0) && ((g != gc)) wait(accès[g]) ;
Autre bonne solution :
Découpler l'évaluation des deux termes
du prédicat :
void Obtenir( int g) {
if (np == 0) gc = g ; /* test ressource libre */
/* gc != 0 */
if (g != gc) wait(accès[g]) ;
/* gc != 0 /\ g =gc */
np +=1 ;
signal(accès[g]) ;
}
Attention toutefois au fait que, dans cette solution, la mise-à-jour
de la variable gc lors de l'allocation de la ressource à un nouveau
groupe sera à la charge de l'opération Liberer.
- Justifier l'occurrence de l'instruction signal(accès[g])
dans l'opération. Préciser son rôle ;
Réponse
Il s'agit d'assurer le réveil en chaîne des processus d'un même
groupe bloqués en attente de la libération de la ressource. En effet, l'opération
Libérer ne peut que réveiller le processus en tête de file d'attente
de la variable condition. Or, tous les processus du groupe élu doivent être
réactivés.
- Montrer que la solution présente un risque de famine et
proposer une modification pour éviter ce risque ;
Réponse
Cette solution pour la primitive Obtenir peut conduire à la monopolisation
de la ressource par un groupe. En effet, lorsqu'un groupe possède l'accès
à la ressource, il peut garder ce droit indéfiniment si en permanence au moins un des processus
du groupe utilise la ressource. Cette situation de monopole par un groupe provoque la famine
des autres groupes. Une solution consiste à bloquer les processus du groupe courant
dès qu'il existe au moins un processus en attente appartenant à un autre groupe.
Pour tester cette condition, on introduit la fonction int suivant(g) qui teste s'il existe un groupe
suivant en attente. Si un tel groupe existe, la fonction renvoie le numéro du groupe
en attente. Sinon, par défaut, la fonction renvoie le groupe courant qui
lui avait été passé en paramètre. Autrement dit, la fonction évalue le prédicat :
suivant(g) = g if pour tout gc != g :: empty(acces[gc]) ~ gc if il existe gc != g :: ¬ empty(acces[gc])
L'opération Obtenir s'écrit alors :
void Obtenir( int g) {
if (np == 0) gc = g ; /* test ressource libre */
/* gc != 0 */
if (g != gc || suivant(g) != g) wait(accès[g]) ;
/* gc != 0 /\ g =gc */
np +=1 ;
signal(accès[g]) ;
}
- Lors de la libération de la ressource par le dernier utilisateur du groupe
courant, la ressource devenue libre de tout groupe peut être allouée à un autre
groupe « demandeur ». Proposer une stratégie de choix parmi les groupes demandeurs
de façon à éviter tout risque de famine ;
Réponse
Il s'agit ici d'un deuxième type de famine par coalition d'au moins deux groupes.
À titre d'exemple, si la ressource libérée est toujours allouée au groupe en attente de plus petit numéro, il suffit
qu'un ensemble d'au moins deux groupes ayant des « petits numéros » se coalise pour empêcher
les autres groupes d'accéder à la ressource. On remarquera que le premier type
de famine traite le cas de la coalition d'un ensemble de groupes réduit à un élément.
Pour éviter un tel phénomène, il faut donc
assurer une équité dans le choix du groupe suivant lorsque la ressource est libérée.
Pour cela, lorsque le groupe g libère la ressource, on cherche
un groupe comportant au moins un processus en attente par scrutation modulo N
des variables conditions (files d'attente) en commençant par le numéro g%N + 1
où % dénote l'opérateur modulo.
- Implanter cette stratégie en programmant l'opération Libérer().
Pour implanter la recherche du nouveau groupe, on peut utiliser une implantation
de la fonction suivant utilisée dans l'opération Obtenir. Il suffit que celle-ci respecte le
principe de recherche énoncé dans la question précédente. Une implantation possible est par exemple :
int suivant(int g) {
boolean vide = true ; int i = 1 ;
/* Pré : g=g0 /\ vide /\ i=1 */
/* Invariant : pour tout i appartient à ]g0..g[ :: empty(acces[i]) */
while (vide && i <= N) {
g = g%N + 1 ; vide = empty(accès[g]) ;
if (vide) i += 1 ;
} ;
return (g) ;
/* Post : g=g0 => pour tout i!= g0 :: empty(acces[i]) */
/* /\ g!=g0 => ¬ empty(acces[g]) */
}
À l'aide d'une telle fonction, l'opération de libération (commutation) de groupe peut
être facilemnt implantée :
void Liberer() {
np -=1 ;
if (np ==0) ; { /* la ressource est libre */
/* recherche d'un nouveau groupe non vide */
gc = suivant(gc) ;
/* empty(acces[gc]) => pour tout g:1..N :: empty(acces[g]) */
if (empty(accès[gc])) gc = 0 ; else signal(accès[gc]) ;
}
}
Une solution complète
En réalité, on peut encore simplifier la solution en remarquant que le compte
des processus ayant accès à la ressource suffit pour tester la condition « ressource
libre ». On peut alors numéroter les groupes de 0 à N-1 et éviter la remise
à zéro de gc lorsque la ressource est libre. On obtient :
monitor Exclusivité {
static final int N = ... ;
int np = 0 ; /* nombre de processus ayant obtenus l'accès */
int gc = 0 ; /* groupe courant si la ressource est occupée */
condition accès[N] ; /* numérotation des groupes de 0 à N-1 */
int suivant(int g) {
boolean vide = true ; int i = 1 ;
/* Pré : g=g0 /\ vide /\ i=1 */
/* Invariant : pour tout i appartient à ]g0..g[ :: empty(acces[i]) */
while (vide && i <= N) {
g = g%N ; vide = empty(accès[g]) ;
if (vide) i += 1 ;
} ;
return (g) ;
/* Post : g=g0 => pour tout i!=g0 :: empty(acces[i]) */
/* /\ g!=g0 => ¬ empty(acces[g]) */
}
void Obtenir( int g) {
if (np == 0) gc = g ; /* test ressource libre */
if (g != gc || suivant(g) != g) wait(accès[g]) ;
/* g =gc */
np +=1 ;
signal(accès[g]) ;
}
void Liberer() {
np -=1 ;
if (np ==0) { /* la ressource est libre */
/* recherche d'un nouveau groupe non vide */
gc = suivant(gc) ;
/* empty(acces[gc]) => pour tout g:1..N :: empty(acces[g]) */
if ( ! empty(accès[gc])) signal(accès[gc]) ;
}
}
}
Ce document a été traduit de LATEX par
HEVEA.
