Previous Up Next

Chapter 5  Coordination de processus

Dans ce chapitre, nous reprenons la programmation des threads JAVA, en y introduisant les mécanismes d'exclusion mutuelle indispensables, comme nous allons le voir maintenant, pour assurer la correction de bon nombre de programmes parallèles échangeant des données par mémoire partagée.

5.1  Problème

Modifions la classe Compte du chapitre 3, afin de pouvoir faire des opérations dessus, voir figure 5.1.

public class Compte {
    private int valeur;
    
    Compte(int val) {
        valeur = val;
    }
    
    public int solde() {
        return valeur;
    }
    
    public void depot(int somme) {
        if (somme > 0)
            valeur+=somme;
    }
    
    public boolean retirer(int somme) throws InterruptedException {
        if (somme > 0)
            if (somme <= valeur) {
                Thread.currentThread().sleep(50);
                valeur -= somme;
                Thread.currentThread().sleep(50);
                return true;
            }
        return false;
    }
}

Figure 5.1: Opérations simples sur un compte bancaire.


On fournit ainsi une méthode solde qui renvoie la somme qui reste sur son compte, une méthode depot qui permet de créditer son compte d'une somme positive, et enfin, une méthode retirer qui permet, si son compte est suffisament créditeur, de retirer une somme (en liquide par exemple).

On implémente alors une version idéalisée d'un automate bancaire (qui ne gérerait qu'un seul compte!), voir figure 5.2.

public class Banque implements Runnable {
    Compte nom;
    
    Banque(Compte n) {
         nom = n; }

    public void Liquide (int montant) 
           throws InterruptedException {
         if (nom.retirer(montant)) {
             Thread.currentThread().sleep(50);
             Donne(montant);
             Thread.currentThread().sleep(50); }
         ImprimeRecu();
         Thread.currentThread().sleep(50); }

    public void Donne(int montant) {
         System.out.println(Thread.currentThread().
           getName()+": Voici vos " + montant + " euros."); }

    public void ImprimeRecu() {
         if (nom.solde() > 0)
            System.out.println(Thread.currentThread().
              getName()+": Il vous reste " + nom.solde() + " euros.");
         else
            System.out.println(Thread.currentThread().
              getName()+": Vous etes fauches!");
    }

    public void run() {
        try {
           for (int i=1;i<10;i++) {
                Liquide(100*i);
                Thread.currentThread().sleep(100+10*i);
           }
        } catch (InterruptedException e) {
            return;
        }   
    }   

    public static void main(String[] args) {
        Compte Commun = new Compte(1000);
        Runnable Mari = new Banque(Commun);
        Runnable Femme = new Banque(Commun);
        Thread tMari = new Thread(Mari);
        Thread tFemme = new Thread(Femme);
        tMari.setName("Conseiller Mari");
        tFemme.setName("Conseiller Femme");
        tMari.start();
        tFemme.start();
    }
}

Figure 5.2: Un automate bancaire.


On a programmé en dur dans la méthode run() de l'automate bancaire la transaction suivante: on demande à retirer 100 euros, puis 200, puis 300 et ainsi de suite, jusqu'à épuisement de ses fonds.

Une exécution typique est la suivante:
% java Banque
Conseiller Mari: Voici vos 100 euros.
Conseiller Femme: Voici vos 100 euros.
Conseiller Mari: Il vous reste 800 euros.
Conseiller Femme: Il vous reste 800 euros.
Conseiller Mari: Voici vos 200 euros.
Conseiller Femme: Voici vos 200 euros.
Conseiller Femme: Il vous reste 400 euros.
Conseiller Mari: Il vous reste 400 euros.
Conseiller Mari: Voici vos 300 euros.
Conseiller Femme: Voici vos 300 euros.
Conseiller Femme: Vous etes fauches!
Conseiller Mari: Vous etes fauches! ...
Conclusion: le mari a retiré 600 euros du compte commun, la femme a retiré 600 euros du compte commun, qui ne contenait que 1000 euros au départ. Il est clair que le programme de gestion de compte n'est pas correct.

L'explication est simple et nous entraîne à faire un peu de sémantique.

L'exécution de plusieurs threads se fait en exécutant une action insécable (``atomique'') de l'un des threads, puis d'un autre ou éventuellement du même etc. Tous les ``mélanges'' possibles sont permis.

C'est ce que l'on appelle la sémantique par entrelacements; on en représente une portion ci-dessous:

Donnons une idée de la façon de donner une sémantique à un fragment du langage JAVA (et en supposant les lectures et écritures atomiques). Nous allons prendre comme langage un langage simple qui comprend comme constructions (étant donné une syntaxe pour les CONSTANTEs entières et un ensemble fini de VARIABLEs également entières):
EXPR ::= CONSTANTE | VARIABLE
  | EXPR+EXPR | EXPR*EXPR
  | EXPR/EXPR | EXPR-EXPR
TEST ::= EXPR==EXPR | EXPR < EXPR
  | EXPR > EXPR | TEST && TEST
  | TEST | | TEST | ! TEST
