J’ai remarqué, au cours de plusieurs sessions de formations, que de nombreux développeurs pensent que certains opérateurs du C (ou de ses descendants)  sont naturellement atomiques vis-à-vis de l’ordonnancement. Pour vérifier ou réfuter ceci, j’ai fait récemment quelques essais avec les participants d’un de mes cours.

Atomicité d’une opération

La notion d’atomicité qui nous concerne ici se rapporte à l’ordonnancement. Une opération sera considérée comme atomique vis-à-vis du scheduler si ce dernier nous garantit qu’une fois l’opération entamée, elle s’exécutera jusqu’à son terme sans être interrompue par une autre tâche en attente. Il existe différent degrés d’atomicité suivant le niveau désiré de protection contre les discontinuité d’exécution.

Les instructions assembleurs exécutées par le micro-processeur sont généralement atomiques et se déroulent en une seule étape (mais en plusieurs cycles d’horloge) même si une demande d’interruption matérielle (IRQ – Interrupt Request) survient pendant leur exécution. Ces instructions sont souvent très simples et la moindre opération un tant soit peu significative pour un programme applicatif regroupe plusieurs – voire plusieurs dizaines – d’instructions assembleurs. Notons que l’atomicité de certaines instructions assembleurs réalisant plusieurs actions comme celle nommée BTS (Bit Test and Set) dans les processeurs x86 (qui fixe un bit d’un registre et renvoie sa valeur précédente) est essentielle pour la construction de certaines structures de contrôle et outils de synchronisation (mutex, spinlock, sémaphores…).

Dans le code du noyau, il est possible de rendre une portion de code atomique en coupant les interruptions sur le processeur local – avec local_irq_disable() ou local_irq_save() – ou en indiquant à l’ordonnanceur qu’une tâche ne doit pas être préemptée – en appelant preempt_disable(). Ceci n’est toutefois valable que dans le code kernel, aucune de ces opérations n’est accessible à l’espace utilisateur.

 Pour les applications, l’atomicité d’une opération est habituellement rendue nécessaire pour se prémunir contre l’accès simultané à des zones de mémoire partagée. Imaginons que nous souhaitions vérifier la somme de contrôle d’une trame de données reçue depuis un port série. Notre tâche commence à additionner les octets de la trame. Soudain, une interruption se produit et l’ordonnanceur décide d’activer une autre tâche qui travaille sur la même zone de mémoire (pour y inscrire une nouvelle trame reçue par exemple). Lorsque nous revenons sur notre première tâche, celle-ci termine son calcul de checksum avec une fin de trame qui n’est plus en corrélation avec les premier octets observés auparavant. Donc une somme de contrôle invalide. Donc une trame de données rejetée indûment. Donc un bug…

Pour se protéger, on a coutume de verrouiller systématiquement un mutex – avec pthread_mutex_lock() – avant tout accès à des données partagées entre threads du même processus puis de le libérer ensuite avec pthread_mutex_unlock(). Lorsque les données sont partagées entre différents processus plutôt qu’entre threads, on emploie un sémaphore – de l’API Posix avec sem_wait() et sem_post() ou Système V avec semop().

Non atomicité d’une opération

Dans la longue liste des légendes modernes et des croyances erronées comme les void main(void) ou fflush(stdin) en C, ou export PATH=$PATH:... dans un script shell, ou encore  sync;sync;sync avant d’arrêter un système, il en est une qui a la vie dure : « l’opérateur ++ du C effectue une incrémentation atomique » parfois nuancée en « l’opérateur ++ sur une variable de type int est atomique ».

Non, le C ne nous garantit rien de tel !

La preuve ? Essayons !

Je vais prendre en exemple l’incrémentation d’une variable entière partagée entre deux threads.

La variable est initialisée à zéro. Pour mettre en évidence la collision durant les accès à cette variable, je vais lancer deux threads qui essayeront simultanément de l’incrémenter un milliard de fois. Une fois les deux threads terminés, nous afficherons la valeur de cette variable. En toute logique nous attendons « deux milliards » mais ce n’est pas ce que nous obtiendrons.

threads_increments.c:
#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int compteur = 0;

void * fonction_thread (void * unused)
{
    int i;
    int j;
    for (i = 0; i < 1000000000; i ++)
        compteur ++;
    return NULL;
}

int main(void)
{
    pthread_t thr1, thr2;
    pthread_create(& thr1, NULL, fonction_thread, NULL);
    pthread_create(& thr2, NULL, fonction_thread, NULL);
    pthread_join(thr1, NULL);
    pthread_join(thr2, NULL);
    fprintf(stdout, "%dn", compteur);
    return EXIT_SUCCESS;
}

 Ce genre de code n’est bien sûr pas propre du tout, il faudrait protéger par un mutex l’accès à cette variable globale. Essayons-le…

