samedi 27 avril 2013

Programmation multithread, kesako ?

La loi de Moore prévoit que la puissance des ordinateurs double tous les deux ans. Or, depuis 2004, la fréquence des processeurs tend à stagner en raison de difficultés rencontrées par la miniaturisation des composants.
Pour gagner en puissance, les constructeurs de microprocesseurs ont dû avoir recours au traitement parallèle afin de maintenir les prédictions de Gordon. Pour ce faire, ils ont privilégié le nombre de cœur tout en prônant la programmation multitâche (appelé multithread dans le jargon).

Dans cet article de vulgarisation, je vais essayer de décrire de façon simple en quoi consiste la programmation multitâche et pourquoi ce concept rend la vie des développeurs qui veulent s'y atteler plus difficile. Nous verrons aussi que malgré les promesses de puissance, toutes les applications ne gagnent pas à être écrite en multithread.


Concept de base

Pour que tout le monde comprenne bien le principe, je vais prendre l'exemple d'une femme de ménage qui doit ranger une maison.


Son programme de rangement est le suivant :
- ranger la salle de bain
- faire les sols
- ranger la cuisine
- ranger le salon
- faire les vitres
- ranger la chambre

Maintenant, comment faire pour que la maison soit rangée le plus vite possible ?

La première idée consiste à optimiser le programme. Par exemple si nous observons que notre femme de ménage utilise les mêmes produits pour la chambre et pour la salle de bain, nous pouvons placer ces deux tâches de manière consécutive. Ensuite, nous pouvons dire que faire les vitres et les sols sont des tâches à faire à la fin. Et si en plus ces deux tâches utilisent les mêmes produits ménagers que pour la salle de bain, on peut les placer à la suite, ce qui donnerais :

- ranger la chambre
- ranger le salon
- ranger la cuisine
- ranger la salle de bain
- faire les sols
- faire les vitres


Après quelques essais, on se rend compte que notre programme est optimisé, mais on ne gagne pas énormément en performance.

Nous décidons alors d'augmenter la fréquence d’exécution de notre femme de ménage :
La maison se range un peut plus vite, mais vous conviendrez que la femme de ménage à une limite physique que même la cocaïne et la promesse d'un gros salaire ne peuvent dépasser.

Pour aller plus vite, il faut donc faire du multitâche, et c'est la que les choses se compliquent.

Déjà, première chose, comme vous l'aurez compris dans mon analogie, la femme de ménage représente le microprocesseur de l'ordinateur, c'est à dire l'unité d’exécution du programme.

Si je demande à cette même femme de ménage de ranger en même temps la chambre, le salon, la cuisine, la salle de bain, etc... je lui fait faire du multitâche ! mais que va-t-il se passer ?



Tout d'abord, elle vas commencer par la chambre. En plein milieu de son activité, elle va tout arrêter, noter sur un petit tableau ce qu'elle est entrain de faire, ranger son matériel dans son petit chariot pour passer dans le salon. Là, elle va redéployer tout son matériel afin de commencer une nouvelle tâche comme passer l'aspirateur. Au bout de quelques minutes, elle arrête, note là où elle en est, range son matériel et passe dans la cuisine, tout cela en boucle jusqu’à ce que la maison soit toute rangée.

Comme vous le remarquerez, le passage d'une tâche à une autre fait perdre beaucoup de temps. C'est ce que l'on appelle en informatique le "Context Switch". Ainsi, faire un programme qui exécute plus de tâches parallèles qu'il n'y a d'unité d’exécution fait perdre énormément de temps ! Voici un premier point de vigilance à prendre en compte lorsque l'on est débutant en programmation multithread.

La solution semble donc toute trouvée ! Il suffit d'avoir autant de femme de ménage qu'il y a de tâches parallélisables.

Une pour ranger la chambre,
Une pour ranger le salon,
Une pour ranger la cuisine,
Une pour ranger la salle de bain
Une pour les sols et une pour les vitres. 