INSTR ::= VARIABLE=EXPR
BLOCK ::= e | INSTR;BLOCK
  | if TEST
    then BLOCK
    else BLOCK ;BLOCK
  | while TEST
     BLOCK ;
    BLOCK

Appelons L le langage engendré par la grammaire plus haut. On définit la sémantique d'un BLOCK inductivement sur la syntaxe, en lui associant ce que l'on appelle un système de transitions. Un système de transitions est un quadruplet (S,i,E,Tran) où, En fait, on représente généralement un système de transitions comme un graphe orienté et étiqueté, comme le suggère la représentation graphique de la relation de transition Tran, que nous avons déjà vue.

Donnons maintenant les règles de formation du système de transition correspondant à un BLOCK. Tout d'abord, appelons environnement une fonction de VARIABLE vers l'ensemble des entiers relatifs. Un état du système de transition que nous allons construire sera une paire (l,r) où l Î L et r est un environnement. Intuitivement, l est le programme qu'il reste à exécuter et r est l'état courant de la machine, c'est à dire la valeur courante de toutes ses variables. On a alors: Maintenant, supposons que l'on ait un ensemble de processus P1,...,Pn qui chacun sont écrits dans le langage L. On peut encore donner une sémantique opérationnelle (en termes de systèmes de transitions) dite par ``entrelacements'' en posant: Ce n'est pas tout: jusqu'à présent cela ne donne la sémantique qu'à une machine parallèle où chacun des processus ne calcule que dans sa mémoire locale. On n'a en effet pas encore modélisé l'échange d'information entre les processus. Pour ce faire, il faut décider des variables partagées. Notons VP l'ensemble des variables partagées (les autres étant locales aux différents processus). Alors il faut changer la sémantique précédente pour que: Les exécutions ou traces ou entrelacements dans cette sémantique sont des suites finies:
s0=i ®t1 s1 ®t2 s2 ... ®tn sn
telles que si-1 ®ti si Î Tran pour tout i entre 1 et n.

On voit dans un des entrelacements que si les 2 threads tMari et tFemme sont exécutés de telle façon que dans retirer, chaque étape est faite en même temps, alors le test pourra être satisfait par les deux threads en même temps, qui donc retireront en même temps de l'argent.

Raisonner directement sur la sémantique par entrelacement est en général impossible. On en verra un peu plus loin une abstraction (au sens de [CC77]) un peu plus gérable, les schémas de preuve à la Hoare. Le domaine de la sémantique, de la preuve et de l'analyse statique de programmes (parallèles et distribués) sortent du cadre de ce cours, on pourra se reporter aux cours du MPRI pour en savoir plus.

5.2  Une solution: synchronized

Une solution est de rendre ``atomique'' le fait de retirer de l'argent. Cela veut dire que la méthode retirer sera considérée comme une action élémentaire, non-interruptible par une autre instance de retirer. Dis autrement encore, retirer s'exécutera de façon exclusive: une seule instance de cette méthode pourra être exécutée à tout instant. Cela se fait en JAVA en déclarant ``synchronisée'' la méthode retirer de la classe Compte:
public synchronized boolean retirer(int somme)
Maintenant l'exécution typique paraît meilleure:
% java Banque
Conseiller Mari: Voici vos 100 euros.
Conseiller Femme: Voici vos 100 euros.
Conseiller Mari: Il vous reste 800 euros.
Conseiller Femme: Il vous reste 800 euros.
Conseiller Mari: Voici vos 200 euros.
Conseiller Mari: Il vous reste 400 euros.
Conseiller Femme: Voici vos 200 euros.
Conseiller Femme: Il vous reste 400 euros.
Conseiller Mari: Voici vos 300 euros.
Conseiller Femme: Il vous reste 100 euros.
Conseiller Mari: Il vous reste 100 euros.
Conseiller Femme: Il vous reste 100 euros.
Conseiller Mari: Il vous reste 100 euros...
Le résultat est maintenant que le mari a tiré 600 euros, la femme a tiré 300 euros, et il reste bien 100 euros dans le compte commun, ouf!

Remarquez que synchronized peut aussi s'utiliser sur un morceau de code: étant donné un objet obj:
   synchronized(obj) {
      BLOCK }
permet d'exécuter BLOCK en exclusion mutuelle.

5.3  Moniteurs

Chaque objet fournit un verrou, mais aussi un mécanisme de mise en attente (forme primitive de communication inter-threads; similaire aux variables de conditions ou aux moniteurs [Hoa74]).

void wait() attend l'arrivée d'une condition sur l'objet sur lequel il s'applique (en général this). Il doit être appelé depuis l'intérieur d'une méthode ou d'un bloc synchronized (il y a aussi une version avec timeout). void notify() notifie un thread en attente d'une condition, de l'arrivée de celle-ci. De même, cette méthode doit être appelée depuis une méthode déclarée synchronized. Enfin, void notify_all() fait la même chose mais pour tous les threads en attente sur l'objet.

5.4  Sémaphores

5.4.1  Sémaphores binaires