$ gcc threads_increments.c -o threads_increments -pthread -O2
$ ./threads_increments 
1003987499
$ ./threads_increments 
1029276863
$ ./threads_increments 
1024894145
$

Nous espèrions atteindre deux milliards et nous arrivons poussivement jusqu’à un milliard… Essayons de contraindre nos deux threads sur le même CPU.

$ taskset -c 0 ./threads_increments
1191969269
$ taskset -c 0 ./threads_increments
1188035064
$ taskset -c 0 ./threads_increments
1191212419
$

Il y a un peu moins de collisions si les deux tâches s’exécutent sur un même cœur de processeur (car la concurrence repose alors sur la préemption mutuelle et non plus sur le parallélisme), mais le résultat n’est toujours pas concluant.

Vous pouvez essayer de reprendre cet exemple avec des variantes comme

• déclarer la variable globale volatile,
• utiliser ++compteur au lieu de compteur++,
• compiler avec ou sans l’option -O2 (optimisation du code produit)
• etc.

Rien n’y fait, les collisions d’accès à la variable globale rendent le résultat incorrect. La seule solution serait d’encadrer ces accès par des pthread_mutex_lock() / pthread_mutex_unlock().

Code assembleur

Il peut paraître étonnant que l’opération i++ (ou ++i au choix) ne soit pas atomique. Observons le code assembleur produit par gcc en repartant d’un exemple plus simple que le précédent.

incrementation.c:
#include <stdio.h>
#include <stdlib.h>

int main(int argc, char * argv[])
{
    int i;

    if ((argc != 2)
     || (sscanf(argv[1], "%d", & i) != 1)) {
        fprintf(stderr, "usage: %s valeurn", argv[0]);
        exit(EXIT_FAILURE);
    }
    fprintf(stdout, "Valeur initiale : %dn", i);

    i ++;

    fprintf(stdout, "Valeur incrementee : %dn", i);
    return EXIT_SUCCESS;
}

Compilons-le et examinons le code désassemblé.

$ gcc incrementation.c -o incrementation 
$ objdump -d incrementation
[...]
080484b4 <main>:
 80484b4:       55                      push   %ebp
 80484b5:       89 e5                   mov    %esp,%ebp
 80484b7:       83 e4 f0                and    $0xfffffff0,%esp
 80484ba:       83 ec 20                sub    $0x20,%esp
 80484bd:       83 7d 08 02             cmpl   $0x2,0x8(%ebp)
 80484c1:       75 26                   jne    80484e9 <main+0x35>
 80484c3:       ba 40 86 04 08          mov    $0x8048640,%edx
 80484c8:       8b 45 0c                mov    0xc(%ebp),%eax
 80484cb:       83 c0 04                add    $0x4,%eax
 80484ce:       8b 00                   mov    (%eax),%eax
 80484d0:       8d 4c 24 1c             lea    0x1c(%esp),%ecx
 80484d4:       89 4c 24 08             mov    %ecx,0x8(%esp)
 80484d8:       89 54 24 04             mov    %edx,0x4(%esp)
 80484dc:       89 04 24                mov    %eax,(%esp)
 80484df:       e8 0c ff ff ff          call   80483f0 <__isoc99_sscanf@plt>
 80484e4:       83 f8 01                cmp    $0x1,%eax
 80484e7:       74 2b                   je     8048514 
 80484e9:       8b 45 0c                mov    0xc(%ebp),%eax
 80484ec:       8b 08                   mov    (%eax),%ecx
 80484ee:       ba 43 86 04 08          mov    $0x8048643,%edx
 80484f3:       a1 20 a0 04 08          mov    0x804a020,%eax
 80484f8:       89 4c 24 08             mov    %ecx,0x8(%esp)
 80484fc:       89 54 24 04             mov    %edx,0x4(%esp)
 8048500:       89 04 24                mov    %eax,(%esp)
 8048503:       e8 d8 fe ff ff          call   80483e0 <fprintf@plt>
 8048508:       c7 04 24 01 00 00 00    movl   $0x1,(%esp)
 804850f:       e8 ac fe ff ff          call   80483c0 <exit@plt>
 8048514:       8b 4c 24 1c             mov    0x1c(%esp),%ecx
 8048518:       ba 55 86 04 08          mov    $0x8048655,%edx
 804851d:       a1 40 a0 04 08          mov    0x804a040,%eax
 8048522:       89 4c 24 08             mov    %ecx,0x8(%esp)
 8048526:       89 54 24 04             mov    %edx,0x4(%esp)
 804852a:       89 04 24                mov    %eax,(%esp)
 804852d:       e8 ae fe ff ff          call   80483e0 <fprintf@plt>
 8048532: 8b 44 24 1c mov 0x1c(%esp),%eax
 8048536: 83 c0 01 add $0x1,%eax
 8048539: 89 44 24 1c mov %eax,0x1c(%esp)
 804853d:       8b 4c 24 1c             mov    0x1c(%esp),%ecx
 8048541:       ba 6b 86 04 08          mov    $0x804866b,%edx
 8048546:       a1 40 a0 04 08          mov    0x804a040,%eax
 804854b:       89 4c 24 08             mov    %ecx,0x8(%esp)
 804854f:       89 54 24 04             mov    %edx,0x4(%esp)
 8048553:       89 04 24                mov    %eax,(%esp)
 8048556:       e8 85 fe ff ff          call   80483e0 <fprintf@plt>
 804855b:       b8 00 00 00 00          mov    $0x0,%eax
 8048560:       c9                      leave  
 8048561:       c3                      ret    
