Chapter 5 Algorithmes d'exclusion mutuelle (mémoire partagée)
5.1 Peut-on se passer de synchronized?
On cherche à programmer un mécanisme d'``exclusion mutuelle'', en mémoire partagée,
à
partir des primitives que l'on a vu, sauf les primitives
de synchronisation synchronized
ainsi que wait et notify. On doit évidemment avoir
une hypothèse de base sur la sémantique du système sous-jacent. On ne
va imposer comme condition que le fait que la lecture et écriture en
mémoire est atomique c'est à dire que plusieurs lectures et
écritures en parallèle sont en fait exécutées séquentiellement dans
un ordre à priori quelconque. Remarquer que c'est le cas en JAVA (on va
le supposer en tout cas), au moins
pour des types scalaires comme int mais pas long!
On veut donc pouvoir
faire en sorte qu'un thread impose à tous les autres d'être l'unique
à s'exécuter (pendant que les autres attendent leur tour).
En fait, on pourra se déclarer content d'un algorithme d'exclusion mutuelle
seulement s'il satisfait les conditions suivantes:
- (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 qui 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.
- (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).
La première
idée qui vienne à l'esprit
est de rajouter aux threads considérés 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.
Pour simuler l'algorithme, on fait en sorte que tous
les threads instance de CS1 aient la même exécution:
public void run() {
while(true) {
AttendtonTour();
System.out.println("C'est le tour de "+
Thread.currentThread().getName());
RendlaMain();
}
}
On en arrive au code naturel de la figure 5.1.
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) {}
}
}
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();
} }
public static void main(String[] args) {
Thread Un = new CS1();
Thread Deux = new CS1();
Un.setName("UN");
Deux.setName("DEUX");
Un.start();
Deux.start();
} }
Figure 5.1:
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!
5.2 Premiers algorithmes?
Continuons sur l'idée de la dernière section, et
essayons de programmer une première approximation
de code permettant d'assurer l'exclusion mutuelle. Intéressons-nous
d'abord à un premier cas dans lequel on a seulement
deux processus P0 et P1.
L'idée est
d'assurer que l'on ne puisse jamais être en même temps dans
certaine partie du code (appelée section critique) pour P0 et
P1.
Le premier code auquel on puisse penser
pour Pi est (i=0,1, j=(i+1) mod 2) est montré à la figure 5.2.
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;
}
Figure 5.2:
Remarquer que l'entier turn est déclaré en volatile c'est à
dire qu'il est susceptible d'être modifié à tout moment par l'extérieur
(un autre thread par exemple). Cela empêche javac de le placer
dans un registre en cours d'exécution, pour optimiser le code (ce serait
en l'occurrence une optimisation fausse dans notre cas!).
Ce code est une instance de la classe abstraite ExclusionMutuelle de la
figure 5.3.
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);
}
Figure 5.3:
Pour tester cet algorithme, on utilise des taches très simples, simulant
l'entrée et la sortie d'une section critique, voir figure 5.4.
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();
}
}
private String name;
private int id;
private ExclusionMutuelle section;
}
Figure 5.4:
Et enfin on utilise un main qui crée et lance deux tâches, voir figure 5.5.
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();
}
}
Figure 5.5:
Mais
avec Algorithme1, les processus
ne peuvent entrer en section critique qu'à tour
de rôle, ce qui est contredit (B) (mais il est vrai que cet algorithme
satisfait à (A) et (C), si on suppose que chaque section critique se déroule
en temps fini).
En fait, on peut prouver (voir [Lyn96])
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, donc il est clair qu'il faut un peu
compliquer le code précédent (n=2, mais seulement une variable partagée,
turn!).
Pour résoudre la difficulté précédente, il faut s'arranger pour
connaître l'état de chaque processus afin de
prendre une décision. Un essai de solution serait le code de la figure 5.6.
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();
}
public void Vmutex(int t) {
flag[t] = false;
}
private volatile boolean[] flag = new boolean[2];
}
Figure 5.6:
Si on remplace INIT par false on s'aperçoit que la condition
(A)
d'exclusion mutuelle n'est pas satisfaite!
Pour s'en convaincre il suffit de considérer l'exécution suivante:
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 (synchrone)
fait que les deux processus bouclent indéfiniment, contredisant (B) et (C)!
On propose alors le code de la figure 5.7, toujours plus compliqué...
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;
}
public void Vmutex(int t) {
flag[t] = false;
}
private volatile boolean[] flag = new boolean[2];
}
Figure 5.7:
Il réalise bien l'exclusion mutuelle mais
peut causer un interblocage si les deux processus s'exécutent
de façon purement synchrone. A ce moment là,
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.
Tout cela paraît sans issue. En fait,
une solution est d'instaurer une règle de politesse entre les processeurs.
C'est l'algorithme de Dekker (1965), à la figure 5.8.
5.3 Algorithme de 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;
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];
}
Figure 5.8:
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.
Considérons le code plus simple de la figure 5.9, proposé par Hyman en 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;
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];
}
Figure 5.9:
Il est malheureusement faux car,
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!
Une vraie amélioration de l'algorithme de Dekker est
l'algorithme de Peterson proposé en 1981.
5.4 Algorithme de Peterson
Contentons nous d'abord du cas simple où l'on dispose uniquement de
deux tâches zero et un. Le code
des deux tâches est donné à la figure 5.10.
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;
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];
}
Figure 5.10:
On a bien alors exclusion mutuelle sans interblocage et
avec équité (pas de famine).
Donnons ici quelques idées de preuve de cet algorithme.
On va décorer le code par des ``assertions'' écrites avec
des prédicats logiques du premier ordre, portant sur les valeurs des variables
du programme (et donc également de celles que l'on vient d'introduire),
avec comme prédicats l'égalité avec des constantes (cela nous suffira
ici). Ces assertions seront introduites entre deux instructions consécutives, c'est
à dire qu'elles seront associées à chaque point de contrôle de chaque
processus.
On va introduire, de façon intuitive et pas trop formelle, une méthode
de raisonnement et de preuve sur des processus parallèles (disons, en nombre
n) en mémoire partagée
due à l'origine à S. Owicki et D. Gries [OG75].
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).
Cela veut dire la chose suivante. Soit 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 (c1,...,cn,E) où ci (1 £ i £ n) est
un point de contrôle du ième processus et E est un environnement, c'est
à dire une fonction qui à chaque variable du programme associe une valeur.
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 (c1,...,cn,E) du système
de transition tel que ci=c alors P est vrai pour l'environnement E.
L'idée est que l'on veut pouvoir inférer quand c'est possible, ou tout du
moins vérifier que les assertions que l'on rajoute dans le code de chacun des
processus dit bien des choses vraies sur toutes les exécutions possibles du
code.
Soit I une instruction ou un block d'instructions JAVA. On rajoute des
assertions décrivant ce qui se passe avant et après le code I en
écrivant {p }I {q }.
On a les règles suivantes, pour un fragment de JAVA, qui va nous suffire
pour le moment:
{p[x¬ u] }x=u {p }
{p1 } |
( |
if B then {p2}I1 {q2} else
{p3}I2 {q3} |
) |
{q1 } |
si on a,
p1 Ù B Þ p2 |
p1 Ù ¬ B Þ p3 |
{p2}I1 {q2} |
{p3}I2{q3} |
q2 Þ q1 |
q3 Þ q1 |
{p1}while B |
{ |
{p2}C {q2} |
} |
{q1} |
si on
a,
p1 Ù B Þ p2 |
p1 Ù ¬ B Þ q1 |
{p2}C {q2} |
q2 Ù B Þ p2 |
q2 Ù ¬ B Þ q1 |
Par exemple (voir [Win93]), le système suivant est un système
d'assertions correctes:
{ 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}
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! Cela s'appelle la preuve de non-interférence.
Attention car on suppose ici que les affectations sont atomiques (ce sera
vrai en JAVA dans la suite pour les affectations de constantes, ce qui sera
le seul cas intéressant pour nous; sinon il faudrait décomposer les
affectation en load, store etc. comme expliqué précédemment).
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é. Sans cela, la méthode est
fausse (en fait, l'article d'origine de S. Owicki et de D. Gries comportait
cet oubli). Par exemple, on devrait transformer la preuve précédente
en:
{ 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}
c représente le point de contrôle courant, numéroté de façon
fort logique de 1 à 5 ici.
On va donc supposer que chaque thread Pi parmi P1,...,Pk a un compteur
ci et des assertions Ai,k avant les instructions
Ii,k de Pi (pour k variant sur l'ensemble
des points de contrôle de Pi) utilisant éventuellement des prédicats
aussi sur les autres compteurs ordinaux
c1,...,ck. Alors il faut vérifier les conditions dites
de non-interférences suivantes, quand Ij,l est une affectation x=u:
{(Ai,k Ù Aj,l)[x¬ u] }Ij,l {Ai,k}
On peut simplifier un peu cela dans le cas qui nous préoccupe, car
on n'a qu'une affectation sur un objet partagé, donc on n'a pas besoin de numéroter
toutes les instructions.
Introduisons deux variables auxiliaires after[0] et
after[1] (qui servent à
indiquer si le contrôle est après turn=t
dans le code).
Rajoutons également les instructions after[0]=true,
after[1]=true après respectivement turn=0 et turn=1.
En utilisant l'abbréviation I= [turn=1 ou turn=2] on commente le code
avec les assertions comme à la figure 5.11.
{ 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;
Figure 5.11:
De même pour le deuxième processus, à la figure 5.12.
{ 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;
Figure 5.12:
Il est relativement aisé de se convaincre ces assertions forment
bien un shéma de preuve correct de chacun des processus pris séquentiellement.
Seule subsiste la preuve de non-interférence.
En fait, seul,
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;
et
turn=1; after[1]=true;
Or,
{ 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.
Remarquez qu'il existe une
généralisation de l'algorithme de Peterson à n processeurs.
C'est le programme de la figure 5.13, codé sur chacun des n processeurs (liste[0] à liste[nproc-1]).
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; }
}
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;
}
private volatile int[] turn;
private int nproc;
private volatile int[] flag;
}
Figure 5.13:
Il faut évidemment légèrement changer le programme de test (ici pour 5 tâches), voir
figure 5.14.
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();
}
}
}
Figure 5.14:
En fait 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é.
Dans les améliorations possibles, il y a en particulier
l'algorithme de Burns (1981). C'est une solution entièment symétrique
qui minimise
le nombre de variables utilisées ainsi que les valeurs qu'elles peuvent
prendre en cours de programme.