Un sémaphore binaire est un objet sur lequel on peut appliquer les méthodes P(): un processus ``acquiert'' ou ``verrouille'' le sémaphore, et V(): un processus ``relâche'' ou ``déverrouille'' le sémaphore. Tant qu'un processus a un verrou sur le sémaphore, aucun autre ne peut l'obtenir.

public class Semaphore {
    int n;
    String name;

    public Semaphore(int max, String S) {
        n = max;
        name = S;
    }

    public synchronized void P() {
        if (n == 0) {
            try {
                 wait();
            } catch(InterruptedException ex) {};
        }
        n--;
        System.out.println("P("+name+")");        
    }

    public synchronized void V() {
        n++;
        System.out.println("V("+name+")");
        notify();
    }
}

Figure 5.3: Implémentation de sémaphores.


Cela permet de réaliser l'exclusion mutuelle, donc l'accès par des processus à des sections critiques, comme on le montre à la figure 5.4.

public class essaiPV extends Thread {
    static int x = 3;
    Semaphore u;

    public essaiPV(Semaphore s) {
        u = s;
    }

    public void run() {
        int y;
        // u.P();

        try {
            Thread.currentThread().sleep(100);
            y = x;
            Thread.currentThread().sleep(100);
            y = y+1;
            Thread.currentThread().sleep(100);
            x = y;
            Thread.currentThread().sleep(100);
        } catch (InterruptedException e) {};
        System.out.println(Thread.currentThread().
                           getName()+": x="+x);
        // u.V(); 
    }

    public static void main(String[] args) {
        Semaphore X = new Semaphore(1,"X");
        new essaiPV(X).start();
        new essaiPV(X).start();
    }
}

Figure 5.4:


Une exécution typique de ce programme (où on a commenté les lignes u.P() et u.V()) est la suivante:
% java essaiPV
Thread-2: x=4
Thread-3: x=4
En effet, dans ce cas, les deux processus s'exécutent de façon à peu près synchrone, lisent tous les deux x et trouvent la valeur 3, incrémentent en même temps leur copie locale, pour écrire la valeur 4 dans x.

Maintenant, si on décommente u.P() et u.V(), on a par exemple:
% java essaiPV
P(X)
Thread-2: x=4
V(X)
P(X)
Thread-3: x=5
V(X)
La seule autre exécution possible est celle dans laquelle c'est le Thread-3 qui aurait calculé 4 et le Thread-2 qui aurait calculé 5. Dans ce cas (c'est un exemple de programme séquentialisable, voir section 5.6), l'exclusion mutuelle assurée par le sémaphore binaire u permet de faire en sorte que les exécutions parallèles sont toutes ``équivalentes'' à une des exécutions séquentielles, dans n'importe quel ordre, de l'ensemble des processus présents, considérés comme insécables.

5.4.2  Un peu de sémantique

On va rajouter à notre langage L les primitives P(.) et V(.). La sémantique par systèmes de transitions change assez peu: Ceci implique, par omission en quelque sorte, qu'aucune exécution d'un Px n'est possible si k(x)=0, c'est à dire quand la ressource x n'est pas disponible. C'est ce qui permet de modéliser le blocage d'un processus en attendant la libération d'une ressource, et donc l'exclusion mutuelle.



L'apparition de ces nouvelles transitions contraint en fait les entrelacements possibles. Si on ``abstrait'' ce système de transition (et le langage de base) à de simples suites de verrouillages et déverrouillages de variables partagées, on peut facilement se rendre compte de ce qui peut se passer.

Un des problèmes les plus courants est d'avoir voulu trop protéger les accès partagés et d'aboutir à une situation où les processus se bloquent mutuellement; on dit alors qu'il y a une étreinte fatale, ou encore que le système de transition a des points morts (des états desquels aucune transition n'est possible, mais qui ne sont pas des états finaux autorisés: ces états finaux autorisés seraient uniquement en général des n-uplets des états finaux de chacun des processus).



Un exemple classique est donné par le programme ``abstrait'' suivant constitué des deux processus:
A=Pa;Pb;Va;Vb
B=Pb;Va;Vb;Va
En regardant la sémantique par entrelacements, on trouve assez vite qu'une exécution synchrone de A et de B rencontre un point mort: en effet dans ce cas A (respectivement B) acquiert a (respectivement b) et attend ensuite la ressource b (respectivement a).

