next up previous contents
Next: Les primitives matérielles de Up: Les mécanismes de synchronisations Previous: Le problème de la

Les solutions logicielles.

Première idée pour 2 processus: un feu vert/rouge.
le feu est initialisé à vert.
debut
tant que vrai faire debut
        tant que feu = rouge faire rien;
        feu := rouge;
        Section Critique;
        feu := vert;
        Section Non Critique
        fin
fin
Les 2 processus peuvent être ensemble en S.C

Deuxième idée : Deux drapeaux
Flag[i] signifie que Pi veut entrer et les drapeaux sont initialisés à faux.
debut
tant que vrai faire debut
        Flag[i] := true;
        tant que Flag[j] faire rien;
        Section Critique;
        Flag[i] := false;
        Section Non Critique
        fin
fin

Les 2 processus ne peuvent pas être ensemble en S.C

Il n'y a pas d'attente s'il n'y a pas de compétition.

Il y a possibilité d'attente infinie (famine).

la preuve est faite par la construction du graphe du comportement des deux processus.

Troisième idée : une variable qui indique "A qui le tour".
debut
tant que vrai faire debut
        tant que tour = j faire rien;
        Section Critique;
        tour := j ;
        Section Non Critique
        fin
fin

2 processus ne peuvent pas être ensemble en S.C

Il n'y a pas d'attente infinie.

Il peut y avoir attente s'il n'y a pas de compétition. C'est un algorithme d'alternance (jeton).

Algorithme de Peterson pour 2 processus.
Combiner les deuxième et troisième idées.
debut
tant que vrai faire debut
        Flag[i] := true;
        tour := i ;
        tant que (Flag[j] et tour = i) faire rien;
        Section Critique;
        Flag[i] := false;
        Section Non Critique
        fin
fin
La preuve sera faite en TD

Section critique pour N processus.
Solutions complexes et difficiles à prouver.



Alain GRIFFAULT
2002-02-11