Algorithme 2

Cet algorithme utilise 2 variables D1 et D2 (drapeaux) initialisées à faux correspondant aux demandes respectives de P1 et P2 d’entrer en section critique.

Un processus pi désirant entrer dans la section critique commence par lever son drapeau (affecte à Di la valeur vrai), puis il consulte le drapeau de l’autre processus (Dj). Il ne peut entrer que si Dj == faux c’est à dire Pj ne demande pas à entrer dans sa section critique.

A sa sortie Pi positionne Di à faux signalant qu’il se désintéresse provisoirement de sa section critique.

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

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

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

L’algorithme devient :

While (1)
{
< section restante >
Di = vrai ;
While (Dj) ;
< section critique >
Di = faux;
}

On peut associer aussi à cet algorithme un automate :
L’alphabet d’actions est donné par l’ensemble : A = {Ri, Ai ,Ei, Ci, Si / i= 1,2}

• Ri représente une instruction quelconque de la section restante
• Ci représente une instruction quelconque de la section critique
• Si représente une instruction quelconque de la section de sortie
• Pour la section d’entrée, nous distinguons 2 actions :
• Ai: Di = vrai
• Ei: consultation de Dj (while ….)

L’état de l’automate est donné par un quadruplet (q1, q2, d1, d2) :

• q1 et q2 ont la même signification :
• qi == 1 si pi est dans sa section critique et 0 sinon
• d1 et d2 représentent les valeurs de variables D1 et D2
• l’état initial est donné par le quadruplet (0, 0, faux, faux)

La fonction de transitions (delta : E x A -> E) est définie de la façon suivante :

• Section restante de pi :
  Si qi = 0 et dI = faux alors delta ((q1, q2, d1, d2), Ri) = (q1, q2, d1, d2)
• Section d’entrée de pi : exécution de l’instruction Ai :
  Si qi = 0 et di = faux alors delta ((q1, q2, d1, d2), Ai) = (q1, q2, d’1, d’2) avec d’i== vrai et d’j,== dj pour j ? i
• Attente de pi dans la section d’entrée :
  Si qi = 0 et di = vrai et dj = vrai i , alors delta ((q1, q2, d1, d2), Ei) = (q1, q2, d1, d2)
• Entrée de pi en section critique :
  Si qi = 0 et di = vrai et dj = faux , alors delta ((q1, q2, d1, d2), Ei) = (q’1, q’2, d1, d2) avec : q’i=1 et q’j=qj pour j ? i
• Section critique de pi :
  Si qi= 1 alors delta ((q1, q2, d1, d2), Ci) = (q1, q2, d1, d2)
• Section de sortie de pi :
  Si qi = 1 et di = vrai, alors delta ((q1, q2, d1, d2), Si) = (q’1, q’2, d’1, d’2), avec : q’i = 0, d’i== faux, q’j = qj et d’j,== dj pour j ? i.

Comme précédemment, chaque action possible modifie ou non certaines composantes de cet état, suivant l’instruction du programme.

La représentation graphique de cet automate est donnée par le schéma suivant :

Là aussi, on peut s’appuyer sur le graphe précédent pour étudier la validité de l’algorithme proposé.

Pour étudier la réalisation de l’exclusion mutuelle, il faut examiner tous les états afin d’examiner les valeurs de leurs composantes (q1, q2, D1, D2). Il est assez facile de constater sur le diagramme précédent que, pour chaque état, une au plus des composantes q1 et q2 a la valeur 1. Donc l’exclusion mutuelle est assurée aussi par cet algorithme.

Pour étudier la vérification de la condition de progression, il faut examiner le comportement de l’automate quand il se trouve dans un état de la forme (0, 0, V, F) et (0, 0, F, V). Ces états traduisent e fait que l’un des deux processus est dans sa section restante alors que l’autre se trouve dans le prologue. La non-vérification de cette condition est aisément détectée par la présence d’états de la forme précédente que l’un des processus ne peut pas quitter. Il est assez facile de remarquer :

• L’existence, à partir de l’état (0, 0, V, F), d’une transition d’étiquette E1 qui permet au premier processus, P1, d’entrer en section critique pendant que le deuxième processus, P2 , est en section restante.
• L’existence, à partir de l’état (0, 0, F, V), d’une transition d’étiquette E1 qui permet au deuxième processus, P2, d’entrer en section critique pendant que le premier processus, P1, est en section restante

La progression est ainsi vérifiée pour les comportements acceptés par l’automate.

La vérification, des deux conditions précédentes, ne suffit pas pour affirmer la validité de cette solution, il faut aussi étudier la vérification des autres conditions :

• Interblocage
• Famine

Pour démontrer que, l’algorithme précédent, ne conduit pas à une situation d’interblocage il suffit de vérifier sur l’automate précédent, l’absence d’un «état puits» qui correspond à un état atteignable duquel on n’en peut plus sortir. L’examen de l’automate montre l’existence d’un tel état : (0, 0, vrai, vrai) à partir duquel aucune action n’est possible, excepté les actions E1 et E2, qui correspondent à l’attente de chaque processus dans sa section d’entrée.

Exemple :
Le comportement partiel A1A2 (où chacun des processus a affecté à la variable Di la valeur «vrai») permet d’atteindre cet état.

L'algorithme précédent n’est pas valide parce qu’il ne peut garantir l’absence de blocage.