---
author:
- Orestis Malaspinas, Steven Liatti
title: Introduction aux variables de condition
autoSectionLabels: false
autoEqnLabels: true
eqnPrefix:
- "éq."
- "éqs."
chapters: true
numberSections: false
chaptersDepth: 1
sectionsDepth: 3
lang: fr
documentclass: article
papersize: A4
cref: false
urlcolor: blue
toc: false
date: 2020-01-01
mathjax: on
include-before: <script src="css/prism.js"></script>
---
# Les variables de condition
Le contenu de ce chapitre est basé sur l'excellent livre de R. H. Arpaci-Dusseau et A. C. Arpaci-Dusseau[^4].
Après avoir discuté les verrous, et leur construction, nous allons
discuter d'une autre structure qui est nécessaire
pour construire des applications concurrentes: les **variables de conditions**. Les variables de condition sont utilisées
lorsque qu'un fil d'exécution doit d'abord vérifier
une condition avant de continuer.
Le problème peut s'illustrer de la façon suivante
```language-c
void *foo() {
printf("Nous y sommes.\n");
// On veut signaler qu'on a terminé:
// mais comment faire?
return NULL;
}
int main() {
printf("Début du programme.\n");
pthread_t tid;
pthread_create(&tid, NULL, foo, NULL);
// On aimerait attendre sur la fonction foo
// mais comment faire?
printf("Fin du programme.\n");
return EXIT_SUCCESS;
}
```
Une solution serait d'utiliser une variable partagée
entre le thread principal et le thread enfant comme
dans l'exemple ci-dessous
```language-c
bool done = false;
void *foo() {
printf("Nous y sommes.\n");
done = true;
return NULL;
}
int main() {
printf("Début du programme.\n");
pthread_t tid;
pthread_create(&tid, NULL, foo, NULL);
while (!done) {
// do nothing, just wait
}
printf("Fin du programme.\n");
return EXIT_SUCCESS;
}
```
Cette solution, bien que très simple, est très inefficace.
En effet, le thread principal va tourner dans la boucle `while`{.language-c} et gaspiller des ressources pour rien.
Par ailleurs, il est assez simple d'imaginer des situations
où on peut produire du code qui sera simplement faux.
## Définition
Pour pallier aux problèmes d'inefficacité et de justesse que nous venons de discuter, on utilise les **variables de condition**.
Une variable de condition est une file d'attente, dans laquelle les
fils d'exécution peuvent se mettre lorsqu'une condition n'est pas satisfaite. Ils y attendront que la dite condition soit remplie.
Un autre thread peut alors, lorsque l'état de la condition change,
réveiller un ou plusieurs fils qui sont en attente pour leur permettre
de continuer. Il va **signaler** aux threads en attente de se réveiller.
Les variables de conditions dans la librairie POSIX se déclare
via le type `pthread_cond_t`{.labguage-c}. Une telle
variable se manipule via les fonctions[^1]
```language-c
pthread_cond_wait(pthread_cond_t *c, pthread_mutex_t *m);
pthread_cond_signal(pthread_cond_t *c);
```
Ces deux fonctions, sont les appels fondamentaux des variables de
condition. La fonction `cond_signal()`{.language-c} (on va utiliser ici
les raccourcis `cond_wait()`{.language-c} et `cond_signal()`{.language-c}
car je suis flemmard) est utilisée pour signaler qu'une variable a
changé d'état et réveille un thread. La fonction `cond_wait()`{.language-c}
a la responsabilité de mettre le thread qui l'appelle en attente.
Il faut noter que cette fonction prend un `mutex`{.language-c} en
paramètre. Par ailleurs, `cond_wait()`{.language-c}
fait l'hypothèse que le `mutex`{.language-c} est verrouillé
et a la responsabilité de libérer le verrou et de mettre
le thread en attente. Puis, lorsque le dit thread doit se réveiller
(parce qu'un autre fil d'exécution le lui a signalé)
`cond_wait()`{.language-c} doit acquérir le verrou à nouveau
et continuer l'exécution du thread. Cette partie est quelque peu
complexe. Pour la comprendre considérons le code ci-dessous
```language-c
bool done = false;
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
void cond_wait() {
pthread_mutex_lock(&mutex);
while (!done) {
pthread_cond_wait(&cond, &mutex);
}
pthread_mutex_unlock(&mutex);
}
void cond_signal() {
pthread_mutex_lock(&mutex);
done = true;
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
}
void *foo() {
printf("Nous y sommes.\n");
cond_signal();
return NULL;
}
int main() {
printf("Début du programme.\n");
pthread_t tid;
pthread_create(&tid, NULL, foo, NULL);
cond_wait();
printf("Fin du programme.\n");
return EXIT_SUCCESS;
}
```
Il y a deux cas distincts:
1. Le thread principal crée un thread enfant et continue son exécution.
Il acquière le `mutex`{.language-c} et est mis en attente
lorsqu'il appelle `cond_wait()`{.language-c} et libère le verrou.
A un moment ou un autre, le fil enfant s'exécutera.
En appelant la fonction `cond_signal()`{.language-c}, il
verrouillera le `mutex`{.language-c}, assignera
la valeur `true`{.language-c} à la variable `done`{.language-c}
et appellera `pthread_cond_signal()`{.language-c}, ce qui aura pour effet
de réveiller le thread principal. Le thread principal
sera réveillé et aura le `mutex`{.language-c} dans un état
verrouillé, sortira de la boucle `while`{.language-c}
déverrouillera le `mutex`{.language-c} et terminera son exécution.
2. Le thread enfant est exécuté immédiatement, il appelle `cond_signal()`{.language-c}
et il modifie `done`{.language-c}. Comme
il n'y a pas de thread en attente, rien ne se passe. Le thread
principal peut donc finir son exécution tranquillement.
---
Remarque #
Comme nous allons le voir plus bas, il est très important d'utiliser la boucle `while`{.language-c} bien qu'ici cela ne soit
pas strictement nécessaire.
---
Il se pourrait que vous soyez tenté·e·s de modifier quelque peu
l'implémentation ci-dessus. N'en faites rien, cela pourrait causer
des dommages irréversibles à vos codes. Changeons un peu les
différentes parties du programme pour voir ce qui peut se passer.
Si nous remplaçons les fonctions `cond_wait()`{.language-c} et
`cond_signal()`{.language-c} par les codes ci-dessous (il va y avoir plusieurs
exemples faux)
```language-c
void cond_wait() {
pthread_mutex_lock(&mutex);
pthread_cond_wait(&cond, &mutex);
pthread_mutex_unlock(&mutex);
}
void cond_signal() {
pthread_mutex_lock(&mutex);
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
}
```
---
Question #
Pourquoi cette façon de faire est-elle problématique?
---
Dans ce cas, on utilise pas la variable `done`{.language-c}.
Hors, si on imagine qu'on est dans le cas où le thread enfant
est exécuté immédiatement, il va effectuer la signalisation et
retourner immédiatement. Le thread principal lui va ensuite
attendre indéfiniment, car plus aucun autre thread ne lui signalera
jamais de se réveiller.
L'exemple suivant est également faux. Nous nous débarrassons
cette fois du verrou
```language-c
void cond_wait() {
if (!done) {
pthread_cond_wait(&cond, &mutex);
}
}
void cond_signal() {
done = true;
pthread_cond_signal(&cond);
}
```
---
Question #
Pourquoi cette façon de faire est-elle également problématique?
---
Il y a ici un problème d'accès concurrent. Si le thread enfant
appelle `cond_wait()`{.language-c} et voit que
`done == false`{.language-c} il voudra se mettre en attente.
Hors, si à ce moment précis il y a un changement de contexte
et `cond_signal()`{.language-c} est appelé, il signalera
la condition, mais comme aucun fil n'est en attente, ce signal
sera perdu. Le thread enfant sera à un moment ou un autre
ré-ordonnancé et sera mis en attente. Comme aucun autre
signal ne sera jamais émis il restera endormi à jamais.
De ces deux mauvais exemples, on peut tirer un enseignement.
Même si cela n'est pas toujours nécessaire, il faut **toujours**
détenir le verrou avant de signaler une condition. A l'inverse,
il est toujours nécessaire d'avoir un verrou lors de l'appel
de `pthread_cond_wait()`{.language-c}. La fonction `pthread_cond_wait()`{.language-c}
présuppose que le verrou est détenu lors de son appel.
La règle générale est finalement: quoi qu'il arrive avant
d'attendre ou de signaler acquérir le verrou (et le libérer ensuite).
## Le problème producteurs/consommateurs
Le problème des **producteurs/consommateurs** a été à l'origine du
développement des variables de condition par Dijkstra.
On peut imaginer un ou plusieurs fils d'exécution
produisant des données et les plaçant dans une mémoire
tampon (buffer). Le ou les consommateurs vont chercher
les données dans la mémoire tampon et les utilisent.
Un exemple typique est la fonction `pipe` d'un programme dans un autre dans les systèmes UNIX:
```language-bash
grep hop file.txt | wc -l
```
Ici un processus exécute la fonction `grep`, qui écrit les lignes
du fichier `file.txt` où `hop` est présent sur la sortie standard
(enfin c'est ce que `grep` croit). Le système d'exploitation
redirige en fait la sortie dans un "tuyau" (*pipe*) UNIX. L'autre côté
du *pipe* est connecté à l'entrée du processus `wc` qui compte les
lignes dans le flot de données en entrée et affiche le résultat.
On a donc que `grep` produit des données et `wc` les consomme
avec un buffer entre deux.
---
Question #
Pouvez-vous imaginer une autre application de ce type?
---
Comme la mémoire tampon est une ressource partagée, il faut trouver un mécanisme de synchronisation pour éviter
les accès concurrents.
Pour simplifier, représentons le buffer par un simple entier[^2].
On a ensuite deux fonctions:
* la fonction `put()`{.language-c} qui va insérer une valeur
dans la mémoire tampon.
* la fonction `get()`{.language-c} qui va récupérer une valeur
de la mémoire tampon.
Finalement, on a également besoin de savoir combien de données
sont stockées dans le buffer. Pour cela on utilise un simple compteur.
```language-c
int buffer;
int counter = 0; // le compteur
void put(int value) {
assert(counter == 0 && "trying to put into a full buffer");
counter = 1;
buffer = value;
}
int get() {
assert(counter == 1 && "trying to get from empty buffer");
counter = 0;
return buffer;
}
```
La fonction `put()`{.language-c} suppose que le `buffer`
ne contient rien (`counter == 0`{.language-c}) et vérifie l'état
avec une `assert()`{.language-c}. Ensuite elle incrémente la valeur
du compteur à 1 et assigne la valeur `value`{.language-c} au
`buffer`{.language-c}. A l'inverse la fonction `get()`{.language-c}
fait l'hypothèse que le `buffer` contient une valeur
(`counter == 1`{.language-c}) et vérifie également cet état avec
une `assert()`{.language-c}.
A présent, il faut des fonctions qui auront la sagesse nécessaire
pour appeler les fonctions `put()`{.language-c} et `get()`{.language-c} au moments opportuns (quand `counter` a la bonne valeur, zéro ou un respectivement). Grâce au design astucieux
de `put()`{.language-c} et `get()`{.language-c} on saura très
vite si on fait quelque chose de faux, car les assertions
vont faire planter le programme.
Ces actions seront effectuées par deux types de threads:
les threads **producteurs** et les threads **consommateurs**.
Pour simplifier, écrivons d'abord une version complètement fausse
et naive mais qui illustre ce que ferait un thread producteur qui
met `loops`{.language-c} valeurs dans le buffer et un
thread consommateur qui récupère à l'infini les valeurs
stockées dans le buffer.
```language-c
// rien n'est initialisé c'est normal c'est une illustration
// complètement absurde
void *producer(void *arg) {
int loops = (int)*arg;
for (int i = 0; i < loops; ++i) {
put(i);
}
}
void *consumer(void *arg) {
while (1) {
int i = get();
printf("%d\n", i);
}
}
```
Il est évident que ce code ne peut pas fonctionner.
Les `assert()`{.language-c} passeraient le temps à tout
arrêter. On a des sections critiques dans `put()`{.language-c}
et `get()`{.language-c} qui ne sont pas du tout gérées.
Mais vous voyez l'idée de ce qu'on essaie de faire.
Juste utiliser un verrou pour protéger,
`put()`{.language-c} et `get()`{.language-c}
comme on l'a fait jusqu'ici ne peut pas fonctionner.
---
Question #
Pourquoi?
---
Il nous faut en fait un moyen de prévenir chacun des threads
de l'état du buffer afin qu'il puisse effectuer une action
appropriée.
### Une solution, fausse
La solution la plus simple serait d'ajouter une variable de condition et son verrou associé. Un code du genre de celui
se trouvant ci-dessous par exemple
```language-c
int loops = 10; // une initialisation au hasard
pthread_cond_t cond;
pthread_mutex_t mutex
void *producer(void *arg) {
for (int i = 0; i < loops; ++i) {
pthread_mutex_lock(&mutex);
if (count == 1) {
pthread_cond_wait(&cond, &mutex);
}
put(i);
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
}
}
void *consumer(*void arg) {
for (int i = 0; i < loops; ++i) {
pthread_mutex_lock(&mutex);
if (count == 0) {
pthread_cond_wait(&cond, &mutex);
}
int tmp = get();
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
printf("%d\n", tmp);
}
}
```
Si nous avons un thread producteur et un thread consommateur
ce code fonctionne. Par contre, si nous ajoutons plus de threads
cela ne fonctionne plus.
---
Question #
Que se passe-t-il dans le cas où nous avons deux threads consommateurs pour un producteur?
---
Le premier problème est relié à l'instruction `if`{.language-c}
avant l'appel à `wait()`{.language-c}.
Le second est relié à l'utilisation d'une unique variable
de condition. Voyons à présent ce qui peut se passer.
Soient les threads consommateurs $T_{c_1}$ et $T_{c_2}$ et le
thread producteur $T_p$. Supposons que $T_{c_1}$ s'exécute.
Il acquière le verrou et vérifie s'il y a quelque chose à consommer dans le frigo... euh... dans le buffer. Comme il
n'y a rien il se met en attente et libère le verrou.
Ensuite le thread $T_p$ s'exécute. Il acquière le verrou
et vérifie si le buffer est vide. Comme il l'est il peut y déposer
une valeur. Il va ensuite signaler que le buffer est rempli.
Cela va mettre $T_{c_1}$ en état de réveil et prêt à être exécuté
(il ne s'exécute pas encore). Finalement pour $T_p$,
il se rend compte que le buffer est plein et va se mettre
en sommeil. A ce moment précis, $T_{c_2}$ est ordonnancé.
Il acquière le verrou, lit la valeur dans le buffer, signale qu'il
a lu
et libère le verrou. A ce moment précis, si $T_{c_1}$ est
ordonnancé, il va acquérir le verrou et continuer son exécution
là où elle c'était arrêtée. Il va donc tenter de lire à son tour
dans le buffer, mais celui-ci sera vide! L'assertion dans
`get()`{.language-c} nous sautera au visage et arrêtera
l'exécution. Au moins, nous sommes sauvés d'un comportement
erroné que nous croyions correct.
Pour prévenir cette erreur, nous aurions dû empêcher $T_{c_1}$
de tenter de consommer une valeur déjà consommée. En fait le signal
envoyé par $T_p$ doit être considéré comme une indication
que quelque chose a changé. Il n'y a en revanche aucune garantie
que cela sera toujours le cas lorsque le thread mis en sommeil
sera réveillé. La solution ici est de remplacer le
`if`{.language-c} par un `while`{.language-c}. De cette façon
$T_{c_1}$ aurait vérifié que la condition a bien changé après
son réveil et avoir acquis le verrou. Ainsi il n'aurait pas essayé
de consommer une valeur déjà consommée.
---
Règle #
Toujours utiliser une boucle `while`{.language-c} et jamais de `if`{.language-c}.[^3]
---
Voilà un premier problème de réglé, mais nous ne sommes pas sortis d'affaire.
En effet, un autre problème existe. Imaginons que $T_{c_1}$ et
$T_{c_2}$ s'exécutent en premier et sont mis en sommeil. $T_p$
s'exécute alors, met une valeur dans le buffer et
réveille un thread, disons $T_{c_1}$. $T_p$ refait un tour de
boucle, libère et réacquière le verrou et réalise que le buffer est plein. Il se met en sommeil. $T_{c_1}$ peut s'exécuter
(alors que $T_{c_2}$ et $T_p$ sont endormis). Il refait un tour
dans la boucle `while`{.language-c}, trouve le buffer plein et le
vide. Il signale qu'il a fini et va se rendormir. Si à présent
c'est $T_{c_2}$ qui se réveille (on a aucune garantie sur l'ordre
de l'exécution), il va trouver le buffer vide et se rendormir.
On a donc les trois threads en sommeil avec aucun moyen de les
réveiller (pas de prince·esse charmant·e, ni rien)!
On a besoin d'un autre signal qui soit dirigé: un consommateur
doit réveiller un producteur et vice-versa. Pour corriger
ce bug, nous pouvons simplement utiliser **deux** variables
de condition: une relié au remplissage du buffer, l'autre à sa
vidange comme dans le code ci-dessous.
```language-c
pthread_cond_t fill, empty; // pas oublier d'initialiser hein
pthread_mutex_t mutex;
void *producer(void *arg) {
for (int i = 0; i < loops; ++i) {
pthread_mutex_lock(&mutex);
while (count == 1) {
pthread_cond_wait(&empty, &mutex);
}
put(i);
pthread_cond_signal(&fill);
pthread_mutex_unlock(&mutex);
}
}
vois *consumer(*void arg) {
for (int i = 0; i < loops; ++i) {
pthread_mutex_lock(&mutex);
while (count == 0) {
pthread_cond_wait(&fill, &mutex);
}
int tmp = get();
pthread_cond_signal(&empty);
pthread_mutex_unlock(&mutex);
printf("%d\n", tmp);
}
}
```
Dans ce code, on voit que les threads producteurs attendent
sur la condition `empty`{.language-c} et signalent la
condition `fill`{.language-c}, alors que les threads
consommateurs attendent sur la condition `fill`{.language-c}
et signalent la condition `empty`{.language-c}.
### Aller plus haut
On vient de voir comment résoudre le problème producteurs/consommateurs
pour un buffer unique. Cette solution est généralisable
pour permettre des applications plus concurrentes et efficaces.
Pour ce faire, on va créer un buffer avec plus d'espaces.
Ainsi il sera possible de produire plus de valeurs
et de les consommer avant que les threads se mettent en sommeil.
Pour ce faire, nous créons un buffer qui sera cette fois
un tableau statique. On doit garder une trace du taux de remplissage,
ainsi que de la position à laquelle nous devons lire.
On modifie donc les fonctions `put()`{.language-c} et
`get()`{.language-c} de la façon suivante
```language-c
#define MAX 100;
int buffer[MAX];
int fill_pos = 0;
int read_pos = 0;
int count = 0;
void put(int value) {
buffer[fill_pos] = value;
fill_pos = (fill_pos + 1) % MAX;
count += 1;
}
int get() {
int tmp = buffer[read_pos];
read_pos = (read_pos + 1) % MAX;
count -= 1;
return tmp;
}
```
Une toute petite adaptation à la vérification nécessaire avant
le `wait()`{.language-c} ou `signal()`{.language-c}
et le tour est joué
```{.language-c}
pthread_cond_t empty, fill;
pthread_mutex_t mutex;
void *producer(void *arg) {
for (int i = 0; i < loops; ++i) {
pthread_mutex_lock(&mutex);
while (count == MAX) {
pthread_cond_wait(&empty, &mutex);
}
put(i);
pthread_cond_signal(&fill);
pthread_mutex_unlock(&mutex);
}
}
void *consumer(void *arg) {
for (int i = 0; i < loops; ++i) {
pthread_mutex_lock(&mutex);
while (count == 0) {
pthread_cond_wait(&fill, &mutex);
}
int value = get();
pthread_cond_signal(&empty);
pthread_mutex_unlock(&mutex);
printf("%d\n", value);
}
}
```
On voit que le producteur ne se met en sommeil que lorsque
le buffer est plein et à l'inverse le consommateur n'appelle
`wait()`{.language-c} que lorsque le buffer est vide.
## Signalisation globale
Dans certains cas, on aimerait être un peu plus large lorsqu'on
réveille des threads. En particulier, on aimerait pouvoir réveiller
tous les threads endormis à la fois. Afin d'illustrer le problème
considérons l'exemple d'une application d'allocation
de mémoire sur la pile. La pile a une taille maximale
`MAX_HEAP_SIZE`{.language-c}. Nos threads vont allouer
un certain nombre d'octets
`void *allocate(int size)`{.language-c} et libérer
un certain nombre de bytes de la mémoire
`void free(void *ptr, int size)`{.language-c}.
Lorsque la mémoire est pleine, les fils d'exécution
qui sont en charge de l'allocation doivent se mettre en sommeil.
Lorsque de la mémoire se libère il faut signaler que de la place
est à nouveau disponible. Une approche simple serait le code
suivant
```language-c
int avail_bytes = MAX_HEAP_SIZE; // nombre d'octets disponibles
// comme d'habitude, une variable de condition et son verrou
pthread_cont_t cond;
pthread_mutex_t mutex;
void *allocate(int size) {
pthread_mutex_lock(&mutex);
while (avail_bytes < size) { // on doit avoir assez de mémoire
pthread_cond_wait(&cond, &mutex);
}
void *ptr = ...; // on récupère la mémoire depuis le tas
avail_bytes -= size;
pthread_mutex_unlock(&mutex);
return ptr;
}
void free(void *ptr, int size) {
pthread_mutex_lock(&mutex);
avail_bytes += size;
pthread_cond_signal(&cond);
pthread_mutex_unlock(&mutex);
}
```
---
Question #
Ce code a un problème. Lequel?
---
Imaginons qu'à un moment donné
on ait plus de place en mémoire (`avail_bytes == 0`{.language-c}). Un premier thread $T_1$
appelle `allocate(100)`{.language-c} et un deuxième thread $T_2$
appelle `allocate(10)`{.language-c}. Chacun de ces threads
va appeler `wait()`{.language-c} et se mettre en sommeil.
A présent, un troisième thread appelle `free(40)`{.language-c}, il libère 40 bytes et signale qu'il y a de la mémoire disponible. Si $T_1$ est réveillé, il retournera en sommeil
car il n'y a pas la place suffisante pour allouer et le programme
se retrouve à ne rien faire alors qu'il pourrait. Il suffisait
de réveiller $T_2$ bon sang! La solution la plus simple ici est
de réveiller **tous** les threads grâce à la fonction
`pthread_cond_broadcast()`{.language-c}
```language-c
int pthread_cond_broadcast(pthread_cond_t *cond);
```
Tous les threads attendant après l'appel de `wait()`{.language-c}
seront réveillés, ils vérifieront le nombre de bytes disponibles
et se remettront en sommeil immédiatement si l'espace n'est pas
disponible.
[^1]: Il ne faut pas oublier qu'il faut également initialiser les variables de condition et éventuellement les détruire aussi.
[^2]: Cela pourrait aussi être un pointeur vers une structure de
donnée plus complexe.
[^3]: C'est pas toujours nécessaire, mais ça ne fait pas de mal!
[^4]: R. H. Arpaci-Dusseau et A. C. Arpaci-Dusseau, *Operating Systems: Three Easy Pieces*, Arpaci-Dusseau Books, ed. 0.91, (2015).