Une image pratique (qui s'abstrait élégamment de la lourdeur de la représentation des entrelacements) est d'utiliser une image géométrique continue, les ``progress graphs'' (E.W.Dijkstra (1968)), en français, ``graphes d'avancement''.

Associons en effet à chaque processus une coordonnée dans un espace IRn (n étant le nombre de processus). Chaque coordonnée xi représente en quelque sorte le temps local du ième processus. Les états du système parallèle sont donc des points dans cet espace IRn (inclus dans un hyper-rectangle dont les bornes en chaque coordonnée sont les bornes des temps locaux d'exécution de chaque processus). Les traces d'exécution sont les chemins continus et croissants dans chaque coordonnée. Dans la figure suivante, on a représenté le graphe de processus correspondant à nos deux processus A et B.

On constate que certains points dans le carré unité ne sont pas des états valides du programme parallèle. Prenons un point qui a pour coordonnée T1 un temps local compris entre Pb et Vb et pour coordonnée T2 un temps local compris également entre Pb et Vb (mais cette fois pour le processus B). Il ne peut être valide car dans cet état, les deux processus auraient chacun un verrou sur le même objet b. Cela contredit la sémantique par système de transitions vue auparavant, c'est à dire que cela contredit la propriété d'exclusion mutuelle sur b. On doit également interdire le rectangle horizontal, à cause de la propriété d'exclusion mutuelle sur la variable partagée a.

On s'aperçoit maintenant que tout chemin d'exécution (partant donc du point initial en bas à gauche du graphe d'avancement) et qui rentrerait dans le carré marqué ``dangereux'' doit nécessairement (par sa propriété de croissance en chaque coordonnée et par sa continuité) aboutir au point mort, minimum des intersections des deux rectangles interdits. Cette concavité inférieure est responsable de l'étreinte fatale entre les processus A et B. De même on s'aperçoit que certains états, dans la concavité supérieure de la région interdite, sont des états inatteignables depuis l'état initial. On reviendra la-dessus et sur des critères plus simples pour trouver si un système a des points morts à la section 5.4.4. Sachez simplement que ces idées apparemment simples peuvent être développées extrêmement loin (voir par exemple [Gou03]).

Remarquez également que synchronized de JAVA ne fait jamais que P du verrou associé à une méthode ou à un bloc de code, puis V de ce même verrou à la fin de ce même code. Une méthode M de la classe A qui est synchronized est équivalente à P(A), corps de M, V(A). Il y a malgré tout une subtile différence. La construction synchronized est purement déclarative et a donc une portée définie statiquement, contrairement à l'utilisation de P et V.

On retrouvera des considérations sémantiques plus simples, dans le cas du passage de messages, et des approches de preuve de programmes, dans le TD consacré à l'algèbre de processus CCS.

5.4.3  Un complément sur la JVM

Pour bien comprendre la sémantique des communications inter-threads en JAVA, il nous faut expliquer un peu en détail comment la JVM traite les accès mémoire des threads.

Toutes les variables (avec leurs verrous correspondants et la liste des threads en attente d'accès) de tous les threads sont stockées dans la mémoire gérée par la JVM correspondante. Bien évidemment, les variables locales d'un thread ne peuvent pas être accédées par d'autres threads, donc on peut imaginer que chaque thread a une mémoire locale et a accès à une mémoire globale.

Pour des raisons d'efficacité, chaque thread a une copie locale des variables qu'il doit utiliser, et il faut bien sûr que des mises à jour de la mémoire principale (celle gérée par la JVM) soient effectuées, de façon cohérente.

Plusieurs actions atomiques (c'est à dire non interruptibles, ou encore qui ne s'exécuteront qu'une à la fois sur une JVM) peuvent être effectuées pour gérer ces copies locales de la mémoire principale, au moins pour les types simples (int, float...). Ces actions décomposent les accès mémoires qui sont nécessaires à l'interprétation d'une affectation JAVA: Pour les types ``plus longs'' comme double et long, la spécification permet tout à fait que load, store, read et write soient non-atomiques. Elles peuvent par exemple être composées de deux load atomiques de deux ``sous-variables'' int de 32 bits. Le programmeur doit donc faire attention à synchroniser ses accès à de tels types, s'ils sont partagés par plusieurs threads.

L'utilisation par la JVM de ces instructions élémentaires est soumise à un certain nombre de contraintes, qui permettent de définir la sémantique fine des accès aux ressources partagées de JAVA. Tout d'abord, pour un thread donné, à tout lock correspond plus tard une opération unlock. Ensuite, chaque opération load est associée à une opération read qui la précède; de même chaque store est associé à une opération write qui la suit.

Pour une variable donnée et un thread donné, l'ordre dans lequel des read sont faits par la mémoire locale (respectivement les write) est le même que l'ordre dans lequel le thread fait les load (respectivement les store). Attention, ceci n'est vrai que pour une variable donnée! Pour les variables volatile, les règles sont plus contraignantes car l'ordre est aussi respecté entre les read/load et les write/store entre les variables. Pour les volatile on impose également que les use suivent immédiatement les load et que les store suivent immédiatement les assign.

Pour bien comprendre tout cela prenons deux exemples classiques, aux figures 5.6 et 5.7 respectivement. On utilise ces classes dans deux threads de la même façon, on en donne donc le code à la figure 5.5 uniquement dans le cas de Exemple1.

class Essai1 extends Thread {
  public Essai1(Exemple1 e) {
    E = e;
  }

  public void run() {
    E.F1(); 
  }

  private Exemple1 E;
} 
class Essai2 extends Thread {
  public Essai2(Exemple1 e) {
    E = e;
  }

  public void run() {
    E.G1();
  }

  private Exemple1 E;
} 

class Lance {
  public static void main(String args[]) {
    Exemple1 e = new Exemple1();
    
    Essai1 T1 = new Essai1(e);
    Essai2 T2 = new Essai2(e);

    T1.start();
    T2.start();
    System.out.println("From Lance a="+e.a+" b="+e.b);
  }
} 

Figure 5.5: Classe Essai1.



class Exemple1 {
  int a = 1;
  int b = 2;

  void F1() {
    a = b; 
  }

  void G1() {
    b = a;
  }
}

Figure 5.6: Classe Exemple1.



class Exemple2 {
  int a = 1;
  int b = 2;

  synchronized void F2() {
    a = b; 
  }

  synchronized void G2() {
    b = a;
  }
}

Figure 5.7: Classe Exemple2


Une exécution typique est:
> java Lance
a=2 b=2
Mais il se peut que l'on trouve également:
> java Lance
a=1 b=1
ou encore
> java Lance
a=2 b=1
En fait, pour être plus précis, les contraintes d'ordonnancement font que les chemins possibles d'exécution sont les entrelacements des 2 traces séquentielles
read b ® load b ® use b ® assign a ® store a ® write a

pour le thread Essai1 et
read a ® load a ® use a ® assign b ® store b ® write b

pour le thread Essai2. Appelons la1, lb1 (respectivement la2 et lb2) les copies locales des variables a et b pour le thread Essai1 (respectivement pour le thread Essai2). Alors on peut avoir les entrelacement suivants (modulo les commutations des read a et read b, ce qui n'a aucune influence sur le calcul):
read b ® write a ® read a ® write b
read a ® write b ® read b ® write a
read a ® read b ® write b ® write a

Dans le premier cas l'état de la machine est la1=2, lb1=2, a=2, b=2, la2=2 et lb2=2. Dans le deuxième on a la1=1, lb1=1, a=1, b=1, la2=1 et lb2=1. Enfin dans le troisième, on a la1=2, lb1=2, a=2, b=1, la2=1 et lb2=1.

Si on utilise la version synchronisée de Exemple1, qui est Exemple2 à la figure 5.7, alors on n'a plus que les deux premiers ordonnancements qui soient possibles:
read b ® write a ® read a ® write b
read a ® write b ® read b ® write a

5.4.4  Quelques grands classiques

Exerçons un peu nos talents sur des problèmes classiques du parallélisme (que vous aurez peut-être vu par ailleurs, par exemple en cours de système d'exploitation).

Le premier problème est celui des philosophes qui dînent (introduit par E. W. Dijkstra [Dij68]). Dans le cas général, on a n philosophes assis autour d'une table (plus ou moins) ronde:

avec chacun une fourchette à sa gauche et une autre à sa droite. On n'a pas représenté ici le sujet principal: le bol de spaghettis supposé être au centre. Les philosophes voulant manger, doivent utiliser les 2 fourchettes en même temps pour se servir de spaghettis. Un des premiers ``protocoles'' venant à l'esprit est celui dans lequel chaque philosophe essaie d'attraper sa fourchette gauche, puis droite, se sert et enfin repose la fourchette gauche puis droite. Cela donne en JAVA le code de la figure 5.8.

public class Phil extends Thread {
    Semaphore LeftFork;
    Semaphore RightFork;

    public Phil(Semaphore l, Semaphore r) {
        LeftFork = l;
        RightFork = r;
    }

    public void run() {
        try {
            Thread.currentThread().sleep(100);
            LeftFork.P();
            Thread.currentThread().sleep(100);
            RightFork.P();
            Thread.currentThread().sleep(100);
            LeftFork.V();
            Thread.currentThread().sleep(100);
            RightFork.V();
            Thread.currentThread().sleep(100);
        } catch (InterruptedException e) {};
    }
}

public class Dining {

    public static void main(String[] args) {
        Semaphore a = new Semaphore(1,"a");
        Semaphore b = new Semaphore(1,"b");
        Semaphore c = new Semaphore(1,"c");
        Phil Phil1 = new Phil(a,b);
        Phil Phil2 = new Phil(b,c);
        Phil Phil3 = new Phil(c,a);
        Phil1.setName("Kant");
        Phil2.setName("Heidegger");
        Phil3.setName("Spinoza");
        Phil1.start();
        Phil2.start();
        Phil3.start();
    } }

Figure 5.8: Implémentation des trois philosophes.


Une exécution typique est:
% java Dining
Kant: P(a)
Heidegger: P(b)
Spinoza: P(c)
^C
On constate un interblocage des processus. Comment aurions nous pu nous en douter? L'explication est simple: quand les trois philosophes prennent en même temps leur fourchette gauche, ils attendent tous leur fourchette droite... qui se trouve être la fourchette gauche de leur voisin de droite.

On s'aperçoit que ce point mort est simplement dû à un cycle dans les demandes et attributions des ressources partagées. Essayons de formaliser un peu cela.

Construisons un graphe orienté (le ``graphe de requêtes'') dont les noeuds sont les ressources et dont les arcs sont comme suit. On a un arc d'un noeud a vers un noeud b si il existe un processus qui, ayant acquis un verrou sur a (sans l'avoir relaché), demande un verrou sur b. On étiquette alors cet arc par le nom du processus en question. Alors on peut facilement montrer que si le graphe de requêtes est acyclique alors le système constitué par les threads considérés ne peut pas rentrer en interblocage. En abstrayant le programme JAVA pour ne s'intéresser plus qu'aux suites de verrouillages et déverrouillages, on obtient les trois processus suivants en parallèle:
A=Pa;Pb;Va;Vb
B=Pb;Pc;Vb;Vc
C=Pc;Pa;Vc;Va
Un exemple en est donné à la figure 5.9, correspondant aux 3 philosophes, et ce graphe est bien cyclique.

On pouvait aussi s'en apercevoir sur le graphe d'avancement: le point mort est du à l'intersection de 3 (=nombre de processus) hyperrectangles, ou encore la concavité ``inférieure'' de la figure 5.11...mais cela nous entraînerait trop loin.


Figure 5.9: Le graphe de requêtes pour n philosophes.




Figure 5.10: Graphe d'avancement des 3 philosophes


Figure 5.11: Point mort des 3 philosophes


La condition sur les graphes de requêtes est une condition suffisante à l'absence de points morts, et non nécessaire comme le montre l'exemple suivant (où A, B et C sont encore 3 threads exécutés en parallèle):
A=Px;Py;Pz;Vx;Pw;Vz;Vy;Vw
B=Pu;Pv;Px;Vu;Pz;Vv;Vx;Vz
C=Py;Pw;Vy;Pu;Vw;Pv;Vu;Vv
dont on trouve le graphe de requêtes (fortement cyclique!) à la figure 5.12. Pour avoir une idée de pourquoi cette politique d'accès aux ressources partagées n'a pas de point mort, il faut regarder le graphe d'avancement, représenté à la figure 5.13. La région interdite est homéomorphe à un tore (plus ou moins sur l'antidiagonale du cube... c'est une image bien sûr!) et le chemin passant au milieu du tore n'est jamais stoppé par une concavité intérieure.


Figure 5.12: Graphe de requêtes pour l'exemple Lipsky/Papadimitriou.




Figure 5.13: Graphe de processus pour le terme de Lipsky et Papadimitriou.


Comment remédier au problème d'interblocage dans le cas des n philosophes? Il faut réordonnancer les accès aux variables partagées. Il y a beaucoup de solutions (éventuellement avec ordonnanceur extérieur). Il y en a en fait une très simple: on numérote les philosophes, par exemple dans le sens trigonométrique autour de la table. On impose maintenant que les philosophes de numéro pair acquièrent la fourchette gauche d'abord, puis la droite et aussi que les philosophes de numéro impair acquièrent la fourchette droite d'abord, puis la gauche. Cela donne (en terme de P et de V):
P1=Pa2;Pa1;Va2;Va1
P2=Pa2;Pa3;Va2;Va3
...
P2k=Pa2k;Pa(2k+1);Va2k;Va(2k+1)
P(2k+1)=Pa(2k+2);Pa(2k+1);Va(2k+2);Va(2k+1)
Le graphe de requêtes est décrit à la figure 5.14, on voit bien qu'il est acyclique, donc que le système de processus ne rencontre pas de points morts.


Figure 5.14: Le nouveau graphe de requêtes.


5.4.5  Sémaphores à compteur

On a parfois besoin d'objets qui peuvent être partagés par n processus en même temps et pas par n+1. C'est une généralisation évidente des sémaphores binaires (qui sont le cas n=1). Par exemple, on peut avoir à protéger l'accès à des tampons de messages de capacité n. On appelle les sémaphores correspondants, les sémaphores à compteur. Il sont en fait implémentables à partir des sémaphores binaires [Dij68], comme le fait le code de la figure 5.15.

public class essaiPVsup extends Thread {
    static int x = 3;
    Semaphore u;

    public essaiPVsup(Semaphore s) {
        u = s;
    }

    public void run() {
        int y;
        u.P();
        try {
            Thread.currentThread().sleep(100);
            y = x;
            Thread.currentThread().sleep(100);
            y = y+1;
            Thread.currentThread().sleep(100);
            x = y;
            Thread.currentThread().sleep(100);
        } catch (InterruptedException e) {};
        System.out.println(Thread.currentThread().
                           getName()+": x="+x);
        u.V(); }

    public static void main(String[] args) {
        Semaphore X = new Semaphore(2,"X");
        new essaiPVsup(X).start();
        new essaiPVsup(X).start();
    }
}

Figure 5.15: Utilisation de sémaphores à compteur.


Par exemple:
% java essaiPVsup
Thread-2: P(X)
Thread-3: P(X)
Thread-2: x=4
Thread-2: V(X)
Thread-3: x=4
Thread-3: V(X)
On voit bien que l'on n'a pas d'exclusion mutuelle.

Pour les tampons de capacité bornée cela peut servir comme on l'a déjà dit (problème du type producteur consommateur) et comme on le montre par un petit code JAVA à la figure 5.16.

public class essaiPVsup2 extends Thread {
    static String[] x = {null,null};
    Semaphore u;

    public essaiPVsup2(Semaphore s) {
        u = s;
    }

    public void push(String s) {
        x[1] = x[0];
        x[0] = s;
    }

    public String pop() {
        String s = x[0];
        x[0] = x[1];
        x[1] = null;
        return s; }

    public void produce() {
        push(Thread.currentThread().getName());
        System.out.println(Thread.currentThread().
                           getName()+": push");
    }

    public void consume() {
        pop();
        System.out.println(Thread.currentThread().
                           getName()+": pop"); }

    public void run() {
        try {
            u.P();
            produce();
            Thread.currentThread().sleep(100);
            consume();
            Thread.currentThread().sleep(100);
            u.V();
        } catch(InterruptedException e) {};
    }

    public static void main(String[] args) {
        Semaphore X = new Semaphore(2,"X");
        new essaiPVsup2(X).start();
        new essaiPVsup2(X).start();
        new essaiPVsup2(X).start();
    }
}

Figure 5.16: Producteur/consommateur, avec des sémaphores à compteur.


Dans cet exemple, on a 3 processus qui partagent une file à 2 cellules protégée (en écriture) par un 2-sémaphore. Chaque processus essaie de produire (push) et de consommer (pop) des données dans cette file. Pour que la file ne perde jamais de messages, il faut qu'elle ne puisse pas être ``partagée'' en écriture par plus de 2 processus en même temps.

Un exemple typique d'exécution est le suivant:
% java essaiPVsup2
Thread-2: P(X)
Thread-2: push
Thread-3: P(X)
Thread-3: push
Thread-2: pop
Thread-3: pop
Thread-2: V(X)
Thread-3: V(X)
Thread-4: P(X)
Thread-4: push
Thread-4: pop
Thread-4: V(X)

5.5  Barrières de synchronisation

Un autre mécanisme de protection, ou plutôt de synchronisation qui est couramment utilisé dans les applications parallèles est ce qu'on appelle une barrière de synchronisation. Son principe est que tout processus peut créer une barrière de synchronisation (commune à un groupe de processus) qui va permettre de donner un rendez-vous à exactement n processus. Ce point de rendez-vous est déterminé par l'instruction waitForRest() dans le code de chacun des processus. On en donne une implémentation (tirée du livre [OW00]) à la figure 5.17.

L'idée est d'utiliser un compteur du nombre de threads qu'il faut encore attendre (threads2wa- -it4) et de bloquer tous les processus par un wait tant que le quorum n'est pas atteint. On débloque alors tout le monde par un notifyAll. Le champ privé iex est là pour permettre de récupérer proprement les exceptions.

public class Barrier {
    private int threads2Wait4;
    private InterruptedException iex;

    public Barrier(int nThreads) {
        threads2Wait4 = nThreads;
    }

    public synchronized int waitForRest() 
        throws InterruptedException {
        int threadNum = --threads2Wait4;
        if (iex != null) throw iex;
        if (threads2Wait4 <= 0) {
            notifyAll();
            return threadNum;
        }
        while (threads2Wait4 > 0) {
            if (iex != null) throw iex;
            try {
                wait();
            } catch(InterruptedException ex) {
                iex = ex;
                notifyAll();
            }
        }
        return threadNum;
    }

    public synchronized void freeAll() {
        iex = new InterruptedException("Barrier Released 
                                        by freeAll");
        notifyAll();
    }
}

Figure 5.17: Implémentation d'une barrière de synchronisation en JAVA.


Un exemple d'utilisation typique est donné à la figure 5.18.

public class ProcessIt implements Runnable {
    String[] is;
    Barrier bpStart, bp1, bp2, bpEnd;
    public ProcessIt(String[] sources) {
        is = sources;
        bpStart = new Barrier(sources.length);
        bp1 = new Barrier(sources.length);
        bp2 = new Barrier(sources.length);
        bpEnd = new Barrier(sources.length);
        for (int i=0;i<is.length; i++) {
            (new Thread(this)).start(); } }

    public void run() {
        try {
            int i = bpStart.waitForRest();
            doPhaseOne(is[i]);
            bp1.waitForRest();
            doPhaseTwo(is[i]);
            bp2.waitForRest();
            doPhaseThree(is[i]);
            bpEnd.waitForRest();
        } catch(InterruptedException ex) {};
    }

    public void doPhaseOne(String ps) {
    }

    public void doPhaseTwo(String ps) {
    }

    public void doPhaseThree(String ps) {
    }

    static public void main(String[] args) {
        ProcessIt pi = new ProcessIt(args);
    }
}

Figure 5.18: Essai des barrières de synchronisation.


5.6  Un exemple d'ordonnancement: séquentialisation

Considérez le problème suivant. On a une base de données distribuée qui contient les réservations aériennes et hotelières d'une grande compagnie. Les clients réservent leurs billets au travers d'agences dans le monde entier, qui donc n'ont aucun moyen direct de se synchroniser. Les informations sur les réservations sont dans une mémoire d'ordinateur unique quelque part sur la planète. Supposons que nous ayons deux clients, Bill et Tom, les deux habitant Paris, et souhaitant prendre chacun deux places sur un avion pour New York. Supposons encore que ces deux clients veulent en fait exactement les mêmes vols et qu'il ne reste plus que deux places sur ce vol. Comment faire en sorte de servir ces deux clients de façon cohérente, c'est-à-dire que Bill ou Tom ait les deux places, mais pas seulement une partie (car sinon, ils ne voudraient pas partir du tout)?

Regardons le programme implémentant les requêtes de Bill et Tom de la figure 5.19.

public class Ticket {
    String nom;}

public class Requete extends Thread {
    Ticket Aller;
    Ticket Aller2;
    Semaphore u;
    Semaphore v;
    public Requete(Ticket t, Ticket s, 
                   Semaphore x, Semaphore y) {
        Aller = t;
        Aller2 = s;
        u = x;
        v = y; }

    public void run() {
        try {
            u.P();
            Thread.currentThread().sleep(100);
            if (Aller.nom == null)
                 Aller.nom = Thread.currentThread().
                                    getName();
            Thread.currentThread().sleep(100);
            u.V();
        } catch (InterruptedException e) {};
        try {
            v.P();
            Thread.currentThread().sleep(100);
            if (Aller2.nom == null)
                Aller2.nom = Thread.currentThread().
                                    getName();
            Thread.currentThread().sleep(100);
            v.V();
        } catch (InterruptedException e) {};
    }
}

public class Serial {
    public static void main(String[] args) {
        Semaphore a = new Semaphore(1,"a");
        Semaphore b = new Semaphore(1,"b");
        Ticket s = new Ticket();
        Ticket t = new Ticket();
        Requete Bill = new Requete(s,t,a,b);
        Requete Tom = new Requete(t,s,b,a);
        Bill.setName("Bill");
        Tom.setName("Tom");
        Bill.start();
        Tom.start();
        try {
            Tom.join();
            Bill.join();
        } catch(InterruptedException e) {};
        System.out.println("Le premier billet Paris->New York 
                            est au nom de: "+s.nom);
        System.out.println("Le deuxieme billet New York->Paris 
                            est au nom de: "+t.nom); } }

Figure 5.19: Base de donnée de billets d'avions.


Le résultat est:
% java Serial
Bill: P(a)
Tom: P(b)
Bill: V(a)
Tom: V(b)
Bill: P(b)
Tom: P(a)
Bill: V(b)
Tom: V(a)
Le premier billet Paris->New York est au nom de: Bill
Le deuxieme billet Paris->New York est au nom de: Tom
Ce qui n'est pas très heureux: en fait aucun des deux clients ne sera content car chacun pourra partir, mais seul! Ceci est du au fait que les demandes ont été entrelacées.

Il est facile de voir que le chemin d'exécution qui vient d'être pris correspond à un chemin sur la diagonale du graphe d'avancement (où les deux rectangles du centre représentent les états interdits):

qui ``mélange'' les transactions de nos deux utilisateurs.

Il existe plusieurs protocoles permettant d'atteindre un état plus cohérent de la base de données. Par exemple le protocole ``2-phase locking'' (voir [Abi00]) où chacun des deux clients essaie d'abord de verrouiller tous les billets voulus, avant d'y mettre son nom et de payer, puis de tout déverrouiller, permet cela. On dit que ce protocole est ``séquentialisable'', c'est à dire que tous les accès à la base de données distribuées se font comme si les deux clients étaient dans une même agence, et surtout dans une file ordonnée...

Quand on change dans Requete, l'ordre des verrous, dans la méthode run(), on obtient le programme de la figure 5.20 et l'exécution:

    public void run() {
        try {
            u.P();
            v.P();
            Thread.currentThread().sleep(100);
            if (Aller.nom == null)
                Aller.nom = Thread.currentThread().
                                   getName();
            Thread.currentThread().sleep(100);
            Thread.currentThread().sleep(100);
            if (Aller2.nom == null)
                Aller2.nom = Thread.currentThread().
                                    getName();
            Thread.currentThread().sleep(100);
            u.V();
            v.V();
        } catch (InterruptedException e) {};
    }

Figure 5.20: Une politique d'ordonnancement séquentialisable pour la base de données de billets d'avion.


% java Serial2
Bill: P(a)
Bill: P(b)
Bill: V(a)
Bill: V(b)
Tom: P(b)
Tom: P(a)
Tom: V(b)
Tom: V(a)
Le premier billet Paris->New York est au nom de: Bill
Le deuxieme billet Paris->New York est au nom de: Bill
qui ne satisfait vraiment que Bill mais qui au moins est cohérent!

Evidemment, il est aussi possible dans ce cas qu'une exécution donne également un interblocage:
% java Serial2
Bill: P(a)
Tom: P(b)
^C
On s'aperçoit que dans le cas de la figure 5.20, le graphe d'avancement interdit des chemins non séquentialisables, mais effectivement pas les points morts (les rectangles au centre sont des régions interdites):

Les seules obstructions sont ``au centre'': on peut déformer tout chemin sur l'un des bords, c'est à dire sur l'ensemble des chemins séquentiels. C'est là l'essence de la preuve géométrique de correction du protocole 2PL de [Gun94]. Pour enlever le point mort possible, il suffit de réordonnancer la demande de Bill ou de Tom, pour qu'elle soit dans le même ordre (cf. graphe de requêtes).


Previous Up Next