T rès souvent, on doit exécuter plusieurs instructions
simultanément, ceci pour plusieurs raisons. D'abord, il existe des
machines avec plusieurs processeurs de calcul, et il faut bien les
programmer. Ensuite, de nombreux programmes contrôlent des
automatismes réagissant à des événements asynchrones (programmation
réactive). C'est le cas des jeux dont les programmes réagissent à
plusieurs boutons que l'on peut actionner dans des ordres
imprévisibles. De même, dans les systèmes embarqués, on réagit aux
informations fournies régulièrement par des capteurs. Une autre forte
raison à la programmation concurrente est la recherche de la
diminution des temps de latence. Par exemple, si un programme
controle des claviers ou des périphériques lents, il ne faut pas
bloquer tout un système dans l'attente d'événements très peu
fréquents. Plus généralement, si on croit que les ordinateurs simulent
les humains, on remarque que ces derniers ont un comportement
concurrent. Par exemple, on n'arrête pas le fonctionnement de son
coeur pour lire ces notes de cours. Une autre raison pour
s'intéresser au comportement concurrent des programmes est la
multiplicité des utilisateurs d'un système informatique. De même, sur
un réseau informatique, un grand nombre d'activités ou d'utilisateurs
co-existent. Si on écrit un programme de gestion du réseau, on doit
pouvoir traiter l'exécution simultanée de plusieurs tâches. Une
dernière raison de s'intéresser aux programmes parallèles est qu'on
peut obtenir un facteur d'accélération, puisqu'avec plus de puissance
de calcul on peut résoudre plus rapidement un problème. Si cet
argument est vrai dans le principe et fait l'objet de l'algorithmique
parallèle, il faut remarquer que le facteur d'accélération ne dépasse
jamais le nombre de processeurs exécutant ce programme. Souvent il
est moindre, car une certaine synchronisation est nécessaire entre les
diverses tâches s'exécutant en parallèle.
Toutes ces raisons attestent du besoin d'exprimer la concurrence par
programme. Dans ce chapitre, nous introduisons les notions de base
de la concurrence: processus, sémaphores, conditions, et
problèmes d'ordonnancement.
Un processus (thread) est un programme qui s'exécute. Un
programme est le texte décrivant une suite d'instructions. Un
processus correspond à l'action de l'exécuter. Jusqu'à présent aucune
distinction n'était faite, car on ne considérait qu'un seul
processus. Dans ce chapitre, comme il sera toujours question de
plusieurs processus, la distinction devient importante et on remarque,
par exemple, que plusieurs processus peuvent exécuter un même
programme.
La partie concurrente de Java correspond à l'interface standard des
bibliothèques de processus POSIX (the Portable Operating System
Interface), qui existent actuellement sur pratiquement tous les
systèmes et toutes les architectures matérielles. Certaines
caractéristiques comme le style en programmation par objets sont plus
spécifiques à Java.
Voici un programme qui démarre comme d'habitude par la fonction main, puis qui crée deux processus t1 et t2 exécutant en
parallèle la méthode run de la classe Code. Cette
méthode imprime continuellement le numéro du processus courant, puis
laisse un autre processus s'exécuter, puis recommence l'impression du
processus courant, etc.
class Code implements Runnable {
public void run () {
while (true) {
System.out.println ("Bonjour de " + Thread.currentThread());
Thread.yield();
}
}
public static void main (String[ ] args) {
Code p = new Code();
Thread t1 = new Thread(p);
Thread t2 = new Thread(p);
t1.start(); t2.start();
}
} |
Figure 6.1 : Exécution concurrente de trois processus
L'interface Runnable ne contient que la méthode run qui
est appelée au lancement d'un processus. Le constructeur des
processus (Thread) prend un objet de la classe Runnable
et le transforme en processus. Le lancement des processus t1 et
t2 se fait en appelant la méthode start. Les deux processus
t1 et t2 exécutent le même code p. La fonction statique currentThread donne la valeur du processus courant. On peut aussi
ré-écrire le programme en style programmation par objets, style plus
simple, mais qui donne moins de latitude sur la hiérarchie des classes
utilisées:
class Code1 extends Thread {
public void run () {
while (true) {
System.out.println ("Bonjour de " + this);
Thread.yield();
}
}
public static void main (String[ ] args) {
Thread t1 = new Code1();
Thread t2 = new Code1();
t1.start(); t2.start();
}
} |
Remarquer le remplacement de currentThread en this, puisque this est alors le processus en cours
d'exécution.
Le programme précédent comporte trois processus: le processus
correspondant au programme principal démarrant par la fonction main, les deux processus créés t1 et t2. Un processus s'exécute
sur un processeur. Un processeur est une entité matérielle de
calcul. Tout ordinateur contient au moins un processeur. Pour que
trois processus puissent s'exécuter concurremment, il faudrait au
moins trois processeurs. Or bien souvent les machines actuelles n'ont
qu'un seul processeur. L'environnement d'exécution simule alors
l'existence des trois processeurs demandés, en attribuant par exemple
périodiquement une tranche de temps à chacun des trois processus,
comme illustré sur la figure 6.2. Nous
reviendrons plus tard sur les stratégies d'allocation de temps pour
les processus. Pour l'instant, nous ne considérons que la fonction
yield qui cède le processeur sur lequel le processus tourne et
donne plus de chance aux autres processus de s'exécuter immédiatement.
Figure 6.2 : Exécution concurrente de trois processus sur un processeur
Dans la terminologie officielle des systèmes d'exploitation, nos
processus (threads) sont plutôt appelés des processus
légers (light-weight processes). Les processus (lourds) sont
les processus gérés directement par le système d'exploitation (Unix,
Linux, Windows). Dans le système Unix, on obtient leur liste par la
commande ps ou psaux. Un processus lourds
peut générer plusieurs processus légers, qui sont donc gérés par un
sous-système, par exemple par l'interpréteur de programmes Java (la
Java Virtual Machine --- JVM). Les processus sont dits légers
car basculer d'un processus à un autre est censé être une opération
peu coûteuse. On dit alors que le changement de contexte est
rapide. Du point de vue de la programmation, la principale différence
entre processus lourds et légers concerne la mémoire: les processus
légers partagent la zone mémoire, les processus lourds possèdent leur
propre mémoire. De toutes façons, ici, comme nous ne nous soucions pas
du système d'exploitation sous-jascent, les processus légers sont
simplement appelés des processus.
Un processus peut se terminer spontanément. On peut aussi vouloir
l'arrêter depuis un autre processus. Dans l'exemple précédent, le
processus principal s'arrêtait juste après avoir lancé le processus
t2. Les processus t1 et t2 eux ne s'arrêtaient pas et
continuaient leur exécution indéfiniment. Cela n'est pas trop
grave, puisqu'on peut toujours continuer à faire d'autres tâches en
parallèle. Pourtant, en utilisant la fonction interrupt qui lève
l'exception InterruptedException, on peut interrompre
l'exécution d'un processus comme indiqué dans le programme suivant:
class Exemple1 implements Runnable {
public void run () {
try {
while (true) {
System.out.println ("Bonjour de " + Thread.currentThread());
Thread.sleep (1000); // Une seconde de pause
}
} catch (InterruptedException e) { }
}
public static void main (String[ ] args) {
Thread t = new Thread (new Exemple1());
t.start();
t.interrupt();
}
} |
La fonction sleep arrête l'exécution d'un processus
pendant le nombre de millisecondes données en argument. On l'utilise
ici pour faire une pause entre deux impressions. Sur notre exemple,
on constate que le processus t n'est pas arrêté brutalement depuis
un autre processus puisqu'une exception lui est simplement
envoyée. C'est le processus t qui gère sa propre terminaison. Ainsi
les invariants logiques de t sont préservés, et le processus t
peut se terminer dans un état cohérent.
Un processus peut aussi tester régulièrement s'il n'est pas
interrompu, au lieu d'attendre une exception. Pour cela, il fait
une attente active sur la fonction booléenne isInterrupted de
la bibliothèque standard de Java:
class Exemple2 extends Thread {
public void run () {
while (!isInterrupted()) {
System.out.println ("Bonjour de " + this);
}
}
public static void main (String[ ] args) {
Thread t = new Exemple2();
t.start();
t.interrupt();
}
} |
Un processus attend souvent la fin d'un autre processus. Par exemple,
on lance un processus t et on attend qu'il finisse. Cela peut se
réaliser en utilisant la fonction join qui prend en argument un
délai maximum d'attente en millisecondes (0 si ce délai est
infini). Ainsi:
class Exemple3 extends Thread {
public void run () {
System.out.println ("Bonjour de " + this);
}
public static void main (String[ ] args)
throws InterruptedException {
Thread t = new Exemple3();
t.start();
t.join (0);
}
} |
La méthode join lance une exception si un autre processus a
interrompu le processus courant (qui est en attente).
Nous avons donc considéré la création, le lancement et l'arrêt des
processus. Ceci constitue l'essentiel si les processus ne communiquent
pas entre eux. Mais c'est rarement le cas, puisque si plusieurs
activités sont menées en parallèle, c'est souvent pour calculer un
résultat commun ou partager certaines informations. Le reste du
chapitre décrit la synchronisation nécessaire pour communiquer entre
processus. Plusieurs modèles standards existent pour cette
communication. Ici nous allons considérer le modèle simple de la
mémoire partagée.
Dans le programme suivant, la variable globale x de la classe P
peut être modifiée par les deux processus t1 et t2. Comme ces
deux processus s'exécutent en parallèle, il est dûr de prédire la
valeur de x imprimée dans main: 0, 23, 7 ou autre chose?
class P {
static int x = 0;
public static void main (String args[ ])
throws InterruptedException {
Thread t1 = new P1(), t2 = new P2();
t1.start(); t2.start();
while (true) {
System.out.println (x);
Thread.sleep (1000);
} } }
class P1 extends Thread {
public void run () {
while (true) {
P.x = 23;
Thread.yield();
} } }
class P2 extends Thread {
public void run () {
while (true) {
P.x = 7;
Thread.yield();
} } } |
Pour répondre à cette question, il faut comprendre l'atomicité
des instructions et l'ordonnancement des processus. Une instruction
est atomique si elle ne peut être interrompue pour laisser l'exécution
à un autre processus. Très peu d'instructions sont atomiques au niveau
du langage de programmation puisque chaque instruction correspond à
plusieurs instructions machine exécutées par le processeur. Toutefois
on peut dire que la lecture ou de l'écriture d'un mot (de 32 bits)
dans la mémoire d'un ordinateur est atomique. Au niveau de Java, on
peut donc dire que l'écriture d'un entier dans une variable et que la
lecture de la valeur d'une variable entière sont atomiques.
Cependant, cela n'est plus vrai pour les entiers longs (de 64 bits) ou
pour les flottants en double précision (double), sauf si on
dispose d'un processeur 64 bits.
Par ailleurs, on ne peut prédire l'ordre dans lequel t1 ou t2
modifient la variable partagée x. Cela dépend de l'ordonnancement
des processus t1, t2 et de celui exécutant main. Cet ordre
peut varier entre deux exécutions du même programme. La seule
conclusion à retenir est que les programmes concurrents sont souvent
non déterministes. Ils peuvent donner des résultats différents
sur les mêmes données dans deux exécutions distinctes. Ce phénomène
rend particulièrement délicate la programmation de processus concurrents.
Une section critique rend atomique un ensemble d'instructions,
par exemple pour modifier plusieurs données ou une donnée composite,
tout en maintenant des invariants. Prenons l'exemple classique du
transfert d'argent entre deux comptes bancaires, on veut que la somme
des deux comptes reste constante, même si plusieurs appels de la
fonction transfertVersB sont faits simultanément dans des
processus distincts. Pour cela, il suffit interdire l'exécution de
cette fonction pendant qu'un autre processus l'exécute. C'est ce que
fait le qualificatif synchronized qui contrôle l'accès à une
section critique:
class ComptesBancaires {
private int compteA, compteB;
synchronized void transfertVersB (int s) {
compteA = compteA - s;
compteB = compteB + s;
}
} |
Le corps de la fonction transfertVersB est une section critique
qui doit s'exécuter en exclusion mutuelle. Les exécutions de
cette fonction sont donc sérialisées, c'est-à-dire faites
séquentiellement, puisqu'on garantit qu'un seul appel de cette
fonction s'exécute au plus à un moment donné. Pour cela, le processus,
qui appelle une méthode avec le qualificatif synchronized, doit
obtenir un verrou sur cette fonction. Si le verrou est déjà pris par
ce processus ou par un autre, l'appel est suspendu jusqu'à ce que le
verrou soit disponible. En Java, comme tout est objet, les verrous
sont associés à des objets: une méthode synchronisée doit prendre le
verrou sur l'objet dont elle est une méthode. Il n'y a qu'un verrou
par objet. Si deux méthodes d'un même objet sont synchronisées, elles
s'excluent donc mutuellement. Par conséquent, une méthode synchronisée
au plus peut être appelée simultanément sur un même objet. Mais une
même méthode peut être appelée simultanément sur deux objets
différents, car les deux appels prennent alors un verrou différent sur
chaque objet. Pour les méthodes statiques, une méthode statique prend
un verrou associée à toute la classe si elle est synchronisée.
Finalement, remarquons que seules les méthodes peuvent avoir le
mot-clé synchronized, les champs de données ne peuvent avoir ce
qualificatif. Il est toutefois possible de rendre atomique un
ensemble d'instructions, plutôt que le corps d'une fonction. Alors il
faut donner en argument l'objet sur lequel on veut prendre le verrou.
Cette forme de section critique permet de faire une section
critique plus finement que sur des appels de méthodes.
class ComptesBancaires {
private int compteA, compteB;
void transfertVersB (int a) {
...
synchronized (this) {
compteA = compteA - s;
compteB = compteB + s;
}
...
}
} |
Il est possible de prendre plusieurs verrous pour exécuter un bout de
programme. Mais créer des sections critiques demande un peu
d'attention, puisque des interblocages (deadlocks) sont
possibles. Ainsi dans:
class P1 extends Thread {
public void run () {
synchronized (a) {
synchronized (b) {
...
} } } }
class P2 extends Thread {
public void run () {
synchronized (b) {
synchronized (a) {
...
} } } } |
Si deux processus t1 et t2 exécutent les codes de P1 et P2
en parallèle, le processus t1 peut prendre le verrou sur a; le
processus t2 peut alors prendre le verrou sur b, et il y a un
interblocage, puisque les deux verrous sont pris et que chaque
processus attend la libération d'un verrou pris par l'autre
processus. Détecter les interblocages peut être très complexe, c'est
un des problèmes standards des systèmes concurrents. Souvent un tel
système s'arrête à cause d'un tel interblocage.
Exercice 33
Faire un exemple d'interblocage avec des appels sur des
méthodes synchronisées.
Un paradigme de la programmation concurrente est celui de la file
d'attente concurrente. Pour simplifier, supposons que la longueur
maximale de la file vaut 1. Alors la file ne peut qu'osciller entre
les deux états: vide ou plein. Les deux méthodes ajouter et supprimer peuvent s'exécuter de manière concurrente. On pourrait être
tenté d'écrire:
class FIFO {
boolean pleine;
int contenu;
FIFO () { pleine = false; }
synchronized void ajouter (int x) {
if (pleine)
// Attendre que la file se vide
contenu = x;
pleine = true;
}
synchronized int supprimer () {
if (!pleine)
// Attendre que la file devienne pleine
pleine = false;
return contenu;
}
} |
La fonction ajouter attend que la file se vide, la fonction supprimer attend que la file se remplisse. Ces deux opérations
s'excluent mutuellement pour que les variables internes de la file
(contenu, pleine) restent dans un état cohérent. Mais ce
code ne fonctionne pas, puisqu'un ajout dans une file pleine prend le
verrou et interdit à quiconque de vider la file. Dans chacun des cas
d'attente, la fonction devrait relâcher le verrou pour que l'autre
processus puisse s'exécuter. Il faut donc ressortir de chaque méthode
sans se bloquer et revenir tester la file. C'est alors une attente
active (busy wait) qui coûte cher en temps. Il est préférable
d'utiliser le concept de condition dû à Hoare. Une condition
est associée à un verrou. Quand on attend sur une condition, on
relâche atomiquement le verrou et on attend un signal sur la
condition. Quand il y a notification d'un signal sur la condition, on
reprend le verrou (si possible) et on redémarre à l'endroit où on
s'était mis en attente.
En Java, une condition est une simple référence à un objet (son
adresse). Il n'y a qu'une seule condition par objet (ce qui est une
solide restriction). On peut attendre sur la condition d'un objet dont
on a déjà pris le verrou. L'exemple précédent s'écrit donc
précisément:
synchronized void ajouter (int x)
throws InterruptedException {
while (pleine)
wait();
contenu = x;
pleine = true;
notify();
}
synchronized int supprimer ()
throws InterruptedException {
while (!pleine)
wait();
pleine = false;
notify();
return contenu;
} |
Les fonctions wait et notifiy sont deux méthodes de la
classe Object. Tous les objets possèdent ces deux méthodes
puisque toute classe est une sous-classe de Object. La méthode
wait attend sur la condition et relâche le verrou de l'objet
correspondant à la condition. Si ce verrou n'est pas pris, l'exception
IllegalMonitorStateException est levée. (Cette exception est
une exception du système d'exécution, c'est-à-dire sous-classe de RuntimeException; il n'est pas nécessaire de la mentionner dans la
signature des fonctions ajouter et supprimer). La
méthode notify met dans l'état prêt à l'exécution un des
processus en attente sur cette condition. Quand celui-ci repart, il
reprend automatiquement le verrou. Remarquons que l'on itère sur
l'attente de la condition avec une instruction while, plutôt que
de faire une simple instruction conditionnelle if. En effet,
entre le moment où le processus est réveillé et celui où il s'exécute,
rien n'empêche qu'un autre processus ne prenne le verrou n'invalide le
test sur l'état de la file. Il faut donc toujours utiliser une telle
instruction while. Si on veut réveiller plusieurs processus, on
utilise la méthode notifyAll, qui réveille tous les
processus en attente sur la condition.
Enfin, on remarque que les les méthodes wait et notify
peuvent générer l'exception InterruptedException en cas
d'interruption des processus les appelant. Au total, le programme
contenant le lancement des deux processus t1 et t2 qui appellent
les fonctions ajouter et supprimer s'écrit
comme suit.
class FIFO {
... // définitions de la classe, d'ajouter et de supprimer
public static void main (String[ ] args)
throws InterruptedException {
FIFO f = new FIFO();
Thread t1 = new P1(f), t2 = new P2(f);
t1.start(); t2.start();
Thread.sleep (200);
t1.interrupt(); t2.interrupt();
} }
class P1 extends Thread {
static int i = -1;
FIFO f;
P1 (FIFO x) {f = x; }
public void run () {
try {
while (true) f.ajouter(++i);
} catch (InterruptedException s) { }
} }
class P2 extends Thread {
FIFO f;
P2 (FIFO x) {f = x; }
public void run () {
try { while (true)
System.out.println(f.supprimer());
} catch (InterruptedException s) { }
} } |
Exercice 34
Expliquer ce qu'il se passe si on n'interrompt pas le processus t2.
Exercice 35
Modifier le programme pour que la file puisse contenir n éléments (n > 1).
Exercice 36
Ecrire un programme de gestion d'une pile concurrente avec deux méthodes
ajouter et supprimer.
Pour bien comprendre le sens de wait et de notify, on
remarque que cette dernière fonction n'a pas de mémoire. Elle ne fait
qu'envoyer un signal à un des processus en attente. Rien n'est
enregistré. C'est pourquoi la méthode wait atomiquement relâche
le verrou et attend sur la condition. Sinon, un processus pourrait
prendre le verrou et envoyer un signal de reprise avant que l'on
attende sur la condition et ce signal serait perdu.
Exercice 37
Expliquer ce qu'il se passe si notify est fait après avoir relâché
le verrou.
| 6.6 |
Etats d'un processus et ordonnancement |
|
Un processus peut être dans plusieurs états comme indiqué sur la
figure 6.3. Dans l'état prêt, un processus
est prêt à être exécuté. Si un processeur devient disponible, il passe
dans l'état exécution. Alors le processus s'exécute. En Java, il
donne alors sa valeur à la variable globale currentThread qui
indique à tout moment le processus courant. Un processus peut quitter
l'état d'exécution pour plusieurs raisons. Par exemple, il termine en
passant à l'état mort. Il peut aussi laisser sa place à un autre
processus en repassant à l'état prêt. Il peut enfin passer à l'état
bloqué, car en attente d'une condition ou d'un verrou. Si ceux-ci se
libèrent, il passe dans l'état prêt.
Figure 6.3 : Les états d'un processus
Il peut donc y avoir plusieurs processus prêts à l'exécution. Si le
nombre de processeurs est suffisant, ils peuvent tous passer à l'état
d'exécution. Si ce n'est pas le cas (comme cela l'est bien souvent),
le système doit choisir un des processus pour l'exécuter. En Java,
c'est la JVM qui doit faire ce choix. Il lui faut donc une politique
d'ordonnancement des processus. Les politiques d'ordonnancement se
rangent en deux grandes catégories.
La stratégie d'allocation des processeurs peut être non
préemptive. Cela signifie qu'un processus ne relâche pas un processeur
tant qu'il ne l'a pas fait explicitement, par exemple avec la fonction
Thread.yield. On dit aussi parfois que les processus
fonctionnent alors en co-routines. Le désavantage d'une telle
technique est que rien ne peut empécher un processus gourmand de
monopoliser un processeur. Le gros avantage de cette technique est sa
simplicité, car c'est le programme qui se charge de l'ordonnancement.
La deuxième technique d'allocation des processeurs est préemptive. Cela signifie que le système d'exécution des processus
peut arrêter à tout moment un processus pour laisser la place à un
autre. Souvent cela fonctionne avec un quantum de temps que
l'exécution de tout processus ne doit pas dépasser avant d'abandonner
le processeur.
Au niveau de Java, les transitions entre les divers états d'un processus
sont donnés par:
- le constructeur de la classe Thread pour arriver dans
l'état création,
- la méthode start pour passer de création à prêt,
- l'ordonnanceur de la JVM pour passer de prêt à exécution,
- la méthode Thread.yield ou la fin d'un quantum de temps
(pour les systèmes préemptifs) pour passer d'exécution à prêt,
- la méthode wait ou l'appel à une méthode synchronisée pour
passer d'exécution à bloqué,
- les méthodes notify, notifyAll ou la fin d'une fonction
synchronisée d'un autre processus pour passer de bloqué à prêt,
- la fin de la méthode run pour passer d'exécution à mort.
Tous les processus ne sont pas égaux. On peut établir des priorités
entre eux dans l'accès à l'état d'exécution. Les priorités sont
simplement des nombres entiers associés à chaque processus. Les
priorités statiques peuvent être manipulées et affectées par le
programmeur avec les fonctions getPriority et setPriority.
On peut utiliser les priorités suivantes prédéfinies: MIN_PRIORITY, NORM_PRIORITY, MAX_PRIORITY.
L'ordonnanceur peut aussi affecter des priorités dynamiques pour gérer
sa politique d'allocation du (des) processeur(s). La spécification de
Java dit qu'en général les processus de forte priorité vont s'exécuter
avant les processus de basse priorité.
Cependant, il est important d'écrire du code portable, donc de
comprendre ce que la JVM garantit sur tous les systèmes. Ecrire du
code contrôlant l'accès à des variables partagées en faisant des
hypothèses sur la priorité des processus ou sur leur vitesse relative
(race condition) est très dangereux, et doit donc être
banni.
A titre de curiosité, nous considérons deux exemples de politique
d'ordonnancement: la priorité sur l'age et la priorité dans le système
Unix 4.3 BSD. Dans la stratégie de la priorité sur l'age, tout
processus a initialement une priorité p=p0 dite priorité
statique. Si un processus prêt attend le processeur pendant k
secondes, on incrémente p. Le processus qui s'exécute est choisi
parmi les processus prêts de plus forte priorité. Quand il s'exécute,
on refait p = p0. Cette politique garantit qu'un processus en
attente d'exécution depuis longtemps va prendre le processeur. Après
exécution, on oublie son histoire et on revient à la priorité statique
initiale. Cette stratégie donne donc la priorité aux vieux.
Dans la politique d'ordonnancement des processus du système Unix, au
début p = pnice est la priorité statique initiale, où on
a -20 £ pnice £ 20 (-20 pour le plus
prioritaire, et 20 pour le moins prioritaire). Nous écrivons
pnice au lieu de p0 pour rappeler que c'est la
commande nice d'Unix qui fixe cette valeur. Toutes les 40ms, la
priorité p d'un processus est recalculée par:
| p = PUSER + |
é
ê
ê
ê |
|
|
ù
ú
ú
ú |
+ 2 pnice |
Finallement, voici un exemple démontrant le danger de l'interaction
entre la synchronisation et les priorités, c'est le phénomène
d'inversion de priorités suivant: soient trois processus tb,
tm, th s'exécutant en priorité basse, moyenne, et
haute. Supposons que tb prenne un verrou qui bloque th. Si
maintenant tm s'exécute, il empêche tb (de priorité plus faible)
de s'exécuter. Supposons que tm ne relâche pas le processeur, alors
tb ne peut progresser, et le processus de plus faible priorité
tm empêche le processus th de s'exécuter. On peut s'en sortir
en affectant des priorités sur les verrous en notant qu'un processus
de plus haute priorité attendant sur ce verrou, et on fait monter la
priorité d'un processus ayant pris un verrou bloquant un processus de
forte priorité (cela fonctionne en Windows). Pour conclure, un bon
conseil est d'éviter le mélange de priorités et de synchronisations.
| 6.7 |
Les lecteurs et les écrivains |
|
L'exemple de la file d'attente avec accès concurrents ne fait pas de
distinction entre les phases de lecture et d'écriture. Pourtant il est
très courant d'avoir des fonctions d'accès différenciés entre celles
ne consistant qu'à lire la structure de donnée partagée et celles la
modifiant. La particularité de la lecture est qu'elle ne change pas la
valeur de la donnée lue. Plusieurs lectures concurrentes peuvent donc
s'effectuer simultanément. Pour l'écriture, au contraire, il faut
s'assurer qu'elle se fait en exclusion mutuelle de toutes les autres
fonctions d'accès à la donnée, puisque, si on lit une donnée en cours
de modification, on peut obtenir un résultat incohérent. C'est le
problème dit des lecteurs et des écrivains. Une donnée partagée peut
autoriser la lecture par n (n > 0) processus simultanément, mais
ne permet l'écriture que par un seul processus. Tous les systèmes de
réservation de places en ligne (train, avion, théatre) sont des
exemples de ce problème, puisqu'il ne s'agit pas de signaler une place
disponible au moment même où un autre client la prend.
La lecture commence par exécuter la fonction accesPartage qui
vérifie que l'on peut obtenir un accès partagé à la donnée que l'on
veut lire. Elle se finit par une fonction retourPartage qui
remet en place les verrous pris pour effectuer la lecture. De même,
l'écriture commence par l'exécution de la fonction accesExclusif
et se finit par une autre fonction retourExclusif. Nous
supposons qu'une variable globale nLecteurs donne à tout moment le
nombre de lecteurs. Par convention, nLecteurs = -1 si un écrivain est en
action.
void lecture() {
accesPartage();
// lire la donnée partagée
retourPartage();
}
void ecriture() {
accesExclusif();
// modifier la donnée partagée
retourExclusif();
}
synchronized void accesPartage() {
while (nLecteurs < 0)
wait();
++nLecteurs;
}
synchronized void retourPartage() {
-- nLecteurs;
if (nLecteurs == 0)
notify();
}
synchronized void accesExclusif() {
while (nLecteurs != 0)
wait();
nLecteurs = -1;
}
synchronized void retourExclusif() {
nLecteurs = 0;
notifyAll();
} |
NotifyAll est pratique, il évite de gérer l'ensemble des
lecteurs en attente. Pourtant il peut réveiller trop de processus qui
se retrouvent immédiatement bloqués. Pour arriver à un contrôle plus
fin, on peut considérer deux conditions séparées en lecture et en
écriture, et attendre sur l'une ou sur l'autre. Ceci est impossible en
Java, car on ne peut disposer de conditions différentes sur un même
verrou, mais cela est possible dans toutes les bibliothèques de
processus Posix (un standard assez répandu). Pour exposer notre
solution, nous supposons disposer de telles conditions Posix: wait est une méthode prenant en argument l'objet dont la condition
libère ou reprend le verrou, notify, notifyAll ont leur
sens classique. Avec deux conditions (lecture et écriture), et une variable globale nLecteursEnAttente qui
compte le nombre de lecteurs en attente. on obtient le contrôle plus
fin suivant:
synchronized void accesPartage() {
++ nLecteursEnAttente;
while (nLecteurs < 0)
lecture.wait(this);
-- nLecteursEnAttente;
++ nLecteurs;
}
synchronized void retourPartage(this) {
-- nLecteurs;
if (nLecteurs == 0)
ecriture.notify();
}
synchronized void accesExclusif() {
while (nLecteurs != 0)
ecriture.wait(this);
nLecteurs = -1;
}
synchronized void retourExclusif() {
nLecteurs = 0;
if (nLecteursEnAttente > 0)
lecture.notifyAll();
else
ecriture.notify();
} |
Exécuter notify à l'intérieur d'une section critique n'est pas
très efficace. Avec un seul processeur, ce n'est pas un problème car
les processus réveillés passent dans l'état prêt attendant la
disponibilité du processeur. Avec plusieurs processeurs, le processus
réveillé peut retomber rapidement dans l'état bloqué, tant que le
verrou n'est pas relaché. Le mieux est de faire notify à
l'extérieur de la section critique.
void retourPartage() {
boolean faireNotify;
synchronized (this) {
-- nLecteurs;
faireNotify = nLecteurs == 0;
}
if (faireNotify)
ecriture.notify();
} |
Des blocages inutiles sont possibles (même avec plusieurs processeurs)
sur le notifyAll de fin d'écriture. Comme avant, on peut le
sortir de la section critique. Si plusieurs lecteurs sont réveillés,
un seul prend le verrou. Mieux vaut faire notify en fin
d'écriture, puis refaire notify en fin d'accès partagé pour
relancer les autres lecteurs.
void accesPartage() {
synchronized (this) {
++ nLecteursEnAttente;
while (i < 0)
lecture.wait(this);
-- nLecteursEnAttente;
++ nLecteurs;
}
lecture.notify();
} |
Une famine est possible pour un écrivain en attente de fin
de lecture. La politique d'ordonnancement des processus peut aider. On
peut aussi logiquement imposer le passage d'un écrivain.
void accesPartage() {
synchronized () {
++ nLecteursEnAttente;
if (nEcrivainsEnAttente > 0)
lecture.wait(this);
while (i < 0)
lecture.wait(this);
-- nLecteursEnAttente;
++ nLecteurs;
}
lecture.notify();
}
synchronized void accesExclusif() {
++ nEcrivains;
while (i != 0)
ecriture.wait(this);
-- nEcrivainsEnAttente;
nLecteurs = -1;
} |
En conclusion, on constate que contrôler finement la synchronisation
peut être complexe.
Exercice 38
Donner un exemple précis où notifyAll fait une
différence avec notify.
Exercice 39
Montrer que le réveil des processus n'est pas forcément
dans l'ordre premier en attente, premier réveillé.
Exercice 40
Donner un exemple où un processus peut attendre un temps
infini avant d'entrer en section critique.
Exercice 41
Comment programmer un service d'attente où les processus
sont réveillés dans l'ordre d'arrivée.
| 6.8 |
Implémentation de la synchronisation |
|
Avec des fonctions synchronisées et des opérations atomiques comme
wait ou signal, on peut aisément réaliser la
synchronisation entre les processus. Il reste à comprendre comment
implémenter ces deux fonctions et la prise d'un verrou. En général,
cela dépend de l'architecture matérielle disponible. Très souvent, les
ordinateurs disposent d'une instruction machine ininterruptible Test and Set. Cette opération TAS(m) teste atomiquement si la
variable m vaut false et la positionne si m =
false. Le résultat est vrai si m = true avant
l'exécution, faux sinon. C'est sur les ordinateurs avec plusieurs
processeurs que cette opération prend tout son sens, où une mémoire
spéciale de ``verrous ``, accessibles par TAS, est souvent
partagée entre tous les processeurs.
On programme une section critique ainsi, en posant m = false
comme valeur initiale de m:
while ( TAS(m) )
;
// section critique
m = false; |
L'opération TAS(m) permet de tester et de modifier atomiquement
la variable partagée m, et donc de garantir l'exclusion mutuelle
pour l'exécution de la section critique. Cependant ce programme fait
une attente active sur le passage de la valeur de m à
false. En fait, comme nous le verrons plus loin avec les
sémaphores, l'environnement d'exécution gère un ensemble de processus
en attente sur le changement de valeur de certaines variables. Ces
processus sont alors suspendus pendant cette attente.
Mais, sans l'instruction TAS, on peut tout de même y
arriver, en n'utilisant que l'indivisibilité de la lecture ou de
l'écriture en mémoire d'un scalaire de base. Ces algorithmes
compliqués (Dekker, Peterson) sont des curiosités, car inutiles
puisque le matériel procure toujours des verrous avec
TAS. Cependant, ces algorithmes démontrent bien l'aspect
complexe de la concurrence.
class Peterson extends Thread {
static int tour = 0;
static boolean[ ] actif = {false, false};
int i, j;
Peterson (int x) { i = x; j = 1 - x; }
public void run() {
while (true) {
actif[i] = true;
tour = j;
while (actif[j] && tour == j)
;
// section critique
...
// fin de section critique
actif[i] = false;
Thread.yield();
} }
public static void main (String[ ] args) {
Thread t0 = new Peterson(0), t1 = new Peterson(1);
t0.start(); t1.start();
} } |
La démonstration est loin d'être évidente. Montrons d'abord la sureté
de ce mécanisme d'exclusion mutuelle. Si t0 et t1 entrent tous
les deux dans leur section critique, alors actif[0] =
actif[1] = true. C'est impossible car les deux
tests auraient été franchis en même temps alors que tour
favorise l'un d'entre eux. Donc un des deux est entré. Disons t0.
Cela veut dire que t1 n'a pu avoir trouvé le tour à 1 et
qu'il n'est pas entré en section critique.
Montrons à présent la vivacité, c'est-à-dire qu'un processus voulant
entrer dans la section critique finit par y entrer. En effet,
supposons t0 bloqué dans le while. On a deux cas. Dans le
premier cas, le processus t1 n'est pas intéressé par rentrer dans
la section critique. Alors actif[1] = false. Et
donc t0 ne peut être bloqué par le while. Dans le deuxième
cas, le processus t1 est aussi bloqué dans le while. C'est
impossible car tour vaut 0 ou 1. Donc l'un de t0 ou
t1 ne peut rester dans le while.
Cette démonstration est formalisée avec des assertions logiques
faisant intervenir la valeur des variables et des compteurs ordinaux
c0 et c1, c'est-à-dire des emplacements de l'exécution dans
chacun des deux processus. Les valeurs de ci sont les numéros
affichés ci-dessous à gauche des lignes de la fonction run.
Décorons le code de la fonction avec les assertions suivantes:
. public void run() {
. while (true) {
{¬actif[i] Ù ci¹ 2 }
1 actif[i] = true;
{actif[i] Ù ci = 2}
2 tour = j;
{actif[i] Ù ci ¹ 2}
3 while (actif[j] && tour == j)
. ;
{actif[i] Ù ci¹ 2 Ù (¬actif[j]Ú tour= i Ú cj = 2)}
. // section critique
. ...
. // fin de section critique
5 actif[i] = false;
{¬actif[i] Ù ci¹ 2}
6 Thread.yield();
. } } |
En outre, on adjoint à toutes les assertions la proposition
suivante: j = 1 - i Ù (tour= 0 Ú tour= 1). On peut
vérifier que chaque assertion est vérifiée quand chacun des deux
processus s'exécute. On en déduit alors que les deux programmes ne
peuvent atteindre la section critique simultanément, puisqu'alors on
aurait simultanément les deux invariants de la ligne 5, c'est-à-dire:
| |
(tour= 0 Ú tour= 1) |
| Ù |
actif[0] Ù c0¹ 2 Ù (¬actif[1]Ú tour= 0 Ú c1 = 2) |
| Ù |
actif[1] Ù c1¹ 2 Ù (¬actif[0]Ú tour= 1 Ú c0 = 2) |
(tour= 0 Ú tour= 1) Ù tour = 0 Ù tour = 1
ce qui est impossible.
On peut aussi prouver la vivacité avec les assertions. Par exemple, il
est impossible que t0 soit en dehors de l'accès à la section
critique pendant que t1 reste bloqué dans le while, car alors:
| Ù |
¬actif[0] Ù c0¹ 2 Ù (tour= 0 Ú tour= 1) |
| Ù |
actif[1] Ù c1¹ 2 |
| Ù |
actif[0] Ù tour= 0 |
actif[1] Ù tour= 1
Ù actif[0] Ù tour= 0 Ù (tour= 0 Ú tour= 1)
ce qui est aussi impossible.
Exercice 42
Généraliser l'algorithme de Peterson au cas de n processus et d'une
section critique en exclusion mutuelle.
Une autre forme de synchronisation de bas niveau est la notion de
sémaphore due à Dijkstra. Un sémaphore est une variable
s booléenne, sur laquelle on fait les deux opérations atomiques
suivantes:
-
prendre (proberen en hollandais) le sémaphore: P(s)
teste la valeur de s. Si s vaut true, on met s à
false. Sinon l'instruction attend sur s.
- libérer (verhogen en hollandais) le sémaphore: V(s)
réveille un processus en attente sur s s'il existe un tel
processus, et la valeur de s est inchangée. Sinon s est
mis à true.
A la différence des conditions de Java, les sémaphores ne sont pas
attachés à un verrou. Ce sont des variables qui ont un état. On peut
les utiliser pour justement programmer un verrou comme dans
l'exclusion mutuelle de sections critiques. Ainsi la construction de
Java
synchronized (o) {
// section critique
} |
s'écrit en termes de sémaphores de la manière suivante:
P(s0);
try {
// section critique
} finally V(s0); |
en supposant que so est un sémaphore associé à l'objet
o. On peut aussi définir une classe Semaphore avec deux
méthodes P et V en fonction des primitives wait et notify de Java:
class Semaphore {
boolean libre;
Semaphore (boolean x) { libre = x; }
static void P(Semaphore s) {
synchronized (s) {
while (!s.libre)
try {
s.wait();
} catch (InterruptedException x) { }
s.libre = false;
}
}
static void V(Semaphore s) {
synchronized (s) {
s.libre = true;
s.notify();
} } } |
D'autres définitions de sémaphores sont possibles. Par exemple, pour
V(s), on peut d'abord mettre le sémaphore à true, puis
réveiller un des processus en attente sur s, s'il en existe un. Ainsi,
le processus t effectuant V(s) peut continuer à s'effectuer, même
si d'autres processus t1, t2, ...tn sont en attente sur
s (c'est aussi le cas avec la première définition), mais maintenant
t peut reprendre le sémaphore avant que le processus ti réveillé
ne passe. On peut aussi définir des sémaphores FIFO tels que le
premier processus en attente sur s soit le premier réveillé. En
fait, ces différences n'interviennent pas dans les propriétés de
sureté, mais n'affectent que la vivacité des algorithmes. Cela
signifie que les exclusions mutuelles des sections critiques sont bien
respectées, mais que la garantie de rentrer dans une section critique
n'est pas toujours vraie, car cela peut dépendre de l'équité de la
politique d'ordonnancement entre les divers processus.
Avec les sémaphores, on peut implémenter les conditions Posix avec les
deux fonctions wait et notify de la manière suivante:
class ConditionPosix {
Semaphore sem;
Condition () { s = new Semaphore(false); }
public void wait (Semaphore m) {
Semaphore.V(m);
Semaphore.P(sem);
Semaphore.P(m);
}
public void notify () {
Semaphore.V(sem);
}
} |
Toutefois, il est beaucoup plus difficile de définir
notifyAll avec des sémaphores, puisqu'on doit alors faire
intervenir l'ensemble des processus en attente sur le sémaphore.
On peut enfin généraliser légèrement la notion de sémaphore, en
utilisant un compteur. Un sémaphore généralisé est une
variable s entière positive, sur laquelle on fait deux opérations
atomiques suivantes:
-
P(s) teste la valeur de s. Si s>0, on décrémente
s de 1. Sinon on attend sur s.
- V(s) réveille un processus en attente sur s, s'il existe
un tel processus. Sinon s est incrémenté de 1.
| 6.10 |
Producteur -- Consommateur |
|
Les sémaphores sont des primitives de bas niveau. Toutefois, elles
peuvent servir à programmer quelques exemples non triviaux, même si la
bonne manière consiste presque toujours à utiliser des sections
critiques en exclusion mutuelle avec des conditions. L'exemple type
est celui du producteur -- consommateur. Un processus produit de
l'information, et un autre la consomme. Le premier processus produit
son résultat dans un medium (par exemple une file d'attente) dans
lequel l'autre processus retire l'information. Comme déjà vu pour la
file d'attente concurrente, il faut gérer les cas où l'on veut
consommer dans un medium vide, et où l'on veut produire dans un medium
plein. Supposons le medium infini, seul le cas vide importe. Alors la
solution standard s'écrit de la manière suivante:
class FIFO {
static final int N = 100000;
int debut, fin;
int[] contenu;
Semaphore s, s_occupees;
FIFO (int n) {
debut = fin = 0; contenu = new int[N];
s_occupees = new Semaphore(0);
s = new Semaphore(1);
}
void ajouter (int x) {
Semaphore.P(s);
contenu[fin++] = x;
Semaphore.V(s);
Semaphore.V(s_occupees);
}
int supprimer () {
int res;
Semaphore.P(s_occupees);
Semaphore.P(s);
res = contenu[debut++];
Semaphore.V(s);
return res;
}
} |
On peut aussi traiter le cas où la file est de longueur bornée
avec un autre sémaphore généralisé comptant le nombre de cases vides
dans la file d'attente. Les deux fonctions de manipulation de la file
concurrente deviennent alors:
FIFO (int n) {
debut = fin = 0; contenu = new int[N];
s_occupees = new Semaphore(0); s_libres = new Semaphore(N);
s = new Semaphore(1);
}
void ajouter (int x) {
Semaphore.P(s_libres);
Semaphore.P(s);
contenu[fin] = x;
fin = (fin + 1) % N;
Semaphore.V(s);
Semaphore.V(s_occupees);
}
int supprimer () {
int res;
Semaphore.P(s_occupees);
Semaphore.P(s);
res = contenu[debut];
debut = (debut + 1 ) % N;
Semaphore.V(s);
Semaphore.V(s_libres);
return res;
} |
Exercice 43
Implanter les sémaphores généralisés en Java avec avec les verrous et
conditions.
Exercice 44
Dans le langage Ada, la communication se fait par
rendez-vous. Deux processus P et Q font un rendez-vous s'ils
s'attendent mutuellement chacun à un point de son programme.
On peut en profiter pour passer une valeur. Comment organiser cela
en Java?
Exercice 45
Une barrière de synchronisation entre plusieurs processus
est un endroit commun que tous les processus actifs doivent franchir
simultanément. C'est donc une généralisation à n processus d'un
rendez-vous. Comment la programmer en Java?
Exercice 46
Toute variable peut être partagée entre plusieurs processus,
quel est le gros danger de la communication par variables partagées?
Exercice 47
Un ordonnanceur est juste s'il garantit à tout processus
prêt de passer dans l'état exécution. Comment le construire?
