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.