[...]
$

Inutile d’être un spécialiste de l’assembleur PC pour comprendre ce code. On peut suivre assez facilement sa structure.

• 80484bd cmpl... : test correspondant à (argc != 2)
• 80484df call... : invocation de sscanf(argv[1]...
• 8048503 call... : affichage d’erreur avec fprintf(stderr, "usage..."
• 804850f call... : sortie du programme exit(EXIT_FAILURE)
• 804852d call... : premier affichage fprintf(stdout, "Valeur initiale...
• 8048556 call... : second affichage avec fprintf(stdout, "Valeur incrementee...

Mais nous pouvons également apercevoir les lignes suivantes

 8048532:       8b 44 24 1c             mov    0x1c(%esp),%eax
 8048536:       83 c0 01                add    $0x1,%eax
 8048539:       89 44 24 1c             mov    %eax,0x1c(%esp)

Clairement, il s’agit de notre opération d’incrémentation. Et tout aussi clairement, elle n’est pas du tout atomique. Il est tout à fait possible que notre tâche soit préemptée entre le premier chargement de eax depuis la mémoire et l’addition, ou entre l’addition et la reéécriture de la valeur incrémentée.

Pourtant il existe bien un opérateur INC dans l’assembleur 80386 capable d’agir sur un mot mémoire de 1, 2 ou 4 octets. Peut-être gcc ne l’utilise-t’il qu’en optimisation de code ? Vérifions…

$ gcc incrementation.c -o incrementation -O2
$ objdump -d incrementation
[...]
08048420 <main>:
 [...]
 8048473:       e8 98 ff ff ff          call   8048410 <__fprintf_chk@plt>
 8048478: 8b 44 24 1c mov 0x1c(%esp),%eax
 804847c:       c7 44 24 08 8b 86 04    movl   $0x804868b,0x8(%esp)
 8048483:       08 
 8048484:       c7 44 24 04 01 00 00    movl   $0x1,0x4(%esp)
 804848b:       00 
 804848c: 83 c0 01 add $0x1,%eax
 804848f: 89 44 24 1c mov %eax,0x1c(%esp)
 8048493:       89 44 24 0c             mov    %eax,0xc(%esp)
 8048497:       a1 40 a0 04 08          mov    0x804a040,%eax
 804849c:       89 04 24                mov    %eax,(%esp)
 804849f:       e8 6c ff ff ff          call   8048410 <__fprintf_chk@plt>
 [...]
$

C’est encore pire ! Cette fois deux instructions sont intercalées entre la lecture de la valeur initiale et son incrémentation. Encore plus de risque d’être préempté…

Essayons de préciser que nous travaillons avec un processeur descendant du 80386.

$ gcc incrementation.c -o incrementation -O2 -mtune=i386
$ objdump -d incrementation
[...]
 8048476:       8b 44 24 1c             mov    0x1c(%esp),%eax
 804847a:       40                      inc    %eax
 804847b:       89 44 24 1c             mov    %eax,0x1c(%esp)
[...]
$

Le code produit utilise inc %eax au lieu de add $0x1,%eax mais il n’incrémente toujours pas la variable directement en mémoire.

Conclusion

Notre première expérience a mis en évidence des collisions sur une variable partagée entre threads. Le code était outrancier puisqu’il s’agissait d’accès intensifs et simultanés. Je ne crois pas qu’un développeur puisse raisonnablement écrire ce genre de chose. Toutefois, j’ai déjà vu des programmes où des accès (rares) à certaines variables entières (compteurs statistiques, flags du type « condition_1_ok » etc.) n’était pas protégés en partant de cette croyance que l’incrémentation d’un variable int était atomique. C’est un bug. Un bug qui se déclenche très rarement certes, mais c’est justement ce qui le rend difficilement détectable. Tout accès à des variables partagées entre des tâches – threads ou processus – doit être protégé par un mécanisme approprié : mutex, spinlock, sémaphore, etc.