1   Parallélisme

Eric Goubault

Commissariat à l'Energie Atomique

Saclay

2   Plan du cours

3   Encore des comptes...

public class Compte {
    private int valeur;
    
    Compte(int val) {
        valeur = val;
    }
    
    public int solde() {
        return valeur;
    }

4  

  
    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;
    } }

5   La banque...

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

6  

            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!");

7  

    }

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

8  

        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();
    }
}

9   Une exécution

% 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! ...

10   Résultat...

11   Explication

(``Sémantique'')

12   Sémantique par entrelacements


13   Explication

Si les 2 threads tMari et tFemme sont exécutés de telle façon que dans retirer, chaque étape soit faite en même temps:

14   Une solution

15   Maintenant...

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

16   Résultat...

17   Peut on se passer de synchronized?

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) {}
        }
    }

18  

    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();
        } }

19  

    public static void main(String[] args) {
        Thread Un = new CS1();
        Thread Deux = new CS1();
        Un.setName("UN");
        Deux.setName("DEUX");
        Un.start();
        Deux.start();
    } }
Problème: exécution synchrone des threads!

20   wait() et notify()

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

21   Sémaphores

public class Semaphore {
    int n;
    String name;

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

22  

    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();
    }
}

23   Section Critique

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

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

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

24  

        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(); 
    }

25  

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

26   Résultat (sans P, V)

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

27   Résultat (avec P, V)

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

28   Un peu de sémantique

L'idée de base: ``Progress graphs'' (E.W.Dijkstra (1968))

T1=Pa.Pb.Vb.Va en parallèle avec T2=Pb.Pa.Va.Vb


``Image continue'': xi = temps local

Traces = chemins croissants dans chaque coordonnée = ``di-chemins''

29   Portée de synchronized

30   Pour être plus précis...

31   Pour être plus précis

33   En fait...

Actions de la mémoire principale (la JVM): Pour les types ``plus longs'' comme double et long, la spécification permet tout à fait que load, store, read et write soient non-atomiques.

34   Contraintes

Pour un thread donné:

35   Contraintes

Pour une variable donnée et un thread donné,

36   Exemples

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

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

  private Exemple1 E;  } 

37   Exemples

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

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

  private Exemple1 E;  } 

38   Exemples

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);  } } 

39   Exemples

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

  void F1() {
    a = b;  }

  void G1() {
    b = a;  }  }

40   Exemples

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

  synchronized void F2() {
    a = b;  }

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

41   Exécutions

> java Lance
a=2 b=2
> java Lance
a=1 b=1
> java Lance
a=2 b=1

42   Explication

Les chemins possibles d'exécution sont les entrelacements des 2 traces séquentielles:

pour le thread Essai1 et



pour le thread Essai2.

43   Explication

Appelons a1, b1 (respectivement a2 et b2) les copies locales des variables a et b pour le thread Essai1 (respectivement pour le thread Essai2):



44   Explication

Si on utilise la version synchronisée de Exemple1: Exemple2, alors on n'a plus que les deux premiers ordonnancements qui soient possibles.

45   Philosophes qui dînent


46   Philosophes qui dînent

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

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

47  

    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) {};
    }
}

48  

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();
    } }

49   Résultat

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

50   Interblocage

51   Explication

/* 3 philosophers ``3p'' */
A=Pa.Pb.Va.Vb
B=Pb.Pc.Vb.Vc
C=Pc.Pa.Vc.Va


52   Sémaphores d'ordre supérieur

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

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

53  

    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(); }

54  

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

55   Résultat

% 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)
Pas de protection!

56   Réel intérêt

Pour les tampons de capacité bornée (problème du type producteur consommateur):

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

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

57  

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

58  

    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) {};
    }

59  

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

60   Résultat

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

61   Complément: Priorités et Ordonnancement

62   Etats d'un thread

Un thread peut être dans l'un des 4 cas suivants:

63   Etats d'un thread

64   Etats d'un thread

65   Priorités

66   Processus démons

On peut également déclarer un processus comme étant un démon ou pas:

setDaemon(Boolean on);
boolean isDaemon();
``support'' aux autres (horloge, ramasse-miettes...). Il est détruit quand il n'y a plus aucun processus utilisateur (non-démon) restant

67   Ordonnancement tâches (cas 1 processeur)

68   Ordonnancement de tâches

69   En fait...

L'ordonnancement dépend aussi bien de l'implémentation de la JVM que du système d'exploitation sous-jacent; 2 modèles principaux:
This document was translated from LATEX by HEVEA.