Ce qui fait 6 femmes de ménages qui peuvent travailler en même temps, ainsi la maison sera rangée 6 fois plus vite !

Voici la réflexion que se sont faits les constructeurs de microprocesseur. Le seul moyen d'aller plus vite est de mettre à disposition du programmeur un maximum d'unités de traitement. C'est ce qu'on appelle des cœurs (core en anglais).

Ainsi lorsque vous lisez dans les caractéristiques techniques d'un microprocesseur "2 coeurs, 4 Threads" cela signifie que vous disposez de deux unités de traitement, qui chacune est capable de faire deux choses à la fois sans faire de "Context Switch" (par un mécanisme appelé l'hyperthreading) ce qui virtuellement correspond à 4 unités de calcul.




En gros on vous explique que vous avez 2 femmes de ménages, mais que l'une peut ranger la chambre tout en repassant des chemises, et que l'autre peut faire la vaisselle tout en rangeant la cuisine, alors c'est comme si vous aviez 4 femmes de ménages. Oui je sais, c'est un peut de l'arnaque, et c'est pour ça qu'il vaut mieux privilégier le nombre de cœurs au nombre de threads.

Quelle est l'impacte en terme de programmation ?


Le programmeur qui désire tirer parti de toutes les unités de calcul mises à sa disposition dans son programme n'est pas au bout de ses peines, car celui ci doit gérer plusieurs mécanismes de synchronisation qui non seulement s'avèrent très difficiles à mettre en oeuvre, mais qui plus est, complexifie énormément la relecture de code ainsi que la recherche de bug.

La synchronisation des ressources

Vous avez 6 femmes de ménages qui travaillent en parallèles. Mais comment ça se passe si elles n'ont à leur disposition qu'un seul aspirateur et une seule serpillière ? C'est ce que l'on appelle en informatique la synchronisation de ressources.

Prenons un exemple simple : 
La femme de ménage qui range le salon a pour programme :

  • Passer l'aspirateur
  • Si une tache est visible sur la moquette
    • Prendre l'éponge sur le meuble de la cuisine
    • Laver la tache avec l'éponge
    • Reposer l'éponge sur le meuble de la cuisine
  • Continuer à passer l'aspirateur.

La femme de ménage qui range la cuisine a quant à elle le programme suivant :

  • Ranger la vaisselle issue du lave vaisselle.
  • Si une assiette n'est pas propre
    • Prendre l'éponge sur le meuble de la cuisine
    • Laver l'assiette avec l'éponge
    • Reposer l'éponge sur le meuble de la cuisine
  • Continuer à ranger la vaisselle

Vous remarquez qu'entre ces deux programmes, il y a une ressource partagée qui est l'éponge.




Prendre l'éponge sur le meuble de la cuisine et Reposer l'éponge sur le meuble de la cuisine sont des actions de synchronisation de ressource qu'on appelle en informatique des "sections critiques" qui permettent le "verrouillage par exclusion mutuelle"

Effectivement, lorsque les deux femmes de ménage vont travailler à leurs tâches respectives, si les deux désirent prendre l'éponge en même temps, c'est la première qui aura mis la main dessus qui l' obtiendra, la seconde devra attendre que l'éponge soit remise sur le meuble de la  cuisine pour la prendre à son tour.

Comme vous vous en doutez, celle qui c'est fait piquer l'éponge doit attendre que l'autre veuille bien la rapporter pour continuer son travail, ce qui fait perdre du temps, et peut engendrer de nombreux bugs.

Par exemple, si dans le programme de celle qui range le salon, nous avions oublié de dire Reposer l'éponge sur le meuble de la cuisine, que se passait-il ?

