{"id":2529,"date":"2012-07-16T07:00:40","date_gmt":"2012-07-16T06:00:40","guid":{"rendered":"http:\/\/www.blaess.fr\/christophe\/?p=2529"},"modified":"2012-11-30T13:34:13","modified_gmt":"2012-11-30T12:34:13","slug":"incrementation-et-non-atomicite","status":"publish","type":"post","link":"https:\/\/www.blaess.fr\/christophe\/2012\/07\/16\/incrementation-et-non-atomicite\/","title":{"rendered":"Incr\u00e9mentation et (non) atomicit\u00e9"},"content":{"rendered":"

\"Incr\u00e9mentation<\/a>J’ai remarqu\u00e9, au cours de plusieurs sessions de formations<\/a>, que de nombreux d\u00e9veloppeurs pensent que certains op\u00e9rateurs du C (ou de ses descendants)\u00a0 sont naturellement atomiques vis-\u00e0-vis de l’ordonnancement. Pour v\u00e9rifier ou r\u00e9futer ceci, j’ai fait r\u00e9cemment quelques essais avec les participants d’un de mes cours.<\/p>\n

\n\n<\/p>\n

Atomicit\u00e9 d’une op\u00e9ration<\/h1>\n

La notion d’atomicit\u00e9 qui nous concerne ici se rapporte \u00e0 l’ordonnancement. Une op\u00e9ration sera consid\u00e9r\u00e9e comme atomique vis-\u00e0-vis du scheduler<\/em> si ce dernier nous garantit qu’une fois l’op\u00e9ration entam\u00e9e, elle s’ex\u00e9cutera jusqu’\u00e0 son terme sans \u00eatre interrompue par une autre t\u00e2che en attente. Il existe diff\u00e9rent degr\u00e9s d’atomicit\u00e9 suivant le niveau d\u00e9sir\u00e9 de protection contre les discontinuit\u00e9 d’ex\u00e9cution.<\/p>\n

Les instructions assembleurs ex\u00e9cut\u00e9es par le micro-processeur sont g\u00e9n\u00e9ralement atomiques et se d\u00e9roulent en une seule \u00e9tape (mais en plusieurs cycles d’horloge) m\u00eame si une demande d’interruption mat\u00e9rielle (IRQ – Interrupt Request<\/em>) survient pendant leur ex\u00e9cution. Ces instructions sont souvent tr\u00e8s simples et la moindre op\u00e9ration un tant soit peu significative pour un programme applicatif regroupe plusieurs – voire plusieurs dizaines – d’instructions assembleurs. Notons que l’atomicit\u00e9 de certaines instructions assembleurs r\u00e9alisant plusieurs actions comme celle nomm\u00e9e BTS<\/code> (Bit Test and Set<\/em>) dans les processeurs x86 (qui fixe un bit d’un registre et renvoie sa valeur pr\u00e9c\u00e9dente) est essentielle pour la construction de certaines structures de contr\u00f4le et outils de synchronisation (mutex, spinlock, s\u00e9maphores…).<\/p>\n

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()<\/code> ou local_irq_save()<\/code> – ou en indiquant \u00e0 l’ordonnanceur qu’une t\u00e2che ne doit pas \u00eatre pr\u00e9empt\u00e9e – en appelant preempt_disable()<\/code>. Ceci n’est toutefois valable que dans le code kernel, aucune de ces op\u00e9rations n’est accessible \u00e0 l’espace utilisateur.<\/p>\n

\u00a0Pour les applications, l’atomicit\u00e9 d’une op\u00e9ration est habituellement rendue n\u00e9cessaire pour se pr\u00e9munir contre l’acc\u00e8s simultan\u00e9 \u00e0 des zones de m\u00e9moire partag\u00e9e. Imaginons que nous souhaitions v\u00e9rifier la somme de contr\u00f4le d’une trame de donn\u00e9es re\u00e7ue depuis un port s\u00e9rie. Notre t\u00e2che commence \u00e0 additionner les octets de la trame. Soudain, une interruption se produit et l’ordonnanceur d\u00e9cide d’activer une autre t\u00e2che qui travaille sur la m\u00eame zone de m\u00e9moire (pour y inscrire une nouvelle trame re\u00e7ue par exemple). Lorsque nous revenons sur notre premi\u00e8re t\u00e2che, celle-ci termine son calcul de checksum<\/em> avec une fin de trame qui n’est plus en corr\u00e9lation avec les premier octets observ\u00e9s auparavant. Donc une somme de contr\u00f4le invalide. Donc une trame de donn\u00e9es rejet\u00e9e ind\u00fbment. Donc un bug…<\/p>\n

Pour se prot\u00e9ger, on a coutume de verrouiller syst\u00e9matiquement un mutex – avec pthread_mutex_lock()<\/code> – avant tout acc\u00e8s \u00e0 des donn\u00e9es partag\u00e9es entre threads du m\u00eame processus puis de le lib\u00e9rer ensuite avec pthread_mutex_unlock()<\/code>. Lorsque les donn\u00e9es sont partag\u00e9es entre diff\u00e9rents processus plut\u00f4t qu’entre threads, on emploie un s\u00e9maphore – de l’API Posix avec sem_wait()<\/code> et sem_post()<\/code> ou Syst\u00e8me V avec semop()<\/code>.<\/p>\n

Non atomicit\u00e9 d’une op\u00e9ration<\/h1>\n

Dans la longue liste des l\u00e9gendes modernes et des croyances erron\u00e9es comme les void main(void)<\/code> ou fflush(stdin)<\/code> en C, ou export PATH=$PATH:...<\/code> dans un script shell, ou encore\u00a0 sync;sync;sync<\/code> avant d’arr\u00eater un syst\u00e8me, il en est une qui a la vie dure : \u00ab\u00a0l’op\u00e9rateur ++ du C effectue une incr\u00e9mentation atomique<\/em>\u00a0\u00bb parfois nuanc\u00e9e en \u00ab\u00a0l’op\u00e9rateur ++ sur une variable de type int<\/code><\/span> <\/em> est atomique\u00a0\u00bb.<\/p>\n

Non, le C ne nous garantit rien de tel !<\/p>\n

La preuve ? Essayons !<\/p>\n

Je vais prendre en exemple l’incr\u00e9mentation d’une variable enti\u00e8re partag\u00e9e entre deux threads.<\/p>\n

La variable est initialis\u00e9e \u00e0 z\u00e9ro. Pour mettre en \u00e9vidence la collision durant les acc\u00e8s \u00e0 cette variable, je vais lancer deux threads qui essayeront simultan\u00e9ment de l’incr\u00e9menter un milliard de fois. Une fois les deux threads termin\u00e9s, nous afficherons la valeur de cette variable. En toute logique nous attendons \u00ab\u00a0deux milliards\u00a0\u00bb mais ce n’est pas ce que nous obtiendrons.<\/p>\n

threads_increments.c<\/a>:<\/strong>\n#include <pthread.h>\n#include <stdio.h>\n#include <stdlib.h>\n#include <unistd.h>\n\nint compteur = 0;\n\nvoid * fonction_thread (void * unused)\n{\n    int i;\n    int j;\n    for (i = 0; i < 1000000000; i ++)\n        compteur ++;<\/strong>\n    return NULL;\n}\n\nint main(void)\n{\n    pthread_t thr1, thr2;\n    pthread_create(& thr1, NULL, fonction_thread, NULL);\n    pthread_create(& thr2, NULL, fonction_thread, NULL);\n    pthread_join(thr1, NULL);\n    pthread_join(thr2, NULL);\n    fprintf(stdout, \"%dn\", compteur);\n    return EXIT_SUCCESS;\n}<\/pre>\n
\u00a0Ce genre de code n’est bien s\u00fbr pas propre du tout, il faudrait prot\u00e9ger par un mutex l’acc\u00e8s \u00e0 cette variable globale. Essayons-le…<\/p>\n
$ gcc threads_increments.c -o threads_increments -pthread -O2<\/strong>\n$ .\/threads_increments<\/strong> \n1003987499\n$ .\/threads_increments<\/strong> \n1029276863\n$ .\/threads_increments<\/strong> \n1024894145\n$<\/pre>\n
Nous esp\u00e8rions atteindre deux milliards et nous arrivons poussivement jusqu’\u00e0 un milliard… Essayons de contraindre nos deux threads sur le m\u00eame CPU.<\/p>\n
$ taskset -c 0 .\/threads_increments<\/strong>\n1191969269\n$ taskset -c 0 .\/threads_increments<\/strong>\n1188035064\n$ taskset -c 0 .\/threads_increments<\/strong>\n1191212419\n$<\/pre>\n
Il y a un peu moins de collisions si les deux t\u00e2ches s’ex\u00e9cutent sur un m\u00eame c\u0153ur de processeur (car la concurrence repose alors sur la pr\u00e9emption mutuelle et non plus sur le parall\u00e9lisme), mais le r\u00e9sultat n’est toujours pas concluant.<\/p>\n
Vous pouvez essayer de reprendre cet exemple avec des variantes comme<\/p>\n