Algorithme 1

Cet algorithme considère le cas de deux processus P1 et P2. L’idée est de permettre à ces deux processus dans leurs sections critiques à tour de rôle. On utilise une variable commune tour dont les seules valeurs possibles sont 1 et 2.

Avant qu’un processus Pi puisse entrer dans la section, il consulte la variable tour. L’accès à sa section critique lui est interdit tant que ce n’est pas son tour d’y entrer c’est à dire la valeur courante de tour est différente de son numéro i.

A sa sortie de sa section critique un processus passe le tour à l’autre processus en affectant à tour le numéro de l’autre.

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

Prologue (section d’entrée du processus i ) : while (tour == j) ;


Epilogue (section d’entrée du processus i) : Tour = j ;
(avec i et j == 1,2)

Tour = 1;
P1
While (1)
{
< section restante >
while (tour == 2) ;
< Section critique1 >
Tour = 2 ;
}

P2
While (1)
{
< section restante >
while (tour == 1) ;
< Section critique2 >
Tour = 1 ;
}

Il est assez facile de prouver que cette solution ne vérifie pas la condition de progression. Il suffit de considérer le contre exemple suivant : tour == 1, P1 est dans sa section restante, P2 veut entrer dans sa section critique. Il ne pourra pas le faire avant que p1 n’entre et sort de sa section critique.

De manière formelle, on peut associer à cet algorithme un automate :

L’alphabet d’actions est donné par l’ensemble : A = {Ri, Ei, Ci, Si / i= 1,2}

• Ri représente une instruction quelconque de la section restante
• Ei représente l’instruction de la section d’entrée
• représente une instruction quelconque de la section critique
• Si représente une instruction quelconque de la section de sortie

L’état de l’automate est donné par le triplet (q1, q2, k)

• qi = 1 si pi est dans sa section critique et 0 sinon
• k = la valeur de la variable tour
• l’état initial est donné par le triplet (0, 0,1)

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

• Section restante de pi :
  Si qi = 0 alors delta ((q1, q2, k), Ri) = (q1, q2, k)
• Attente de pi dans la section d’entrée :
  Si qi= 0 et k ? i alors delta((q1, q2, k), Ei) = (q1, q2, k)
• Entrée de pi en section critique :
  Si qi=0 et k=i alors delta((q1, q2, k), Ei)=(q’1, q’2, k), avec : q’i=1, q’j=qj et j ? i
• Section critique de pi :
  Si qi= 1 alors delta((q1, q2, k), Ci) = (q1, q2, k)
• Section de sortie de pi :
  Si qi = 1 alors delta((q1, q2, k), Si) = (q’1, q’2, k), avec : q’i = 0, q’j = qj et j ? i

Chaque action possible modifie ou non certaines composantes de cet état, suivant l’instruction du programme.

On peut s’appuyer sur le graphe précédent pour étudier la validité du protocole 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, k). 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 réalisée.

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, k). 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.

Exemple :

L’automate est dans l’état (0, 0, 1)
P1 en section restante

Par conséquent p2 ne peut pas entrer dans sa section critique

Cette situation correspond au comportement partiel suivant :
E1C1S1R1E2C2S2R2,
Chaque processus a exécuté une fois sa section critique et se trouve en section restante.

A priori, l’un quelconque des deux processus devrait pouvoir entrer à nouveau en section critique. Or seul P1 peut y entrer puisque la valeur de tour est égale à 1.

La condition de progression n’est pas vérifiée.