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…
Aller plus loin
- La mémoire transactionnelle logicielle (938 clics)
- Article d’Ars Technica sur le BlueGene/Q (403 clics)
# Preums
Posté par niconoe . Évalué à -10.
Patrick_g, sors de ce corps !
# Il manque le principal dans le journal : la version hardware
Posté par Nicolas Boulay (site web personnel) . É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 première sécurité est la liberté"
[^] # Re: Il manque le principal dans le journal : la version hardware
Posté par claudex . Évalué à 3.
Effectivement, je m'étais dit que je le rajouterais plus tard et j'ai évidemment oublié. Merci pour la précision.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Il manque le principal dans le journal : la version hardware
Posté par reno . É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 patrick_g (site web personnel) . Évalué à 9.
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 Nicolas Boulay (site web personnel) . É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 première sécurité est la liberté"
# Preums
Posté par Efemero (site web personnel) . Évalué à -3.
Normalement, j'ai demandé un dlfp_mutex donc ce sera le premier commentaire!
[^] # Re: Preums
Posté par claudex . Évalué à 7.
Visiblement, tu l'as demandé trop tard.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Preums
Posté par El Titi . É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 claudex . Évalué à 4.
Ce n'est pas plutôt l'implémentation du langage qui ne le permet pas?
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Preums
Posté par El Titi . Évalué à 2.
Oui mais DLFP NG ne tourne pas sous IronRuby ou JRuby que je sache.
[^] # Re: Preums
Posté par claudex . Évalué à 4.
Je voulais juste souligner que ce n'était pas le langage en lui-même qui posait problème.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
# Introduction pas bien claire...
Posté par klub . Évalué à 1.
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 Kerro . É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 Nicolas Boulay (site web personnel) . É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 première sécurité est la liberté"
[^] # Re: Méthode coûteuse
Posté par Philippe F (site web personnel) . É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 Nicolas Boulay (site web personnel) . É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 première sécurité est la liberté"
[^] # Re: Méthode coûteuse
Posté par beagf (site web personnel) . É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 :
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 pyknite . É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 lasher . É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:
[^] # Re: Instructions atomiques
Posté par pyknite . Évalué à 1.
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 Victor STINNER (site web personnel) . É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.
[^] # Re: Instructions atomiques
Posté par beagf (site web personnel) . É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 claudex . Évalué à 2.
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.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Instructions atomiques
Posté par Batchyx . É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 claudex . É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.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Instructions atomiques
Posté par Batchyx . Évalué à 2.
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.
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 :
[^] # Re: Instructions atomiques
Posté par claudex . Évalué à 1.
Je n'avais pas compris que tu voulais faire du CAS.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Instructions atomiques
Posté par Batchyx . Évalué à 3.
C'est pas comme si on ne parlait que de ça dans ce thread.
[^] # Re: Instructions atomiques
Posté par claudex . É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.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Instructions atomiques
Posté par beagf (site web personnel) . É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 reno . É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 Victor STINNER (site web personnel) . Évalué à 3.
Les développeurs de PyPy (surtout Armin Rigo) sont motivés pour utiliser de la mémoire transactionnelle :
http://morepypy.blogspot.com/2011/08/we-need-software-transactional-memory.html
http://morepypy.blogspot.com/2011/06/global-interpreter-lock-or-how-to-kill.html
http://mail.python.org/pipermail/python-dev/2011-August/113188.html
http://mail.python.org/pipermail/pypy-dev/2011-August/008153.html
# Recouvrement
Posté par Spack . É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 windu.2b . Évalué à 2.
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 darkleon (site web personnel) . É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 lasher . É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 darkleon (site web personnel) . É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 beagf (site web personnel) . É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 djano . É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 Spack . Évalué à 0.
Je dis peut-être une bêtise mais en C on doit pouvoir faire un truc du genre :
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 darkleon (site web personnel) . É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 Ivan Le Lann . Évalué à 3.
"*val -= debit" est du sucre syntaxique pour "*val = *val - debit"
Donc si, on lit la variable.
[^] # Re: Recouvrement
Posté par darkleon (site web personnel) . É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 windu.2b . Évalué à 4.
Mais qui va remplacer la valeur de
varparvar + 10, au final ? Car il faut bien lire ce que contientvarpour savoir de combien il faut l'incrémenter...[^] # Re: Recouvrement
Posté par windu.2b . Évalué à 3.
s/de combien/jusqu'à combien/
[^] # Re: Recouvrement
Posté par darkleon (site web personnel) . É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 beagf (site web personnel) . É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 darkleon (site web personnel) . É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 beagf (site web personnel) . É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 lasher . Évalué à 3.
Ton code a un problème : tu suppose que
*valva ê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 r3ld r4, @val # val est une adresse absolue en mémoire, r4 est choisi arbitrairementsub r4, r4, r3 # r4 -= r3st @val, r4C'est approximatif, mais l'idée est là. Entre le moment où le chargement de
valdansr4et le moment où l'on écrit par dessusval, 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 darkleon (site web personnel) . É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 Ivan Le Lann . É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 claudex . Évalué à 3.
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.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?
Posté par Ivan Le Lann . É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 claudex . Évalué à 2.
Je n'ai pas parler que de truc bloquant.
Et si ton CAS échoue, tu recommence. En gros tu fait de la mémoire transactionnel sur une variable.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?
Posté par Ivan Le Lann . Évalué à -1.
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 claudex . Évalué à 2.
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.
« Rappelez-vous toujours que si la Gestapo avait les moyens de vous faire parler, les politiciens ont, eux, les moyens de vous faire taire. » Coluche
[^] # Re: Et si un thread se fait toujours voler l'accès mémoire ?
Posté par lasher . É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 lasher . É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 windu.2b . É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 neologix . É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 lasher . É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 beagf (site web personnel) . É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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.