grim7reaper

Un artisan du code

Débogage pour la programmation concurrente — Contexte

Problèmes

La programmation concurrente est source d’erreurs qui sont difficiles à reproduire car leur apparition dépend d’un certains nombre de paramètres tels que l’ordonnanceur utilisé, le nombre de processus sur le système, … Il est donc nécessaire d’avoir des outils pour aider à les détecter. On retrouve principalement deux grands type d’erreurs : les situations de compétition et les interblocages.

Situation de compétition

Dans une situation de compétition deux threads accèdent à la même zone mémoire sans protection, et au moins un des accès est une écriture. Exemple avec le code suivant :

Exemple de situation de compétition
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdlib.h>
#include <stdio.h>

#include <pthread.h>

struct T { int i; };

static struct T* foo = NULL;

void init_foo(void)
{
    if(!foo)
        foo = malloc(sizeof *foo);
}

static void* thread1(void* dummy)
{
    (void)dummy;
    init_foo();
    return NULL;
}

static void* thread2(void* dummy)
{
    (void)dummy;
    init_foo();
    return NULL;
}

Dans ce code, la variable foo est partagée entre les deux threads mais aucun mécanisme de synchronisation n’est mis en place pour en contrôler l’accès. On peut donc avoir l’exécution suivante :

  1. thread1 commence son exécution, il appelle init_foo ;
  2. init_foo commence son exécution et exécute le test à la ligne 12, foo est NULL donc on entre dans le if ;
  3. init_foo est interrompu par l’ordonnanceur, il donne la main à thread2 ;
  4. thread2 s’exécute et appelle init_foo à son tour ;
  5. init_foo commence son exécution, exécute le test de la ligne 12, foo est NULL donc on entre dans le if et on alloue la mémoire pour foo (ligne 13) ;
  6. l’ordonnanceur redonne la main à thread1 qui reprend l’exécution d’init_foo là où elle s’était arrêtée, donc ligne 13 (après le test, car celui-ci a été réalisé avant l’interruption). La mémoire est donc allouée une seconde fois.

On a donc un problème: malgré le if, la mémoire est allouée deux fois et la seconde allocation écrase l’adresse de la première ce qui provoque une fuite de mémoire. Ce problème est dû à une situation de compétition entre thread1 et thread2 pour la variable foo.

Interblocage

Pour résoudre ce problème on peut ajouter des verrous pour contrôler l’accès à foo. Mais cela doit être fait avec soin, sous peine de provoquer un interblocage. Encore une fois, voici un petit code d’exemple (oui c’est stupide, un seul verrou est nécessaire dans ce cas-là, mais c’est pour illustrer l’interblocage) :

Exemple d’interblocage
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#include <stdlib.h>
#include <stdio.h>

#include <pthread.h>

struct T { int i; };

pthread_mutex_t mutexA = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t mutexB = PTHREAD_MUTEX_INITIALIZER;
static struct T* foo = NULL;

void init_foo(void)
{
    if(!foo)
        foo = malloc(sizeof *foo);
}

static void* thread1(void* dummy)
{
    (void)dummy;

    /* Ordre A-B. */
    pthread_mutex_lock(&mutexA);
    pthread_mutex_lock(&mutexB);
    init_foo();
    pthread_mutex_unlock(&mutexB);
    pthread_mutex_unlock(&mutexA);

    return NULL;
}

static void* thread2(void* dummy)
{
    (void)dummy;

    /*  Ordre B-A => ordre différent de thread1 => /!\ Problème !!!! */
    pthread_mutex_lock(&mutexB);
    pthread_mutex_lock(&mutexA);
    init_foo();
    pthread_mutex_unlock(&mutexA);
    pthread_mutex_unlock(&mutexB);

    return NULL;
}

Dans ce code, l’ordre d’utilisation des verrous n’est pas cohérent et peux donc provoquer un interblocage si l’on a l’exécution suivante :

  1. thread1 s’exécute, il acquiert mutexA ;
  2. thread1 est interrompu par l’ordonnanceur, il donne la main à thread2 ;
  3. thread2 s’exécute, il acquiert mutexB et attend la libération de mutexA (qui est en possession de thread1) ;
  4. thread1 attend la libération de mutexB (qui est en possession de thread2) ;
  5. les deux threads s’attendent mutuellement, il y a interblocage.

On voit donc l’importance d’avoir des outils pouvant détecter ce genre d’erreur.

Solutions

Pour détecter les erreurs présentées dans la section précédente, il existe quatre grandes approches.

Model checking

Cette approche consiste à modéliser le système à vérifier sous la forme d’un automate fini. On obtient alors un graphe orienté où chaque nœud est associé à des propositions logiques (propositions qui ne peuvent qu’être vraies ou fausses) qui en décrivent l’état. Avec cette structure, on est en mesure de vérifier le respect de certaines propriétés, telle que l’absence d’interblocage. Le problème majeur de cette approche est l’explosion de l’espace des états, ce qui limite fortement la taille des systèmes vérifiables avec une puissance de calcul raisonnable et/ou dans un temps raisonnable.

Analyse statique

Dans cette approche on analyse le code source du programme pour essayer d’y trouver des erreurs. Le problème est qu’il n’est pas possible (dans un temps raisonnable) de trouver toutes les erreurs de ce genre car c’est un problème NP-difficile1. Un problème NP-difficile étant un problème au moins aussi difficile à résoudre qu’un problème NP (problème que l’on peut résoudre efficacement en un temps polynomial en utilisant une machine de Turing non déterministe).

Analyse dynamique

Cette analyse nécessite d’intercepter et de traiter certains évènements qui surviennent lors de l’exécution pendant l’exécution elle-même. L’inconvénient est que le traitement induit un ralentissement sensible de l’exécution.

Analyse post-mortem

Contrairement à l’approche précédente, on ne traite pas les évènements interceptés. On se contente de les enregistrer. Un enregistrement étant bien plus rapide qu’un traitement, le surcoût est plus faible et le ralentissement induit est donc négligeable dans la plupart des cas. Une fois l’exécution du programme terminée, on analyse les traces générées. Le problème ici est que les traces générées peuvent être d’une taille conséquente. En fait, si l’on veut traquer les erreurs de programmation concurrente, ce qui est notre cas ici, il est nécessaire d’enregistrer tous les accès mémoire et cela rend les traces très grosses.

Dans le prochain épisode…

Comme on peut le voir, aucune des approches n’est exempte d’inconvénients. Étant donné qu’il est plus facile d’étudier un outil open source (car on a accès au code), nous allons donc nous pencher sur la détection d’erreurs par analyse dynamique au travers de Valgrind et de ses différents outils dans les deux prochains articles.

  1. Netzer, R. H., and Miller, B. P. What are race conditions? - some issues and formalizations. ACM Letters on Programming Languages and Systems 1 (1992), 74–88.↩