Previous Next Contents

Chapter 5    Algorithmes d'exclusion mutuelle (mémoire partagée)

5.1  Peut-on se passer de synchronized?

On cherche à programmer un mécanisme d'``exclusion mutuelle'', en mémoire partagée, à partir des primitives que l'on a vu, sauf les primitives de synchronisation synchronized ainsi que wait et notify. On doit évidemment avoir une hypothèse de base sur la sémantique du système sous-jacent. On ne va imposer comme condition que le fait que la lecture et écriture en mémoire est atomique c'est à dire que plusieurs lectures et écritures en parallèle sont en fait exécutées séquentiellement dans un ordre à priori quelconque. Remarquer que c'est le cas en JAVA (on va le supposer en tout cas), au moins pour des types scalaires comme int mais pas long!

On veut donc pouvoir faire en sorte qu'un thread impose à tous les autres d'être l'unique à s'exécuter (pendant que les autres attendent leur tour). En fait, on pourra se déclarer content d'un algorithme d'exclusion mutuelle seulement s'il satisfait les conditions suivantes: La première idée qui vienne à l'esprit est de rajouter aux threads considérés un champ:

public class CS1 extends Thread {
    Thread tour = null;
    ...
}
qui précise quel thread doit s'exécuter. On veut écrire une méthode:

public void AttendtonTour()
qui attend l'autorisation de s'exécuter, et

public void RendlaMain()
qui autorise les autres threads présents à essayer de s'exécuter.

Pour simuler l'algorithme, on fait en sorte que tous les threads instance de CS1 aient la même exécution:

    public void run() {
        while(true) {
            AttendtonTour();
            System.out.println("C'est le tour de "+
                       Thread.currentThread().getName());
            RendlaMain();
        }
    }
On en arrive au code naturel de la figure 5.1.


public class CS1 extends Thread {
    Thread tour = null;
    
    public void AttendtonTour() {
        while (tour != Thread.currentThread()) {
            if (tour == null)
                tour = Thread.currentThread();
            try {
                Thread.sleep(100);
            } catch (Exception e) {}
        }
    }

    public void RendlaMain() {
        if (tour == Thread.currentThread()) 
            tour = null;
    }

    public void run() {
        while(true) {
            AttendtonTour();
            System.out.println("C'est le tour de "+
                   Thread.currentThread().getName());
            RendlaMain();
        } }

    public static void main(String[] args) {
        Thread Un = new CS1();
        Thread Deux = new CS1();
        Un.setName("UN");
        Deux.setName("DEUX");
        Un.start();
        Deux.start();
    } }
Figure 5.1:

Mais cela contredit (A) par exemple. Il suffit de considérer une exécution synchrone des threads et on s'aperçoit que les deux processus peuvent rentrer dans leur section critique en même temps!

5.2  Premiers algorithmes?

Continuons sur l'idée de la dernière section, et essayons de programmer une première approximation de code permettant d'assurer l'exclusion mutuelle. Intéressons-nous d'abord à un premier cas dans lequel on a seulement deux processus P0 et P1. L'idée est d'assurer que l'on ne puisse jamais être en même temps dans certaine partie du code (appelée section critique) pour P0 et P1.

Le premier code auquel on puisse penser pour Pi est (i=0,1, j=(i+1) mod 2) est montré à la figure 5.2.


public class Algorithme1 extends MutualExclusion
{
    public Algorithme1() {
        turn = 0;
    }

    public void Pmutex(int t) {
        while (turn != t)
            Thread.yield();
    }

    public void Vmutex(int t) {
        turn = 1-t;
    }

    private volatile int turn;
}
Figure 5.2:

