Chapter 4    Coordination de processus

4.1  Problème

---

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 + " francs."); }

    public void ImprimeRecu() {
         if (nom.solde() > 0)
            System.out.println(Thread.currentThread().
              getName()+": Il vous reste " + nom.solde() + " francs.");
         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 4.1:

---

% java Banque
Conseiller Mari: Voici vos 100 francs.
Conseiller Femme: Voici vos 100 francs.
Conseiller Mari: Il vous reste 800 francs.
Conseiller Femme: Il vous reste 800 francs.
Conseiller Mari: Voici vos 200 francs.
Conseiller Femme: Voici vos 200 francs.
Conseiller Femme: Il vous reste 400 francs.
Conseiller Mari: Il vous reste 400 francs.
Conseiller Mari: Voici vos 300 francs.
Conseiller Femme: Voici vos 300 francs.
Conseiller Femme: Vous etes fauches!
Conseiller Mari: Vous etes fauches! ...

• S est un ensemble d'états,
• i Î S est l'``état initial'',
• E est un ensemble d'étiquettes,
• Tran Í S × E × S est l'ensemble des transitions. On note plus communément (s,t,s') Î Tran comme s ®^t s'.

• (x=expr;block,r) ®^x=expr (block,r[x® [ [ expr ] ](r)])
  où [ [ expr ] ] (r) dénote la valeur entière résultat de l'évaluation de l'expression expr dans l'environnement r (on ne donne pas les règles formelles évidentes qui donnent un sens précis à cela...).
• (if t then b₁ else b₂; b₃,r) ®^then (b₁; b₃,r)
  si [ [ t ] ] r = vrai sinon
  (if t then b₁ else b₂; b₃,r)®^else (b₂; b₃,r)
• (while t b₁; b₂,r) ®^while (b₁;while t b₁; b₂,r)
  si [ [ t ] ] r = vrai sinon
  (while t b₁; b₂,r) ®^while (b₂,r)

