Technologie IBM lance la mémoire transactionnelle dans le matériel

45
7
sept.
2011
Technologie

Le supercalculateur Sequoia (prévu pour être le plus puissant supercalculateur lors de sa sortie) ne fera pas que battre des records de FLOPS, il utilisera aussi des processeurs BlueGene/Q d’IBM, les premiers processeurs commerciaux à utiliser une mémoire transactionnelle matérielle. Le processeur développé par Sun et annulé avec le rachat par Oracle, aurait également dû le prendre en charge.

C’est l’occasion d’expliquer ce qu’est la mémoire transactionnelle : une technique peu connue car elle pose des problèmes de performance lorsque plusieurs processus ou fils d’exécution (threads) doivent accéder à une valeur partagée.

N. D. A. : Merci à Nÿco, NeoX et Michel Barret pour leur aide lors de la rédaction de cette dépêche.

Le problème du multithread

Le multithread permet souvent d’améliorer les performances en exécutant plusieurs opérations en même temps. Cependant, à part quelques algorithmes qui peuvent s’exécuter en parallèle de manière totalement indépendante, il est souvent nécessaire de partager des ressources, comme une valeur, entre les différents threads. Et il faut absolument éviter qu’un thread lise une valeur obsolète ou incohérente.

Prenons l’exemple d’une mise à jour de compte en banque. Un thread va retirer de l’argent et un autre thread va en ajouter, tout ça sur le même compte. Les deux threads lisent la valeur du montant du compte. Ensuite, le thread qui ajoute de l’argent s’exécute plus vite (il y a plein de raisons possibles pour ça), il met à jour la valeur du compte par la nouvelle valeur qu’il a calculé (montant + valeur qu’il a ajoutée). Cependant, lorsque l’autre thread se termine, il met à jour la valeur, il écrit dans la mémoire la valeur qu’il a calculé (le montant lors de la lecture - la valeur qu’il retire), la valeur dans la mémoire ne tient donc pas compte de l’ajout qui a été fait.

Les mutex

Pour régler ce problème, on utilise, la plupart du temps, des mutex (mutual exclusion ou exclusion mutuelle). Le programmeur détermine quelles sont les zones sensibles, au début de celles‐ci, le programme demande l’acquisition du mutex, et si personne ne l’a demandé, il l’obtient et peut exécuter la suite du code. Quand il a fini, il libère le mutex. Si un thread a déjà le mutex, celui qui le demande est mis en attente jusqu’à ce qu’il soit libéré.

Cette technique permet d’être sûr que le thread est le seul à utiliser la ressource partagée. Cependant, elle pose d’autres problèmes. Premièrement, il faut être sûr de relâcher le mutex quand on a fini de l’utiliser, sous peine de bloquer tous les autres threads. Deuxièmement, il y a un risque de blocage complet quand on utilise plusieurs mutex. Par exemple, prenons deux threads avec deux mutex A et B (chacun pour une ressource partagée) ; le premier thread prend le mutex A, le second thread prend le mutex B. Le premier thread veut ensuite prendre le mutex B (sans avoir relâché le mutex A) et le second thread veut prendre le mutex A, on se retrouve dans une situation où les deux threads vont attendre indéfiniment que les mutex soient relâchés, sans que cela se produise. Cela n’arriverait pas si les threads prenaient les mutex dans le même ordre (d’abord le A puis le B), mais ce n’est pas toujours facile à mettre en place, ni même possible.

Les transactions

Pour résoudre les problèmes, on peut utiliser la mémoire transactionnelle. Elle peut être implémentée de manière logicielle ou matérielle. La technique est similaire à celle utilisée dans les transactions des bases de données. La méthode est optimiste, les threads s’exécutent sans verrou, et à la fin de l’opération (le commit), on vérifie que les données n’ont pas été modifiées par d’autres threads pendant le traitement, sinon, on recommence.

On peut l’exprimer dans le code de la manière suivante, le bloc « atomic » définit la transaction :

// Insère atomiquenent un nœud dans une liste doublement liée
 atomic {
     newNode→prev = node;
     newNode→next = node→next;
     node→next→prev = newNode;
     node→next = newNode;
 }

Il y a un surcoût en mémoire et en temps processeur, car les données doivent être dupliquées pour chaque transaction et des instructions sont parfois exécutées dans le vide, puisque la transaction échouera si les données sont modifiées. D’après les défenseur des transactions, le surcoût processeur est récupéré par l’absence de gestion des mutex, qui n’est pas une opération négligeable. Dans le cas du BlueGene/Q, le surcoût en mémoire sera absorbé par les caches des processeurs, par contre, le surcoût processeur sera toujours présent.

