Chapitre 4 : Synchronisation entre processus


Algorithme 3 : Peterson 81

Les sections précédentes ont montré les difficultés du problème de la section critique. En effet, en plus de la réalisation mutuelle, une solution valide doit garantir :


La dernière condition permet d’assurer une certaine équité entre les processus. Quand un processus est en attente de sa section critique, il existe une borne supérieure au nombre de fois où d’autres processus exécutent leur section critique. Il faut interdire aux processus d’exécuter itérativement leur section critique en laissant un processus attendre pendant une durée arbitrairement longue l’entrée dans sa propre section critique.

En 1981 une solution a été proposée. Nous allons l’étudier pour le cas de deux processus.

Le principe de cette solution consiste en quelque sorte à combiner les deux tentatives précédentes (algorithme 1 et algorithme 2) afin de combiner leurs avantages. Ainsi, les deux processus partagent :
Ces variables ont les mêmes rôles que précédemment. La variable tour permet d’éviter l’interblocage, et les 2 variables booléennes D1 et D2 permettent d’assurer la progression. Donc, un processus Pi n’aura pas le droit d’entrer dans sa section critique uniquement quand l’autre processus Pj a demandé à entrer dans sa section critique et en plus c’est le tour de ce deuxième processus de passer.

Donc, un processus Pi désirant entrer dans sa section critique, commence par lever son drapeau (affecte à Di la valeur «vrai ») et cède immédiatement son tour à l’autre (affecte à tour la valeur j). Puis, il tente d’entrer dans sa section critique. Ce processus doit être bloqué si l’autre processus, Pj, a fait déjà aussi sa demande (c’est à dire Dj== Vrai) et en plus c’est le tour de Pj de passer (tour == J).

A sa sortie de sa section critique, le processus Pi doit tout simplement baisser son drapeau (c’est à dire affecter à Di la valeur «Faux »)

Les deux sections de ce protocole se définissent alors de la manière suivante :

Prologue (section d’entrée du processus i ) :
Di = vrai ;
Tour = J ;
While (Dj et tour ==j ) ; /*attendre*/


Epilogue (section d’entrée du processus i) :
Di = faux; /*baisser le drapeau*/
(avec i et j == 1,2)

L’algorithme exécuté par le processus Pi devient :

While (1)
{
< section restante >
Di = vrai ;
 Tour = j ;
While (Dj et tour ==j ) ;
 < section critique i >
Di = faux;
 }

Exemple :
Supposons que P1 et P2 sont dans leurs sections d’entrée : Exécution de la première instruction : D1 et D2 sont vraies. La variable tour prend ensuite la valeur correspondante à la dernière écriture, si cette écriture provient de P1 alors P2 va pouvoir entrer en section critique sinon P2 sera bloqué et P1 entre en section critique.

Cette solution est correcte car elle vérifie toutes les hypothèses :

Exclusion mutuelle

On va démontrer la réalisation de l’exclusion mutuelle en effectuant un raisonnement par l’absurde :

Supposons que l’exclusion mutuelle n’est pas assurée. Alors, les deux processus P1 et P2 peuvent se trouver en même temps dans leurs sections critiques.

Si P1 et P2 sont tous les deux en sections critiques alors nous aurions les 3 propositions suivantes vérifiées (vraies) en même temps :
Donc, pour que la première condition soit vérifiée, il faut que la valeur de tour soit égale à 1 (d’après la troisième proposition, D2 est vrai)
De même, pour que la deuxième condition soit vérifiée, il faut que la valeur de tour soit égale à 2 (d’après la troisième proposition, D1 est vrai)

Ainsi, la variable tour serait égale à 1 et à 2 en même temps. Ce qui est impossible. Par conséquent, l’exclusion mutuelle est réalisée.

Interblocage

Nous allons suivre le même type de raisonnement afin de démontrer que cet algorithme évite les situations d’interblocage.

Donc, si les deux processus P1 et P2 sont bloqués en mêmes alors nous aurions les 2 propositions suivantes vérifiées (vraies) en même temps :
Là aussi, la variable tour serait égale à 1 et à 2 en même temps. Ce qui est également impossible. Par conséquent, l’absence de l’interblocage est garantie.

Progression
(solution symétrique)

Supposons que P2 est en section restante donc Si P2 ne peut pas entrer en section critique (c’est à dire, la condition de progression n’est pas assurée) alors la proposition suivante serait vérifiée Dans ce cas, nous aurions la variable D2 égale à faux et égale à vrai en même temps ce qui est également impossible.
Un raisonnement symétrique permet de prouver que quand P1 est dans sa section restante alors il ne peut pas interdire à P1 d’entrer dans sa section critique si ce dernier le désirait.
Par conséquent, la condition de progression est respectée.

Famine

Si un des deux processus demande à entrer dans sa section critique et si l’autre est dans sa section restante alors il va pouvoir entrer sans attendre car la progression est assurée comme nous l’avons constaté dans le paragraphe précédent.
Donc, le cas important devant être examiné est celui dans lequel les deux processus P1 et P2 ont demandé à entrer dans leurs sections critiques ; comme il n’y a pas d’interblocage alors l’un des deux a pu entrer, soit P1 (respectivement P2 ) ce processus. Donc :
Si p1 demande une nouvelle fois l’entrée en section critique après avoir exécuté sa section de sortie, alors nous aurions dans ce cas :
Ce qui interdit à p1 d’entrer en section critique et laisse passer P2.

Chaque processus, lorsqu’il a demandé à entrer en section critique, attend au plus un passage de l’autre en section critique pour pouvoir y entrer à son tour. L’attente d’un processus est donc bornée. Par conséquent, la solution précédente évite la famine.