• A chaque P_j on associe par [ [ . ] ] défini plus haut un système de transition (S_j,i_j,E_j,Tran_j),
• On définit (S,i,E,Tran)=[ [ P₁ | ... | P_n ] ] par:
  • S=S₁ × ... × S_n,
  • i=(i₁,...,i_n),
  • E=E₁ È ... È E_n,

  • Tran=

    ì í î

    (s1,...,sj,...,sn) ®

    tj

    (s1,...,sj',...,sn) où

    sj ®

    tj

    sj' Î Tranj

    ü ý þ

4.2  Une solution: synchronized

public synchronized boolean retirer(int somme)

% java Banque
Conseiller Mari: Voici vos 100 francs.
Conseiller Mari: Il vous reste 800 francs.
Conseiller Femme: Voici vos 100 francs.
Conseiller Femme: Il vous reste 800 francs.
Conseiller Mari: Voici vos 200 francs.
Conseiller Mari: Il vous reste 400 francs.
Conseiller Femme: Voici vos 200 francs.
Conseiller Femme: Il vous reste 400 francs.
Conseiller Femme: Il vous reste 100 francs.
Conseiller Mari: Voici vos 300 francs.
Conseiller Mari: Il vous reste 100 francs.
Conseiller Femme: Il vous reste 100 francs.
Conseiller Mari: Il vous reste 100 francs...

   synchronized(obj) {
      BLOCK }

4.3  Moniteurs

4.4  Sémaphores

4.4.1  Sémaphores binaires

---

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 4.2:

---

---

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 4.3:

---

% java essaiPV
Thread-2: x=4
Thread-3: x=4

% java essaiPV
P(X)
Thread-2: x=4
V(X)
P(X)
Thread-3: x=5
V(X)

4.4.2  Un peu de sémantique

• On rajoute dans l'ensemble d'états S du système de transitions une composante nouvelle qui est une fonction k: VARIABLE ® {0,1}. Donc S=(S₁,...,S_n,k). Cette fonction k represente le fait de savoir si chaque variable est verrouillée par un processus ou non,
• i=(P₁,...,P_n,k₀) où k₀ est la fonction qui donne uniformément 1,
• E contient maintenant les nouvelles actions Px et Vx pour toutes les variables x du programme,
• On a de nouvelles transitions dans Tran de la forme:
  (b₁,...,Px;b_j,...,b_n,k) ®^Px (b₁,...,b_j,...,b_n,k')
  si k(x)=1; et alors k'(y)=k(x) pour tout y ¹ x et k'(x)=0, et,
  (b₁,...,Px;b_j,...,b_n,k) ®^Vx (b₁,...,b_j,...,b_n,k')
  avec k'(y)=k(x) pour tout y ¹ x et k'(x)=1.

A=Pa;Pb;Va;Vb
B=Pb;Va;Vb;Va

4.4.3  Un complément sur la JVM

• les actions qu'un thread peut exécuter sont:
  • use transfère le contenu de la copie locale d'une variable à la machine exécutant le thread.
  • assign transfère une valeur de la machine exécutant le thread à la copie locale d'une variable de ce même thread.
  • load affecte une valeur venant de la mémoire principale (après un read, voir plus loin) à la copie locale à un thread d'une variable.
  • store transfère le contenu de la copie locale à un thread d'une variable à la mémoire principale (qui va ainsi pouvoir faire un write, voir plus loin).
  • lock réclame un verrou associé à une variable à la mémoire principale.
  • unlock libère un verrou associé à une variable.
• les actions que la mémoire principale (la JVM) peuvent exécuter sont:
  • read transfère le contenu d'une variable de la mémoire principale vers la mémoire locale d'un thread (qui pourra ensuite faire un load).
  • write affecte une valeur transmise par la mémoire locale d'un thread (par store) d'une variable dans la mémoire principale.

---

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 4.4:

---

---

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

  void F1() {
    a = b; 
  }

  void G1() {
    b = a;
  }
}

Figure 4.5:

---

---

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

  synchronized void F2() {
    a = b; 
  }

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

Figure 4.6:

---

> java Lance
a=2 b=2

> java Lance
a=1 b=1

> java Lance
a=2 b=1

4.4.4  Quelques grands classiques

---

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 4.7:

---

% java Dining
Kant: P(a)
Heidegger: P(b)
Spinoza: P(c)
^C

A=Pa;Pb;Va;Vb
B=Pb;Pc;Vb;Vc
C=Pc;Pa;Vc;Va

---

Figure 4.8: Le graphe de requêtes pour les 3 philosophes.

---

---

Figure 4.9: Point mort des 3 philosophes

---

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

---

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

---

---

Figure 4.11:

---

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)

---

Figure 4.12: Le nouveau graphe de requêtes.

---

4.4.5  Sémaphores à compteur

---

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 4.13:

---

% 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)

---

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 4.14:

---

% 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)

4.5  Barrières de synchronisation

---

    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 4.15:

---

---

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 4.16:

---

4.6  Un exemple d'ordonnanceur: séquentialisation

---

public class Ticket {
    String nom;}

public class Requete extends Thread {
    Ticket Aller;
    Ticket Retour;
    Semaphore u;
    Semaphore v;
    public Requete(Ticket t, Ticket s, 
                   Semaphore x, Semaphore y) {
        Aller = t;
        Retour = 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 (Retour.nom == null)
                Retour.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 billet Paris->New York 
                            est au nom de: "+s.nom);
        System.out.println("Le billet New York->Paris 
                            est au nom de: "+t.nom); } }

Figure 4.17:

---

% 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 billet Paris->New York est au nom de: Bill
Le billet New York->Paris est au nom de: Tom

---

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

Figure 4.18:

---

---

    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 (Retour.nom == null)
                Retour.nom = Thread.currentThread().
                                    getName();
            Thread.currentThread().sleep(100);
            u.V();
            v.V();
        } catch (InterruptedException e) {};
    }

Figure 4.19:

---

% 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 billet Paris->New York est au nom de: Bill
Le billet New York->Paris est au nom de: Bill

% java Serial2
Bill: P(a)
Tom: P(b)
^C

• elle permet d'assurer la persistence de certains objets,
• elle est utilisée en particulier pour les entrées sorties