Remarquer que l'entier turn est déclaré en volatile c'est à dire qu'il est susceptible d'être modifié à tout moment par l'extérieur (un autre thread par exemple). Cela empêche javac de le placer dans un registre en cours d'exécution, pour optimiser le code (ce serait en l'occurrence une optimisation fausse dans notre cas!).

Ce code est une instance de la classe abstraite ExclusionMutuelle de la figure 5.3.


public abstract class ExclusionMutuelle
{
    public static void Critique() {
        try {
            Thread.sleep((int) (Math.random()*3000));
        }
        catch (InterruptedException e) { }
    }

    public static void nonCritique() {
        try {
            Thread.sleep((int) (Math.random()*3000));
        }
        catch (InterruptedException e) { }
    }

    public abstract void Pmutex(int t);
    public abstract void Vmutex(int t);
}
Figure 5.3:

Pour tester cet algorithme, on utilise des taches très simples, simulant l'entrée et la sortie d'une section critique, voir figure 5.4.


public class Tache extends Thread
{
    public Tache(String n,int i,ExclusionMutuelle s) {
        name = n;
        id = i;
        section = s;
    }

    public void run() {
        while (true) {
            section.Pmutex(id);
            System.out.println(name+" est en section critique");
            ExclusionMutuelle.Critique();
            section.Vmutex(id);

            System.out.println(name+" est sorti de la section critique");
            ExclusionMutuelle.nonCritique();
        }
    }

    private String name;
    private int id;
    private ExclusionMutuelle section;
}
Figure 5.4:

Et enfin on utilise un main qui crée et lance deux tâches, voir figure 5.5.


public class Test
{
    public static void main(String args[]) {
        ExclusionMutuelle alg = new Algorithme1();

        Tache zero = new Tache("Tache 0",0,alg);
        Tache un = new Tache("Tache 1",1,alg);

        zero.start();
        un.start();
    }
}
Figure 5.5:

Mais avec Algorithme1, les processus ne peuvent entrer en section critique qu'à tour de rôle, ce qui est contredit (B) (mais il est vrai que cet algorithme satisfait à (A) et (C), si on suppose que chaque section critique se déroule en temps fini).

En fait, on peut prouver (voir [Lyn96]) que pour résoudre le problème de l'exclusion mutuelle entre n processus dans notre cadre, il faut au moins n variables partagées distinctes, donc il est clair qu'il faut un peu compliquer le code précédent (n=2, mais seulement une variable partagée, turn!).

Pour résoudre la difficulté précédente, il faut s'arranger pour connaître l'état de chaque processus afin de prendre une décision. Un essai de solution serait le code de la figure 5.6.


public class Algorithme2 extends MutualExclusion
{
    public Algorithme2() {
        flag[0] = false;
        flag[1] = false;
    }

    public void Pmutex(int t) {
        int other;
        other = 1-t;
        flag[t] = INIT;
        while (flag[other] == true)
            Thread.yield();
    }

    public void Vmutex(int t) {
        flag[t] = false;
    }

    private volatile boolean[] flag = new boolean[2];
}
Figure 5.6:

Si on remplace INIT par false on s'aperçoit que la condition (A) d'exclusion mutuelle n'est pas satisfaite!

Pour s'en convaincre il suffit de considérer l'exécution suivante:

zero un flag[t] flag[other]
flag[1]=false ?: OUI flag[0]=false ?: OUI false false
flag[0]:= true flag[1]:=true true true
Section Critique Section Critique - -

Si d'autre part, on fait INIT=true, la même exécution (synchrone) fait que les deux processus bouclent indéfiniment, contredisant (B) et (C)!

On propose alors le code de la figure 5.7, toujours plus compliqué...


public class Algorithme4 extends MutualExclusion
{
    public Algorithme4() {
        flag[0] = false;
        flag[1] = false;
    }

    public void Pmutex(int t) {
        int other;
        other = 1-t;
        flag[t] = true;
        while (flag[other] == true) {
            flag[t] = false;
            while (flag[other])
                Thread.yield();
            flag[t] = true;
    }

    public void Vmutex(int t) {
        flag[t] = false;
    }

    private volatile boolean[] flag = new boolean[2];
}
Figure 5.7:

Il réalise bien l'exclusion mutuelle mais peut causer un interblocage si les deux processus s'exécutent de façon purement synchrone. A ce moment là, après la première affectation, les deux tests de la boucle while sont vrais, d'où les deux flag sont mis à false simultanément puis à true et ainsi de suite. Les programmes de zero et de un bouclent avant la portion Section Critique.

Tout cela paraît sans issue. En fait, une solution est d'instaurer une règle de politesse entre les processeurs. C'est l'algorithme de Dekker (1965), à la figure 5.8.

5.3  Algorithme de Dekker


public class Dekker extends ExclusionMutuelle
{
    public Dekker() {
        flag[0] = false;
        flag[1] = false;
        turn = 0;
    }

    public void Pmutex(int t) {
        int other;
        other = 1-t;
        flag[t] = true;

        while (flag[other] == true) {
            if (turn == other) {
                flag[t] = false;
                while (turn == other)
                    Thread.yield();
                flag[t] = true;
            }
        }
    }

    public void Vmutex(int t) {
        turn = 1-t;
        flag[t] = false;
    }

    private volatile int turn;
    private volatile boolean[] flag = new boolean[2];
}
Figure 5.8:

Il réalise l'exclusion mutuelle sans blocage mutuel. L'équité (la condition (C)) est vérifiée si l'ordonnanceur de tâche est lui-même équitable, ce que l'on supposera.

Considérons le code plus simple de la figure 5.9, proposé par Hyman en 1966.


public class Hyman extends ExclusionMutuelle
{
    public Hyman() {
        flag[0] = false; 
        flag[1] = false;
        turn = 0;
    }

    public void Pmutex(int t) {
        int other = 1-t;
        flag[t]= true;

        while (turn==other) {
            while (flag[other]) 
                Thread.yield();
            turn = t;
        }
    }
    
    public void Vmutex(int t) {
        flag[t] = false;
    }

    private volatile int turn;
    private volatile boolean[] flag = new boolean[2];
}
Figure 5.9:

Il est malheureusement faux car, si turn est à 0 et zero positionne flag[1] à true puis trouve flag[0] à false, alors zero met flag[0] à true, trouve turn égal à 0 et rentre en section critique. un affecte alors 1 à turn et rentre également en section critique!

Une vraie amélioration de l'algorithme de Dekker est l'algorithme de Peterson proposé en 1981.

5.4  Algorithme de Peterson

Contentons nous d'abord du cas simple où l'on dispose uniquement de deux tâches zero et un. Le code des deux tâches est donné à la figure 5.10.


public class Peterson extends MutualExclusion
{
    public Peterson() {
        flag[0] = false;
        flag[1] = false;
        turn = 0;
    }

    public void Pmutex(int t) {
        int other;
        other = 1-t;
        flag[t] = true;
        turn = t;
        while (flag[other] && (turn == t))
            Thread.yield();
    }

    public void Vmutex(int t) {
        flag[t] = false;
    }

    private volatile int turn;
    private volatile boolean[] flag = new boolean[2];
}
Figure 5.10:

On a bien alors exclusion mutuelle sans interblocage et avec équité (pas de famine).

Donnons ici quelques idées de preuve de cet algorithme.

On va décorer le code par des ``assertions'' écrites avec des prédicats logiques du premier ordre, portant sur les valeurs des variables du programme (et donc également de celles que l'on vient d'introduire), avec comme prédicats l'égalité avec des constantes (cela nous suffira ici). Ces assertions seront introduites entre deux instructions consécutives, c'est à dire qu'elles seront associées à chaque point de contrôle de chaque processus.

On va introduire, de façon intuitive et pas trop formelle, une méthode de raisonnement et de preuve sur des processus parallèles (disons, en nombre n) en mémoire partagée due à l'origine à S. Owicki et D. Gries [OG75].

Les assertions que l'on rajoute doivent être des ``invariants'' décrivant des relations logiques entre les valeurs des variables, vraies pour toutes les exécutions possibles (en particulier tous les ordonnancements des actions atomiques). Cela veut dire la chose suivante. Soit T le système de transition donnant la sémantique du programme considéré. On sait qu'un état de T est un (n+1)-uplet (c1,...,cn,E) où ci (1 £ i £ n) est un point de contrôle du ième processus et E est un environnement, c'est à dire une fonction qui à chaque variable du programme associe une valeur. Alors le système d'assertion A qui à chaque point de contrôle c (de n'importe quel processus i) associe un prédicat P est admissible si quelque soit l'état (c1,...,cn,E) du système de transition tel que ci=c alors P est vrai pour l'environnement E.

L'idée est que l'on veut pouvoir inférer quand c'est possible, ou tout du moins vérifier que les assertions que l'on rajoute dans le code de chacun des processus dit bien des choses vraies sur toutes les exécutions possibles du code.

Soit I une instruction ou un block d'instructions JAVA. On rajoute des assertions décrivant ce qui se passe avant et après le code I en écrivant {p }I {q }. On a les règles suivantes, pour un fragment de JAVA, qui va nous suffire pour le moment: Par exemple (voir [Win93]), le système suivant est un système d'assertions correctes:

{ x=x0 et y=y0 }
q = 0;
while (x >= y) {
  {x=x0-qy0 et y=y0}
  q = q+1;
  {x=x0-(q-1)y0 et y=y0}
  x = x-y;
  {x=x0-qy0 et y=y0}
}
{x=x0-qy0 et x<y et y=y0}
Une fois la preuve faite séquentiellement, il faut prouver que les invariants trouvés pour chaque thread pris séparément, est encore valide si tout ou partie d'autres threads s'exécutent entre deux instructions, modifiant ainsi l'état local du thread! Cela s'appelle la preuve de non-interférence. Attention car on suppose ici que les affectations sont atomiques (ce sera vrai en JAVA dans la suite pour les affectations de constantes, ce qui sera le seul cas intéressant pour nous; sinon il faudrait décomposer les affectation en load, store etc. comme expliqué précédemment).

Pour que cela puisse se faire de façon correcte, il faut introduire des variables nouvelles dans le code séquentiel, qui déterminent le point de contrôle auquel le processus est arrivé. Sans cela, la méthode est fausse (en fait, l'article d'origine de S. Owicki et de D. Gries comportait cet oubli). Par exemple, on devrait transformer la preuve précédente en:

{ x=x0 et y=y0 et c=0}
q = 0;
{ x=x0 et y=y0 et c=1}
while (x >= y) {
  {x=x0-qy0 et y=y0 et c=2}
  q = q+1;
  {x=x0-(q-1)y0 et y=y0 et c=3}
  x = x-y;
  {x=x0-qy0 et y=y0 et c=4}
}
{x=x0-qy0 et x<y et y=y0 et c=5}
c représente le point de contrôle courant, numéroté de façon fort logique de 1 à 5 ici.

On va donc supposer que chaque thread Pi parmi P1,...,Pk a un compteur ci et des assertions Ai,k avant les instructions Ii,k de Pi (pour k variant sur l'ensemble des points de contrôle de Pi) utilisant éventuellement des prédicats aussi sur les autres compteurs ordinaux c1,...,ck. Alors il faut vérifier les conditions dites de non-interférences suivantes, quand Ij,l est une affectation x=u:
{(Ai,k Ù Aj,l)[x¬ u] }Ij,l {Ai,k}

On peut simplifier un peu cela dans le cas qui nous préoccupe, car on n'a qu'une affectation sur un objet partagé, donc on n'a pas besoin de numéroter toutes les instructions. Introduisons deux variables auxiliaires after[0] et after[1] (qui servent à indiquer si le contrôle est après turn=t dans le code). Rajoutons également les instructions after[0]=true, after[1]=true après respectivement turn=0 et turn=1.

En utilisant l'abbréviation I= [turn=1 ou turn=2] on commente le code avec les assertions comme à la figure 5.11.


{ non flag[0] }
flag[0]=true; after[0]=false;
{ flag[0] et non after[0] }
turn=0; after[0]=true;
{ inv: flag[0] et after[0] et I }
while (flag[1] && (turn==0))
   { flag[0] et after[0] et I }
   Thread.yield();
{ flag[0] et after[0] et (flag[1] et (non(after[1]) ou turn=1)) }
[ Section Critique CS1]
{ flag[0] }
flag[0]=false;
Figure 5.11:

De même pour le deuxième processus, à la figure 5.12.


{ non flag[1] }
flag[1]=true; after[1]=false;
{ flag[1] et non after[1] }
turn=1; after[1]=true;
{ inv: flag[1] et after[1] et I }
while (flag[0] && (turn==0)) do
   { flag[1] et after[1] et I }
   Thread.yield();
{ flag[1] et after[1] et (flag[0] et (non(after[0]) ou turn=0)) }
[ Section Critique CS2]
{ flag[1] }
flag[1]=false;
Figure 5.12:

Il est relativement aisé de se convaincre ces assertions forment bien un shéma de preuve correct de chacun des processus pris séquentiellement. Seule subsiste la preuve de non-interférence. En fait, seul,

pre(CS1) = flag[0] et after[0] et (flag[1] et (non(after[1]) 
                                           ou (turn=1)))
contient des références à des objets manipulés par l'autre processus, et ce, seulement en les lignes

flag[1]=true; after[1]=false;
et

turn=1; after[1]=true;
Or,

{ pre(CS1) } flag[1]=true; after[1]=false; { pre(CS1) }
et

{ pre(CS1) } turn=1; after[1]=true; { pre(CS1) }
et de même par symétrie. De plus, on peut voir que

pre(CS1) et pre(CS2) implique (turn=0 et turn=1)
Ce qui implique que l'on a toujours

non(pre(CS1) et pre(CS2))
prouvant ainsi l'exclusion mutuelle.

Remarquez qu'il existe une généralisation de l'algorithme de Peterson à n processeurs. C'est le programme de la figure 5.13, codé sur chacun des n processeurs (liste[0] à liste[nproc-1]).


public class PetersonN extends ExclusionMutuelle
{
    public PetersonN(int nb) {
        int i;
        nproc = nb;
        turn = new int[nproc-1];
        flag = new int[nproc];
        for (i=0; i < nproc; i++) {
            flag[i] = -1; }
    }

    public void Pmutex(int t) {
        int j, k;
        boolean cond;
        for (j=0; j < nproc-1; j++) {
            flag[t] = j;
            turn[j] = t; 
            cond = true;
            for (k=0; (k < nproc) && (k != t); k++)
                cond = cond || (flag[k] >= j); 
            while (cond && (turn[j] == t))
                Thread.yield();
        }
    }

    public void Vmutex(int t) {
        flag[t] = -1;
    }

    private volatile int[] turn;
    private int nproc;
    private volatile int[] flag;
}
Figure 5.13:

Il faut évidemment légèrement changer le programme de test (ici pour 5 tâches), voir figure 5.14.


public class TestN
{
    public final static int nb = 5;

    public static void main(String args[]) {
        int i;
        Tache[] liste;

        liste = new Tache[nb];
        ExclusionMutuelle alg = new PetersonN(nb);
        
        for (i=0; i < nb; i++) {
            liste[i] = new Tache("Tache "+i,i,alg);
            liste[i].start();
        }
    }
}
Figure 5.14:

En fait c'est la solution pour 2 processeurs itérée n-1 fois. flag[i]=-1 signifie que liste[i] ne s'engage pas en section critique. turn permet de gèrer les conflits dans un couple de processus. Cet algorithme réalise bien l'exclusion mutuelle sans interblocage et avec équité.

Dans les améliorations possibles, il y a en particulier l'algorithme de Burns (1981). C'est une solution entièment symétrique qui minimise le nombre de variables utilisées ainsi que les valeurs qu'elles peuvent prendre en cours de programme.


Previous Next Contents