Des implémentations logicielles existent pour beaucoup de langages, dont C++, Java, Python, Scala, Perl…

  • # Preums

    Posté par . Évalué à  -10 .

    Patrick_g, sors de ce corps !

  • # Il manque le principal dans le journal : la version hardware

    Posté par . Évalué à  10 .

    Data in cache has a version tag, and the cache can store multiple versions of the same data. Software tells the processor to begin a transaction, does the work it needs to do, and then tells the processor to commit the work. If other threads have modified the data—creating multiple versions—the cache rejects the transaction and the software must try again. If other versions weren't created, the data is committed.

    En gros, la transaction reste dans le cache et le write-back est fait uniquement si il existe une seule copie des données.

    "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

    • [^] # Re: Il manque le principal dans le journal : la version hardware

      Posté par (page perso) . Évalué à  3 .

      Effectivement, je m'étais dit que je le rajouterais plus tard et j'ai évidemment oublié. Merci pour la précision.

      « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

    • [^] # Re: Il manque le principal dans le journal : la version hardware

      Posté par . Évalué à  6 .

      Bof, c'est tellement peu précis cette description que je ne suis pas sûr que ça aide vraiment: il n'est expliqué nulle part comment se fait la synchronisation des caches..

      Je trouve par contre que l'article aurait du expliquer l'avantage principal des mémoires transactionelles: c'est une technique 'optimiste' c'est à dire que par défaut tu n'es pas bloqué, tu es bloqué uniquement s'il y a un conflit, pour les mutex tu es toujours bloqué, bon c'est expliqué dans la page wikipédia liée..

      • [^] # Re: Il manque le principal dans le journal : la version hardware

        Posté par (page perso) . Évalué à  9 .

        Je trouve par contre que l'article aurait du expliquer l'avantage principal des mémoires transactionelles

        Pour aller plus loin l'article d'Ars Technica (donné en lien) est vraiment remarquable en tant que vulgarisation de cette technologie. C'est bien écrit et on comprend presque tout.

      • [^] # Re: Il manque le principal dans le journal : la version hardware

        Posté par . Évalué à  4 .

        A mon avis, c'est le même mécanisme qui gère l'aliasing mémoire (bus snopping, cohérence de cache), mais au lieu d'invalider la mémoire tout de suite, il attend le commit pour faire sa vérification.

        "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

  • # Preums

    Posté par (page perso) . Évalué à  -3 .

    Normalement, j'ai demandé un dlfp_mutex donc ce sera le premier commentaire!

    • [^] # Re: Preums

      Posté par (page perso) . Évalué à  7 .

      Visiblement, tu l'as demandé trop tard.

      « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

      • [^] # Re: Preums

        Posté par . Évalué à  1 .

        Pourtant ca ne devrait pas arriver avec un site qui est écrit dans un langage qui n'est pas capable de gérer les accès concurrents autrement qu'avec un GIL

        • [^] # Re: Preums

          Posté par (page perso) . Évalué à  4 .

          Ce n'est pas plutôt l'implémentation du langage qui ne le permet pas?

          « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

          • [^] # Re: Preums

            Posté par . Évalué à  2 .

            Oui mais DLFP NG ne tourne pas sous IronRuby ou JRuby que je sache.

            • [^] # Re: Preums

              Posté par (page perso) . Évalué à  4 .

              Je voulais juste souligner que ce n'était pas le langage en lui-même qui posait problème.

              « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

  • # Introduction pas bien claire...

    Posté par . Évalué à  1 .

    C’est l’occasion d’expliquer ce qu’est la mémoire transactionnelle : une technique peu connue car elle pose des problèmes de performance lorsque plusieurs processus ou fils d’exécution (threads) doivent accéder à une valeur partagée.

    Tout l'intérêt de la mémoire transactionnelle est justement de gérer l'accès concurrent à des variables, de façon plus efficace qu'un mutex.

    De façon grossière, on peut dire que la mémoire transactionnelle est intéressante si la transaction a peut de chance d'être invalidée: par exemple énormément de lectures et peu d'écritures.

    Mon état de l'art n'est pas très à jour, j'imagine que si ça sort en production, c'est qu'ils ont réussi à optimiser le bousin.

  • # Méthode coûteuse

    Posté par . Évalué à  2 .

    Une vraie question:
    pourquoi mettre en place cette méthode qui me semble coûteuse (en transistors donc en prix du processeur, puis en temps de traitement), alors que le problème est que le mutex sont lents (heu... ça dépend franchement desquels !).
    Pourquoi ne pas avoir enfin implémenté:
    - un mutex peu coûteux
    - un moyen de communiquer entre tâches peu coûteux
    Cela ne me semble pas insurmontable de ne pas avoir besoin d'aller en mode noyau pour lire/écrire un octet dans une zone parfaitement connue à l'avance (important ça: parfaitement connue à l'avance).
    Que ce soit sous forme d'une instruction dont on a amélioré le câblage. Que ce soit via un mécanisme de cache. Ou je ne sais quoi.

    Après, je me fais peut-être des idées.

    • [^] # Re: Méthode coûteuse

      Posté par . Évalué à  2 .

      Allez en mode noyau est très couteux, plus qu'un mutex, c'est sûr.

      Ensuite, les liens de communication intercpu sont infiniment plus lent que les liens pour les cpus d'accéder à leur DRAM, cet accès est lui-même plus lent que l'accès au cache. Ils ont simplement dû rajouter des instructions supplémentaires, ce qui ne nécessite pas de support de l'OS (dommage que ARM n'ai pas encore compris cela).
      Si ils utilisent le système assurant la cohérence mémoire, le cout n'est pas élevé et surtout doit pouvoir s'exercer sur la totalité de la mémoire et pas seulement sur de petites zones.

      "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

      • [^] # Re: Méthode coûteuse

        Posté par (page perso) . Évalué à  2 .

        Dans les cas présentés, la gestion des mutex parait très simple. Dans des cas réels un peu complexes, avec plusieurs threads occupés à des tâches qui n'ont rien à voir entre elles, partageant plusieurs ressources à coups de mutex, écrire un programme correct s'avère beaucoup plus compliqué.

        Dans ce cas, la mémoire transactionnelle peut apporter une solution intéressante en terme de simplification logicielle. Je ne saurai dire en terme de performance car c'est pas trop mon rayon.

        Pour prendre un cas concret, Armin Rigo, le développeur de PyPy (l'implémentation alternative de CPython) vient justement de poster un article de blog sur le sujet 1, en disant que la mémoire transactionnée serait une alternative réaliste et intéressante pour se passer du GIL. Par contre, il cite des impacts de performance assez massif, donc ça reste un sujet expérimental à ce stade.

        • [^] # Re: Méthode coûteuse

          Posté par . Évalué à  2 .

          Les impacts sont à propos de mémoire transactionnel logiciel. De plus, le gain relatif augmente avec le nombre de thread et de cpu, surtout si on a pas besoin de lock en lecture.

          "La liberté de tout dire n'a d'ennemis que ceux qui veulent se réserver le droit de tout faire". "La question n'est pas de savoir si vous avez quelque chose à cacher. La question est de savoir si c'est nous qui contrôlons le gouvernement ou l'inverse

    • [^] # Re: Méthode coûteuse

      Posté par (page perso) . Évalué à  9 .

      Le problème des mutex n'est généralement pas leur coût au moment du lock et du unlock. A ce niveau c'est plutôt devenu très rapide sur un mutex de base. (pas de lock récursif ou autres)
      Le soucis c'est plutôt que les mutex sont pessimiste, tu doit faire un lock même si il y a très peu de chances qu'il soit nécessaire.

      La mémoire transactionelle est plutôt à comparer à l'instruction compare-and-swap. Tu fais tout ton calcul comme s'il n'allait pas y avoir de problèmes, et au moment de stocker le résultat, tu vérifie juste que personne n'a fait de connerie pendant ce temps.

      En gros :

      • tu lis la valeur de départ
      • tu fais ton calcul
      • tu stocke le résultat si personne n'a modifié la valeur de départ.

      Si la probabilité que de thread modifient la même zonne est très basse, en général tu n'as pas à recommencer ton calcul.

      Cette stratégie permet d'éviter les mutex et donc le cout associé aux lock, et surtout permet de ce passer complètement du lock, donc tu n'empêche pas un autre thread de bosser.

      C'est particulièrement efficace dans le cas ou tu as un grand vecteur de valeur qui peuvent être modifiées. Avec des mutex, soit tu as un mutex pour tout le vecteur, et donc si tu modifie une seule valeur, tu empêches les autres threads de modifier les autres valeurs, voir de les lires, soit tu as un mutex par valeur et ça deviens très couteux.
      Avec la mémoire transactionnelle tu n'as plus ce problème.

      Par contre il faut que le calcul ne soit pas trop lourd, réversible et atomisable. Et surtout il faut que la probabilité de conflit soit basse: c'est-à-dire être dans une situation optimiste.
      C'est par exemple le cas d'une table de hashage lock-free.

  • # Instructions atomiques

    Posté par (page perso) . Évalué à  1 .

    Pourquoi ne pas utiliser les instructions atomiques (CAS, Fetch and Add,...)?

    Je sais, c'est super pénible à coder (problème ABA &co), mais c'est pas plus efficace?

    • [^] # Re: Instructions atomiques

      Posté par . Évalué à  4 .

      L'intérêt des mémoires transactionnelles est qu'elles rendent le code bien plus simple à écrire (et à comprendre !). Le problème (selon moi) des MT est que la plupart sont faites au niveau logiciel, ce qui les rend généralement bien plus lentes que l'utilisation de verrous (ou d'instructions atomiques). C'est en fait ma principale raison de ne pas aimer les systèmes à base de STM (software transactional memory). Par contre il existe toute une littérature concernant les MT faites au niveau matériel, avec des modifications plus ou moins grosses à effectuer sur les processeurs actuels, et ça je crois vraiment que ça peut aider beaucoup, beaucoup de monde.

      Il existe une étude (je n'arrive plus à trouver le lien) qui montre que des étudiants confrontés aux verrous et mémoires transactionnelles pour la première fois ont différents niveaux de productivité une fois formés à leur utilisation. Si je me souviens bien, l'ordre de productivité (time-to-solution) était ceci:

      1. Verrouillage à gros grain (mettre un gros verrou sur une liste, un tableau dynamique, etc.)
      2. Mémoires transactionnelles
      3. Verrouillage à grain fin (plein de deadlocks possibles, dur à debugger pour un débutant ­et même des programmeurs relativement expérimentés ! — etc.)
      • [^] # Re: Instructions atomiques

        Posté par (page perso) . Évalué à  1 .

        Verrouillage à grain fin (plein de deadlocks possibles, dur à debugger pour un débutant ­et même des programmeurs relativement expérimentés ! — etc.)
        
        

        Si je me souviens bien de mes cours, la granularité fine c'est forcéement plus efficace selon les cas.

        Par exemple, l'ajout/suppression dans une liste triée (je précise triée, dans une linked list il n'y aurait qu'un lock sur l'élément de queue, ce qui est le contraire dans notre cas étant donné que l'on parcours toute la liste est que l'on doit à chaque fois verrouiller au moins un élément) est bien plus rapide avec un biglock qu'avec une granularité fine.

    • [^] # Re: Instructions atomiques

      Posté par (page perso) . Évalué à  2 .

      Si tu prends l'exemple de la dépêche, il faut modifier quatre pointeurs atomiquement. Or la majorité des instructions modifient un seul mot mémoire à la fois.

      // Insère atomiquenent un nœud dans une liste doublement liée
       atomic {
           newNode→prev = node;
           newNode→next = node→next;
           node→next→prev = newNode;
           node→next = newNode;
       }
      
      
      • [^] # Re: Instructions atomiques

        Posté par (page perso) . Évalué à  4 .

        Non, il n'y a que deux pointeurs à modifier. Tu commence par modifier les deux pointeurs qui sont dans le nœud à ajouter, pour ceux la tu n'as besoin d'aucune protection. Ensuite, tu modifies les deux pointeurs externes.

        Et certains processeur supportent le CAS sur deux valeurs, par contre en général elles doivent être contiguës en mémoire ce qui n'est pas le cas ici.

        Mais que ce soit avec de la mémoire transactionnelle ou n'importe quoi d'autre, dans tous les cas, il vaut mieux mettre le minimum d'affectations dans le atomic.

        • [^] # Re: Instructions atomiques

          Posté par (page perso) . Évalué à  2 .

          Tu commence par modifier les deux pointeurs qui sont dans le nœud à ajouter, pour ceux la tu n'as besoin d'aucune protection.

          Si tu ne protège l'affectation du newNode→next, tu peux très bien perdre un nœud si un nouveau nœud est ajouté entre le moment où tu affecte la valeur de newNode→next et le moment où tu affecte la valeur node→next.

          « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

          • [^] # Re: Instructions atomiques

            Posté par . Évalué à  2 .

            Tu ne "protège" pas l'affectation de newNode->next, puisque tu te fiche de sa valeur précédente (surtout si tu sait qu'elle est initialisée à NULL). Tu refait juste cette affectation si ton CAS sur node->next et node->next->prev échoue. Tu n'a besoin de protéger que deux affectations au final.

            C'est dans le cas de la mémoire transactionnelle que tu doit protéger les quatre opérations.

            • [^] # Re: Instructions atomiques

              Posté par (page perso) . Évalué à  1 .

              Si tu as besoin de protéger l'affectation sinon tu peux perdre un nœud de la manière suivante :

              Soit node→next=A. Affectaction de newNode→next à A, un autre thread ajoute un nouveau nœud B, node→next devient B. Affectation de node→next à newNode. On a perdu le nœud B. Et c'est tout aussi valable si A est NULL.

              « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

              • [^] # Re: Instructions atomiques

                Posté par . Évalué à  2 .

                Si tu as besoin de protéger l'affectation

                Non, ça ne sert à rien. Si tu protège l'affectation newNode->... par un CAS, ça veut dire que tu connais sa valeur précédente, et que tu souhaite vérifier qu'un thread concurrent ne l'a pas modifié en même temps que toi. Ce qui n'arrivera pas tant que t'aura pas inséré le nœud.

                Soit node→next=A. [...] node→next devient B. [...] Affectation de node→next à newNode.

                Ce n'est pas qu'une affectation, c'est un Compare And Swap. Donc c'est "Affectation de node->next à newNode et node->next->prev à newNode si node->next vaut A et node->next->prev vaut node sinon rien faire et indiquer l'echec" (dans notre cas, on peut récupérer A à partir de newNode->next, si on ne l'a pas stocké dans une autre variable temporaire)

                Donc dans ton cas le CAS échoue, la modification concurrente est détéctée, et on refait les affectations depuis le début. Heureusement, parce que sinon les CAS ne serviraient strictement à rien si ça n'étaient que des affectations.

                Voila du code si t'en a envie :

                do {
                   NodeType* old_node_next = node->next;
                   NodeType* old_node_next_prev = node->next->prev;
                   newNode->next = old_node_next;
                   newNode->prev = old_node_next_prev;
                // en supposant que __sync_bool_compare_and_swap2 existe.
                } while ( faise == __sync_bool_compare_and_swap2(&node->next, old_node_next, newNode,
                                                                 &node->next->prev, old_node_next_prev, newNode));
                
                
                • [^] # Re: Instructions atomiques

                  Posté par (page perso) . Évalué à  1 .

                  Je n'avais pas compris que tu voulais faire du CAS.

                  « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

                  • [^] # Re: Instructions atomiques

                    Posté par . Évalué à  3 .

                    C'est pas comme si on ne parlait que de ça dans ce thread.

                    • [^] # Re: Instructions atomiques

                      Posté par (page perso) . Évalué à  1 .

                      Tu répond à un thread qui n'en fait pas mention qui lui répondait à un thread qui parlait d'opération atomique en général et ne citait le CAS que parmis d'autres.

                      « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

                      • [^] # Re: Instructions atomiques

                        Posté par (page perso) . Évalué à  3 .

                        Si, on parlait du CAS : moi surtout en fait...

                        Le premier message parle d'instruction atomique dont le CAS. Victor Stinner répond que l'on ne peut pas les utiliser car il y a quatre pointeurs à modifier. --> d'un point de vue instruction atomique c'est forcément du CAS ou du load-lock ici.

                        Je lui répond qu'en fait il n'y en a que deux, et vu que l'on parle d'instruction atomique et de modifier des pointeurs, c'est encore du CAS... je le dis même de manière explicite à la ligne du dessous.

                        Toutes les instructions atomiques qui permettent d'affecter un pointeur on globalement le même comportement : tu affectes la valeur s'il elle n'a pas été modifiée depuis un certains temps.
                        Donc pour tous les cas ou l'on utilise des instructions atomiques (ce qui est le sujet de ce thread) il n'y a besoin que de deux affectations atomiques. Si elles échoue, tu refais les deux autres affectations et tu réessayes, c'est le principe de ces instructions.

                        Dans le cas de la mémoire transactionelle c'est en effet différent puisqu'on garantit l'atomicité d'une transaction sans tests avec les valeurs précédentes. C'est une stratégie différente mais, même si c'est le thème du journal, ce thread à pour thème les instruction atomiques.

    • [^] # Re: Instructions atomiques

      Posté par . Évalué à  3 .

      Je crois que tu parles des algorithmes 'lock-free', oui c'est plus efficace, mais le problème est que 'super pénible' est totalement insuffisant pour décrire la situation: il y en a qui font des thèses (donc qui travaillent plusieurs années) pour faire des algorithmes de ce type et ils se limitent a des structures relativement simple.
      Donc si tu as un problèmes où tu peux réutiliser une librairie déjà faite, c'est bien, sinon ce n'est pas une solution réaliste.

  • # PyPy et mémoire transactionnelle

    Posté par (page perso) . Évalué à  3 .

  • # Recouvrement

    Posté par . Évalué à  1 .

    Je ne suis pas programmeur cependant dans l'exemple de la banque est-il vraiment nécessaire d'utiliser un mutex ?

    Chaque thread peut posséder un pointeur vers la valeur partagée et la modifier sans avoir à la lire (dans le cas où il s'agit d'une simple addition ou soustraction). Une fois l'opération faite, il suffit d'appeler une fonction recouvrement() qui elle posera un verrou afin de vérifier si le client est dans le rouge ou non...

    • [^] # Re: Recouvrement

      Posté par . Évalué à  2 .

      Chaque thread peut posséder un pointeur vers la valeur partagée et la modifier sans avoir à la lire (dans le cas où il s'agit d'une simple addition ou soustraction)

      Pour modifier une valeur, il faut d'abord connaitre... cette valeur !
      Donc tu es obligé de lire la valeur, puis de la modifier, puis d'écrire la nouvelle valeur. Avec le risque qu'un autre thread t'a grillé la priorité !

      • [^] # Re: Recouvrement

        Posté par (page perso) . Évalué à  1 .

        Mais d'ans l'exemple de la banque on calcule un delta€, on pourrait avoir un troisième thread "pile" dont la seule fonction est de prendre un delta€ et de faire l'opération avec le montant.
        Du coup, quelque soit l'ordre d'execution du delta1(ajout) et delta2(retrait), ils seront appliqués de manière séquencielle.
        Et pour vérifier que le montant est "stabilisé", il suffit de vérifier que la pile sur ce montant est vide.
        Bon pour cet exemple c'est simple ^^ (où alors je n'ai rien compris, ce qui est "probabilistiquement" possible ^^)

        • [^] # Re: Recouvrement

          Posté par . Évalué à  2 .

          Déjà, ton troisième thread, il a quelle tête ? S'il s'agit d'un thread, je suppose qu'il existe aussi longtemps que la valeur que tu veux pouvoir modifier existe. On crée combien de threads comme ça ? Un par valeur ? Un pour dix valeurs ?

          Ensuite, comment fais-tu pour traiter les nouveaux deltas ? Il faut bien trouver un moyen de les communiquer au thread, non ? Donc il faut (roulements de tambour...) une structure de donnée partagée ! ... Et du coup on en revient à la case départ.

          Déléguer les modifications d'une variable à un thread, ça peut parfaitement faire sens¹, mais pas dans cet exemple.

          [1] C'est pour ça qu'on utilise des buffers d'écriture par exemple : il vaut mieux déléguer les écritures sur disque à un nombre restreint de threads, qui pourront bénéficier de la bande passante maximale, plutôt que d'avoir 300 threads qui essaient tous d'écrire sur le disque en même temps, et qui au final font que le travail global est ralenti.

          • [^] # Re: Recouvrement

            Posté par (page perso) . Évalué à  0 .

            En fait tu crée un thread de modification de mémoire qui s'appuie sur une queue spécifiant quelle variable et de combien tu veux la modifier.
            Certes tu ne pourra pas avoir d'accès concurrentiels à ce thread, chaque demande de modification devra attendre que la fonction d'ajout d'un élément à la pile se libère.
            Mais au moins, il n'y a pas d'accès concurrentiels sur la valeur elle même.

            Où alors on part dans l'assembleur avec les instructions CAS et assimilées, je ne vois pas comment rendre un CAS transparent (dépendant de l'architecture du processeur) dans un langage de haut niveau.

            • [^] # Re: Recouvrement

              Posté par (page perso) . Évalué à  2 .

              Mais ta file d'attente d'opérations doit gérer le cas ou plusieur thread veulent ajouter des deltas et donc repose sur un mutex ou des CAS...

              Dans la pratique tu n'utilises pas forcément un mutex de manière explicite, pour éviter les emerdes il peut être implicite et gérer par une sous classe ou par une instruction spéciale du langage, mais ça reste beaucoup plus efficace et moins risqué que de passer par un thread supplémentaire.

            • [^] # Re: Recouvrement

              Posté par . Évalué à  2 .

              Voir l'architecture LMAX et le paquetage java.util.concurrent.atomic avec un petit compareAndSet(). Cela couvre certains cas d'utilisation que tu mentionnes.

      • [^] # Re: Recouvrement

        Posté par . Évalué à  0 .

        Je dis peut-être une bêtise mais en C on doit pouvoir faire un truc du genre :

        float *val = &val_partagee;
        *val -= debit;
        
        

        Du coup on modifie directement la valeur sans pour autant savoir ce qu'il y a dedans et la fonction de vérification s'occupe de connaître l'état du compte.

        • [^] # Re: Recouvrement

          Posté par (page perso) . Évalué à  0 .

          J'aime bien, mais ça va dépendre du code assembleur généré par ton compilateur et de ton CPU.

          En plus sur du multiproc, avec les latences mémoires, le temps que le proc n°1 lise la variable fasse la soustraction et la latence pour réecrire la valeur, il n'est pas dit que le proc n°2 ne fasse pas un accès interlacé entre temps.

        • [^] # Re: Recouvrement

          Posté par . Évalué à  3 .

          "*val -= debit" est du sucre syntaxique pour "*val = *val - debit"
          Donc si, on lit la variable.

          • [^] # Re: Recouvrement

            Posté par (page perso) . Évalué à  -1 .

            En assembleur x86, il y a un mode pour travailler directement sur la mémoire sans passer par les registres, en cherchant sur "le ternet" j'ai trouvé cet exemple
            add BYTE PTR [var], 10 — add 10 to the single byte stored at memory address var

            Mais bon, si le compilateur C optimise comme un pied, tu te retrouveras avec plusieurs instructions.

            Il me semble que le 68k a des instructions équivalentes.

            Par contre les premiers risc "pur" doivent charger la valeur dans un registre, faire l'opération, puis renvoyer la nouvelle valeur en mémoire, ce que tu décris.

            ça peut marcher, mais comme les compilateurs C n'apportent aucune garantie sur la séquence d'instructions assembleurs générée, seulement que cela fera bien ce qui est décrit.
            Par exemple sur HP/UX en ~95, j'avais voulu tester le nombre d'instructions qu'il pouvait executer en // (c'était la mode des architectures superscalaire).
            J'ai juste fait une boucle qui incrémentait 5 variables (ça sert à rien, mais a 100mhz, j'avais 500 mips ^^).
            Et pourtant en -04, j'avais 7 lignes d'instructions, et sans optimisation une trentaine de ligne. Ce qui m'avait marqué en -O4, c'est que le test de boucle était écrit avant la dernière incrémentation, le compilateur de HP était capable de réordonner les instructions pour maximiser l'utilisation du pipeline et de la latence de décodage et d'execution. Mais les 2 versions me renvoyaient les mêmes résultat à la fin.

            • [^] # Re: Recouvrement

              Posté par . Évalué à  4 .

              add BYTE PTR [var], 10 — add 10 to the single byte stored at memory address var

              Mais qui va remplacer la valeur de var par var + 10, au final ? Car il faut bien lire ce que contient var pour savoir de combien il faut l'incrémenter...

              • [^] # Re: Recouvrement

                Posté par . Évalué à  3 .

                s/de combien/jusqu'à combien/

              • [^] # Re: Recouvrement

                Posté par (page perso) . Évalué à  0 .

                Il faudrait demander à un spécialiste de l'assembleur, mais il me semble que l'instruction finira de s'executer même si une interruption est déclenchée.

                Mais ça pourrait ne pas empêcher l'entrelacement des accès mémoires avec plusieurs processeurs, encore que sur les procs modernes, il y a un contrôleur mémoire pour plusieurs core, donc ça devrait marcher.

                • [^] # Re: Recouvrement

                  Posté par (page perso) . Évalué à  4 .

                  Non ça ne marchera pas car chaque cœur à son propre cache et sur les processeur récent le passage par le cache L1 est obligatoire.

                  Par contre, si tu rajoute le prefix LOCK devant ça marche, tout simplement car cela deviens une instruction atomique, mais vu que c'est coûteux le compilo ne l'ajoute pas automatiquement partout, uniquement quand tu lui demande explicitement en utilisant les intrinsics...

                  Donc au final, on en reviens toujours au même point : quoi que tu fasses il y a une faille sauf si tu demande explicitement la version atomique.

                  En plus, ce reposer sur un comportement spécifique d'un processeur c'est plutot extrêment pourris à ça ne n'apporte qu'une chose : des emmerdes plus ou moins rapidement.

                  • [^] # Re: Recouvrement

                    Posté par (page perso) . Évalué à  -1 .

                    On est d'accord sur
                    - On ne peut pas présager de la génération de code assembleur de son programme de "haut-niveau"
                    - Il faut bien avoir un verrou un jour ou l'autre.

                    A part déléguer cette partie à une fonction de OS qui peut avoir du joli code assembleur pour tes verrous mitonnés à la mimine, on tourne en rond si on veut des performances ^^

                    • [^] # Re: Recouvrement

                      Posté par (page perso) . Évalué à  2 .

                      Sauf que entre :
                      - utiliser un mutex fournis par l'OS ou une opération atomique,
                      - espérer que le compilateur va produire le bon code et que les instructions font ce que l'on suppose,
                      La première solution à l'avantage de marcher et en plus d'être plus portable.

                      Le code en assembleur, il vaut mieux le laisser au compilateur à travers les builtin et intrinscs, dans des bibliothèques bien testées ou dans le noyeau.

        • [^] # Re: Recouvrement

          Posté par . Évalué à  3 .

          Ton code a un problème : tu suppose que *val va être lu depuis la mémoire. En pratique c'est très souvent faux, car le compilateur a tendance à générer un code de ce genre :

          # On suppose que debit est stocké dans r3
          ld r4, @val # val est une adresse absolue en mémoire, r4 est choisi arbitrairement
          sub r4, r4, r3 # r4 -= r3
          st @val, r4

          C'est approximatif, mais l'idée est là. Entre le moment où le chargement de val dans r4 et le moment où l'on écrit par dessus val, plein de choses peuvent s'être passées — entre autres, un autre thread essaye de faire exactement la même chose.

  • # Et si un thread se fait toujours voler l'accès mémoire ?

    Posté par (page perso) . Évalué à  1 .

    Imaginons X thread qui doivent modifier la même variable.
    Imaginons que le premier thread mette trop de temps à faire ses calculs, selon la règle du premier qui comit gagne, le second vole son tour, le premier thread relance sa routine, et paf le 3éme thread lui vole son tour, ad libitum...
    Si le programme tourne 24/24 en faisant une rotation sur ses X threads, on se retrouve avec l'équivalent d'un dead lock, non ?
    Maintenant, si on sait que les X thread mettront un temps fini, ils finiront par "attraper le train", mais on pourrait se retrouver avec des threads qui font le traitement X-1 fois (voir +oo dans le cas d'un service 24/24).

    Autrement ça à l'air génial comme technique, mais il y a toujours un mais...

    • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

      Posté par . Évalué à  2 .

      Bon exemple en effet. Présenté comme ça, ce n'est pas très engageant.

      Et plus généralement, même si je suis prêt à admettre que la MT a de grands avantages dans certains cas que je ne connais pas, je n'aime pas trop la philosophie derrière : "C'est bon vous pouvez tout partager maintenant, on se charge du reste".
      Je préfère un esprit fonctionnel ("On ne partage rien. Chaque thread a ses ressources. Le peu qui est partagé est protégé.") que j'essaie d'appliquer le plus rigoureusement possible.

      Dans l'exemple bancaire de l'article, je dirais qu'un seul thread doit être responsable de la mise à jour de la valeur et que les deux threads mentionnés ne font que produire un delta à appliquer qu'ils lui communiquent au moyen d'une structure atomique (fifo).

      • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

        Posté par (page perso) . Évalué à  3 .

        au moyen d'une structure atomique (fifo)

        La structure atomique a beaucoup de chance d'être implémenter avec des mutex, des sémaphores ou d'autre méthode pour garantir la synchronisation et la cohérence des données, tu déplace le problème.

        « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

        • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

          Posté par . Évalué à  1 .

          Un exemple : http://tim.klingt.org/boost_lockfree/
          Un autre : concurrent_queue chez Intel TBB.

          Pas de mutex ou autres trucs bloquants, uniquement des instructions atomiques genre CAS.
          Donc non, je ne pense pas "déplacer" pas le problème.

          NB:
          Je ne dis pas non plus qu'il faut mettre des instructions atomiques partout.
          Comme dit avant, moins on partage, mieux on se porte.

          • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

            Posté par (page perso) . Évalué à  2 .

            Pas de mutex ou autres trucs bloquants

            Je n'ai pas parler que de truc bloquant.

            uniquement des instructions atomiques genre CAS.

            Et si ton CAS échoue, tu recommence. En gros tu fait de la mémoire transactionnel sur une variable.

            « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

            • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

              Posté par . Évalué à  -1 .

              En gros tu fait de la mémoire transactionnel sur une variable.

              Ce qui existe déjà depuis des décennies et est conceptuellement mille fois plus simple (et plus propre à mon humble avis) que de la mémoire transactionnelle sur tout un pan de code.
              Dont on parle aujourd'hui.

              • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

                Posté par (page perso) . Évalué à  2 .

                Ce qui existe déjà depuis des décennies et est conceptuellement mille fois plus simple (et plus propre à mon humble avis)

                Mais ce n'est pas toujours utilisable et/ou performant dans tout les cas. Dans ces cas, la mémoire transactionnelle peut s'avérer utile.

                « Moi, lorsque je n’ai rien à dire, je veux qu’on le sache. » Raymond Devos

              • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

                Posté par . Évalué à  2 .

                Mais ça ne passe pas forcément à l'échelle. C'est pour ça qu'il existe (par exemple) des modèles mémoire (tels Entry Consistency ou Location Consistency) qui ont des contraintes très relâchées en ce qui concerne la façon dont la mémoire est vue au sein d'un système et vis à vis d'un cœur.

          • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

            Posté par . Évalué à  4 .

            Si si, tu déplaces le problème. :) Le problème devient un problème « matériel » où la contention sur les opérations atomiques mène à une baisse de performance en cas de pas-de-bol-itude. En pratique, les algos non-bloquants, et plus généralement les algos "lock-free" garantissent que parmi tous les threads au moins un progresse, mais n'offrent aucune garantie quant à la vitesse d'exécution proprement dite. Il existe tout un tas d'études qui montrent que les algos utilisant des verrous à grain fin vont plus vite que ceux utilisant une méthode lock-free, tout bêtement parce que l'implémentation des verrous fait qu'une bonne partie des opérations peut avoir lieu en cache et pas directement en D-RAM.

            Aussi, en pratique, utiliser des opérations atomiques fait gagner (pour une même charge de travail) un facteur 2 (ce qui n'est pas négligeable, j'en conviens), dans le cas où tout est optimiśe aux petits oignons (je peux retrouver des références si tu veux, et je peux aussi te rediriger vers mon collègue qui a écrit un de ces articles). Mais dans la vraie vie malheureusement, les gens ont du mal à correctement implémenter des algos non-bloquants et/ou lock-free. Herb Sutter a même écrit des articles sur le sujet.

    • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

      Posté par . Évalué à  6 .

      Théoriquement, n'a-t-on pas déjà ce cas avec les mutex ?

      Je m'explique : soit un thread A qui a la main sur un mutex. Le thread B, voyant que la place est prise, s'endort, seul la libération du mutex pouvant le réveiller.
      Mais, rien ne garantit qu'une fois le mutex libéré, la main sera immédiatement passée au thread endormi ! Il pourrait donc y avoir un autre thread qui lui pique la priorité, le renvoyant dormir une nouvelle fois.

      • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

        Posté par (page perso) . Évalué à  4 .

        Ce n'est pas pareil.
        Le problème qu'il décrit est un genre de livelock. Mais en pratique cela ne se produit pas, parce que statistiquement, au bout d'un certain temps, tu n'auras qu'un thread actif au sein de la section critique (qui est censée être courte), ou du moins tu n'auras pas de thread en train de modifier les donnés protégées.
        Dans le cas que tu décris, effectivement, en cas de forte contention, en théorie tu peux avoir un problème de "starvation", où un thread se fait griller par ses petits copains ad vitam.
        Mais c'est une question d'implémentation: par exemple, POSIX garantit ceci (man pthread_mutex_unlock):
        """If there are threads blocked on the mutex object referenced by mutex when pthread_mutex_unlock() is called, resulting in the mutex becoming available, the scheduling policy is used to determine which thread shall acquire the mutex."""

        Le point important est "the scheduling policy" : c'est l'ordonnanceur qui choisit le thread qui va acquérir le mutex, et si un threads reste en attente trop longtemps sur un mutex, sa priorité finit par être plus importante que celle de ses amis.

        Au passage, il y a un mécanisme de synchronisation utilisé par le noyau Linux qui se rapproche de STM : les seqlocks (il y a un lock utilisé pour les writers, mais pas de locks pour les readers).

        Enfin, l'implémentation "STM" pour CPython d'Armin Rigo n'est pas vraiment (du tout) une forme de STM : elle se contente de garder le GIL locké (donc pas de concurrence, pas de notion de commit/rollback, c'est en fait un gros verrou global "implicite"). En plus elle présente pas mal de risques de deadlocks...

      • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

        Posté par . Évalué à  2 .

        Oui. Le problème se pose avec tout besoin d'atomicité sur des variables partagées.

    • [^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?

      Posté par (page perso) . Évalué à  2 .

      Oui, tu peut avoir un thread qui est toujours bloqué mais, car il y a un mais comme toujours ;-) ce genre de mécanisme : instruction atomiques ou mémoire transactionelle, serve le plus souvent à implémenter des algorithmes de type "forward progress".

      C'est-à-dire que en général ce qui t'intéresse c'est de garantir que de manière globale le système avance. Si ton thread échoue toujours ce n'est pas grave car à chaque fois qu'il échoue cela veut dire qu'un autre à réussi et donc que globalement le système à progressé.

      Et si tu gère bien le truc, en général tu as de bonne garanties probabilistes sur les progres de chaque threads. Du style la probabilité d'échouer d'un thread décroit de manière quadratique avec le nombre d'échec ou ce genre de choses.

      Si tu as besoin de garanties plus fortes comme dans le cas d'un système temps réél, il faut passer à d'autres méthodes. Mais le besoin en garanties plus fortes est relativement rare en comparaison des besoins satisfait par le forward progress, et surtout c'est beaucoup plus compliqué à gérer donc tu as très peu de chances de voir ça arriver dans du hardware rapidement.

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.