Cet article est extrait de la version préparatoire de mon livre à venir « Solutions temps-réel sous Linux« . Le sujet m’en a été inspiré par des expériences réalisées lors d’une récente session de formation (merci entre autres à Alejandro, Manuel et Sebastien pour m’avoir encouragé et aidé à explorer ce sujet).
Prise de mutex en temps-partagé
Lorsqu’une application multi-tâches utilise des ressources partagées, il est généralement nécessaire d’utiliser des mécanismes de synchronisation afin d’éviter les problèmes de concurrence d’accès. Dans le cas d’un programme multi-threads on utilisera des mutex Posix. Une question peut se poser quand plusieurs threads sont en attente pour tenter de prendre un mutex alors que ce dernier est verrouillé : qui va l’obtenir lorsqu’il sera libéré par son actuel détenteur ?
Effectuons un premier essai avec un ensemble de cinq threads en concurrence pour obtenir le même mutex. (Les sources se trouvent dans cette archive).
mutex-01.c:
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void * fonction_thread (void * arg)
{
int numero = (int) arg;
usleep(10000 * numero);
while (1) {
fprintf(stderr, "[%d] demande le mutexn", numero);
pthread_mutex_lock(& mutex);
fprintf(stderr, " [%d] tient le mutexn", numero);
sleep(1);
fprintf(stderr, "[%d] lache le mutexn", numero);
pthread_mutex_unlock(& mutex);
usleep(10000);
}
return NULL;
}
#define NB_THREADS 5
int main(void)
{
int i;
pthread_t thread[NB_THREADS];
pthread_mutex_lock(& mutex);
for (i = 0; i < NB_THREADS; i ++)
pthread_create(& thread[i], NULL, fonction_thread, (void *) (i+1));
sleep(1);
fprintf(stderr, "Liberation initiale du mutexn");
pthread_mutex_unlock(& mutex);
for (i = 0; i < NB_THREADS; i ++)
pthread_join(thread[i], NULL);
return EXIT_SUCCESS;
}
Les sommeils dans l’exécution des threads ont plusieurs rôle : le premier usleep() assure que les threads commencent leurs boucles dans l’ordre de création, le sleep() alors que le mutex est tenu par le thread permet un affichage régulier et lisible des messages. Enfin le dernier usleep() garantit que le thread qui vient de lâcher un mutex ne le réclame pas à nouveau instantanément. Nous nous concentrerons par la suite sur ce dernier point.
$ ./mutex-01
[1] demande le mutex
[2] demande le mutex
[3] demande le mutex
[4] demande le mutex
[5] demande le mutex
Liberation initiale du mutex
[1] tient le mutex
[1] lache le mutex
[2] tient le mutex
[1] demande le mutex
[2] lache le mutex
[3] tient le mutex
[2] demande le mutex
[3] lache le mutex
[4] tient le mutex
[3] demande le mutex
[4] lache le mutex
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[1] tient le mutex
[5] demande le mutex
[1] lache le mutex
[2] tient le mutex
[1] demande le mutex
[2] lache le mutex
[3] tient le mutex
[2] demande le mutex
[3] lache le mutex
[4] tient le mutex
[3] demande le mutex
[4] lache le mutex
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[1] tient le mutex
[...]
[3] demande le mutex
[4] lache le mutex
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[1] tient le mutex
[5] demande le mutex
(Contrôle-C)
$
Clairement, le système lors de la libération du mutex, le système l’affecte au premier thread dans la file d’attente. Comment cela se déroule-t-il ?
L’appel pthread_mutex_lock() est avant tout une fonction de la bibliothèque C. Un système utilisant la bibliothèque NPTL incluse dans la GlibC, tire parti des fonctionnalités offertes par le kernel Linux depuis la version 2.6 : les Futex (Fast User Space Mutex). Lorsqu’un thread essaye de verrouiller un mutex, et que ce dernier est libre, la prise du mutex s’effectue entièrement dans l’espace utilisateur (à l’intérieur de la NPTL, sans passer par le kernel). Il n’y aura d’appel au noyau – opération plus coûteuse en temps – que si le mutex est déjà verrouillé. C’est une très bonne optimisation lorsque la protection des données partagées entre les threads n’entraîne que rarement des situations de contention. Dans notre cas toutefois, chaque appel pthread_mutex_lock() entre dans le noyau et le thread s’endort dans une file d’attente.
De même l’appel pthread_mutex_unlock() de la NPTL peut déverrouiller un mutex en restant simplement dans l’espace utilisateur si aucun autre thread n’est en attente du même mutex. Néanmoins dans notre exemple chaque libération du mutex entraînera un appel-système qui réveillera tous les threads en attente et les laissera « lutter » pour l’obtention du mutex lors de l’ordonnancement suivant.
Dans un ordonnancement temps-partagé, il est logique que les prises de mutex de l’exemple précédent s’effectuent dans l’ordre d’arrivée initiale car tous les threads sont symétriques. Si toutefois il y avait des différences entre eux (valeur de nice, consommation du CPU, etc.) l’ordre ne serait plus garanti. Modifions par exemple la fonction des threads, de manière à ce qu’un seul d’entre-eux (le numéro 2) se comporte « bien » vis-à-vis de l’ordonnanceur, les autres réclamant le mutex avec insistance en bouclant autour de pthread_mutex_trylock().
mutex-02.c:
[...]
void * fonction_thread (void * arg)
{
int numero = (int) arg;
usleep(10000 * numero);
while (1) {
fprintf(stderr, "[%d] demande le mutexn", numero);
if (numero != 2)
while (pthread_mutex_trylock(& mutex) != 0)
;
else
pthread_mutex_lock(& mutex);
fprintf(stderr, " [%d] tient le mutexn", numero);
sleep(1);
fprintf(stderr, "[%d] lache le mutexn", numero);
pthread_mutex_unlock(& mutex);
usleep(10000);
}
return NULL;
}
[...]
À l’exécution, le comportement est très différent. Le thread numéro 2 est visiblement favorisé par l’ordonnanceur et retrouve le mutex plus souvent que les autres qui sont « punis » par le scheduler pour leurs comportements hystériques autour du pthread_mutex_trylock().
$ ./mutex-02
[1] demande le mutex
[2] demande le mutex
[3] demande le mutex
[4] demande le mutex
[5] demande le mutex
Liberation initiale du mutex
[2] tient le mutex
[2] lache le mutex
[5] tient le mutex
[2] demande le mutex
[5] lache le mutex
[2] tient le mutex
[5] demande le mutex
[2] lache le mutex
[4] tient le mutex
[2] demande le mutex
[4] lache le mutex
[2] tient le mutex
[4] demande le mutex
[2] lache le mutex
[3] tient le mutex
[2] demande le mutex
[3] lache le mutex
[2] tient le mutex
[3] demande le mutex
[2] lache le mutex
[3] tient le pthread_mutex_trylock()mutex
[2] demande le mutex
[3] lache le mutex
[2] tient le mutex
(Contrôle-C)
$
Comportement en temps-réel
Le comportement observé ci-dessus est le fruit d’un ordonnancement en temps-partagé. Nous savons qu’il n’y a aucune garantie particulière offerte par cet ordonnancement, et que son comportement peut varier d’une version à l’autre de Linux ou de la bibliothéque C (Glibc avec NPTL ou uClibc avec Linux Threads). Pour plus de déterminisme, il convient de se tourner vers un ordonnancement temps-réel.
Le programme est légèrement modifié car les threads ne vont plus boucler (sinon le plus prioritaire aura toujours le mutex). Nous allons observer l’ordre de prise du mutex lors de la libération initiale . Commençons avec des threads dont la priorité est égale à leur numéro d’ordre de création.
mutex-03.c:
#include <pthread.h>
#include <sched.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
static pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
void * fonction_thread (void * arg)
{
int numero = (int) arg;
struct sched_param param;
param.sched_priority = numero;
if (pthread_setschedparam(pthread_self(), SCHED_FIFO, & param) != 0) {
perror("setschedparam");
exit(EXIT_FAILURE);
}
fprintf(stderr, "[%d] demande le mutexn", numero);
pthread_mutex_lock(& mutex);
fprintf(stderr, " [%d] tient le mutexn", numero);
sleep(1);
fprintf(stderr, "[%d] lache le mutexn", numero);
pthread_mutex_unlock(& mutex);
return NULL;
}
#define NB_THREADS 5
int main(void)
{
int i;
pthread_t thread[NB_THREADS];
pthread_mutex_lock(& mutex);
for (i = 0; i < NB_THREADS; i ++) {
pthread_create(& thread[i], NULL, fonction_thread, (void *) (i+1));
usleep(10000);
}
sleep(1);
fprintf(stderr, "Liberation initiale du mutexn");
pthread_mutex_unlock(& mutex);
for (i = 0; i < NB_THREADS; i ++)
pthread_join(thread[i], NULL);
return EXIT_SUCCESS;
}
Pour que les threads puissent prendre un ordonnancement temps-réel, il faut exécuter le programme avec les privilèges root.
# ./mutex-03
[1] demande le mutex
[2] demande le mutex
[3] demande le mutex
[4] demande le mutex
[5] demande le mutex
Liberation initiale du mutex
[5] tient le mutex
[5] lache le mutex
[4] tient le mutex
[4] lache le mutex
[3] tient le mutex
[3] lache le mutex
[2] tient le mutex
[2] lache le mutex
[1] tient le mutex
[1] lache le mutex
#
Les prises successives du mutex se sont bien réalisées en fonction de la priorité du thread. Inversons les priorités pour vérifier que l’ordre initial de demande du mutex n’influe pas.
mutex-04.c: [...] param.sched_priority = 10 - numero; [...]
A l’exécution, l’ordre de prise du mutex est identique à l’exemple précédent.
# ./mutex-04
[1] demande le mutex
[2] demande le mutex
[3] demande le mutex
[4] demande le mutex
[5] demande le mutex
Liberation initiale du mutex
[1] tient le mutex
[1] lache le mutex
[2] tient le mutex
[2] lache le mutex
[3] tient le mutex
[3] lache le mutex
[4] tient le mutex
[4] lache le mutex
[5] tient le mutex
[5] lache le mutex
#
Reprise de mutex en temps-réel
Un problème récurrent dans les systèmes embarqués temps-réel est la nécessité de synchroniser plusieurs threads sur la prise permanente du même mutex. Grossièrement, nous voudrions que chaque thread puisse faire une boucle infinie :
while (1) {
pthread_mutex_lock(& mutex);
// Traitement critique
[...]
pthread_mutex_unlock(& mutex);
}
Dans ce cas, tous les threads (dont le nombre peut être variable en fonction de l’évolution du système) seront placés au même niveau de priorité et ordonnancés en temps-réel Round-Robin par exemple. Nous espèrons ainsi que chacun d’entre-eux pourra successivement recevoir le mutex et effectuer son traitement critique.
mutex-05.c:
[...]
void * fonction_thread (void * arg)
{
int numero = (int) arg;
struct sched_param param;
param.sched_priority = 10;
if (pthread_setschedparam(pthread_self(), SCHED_RR, & param) != 0) {
perror("setschedparam");
exit(EXIT_FAILURE);
}
while (1) {
fprintf(stderr, "[%d] demande le mutexn", numero);
pthread_mutex_lock(& mutex);
fprintf(stderr, " [%d] tient le mutexn", numero);
sleep(1);
fprintf(stderr, "[%d] lache le mutexn", numero);
pthread_mutex_unlock(& mutex);
}
return NULL;
}
[...]
L’exécution semble pourtant décevante…
# ./mutex-05
[1] demande le mutex
[2] demande le mutex
[3] demande le mutex
[4] demande le mutex
[5] demande le mutex
Liberation initiale du mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
[1] lache le mutex
[1] demande le mutex
[1] tient le mutex
(Contrôle-C)
#
Comment se fait-il qu’un seul thread accède au mutex alors qu’ils sont cinq à tenter de l’obtenir simultanément, et que nous les ayons placés en ordonnancement Round-Robin ? Pour comprendre le fonctionnement, reprenons les verrouillage et déverouillage des mutex.
Notre thread numéro 1 a obtenu le mutex car il était le premier de son niveau de priorité à s’exécuter. Il libère ensuite le mutex, ce qui se traduit par un appel-système car le mutex est réclamé par les quatre autres threads (endormis pour le moment). Durant cet appel-système, le kernel réveille les threads en attente, afin qu’ils puissent tenter à nouveau leur chance en réclamant le mutex. Avant de revenir dans l’espace utilisateur, l’ordonnanceur est invoqué, et ce dernier juge que le thread numéro 1, étant en temps-réel peut continuer à s’exécuter jusqu’à ce qu’il ait consommé tout le temps CPU alloué à sa tranche de temps (100 millisecondes). Il faut être conscient que le thread ne consomme que très peu de temps processeur, car il passe l’essentiel de son temps en sommeil dans le sleep() au milieu de la boucle.
Le thread 1 reprenant son exécution, il peut à nouveau réclamer le mutex qu’il vient juste de libérer, et l’obtenir car les autres threads n’ont pas pu être ordonnancés. Lorsque notre thread va s’endormir dans le sleep(), ses confrères vont demander successivement le mutex – déjà verrouillé – et s’endormir l’un après l’autre.
Pour que les autres threads arrivent à prendre le mutex, il faudra attendre que le thread 1 ait consommé l’intégralité de sa tranche de temps CPU, ce qui n’adviendra qu’après un très grand nombre d’itérations si nous conservons le sommeil d’une seconde. Dans l’exemple suivant, nous allons supprimer ce sommeil afin de forcer le thread à consommer du temps CPU. Une variable globale contenant le numero du dernier thread ayant pris le mutex permettra de voir les transitions horodatées.
mutex-06.c:
[...]
static int dernier_thread = 0;
void * fonction_thread (void * arg)
{
int numero = (int) arg;
struct sched_param param;
struct timeval tv;
param.sched_priority = 10;
if (pthread_setschedparam(pthread_self(), SCHED_RR, & param) != 0) {
perror("setschedparam");
exit(EXIT_FAILURE);
}
while (1) {
pthread_mutex_lock(& mutex);
if (dernier_thread != numero) {
gettimeofday(& tv, NULL);
fprintf(stderr, "%ld.%06ld : %d tient le mutexn",
tv.tv_sec, tv.tv_usec, numero);
dernier_thread = numero;
}
pthread_mutex_unlock(& mutex);
}
return NULL;
}
En outre, pour permettre une sortie du programme, un appel-système alarm() est ajouté dans la fonction main(). Ainsi le noyau enverra au processus le signal SIGALRM au bout de quinze secondes. Ce signal n’étant pas géré, il va tuer notre processus.
int main(void)
{
[...]
sleep(1);
alarm(15);
fprintf(stderr, "Liberation initiale du mutexn");
[...]
Les messages devront être redirigés dans un fichier pour être consultés tranquillement.
# ./mutex-06 2> resultat.txt Minuterie d'alerte # cat resultats.txt Liberation initiale du mutex 1319322465.281375 : 1 tient le mutex 1319322466.479252 : 4 tient le mutex 1319322467.479251 : 1 tient le mutex 1319322467.779246 : 3 tient le mutex 1319322468.779247 : 1 tient le mutex 1319322468.879251 : 5 tient le mutex 1319322469.879246 : 3 tient le mutex 1319322469.979245 : 1 tient le mutex 1319322470.079245 : 4 tient le mutex 1319322470.579252 : 2 tient le mutex 1319322471.579246 : 4 tient le mutex 1319322471.679252 : 5 tient le mutex 1319322471.779245 : 2 tient le mutex 1319322471.979246 : 1 tient le mutex [...] #
Les résultats ne sont guère concluants. Nous aimerions que les threads alternent correctement leurs exécutions autour de ce mutex.
Solutions
Mise en sommeil
La première solution, qui vient à l’esprit des programmeurs habitués aux systèmes embarqués temps-réel « classiques » et à la programmation sur micro-contrôleurs est d’ajouter un petit délai entre le relâchement du mutex et sa reprise par le même thread.
Typiquement on utilise un appel usleep(10) pour demander une mise en sommeil de 10 micro-secondes, voire un appel usleep(0) pour forcer un appel au scheduler dans une condition défavorable au processus appelant. En voici un exemple.
mutex-07.c:
[...]
void * fonction_thread (void * arg)
{
int numero = (int) arg;
struct sched_param param;
param.sched_priority = 10;
if (pthread_setschedparam(pthread_self(), SCHED_FIFO, & param) != 0) {
perror("setschedparam");
exit(EXIT_FAILURE);
}
while (1) {
fprintf(stderr, "[%d] demande le mutexn", numero);
pthread_mutex_lock(& mutex);
fprintf(stderr, " [%d] tient le mutexn", numero);
sleep(1);
fprintf(stderr, "[%d] lache le mutexn", numero);
pthread_mutex_unlock(& mutex);
usleep(10);
}
return NULL;
}
[...]
Cette fois l’ordonnancement se fait en mode Fifo, afin d’éviter toute préemption involontaire. Cette solution fonctionne, en voici une démonstration.
# ./mutex-07
[1] demande le mutex
[2] demande le mutex
[3] demande le mutex
[4] demande le mutex
[5] demande le mutex
Liberation initiale du mutex
[1] tient le mutex
[1] lache le mutex
[2] tient le mutex
[1] demande le mutex
[2] lache le mutex
[3] tient le mutex
[2] demande le mutex
[3] lache le mutex
[4] tient le mutex
[3] demande le mutex
[4] lache le mutex
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[1] tient le mutex
[5] demande le mutex
[1] lache le mutex
[2] tient le mutex
[1] demande le mutex
[2] lache le mutex
[3] tient le mutex
[2] demande le mutex
[3] lache le mutex
[4] tient le mutex
[3] demande le mutex
[4] lache le mutex
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[...]
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[1] tient le mutex
[5] demande le mutex
[1] lache le mutex
[2] tient le mutex
[1] demande le mutex
[2] lache le mutex
[3] tient le mutex
[2] demande le mutex
[3] lache le mutex
[4] tient le mutex
[3] demande le mutex
[4] lache le mutex
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[1] tient le mutex
[5] demande le mutex
[1] lache le mutex
[2] tient le mutex
[1] demande le mutex
(Contrôle-C)
#
Appel explicite à l’ordonnanceur
La solution précédente fonctionne mais n’est guère élégante ni efficace. Si le thread est le seul à travailler il effectue incessamment des sommeils inutiles.
Il existe pourtant un appel-système sched_yield() qui permet de forcer un appel à l’ordonnanceur en demandant à être placé à la fin de la liste des tâches de la même priorité que l’appelant. Si aucune autre tâche de même priorité n’est prête, le thread appelant est réactivé immédiatement. Voici comment il faut l’utiliser en cette circonstance :
mutex-08.c:
[...]
void * fonction_thread (void * arg)
{
int numero = (int) arg;
struct sched_param param;
param.sched_priority = 10;
if (pthread_setschedparam(pthread_self(), SCHED_FIFO, & param) != 0) {
perror("setschedparam");
exit(EXIT_FAILURE);
}
while (1) {
fprintf(stderr, "[%d] demande le mutexn", numero);
pthread_mutex_lock(& mutex);
fprintf(stderr, " [%d] tient le mutexn", numero);
sleep(1);
fprintf(stderr, "[%d] lache le mutexn", numero);
pthread_mutex_unlock(& mutex);
sched_yield();
}
return NULL;
}
[...]
L’exécution confirme bien le comportement attendu.
# ./mutex-08
[1] demande le mutex
[2] demande le mutex
[3] demande le mutex
[4] demande le mutex
[5] demande le mutex
Liberation initiale du mutex
[1] tient le mutex
[1] lache le mutex
[2] tient le mutex
[1] demande le mutex
[2] lache le mutex
[3] tient le mutex
[2] demande le mutex
[3] lache le mutex
[4] tient le mutex
[3] demande le mutex
[4] lache le mutex
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[1] tient le mutex
[5] demande le mutex
[1] lache le mutex
[2] tient le mutex
[1] demande le mutex
[2] lache le mutex
[3] tient le mutex
[2] demande le mutex
[3] lache le mutex
[4] tient le mutex
[3] demande le mutex
[4] lache le mutex
[5] tient le mutex
[4] demande le mutex
[5] lache le mutex
[1] tient le mutex
[5] demande le mutex
[1] lache le mutex
[2] tient le mutex
[...]
#
Conclusion
La mise au point d’une application temps-réel est une chose complexe, et de nombreux « pièges » inattendus peuvent se présenter (inversion de priorités…). La prise en boucle d’un mutex peut s’avérer déroutante et difficilement prédictible.
Le premier réflexe est souvent d’utiliser des délais, des attentes, pour synchroniser les opérations. Cette méthode, bien que fonctionnelle dans la plupart des cas, n’est pas toujours optimale ni portable. En explorant l’API disponible, le programmeur pourra souvent trouver de meilleures solutions (variables-conditions, de-scheduling volontaires, etc.). Je vous encourage à étudier les fonctionnalités décrites dans les normes comme Posix ou SUSv3 pour tirer le meilleur parti des possibilités de votre système.