Tant que la femme de ménage qui range le salon ne trouve pas de tache sur la moquette, tout se passe bien. D'ailleurs, tout se passe aussi bien si elle trouve une tache sur la moquette alors que celle qui fait la cuisine a fini de ranger le lave vaisselle. Par contre, si celle du salon prend l'éponge et que celle qui range la cuisine en a besoin car elle a trouvée une assiette sale dans le lave vaisselle, elle attendra indéfiniment l'éponge et ne pourra pas terminer son travail du fait que celle qui range le salon ne la ramènera jamais !

Ce bug de synchronisation de ressource tout bête est déjà bien difficile à analyser alors que seulement une ressource est en concurrence avec deux tâches parallèles. Le moindre oubli en programmation multithread ne pardonne pas !

Un autre type de bugs similaire appelé le "dead-lock" fait le cauchemar des programmeurs.
Imaginons que les programmes de nos deux femmes de ménages soient modifiés de la façon suivante :

La femme de ménage qui range le salon a pour nouveau programme :
  • Faire la poussière
  • Faire d'autres trucs.
  • Prendre l'aspirateur dans le placard.
  • Passer l'aspirateur
  • Si une tache est visible sur la moquette
    • Prendre l'éponge sur le meuble de la cuisine
    • Laver la tache avec l'éponge
    • Reposer l'éponge sur le meuble de la cuisine
  • Continuer à passer l'aspirateur.
  • Remettre l'aspirateur dans le placard
La femme de ménage qui range la cuisine a quant à elle le programme suivant :
  • Ranger les placard de la cuisine
  • Faire d'autre trucs
  • Prendre l'éponge sur le meuble de la cuisine
  • Nettoyer la table de la cuisine
  • Si des miettes tombes par terre
    • Prendre l'aspirateur dans le placard.
    • Aspirer les miettes avec l'aspirateur
    • Remettre l'aspirateur dans le placard
  • Continuer à nettoyer la table.
  • Reposer l'éponge sur le meuble de la cuisine

Pouvez vous voir le bug qui se cache entre ces deux programmes ?
Les deux pris individuellement ne semblent pas poser de problèmes, pourtant lorsqu'ils sont exécutés ensemble, il peuvent conduire à ce que l'on appelle un "interblocage"

Effectivement, nous sommes en présence de deux ressources partagées qui sont utilisées dans des ordres différents. Cette pratique conduit au fameux bug de DEAD-LOCK qui fait trembler tous les programmeurs qui l'on déjà rencontrés.

Comment est-ce possible ?

La femme de ménage du salon fait des trucs et prend l'aspirateur, elle s'approprie donc cette ressource pour continuer son travail. Dans le même temps celle qui range la cuisine prend l'éponge.

Tout va bien jusqu'a ce que celle qui fait le salon rencontre une tache sur la moquette, la elle va aller chercher l'éponge, et va attendre que celle qui fait la cuisine la restitue, car elle est en train de l'utiliser pour ranger la table. Manque de bol, en nettoyant la table, celle qui fait la cuisine fait tomber des miettes, elle va donc aller chercher l'aspirateur dans le placard qui n'y est pas, car il est dans le salon. Sans le savoir, les deux femmes de ménages s'attendent mutuellement, et l'ensemble du programme s'arrête !

Mais comment éviter ça ?!?

De mon expérience  la meilleur façon d'éviter un deadlock lorsque l'on écrit un programme multitâche est de faire en sorte que l’acquisition de plusieurs ressources partagées soient toujours faite dans le même ordre.
Si cela engendre une pénalisation trop forte des performances, il faut faire en sorte de synchroniser les tâches entre elles pour qu'elles prennent un autre chemin de code si une ressource principale est déjà prise.

Mais la meilleur façon d'éviter les dead-lock tout en gardant un bon niveau de performance est bien sûr de tout faire pour avoir un minimum de ressources partagées entre plusieurs tâches. Chose facile à dire :p

La synchronisation des tâches

Vous avez 6 femmes de ménages qui travaillent en parallèles. Mais que se passe-t-il si celle qui fait les sols arrive dans une pièce alors que quelqu'un d'autre est en train de passer l'aspirateur ?

