1  Parallélisme

Eric Goubault

Commissariat à l'Energie Atomique

Saclay

2  Plan du cours

3  Algorithmes d'exclusion mutuelle:

Algorithme d'exclusion mutuelle:

4  Conditions et présupposés

Lectures et écritures en mémoire: atomiques (vrai pour volatile et types pas longs...).

5  Première idée

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

6  Simulation

Tous les threads instance de CS1 ont ici la même exécution:

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

7  D'où

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

8  

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

9  

    public static void main(String[] args) {
        Thread Un = new CS1();
        Thread Deux = new CS1();
        Un.setName("UN");
        Deux.setName("DEUX");
        Un.start();
        Deux.start();
    } }
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!

10  Premiers algorithmes?

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

11  ExclusionMutuelle

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

12  Tache

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

13  

    private String name;
    private int id;
    private ExclusionMutuelle section;  }

14  Test

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

15  Mais...

16  Essai...

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

17  Essai...

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

    private volatile boolean[] flag = new boolean[2];
    }

18  Mais...

19  Autre essai...

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

20  

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

    private volatile boolean[] flag = new boolean[2];
    }

21  Bon?

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

23  

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

24  Conclusion...

25  Hyman (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;

26  

        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];  }
MAIS... 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!

27  Peterson (1981)

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;

28  

        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];  }
On a bien alors exclusion mutuelle sans interblocage et avec équité (pas de famine).

29  Preuve

30  Liaison avec la sémantique

31  Règles de vérification

32  Exemple

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

33  Preuve de non-interférence

34  Exemple

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

35  Preuve parallèle

36  Preuve de Peterson

On n'a pas besoin ici de numéroter toutes les instructions:

37  Assertions

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

38  Pour le 2ième processus...

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

39  Preuve de non-interférence

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;
turn=1; after[1]=true;

40  Mais...

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

41  Peterson général

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

42  

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

43  

    private volatile int[] turn;
    private int nproc;
    private volatile int[] flag;  }

44  Programme test

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

45  Remarques finales


This document was translated from LATEX by HEVEA.