1 Parallélisme

Eric Goubault

Commissariat à l'Energie Atomique

Saclay

2 Plan du cours

Présupposés; Qu'est-ce qu'un algorithme d'exclusion mutuelle?
Premiers essais
Algorithme de Dekker
``Algorithme de Hyman''
Algorithme de Perterson
Preuve de programme; application à Peterson
Peterson avec plus de 2 processeurs

3 Algorithmes d'exclusion mutuelle:

Algorithme d'exclusion mutuelle:

(A) si un thread se trouve en section critique, tout autre thread doit être en train d'exécuter une section non-critique.
(B) supposons qu'un groupe de thread I exécute du code dans une section non-critique, et ne requièrt pas encore d'accéder à une section critique. Supposons maintenant que tous les autres processus (groupe J) requièrent l'accès à une section critique, mais n'en n'ont pas encore obtenu la permission. Alors le processus qui doit rentrer en section critique doit appartenir à J, et cette permission ne doit pas pouvoir être reportée indéfiniment.

4 Conditions et présupposés

(C) un thread qui demande à entrer en section critique obtiendra toujours d'y rentrer au bout d'un temps fini (c'est une propriété d'équité qui permet d'éviter la famine d'un ou plusieurs processus).

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

Algorithme1, les processus ne peuvent entrer en section critique qu'à tour de rôle, ce qui est contredit (B) ( (A) et (C) sont vrais).
En fait, on peut prouver 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... (ici n=2, mais seulement une variable partagée, turn!).
Il faut s'arranger pour connaître l'état de chaque processus afin de prendre une décision.

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

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

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 fait que les deux processus bouclent indéfiniment, contredisant (B) et (C)!

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?

Il réalise bien l'exclusion mutuelle mais peut causer un interblocage si les deux processus s'exécutent de façon purement synchrone.
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.
Une solution est d'instaurer une règle de politesse entre les processeurs.

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

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.

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

On décore le code par des ``assertions'' écrites avec des prédicats logiques du premier ordre: pour un bloc I on écrira {p }I {q }.
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).

30 Liaison avec la sémantique

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 (c₁,...,c_n,E) où c_i (1 £ i £ n) est un point de contrôle du ième processus et E est un environnement.
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 (c₁,...,c_n,E) du système de transition tel que c_i=c alors P est vrai pour l'environnement E.

31 Règles de vérification

{p[x¬ u] }x=u {p }
{p₁ }(if B then {p₂}I₁ {q₂} else {p₃}I₂ {q₃}) {q₁ } si on a p₁ Ù B Þ p₂, p₁ Ù ¬ B Þ p₃, {p₂}I₁ {q₂}, {p₃}I₂{q₃}, q₂ Þ q₁ et q₃ Þ q₁.
{p₁}while B {{p₂}C {q₂}}{q₁} si on a p₁ Ù B Þ p₂, p₁ Ù ¬ B Þ q₁, {p₂}C {q₂}, q₂ Ù B Þ p₂ et q₂ Ù ¬ B Þ q₁

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

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

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

Chaque thread P_i parmi P₁,...,P_k a un compteur ci et des assertions A_i,k avant les instructions I_i,k de P_i (pour k variant sur l'ensemble des points de contrôle de P_i) utilisant éventuellement des prédicats aussi sur les autres compteurs ordinaux c1,...,ck.
Vérifier les conditions de non-interférences, quand I_j,l est une affectation x=u:
{(A_i,k Ù A_j,l)[x¬ u] }I_j,l {A_i,k}

36 Preuve de Peterson

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

2 variables auxiliaires after[0] et after[1] (qui servent à indiquer si le contrôle est après turn=t dans le code).
+ instructions after[0]=true, after[1]=true après respectivement turn=0 et turn=1.
Abbréviation I= [turn=1 ou turn=2].

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

{ 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

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é.
Améliorations possibles: algorithme de Burns (1981). Entièment symétrique qui minimise le nombre de variables utilisées ainsi que les valeurs qu'elles peuvent prendre en cours de programme.

This document was translated from L^AT_EX by H^EV^EA.

`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`	-	-