Nous sommes ici devant un cas de synchronisation de tâches, qui s'il est mal mené peut conduire à un type de bug extrêmement difficile à trouver, j'ai bien sûr nommé le terrifiant "Race Condition" ou "Situation de compétition" pour les français.

Qui quoi donc ?

Une situation de compétition se produit lorsque un défaut de synchronisation apparaît dans un système multitâche.

Sortons du monde des femmes de ménages et imaginons plusieurs personnes qui construisent un mur.


Bob place les briques, c'est sa spécialité. Il ne réfléchi pas, il met la brique sur la couche de ciment de façon parfaite.

Paul lui met le ciment, il en a toujours d'avance et le prépare à une vitesse folle. Il place la bonne dose où il faut et quand il faut.









Le programme est très simple :

Faire
Placer ciment.
Placer brique.
jusqu'à ce que le mur soit fini

Je demande à bob d’exécuter ce programme, mais celui ci me dit qu'il ne sais placer que des briques. Il lui faut l'aide de Paul pour aller plus vite.

La modification du programme est trivial :


Faire
Paul, tu places le ciment.
Bob, tu places la brique.
Jusqu'à ce que le mur soit fini

Je lance le programme, et la, c'est la catastrophe !


Mais que s'est-il passé ?

Je demande à Paul et à Bob de travailler de façon décomposée pour que je comprenne leur erreur. au bout de 3 heures d'observation à regarder Paul placer le ciment puis bob placer la brique, j'arrive à un résultat parfait.


Quelqu'un va-t-il m'expliquer ce qui se passe !?!?!

Nous sommes en présence de ce qu'on appelle en informatique un "Heisenbug"
Ce terme fait référence à Werner Heisenberg, un physicien quantique qui a démontré que dans cette discipline  le simple fait d'observer une expérience peut modifier le résultat de cette expérience. Et c'est exactement ce qui nous est arrivés avec nos deux personnages !

Comment est-ce possible ?

Lorsque je demande à bob de placer une brique, il ne réfléchi pas et place la brique. Il n'attend pas que Paul est mis préalablement le ciment, et inversement.
Ainsi, lorsque je dis de façon unitaire à Paul : "Place le ciment", puis une fois que je me suis assuré qu'il l'a bien fait je dis à bob : "Place la brique", j'agis comme un agent de synchronisation externe sans le savoir !

Par contre, quand je lance le programme, je donne le GO à Paul, puis un peut plus tard je    donne un GO à Bob. Ce décalage de temps peut donner l'illusion que tout va bien, mais il suffit   que Paul prenne un peut de retard pour préparer sa mixture, et Bob va se mettre à empiler des briques l'une sur l'autre sans ciment !!

Mais alors que faire ??

Il faut modifier le programme pour synchroniser les tâches :


Faire
Paul, tu places le ciment, et tu attends que bob est placé une brique
Bob, tu places la brique et tu attends que bob est mis du ciment.
Jusqu'à ce que le mur soit fini

Dorénavant, Paul et Bob sont synchronisés.

Conclusion

J'espère que cet article de vulgarisation très sommaire aura permis à quelques uns d'avoir une meilleure vision de ce que représente le multitâche en programmation. 

Pour ma part, la plus grande difficulté lorsque l'on inspecte un programme multitâche est de réussir à penser en plusieurs dimensions temporelle. Un peut comme si vous deviez lire une partition de musique pour laquelle chaque note peut être jouée par plusieurs instruments en même temps, mais avec des temps décalés.

L'exercice est difficile, mais ce n'est qu'à ce prix qu'un programmeur sera capable d'exploiter toute la puissance offerte par les nouveaux microprocesseurs, et avec l'explosion des nouveaux types d'applications (reconnaissance vocale, réalité augmentée, intelligence artificielle, ...) il faut avouer que ce ne sera pas du luxe !


Aucun commentaire:

Enregistrer un commentaire