|
[[File:MOESI State Transaction Diagram.svg|centre|vignette|upright=2|MOESI State Transaction Diagram]]
==AtomicitéL'atomicité==
Afin de gérer le partage de la mémoire sans problèmes, chaque processeur doit définir un '''modèle mémoire''', un ensemble de restrictions et de contraintes qui garantissent que les instructions ne puissent pas être interrompues (ou donnent l'impression de ne pas l'être) : c'est la propriété d''''atomicité'''. Un thread doit utiliser plusieurs instructions successives sur la donnée pour pouvoir en faire ce qu'il veut, et cela peut poser des problèmes : dans certaines situations,si les instructions peuvent être interrompues par une exception ou tout autre chose. Par exemple, il est possible qu'une lecture démarre avant que la précédente soit terminée. De même, rien n’empêche une lecture de finir avant l'écriture précédente et renvoyer la valeur d'avant l'écriture.
Prenons un exemple, avec un entier entreutilisé par plusieurs threads, chaque thread s’exécutant sur un processeur x86. Chaque thread veut l'incrémenter. Seul problème, l'incrémentation n'est pas effectuée en une seule instruction sur les processeurs x86. Il faut en effet lire la donnée, l'augmenter de 1, puis l'écrire. EtCe siqui deuxfait processeursque veulentl'on augmenterpeut simultanémentse cetteretrouver donnée, on court àdans la catastrophe.situation Chaqueillustrée threadci-dessous, peutoù êtreun interrompu àprocessuer n'importea quelpas momenteu par un autre processeur qui voudra modifier sa donnée. Lesle instructionstemps de nosfinir threadsson s’exécuteront en série, mais le processeur peut parfaitement être dérangé parincrémentation qu'un autre processeur entre deux instructions. Dans notre exemple, une telle situation est illustrée ci-dessous. Onen a doncdémarré une valeur de départ de 5, qui est augmentée de 1 deux fois, ce qui donne au final 6nouvelle.
[[File:Illustration du résultat de deux opérations concurrentes sur la même variable.png|centre|vignette|upright=2|Illustration du résultat de deux opérations concurrentes sur la même variable.]]
Pour avoir le bon résultat il y a une seule et unique solution : le processeur qui accède à la donnée doit avoir un accès exclusif à la donnée partagée. Sans cela, l'autre processeur ira lire une version de la donnée qui n'aura pas encore été modifiée par l'autrelepremier processeur. Dans notre exemple, un seul thread doit pouvoir manipuler notre compteur à la fois. Et bien sûr, cette réponse peut, et doit se généralisergénéralise à presque toutes les autres situations impliquant une donnée partagée. Chaque thread doit donc avoir un accès exclusif à notre donnée partagée, sans qu'aucun autre thread ne puisse manipuler notre donnée. On doit donc définir ce qu'on appelle une '''section critique''' : un morceau de temps durant lequel un thread aura un accès exclusif à une donnée partagée, :avec notrela thread est certaincertitude qu'aucun autre thread n'irane peut modifier la donnée qu'il manipulepartagée durant ce temps. Autant prévenir tout de suite :, créer de telles sections critiques se base sur des mécanismes mêlant le matériel et le logiciel. Il existe deux grandes solutions, qui peuvent être soit codées sous la forme de programmes, soit implantées directement dans le silicium de nos processeurs.
Voyons la première de ces solutions : lL''''exclusion mutuelle'''. Avecpermet celle-ci,à on fait en sorte qu'un thread puissede réserver la donnée partagée. Un thread qui veut manipuler cetteune donnée varéserve donc attendre qu'elle soit libre pour la réserver afin de l'utilisercelle-ci, et la libéreralibère une fois qu'il en a fini avec elle. Si la donnée est occupée par un threadréservée, tous les autres threads devront attendreattendent leur tour. Pour mettre en œuvre cette réservation/dé-réservation, on va devoir ajouterajoute un compteur à la donnée partagée, qui indique si la donnée partagée est libre ou déjà réservée. Dans le cas le plus simple, ce compteur vaudra 0 si la donnée est réservée, et 1 si elle est libre. Ainsi,Ce un thread qui voudra réserver la donnée va d'abord devoir vérifier si ce nombre est à 1 avant de pouvoir réserver sa donnée. Si c'est le cas, il réservera la donnée en passant ce nombre à 0. Si la donnée est réservée par un autre thread, il devra tout simplement attendre son tour. On a alors créécompteur ce qu'on appelle un verrou d'exclusion mutuelle, aussi appelé mutex.
[[File:Mutex.png|centre|vignette|upright=2.5|Mutex.]]
SeulMais problème : cettela vérification et modification du compteur pose problème. Celle-ci ne peut pas être interrompue, sous peine de problèmes. On peut reprendre l'exemple du dessus pour l'illustrer. Si notre compteur est à 0, et que deux threads veulent lire et modifier ce compteur simultanément, il est possible que les deux threads lisent le compteur en même temps : ils liront alors un zéro, et essayeront alors de se réserver la donnée simultanément. Bref, retour à la case départ...
===InstructionsLes instructions atomiques===
Dans le cas précédent, la vérification et modification du compteur ne peut pas être interrompue, sous peine de problèmes. On peut reprendre l'exemple du dessus pour l'illustrer. Si notre compteur est à 0, et que deux threads veulent lire et modifier ce compteur simultanément, il est possible que les deux threads lisent le compteur en même temps : ils liront alors un zéro, et essayeront alors de se réserver la donnée simultanément. Bref, retour à la case départ...
Cette vérification et modification du compteur se fait en plusieurs étapes : une lecture du compteur, puis une écriture si le compteur est à la bonne valeur. Il faudrait que cette lecture et l'écriture se fassent en une seule fois. Pour régler ce problème, certains processeurs fournissent des instructions spécialisées, in-interruptibles, capables d'effectuer cette modification du compteur en une seule fois. Ces instructions peuvent ainsi lire ce compteur, décider si on peut le modifier, et écrire la bonne valeur sans être dérangé par un autre processeur qui viendrait s'inviter dans la mémoire sans autorisation ! Par exemple, sur les processeurs x86, la vérification/modification du compteur vue plus haut peut se faire avec l'instruction test and set. D'autres instructions atomiques similaires existent pour résoudre ce genre de problèmes. Leur rôle est toujours d'implémenter des verrous d'exclusion mutuelle plus ou moins sophistiqués, en permettant d'effectuer une lecture, suivie d'une écriture en une seule fois. Ces instructions permettent ainsi de créer des sémaphores, des Locks, etc. Généralement, un programmeur n'a pas à devoir manipuler des instructions atomiques lui-même, mais ne fait que manipuler des abstractions basées sur ces instructions atomiques, fournies par des bibliothèques ou son langage de programmation. ▼
▲Cette vérification et modification du compteur se fait en plusieurs étapes : une lecture du compteurIdéalement, puis une écriture si le compteur est à la bonne valeur. Ilil faudrait que cette lecture et l'écriture se fassent en une seule fois. Pour régler ce problème, certains processeurs fournissent des instructions spécialisées, in-interruptibles, capables d'effectuer cette modification du compteur en une seule fois. Ces instructionsElles peuvent ainsi lire cele compteur, décider si on peut le modifier, et écrire la bonne valeur sans être dérangé par un autre processeur qui viendrait s'inviter dans la mémoire sans autorisation ! Par exemple, sur les processeurs x86, la vérification/modification du compteur vue plus haut peut se faire avec l'instruction ''test and set ''. D'autres instructions atomiques similaires existent pour résoudre ce genre de problèmes. Leur rôle est toujours d'implémenter des verrous d'exclusion mutuelle plus ou moins sophistiqués, en permettant d'effectuer une lecture, suivie d'une écriture en une seule fois. Ces instructions permettent ainsi de créercomme des sémaphores, des Locks, etc. Généralement, un programmeur n'a pas à devoir manipuler des instructions atomiques lui-même, mais ne fait que manipulermanipule des abstractions basées sur ces instructions atomiques, fournies par des bibliothèques ou son langage de programmation. Ces instructions in-interruptibles sont appelées des '''instructions atomiques'''. De plus, elles empêchent tout accès mémoire tant qu'elles ne sont pas terminées. De telles instructions garantissent que les écritures et lectures s’exécutent l'une après l'autre. Voici la plupart de ces instructions atomiques les plus connues :
Ces instructions in-interruptibles sont appelées des '''instructions atomiques'''. De plus, elles empêchent tout accès mémoire tant qu'elles ne sont pas terminées. De telles instructions garantissent que les écritures et lectures s’exécutent l'une après l'autre. L'instruction atomique va réserver l'accès au bus en configurant un bit du bus mémoire, ou par d'autres mécanismes de synchronisation entre processeurs. Si la donnée est dans le cache, pas besoin de bloquer la mémoire : le processeur a juste à écrire dans la mémoire cache et les mécanismes de cohérence des caches se contenteront de mettre à jour la donnée de façon atomique. Voici la plupart de ces instructions atomiques les plus connues :
{|class="wikitable"
|-
! Instruction !! Description
|-
! Compare And Swap
| Cette instruction va lire une donnée en mémoire, va comparer celle-ci à l'opérande de notre instruction (une donnée fournie par l'instruction), et va écrire un résultat en mémoire si ces deux valeurs sont différentes. Ce fameux résultat est fourni par l'instruction, ou est stocké dans un registre du processeur.
|-
! Fetch And Add
| Cette instruction charge la valeur de notre compteur depuis la mémoire, l'incrémente, et écrit sa valeur en une seule fois. Elle permet de réaliser ce qu'on appelle des sémaphores. Elle permet aussi d'implémenter des compteurs concurrents.
|-
! XCHG
| Cette instruction peut échanger le contenu d'un registre et d'un morceau de mémoire de façon atomique. Elle est notoirement utilisée sur les processeurs x86 de nos PC, qui implémentent cette instruction.
|}
Comme je l'ai dit plus haut, ces instructions empêchent tout autre processeur d'aller lire ou modifier la donnée qu'elles sont en train de modifier. Ainsi, lorsLors de l’exécution de l'instruction atomique, aucun processeur ne peut aller manipuler la mémoire. : notre L'instruction atomique va alors bloquer la mémoire et en réserverréserve l'accès au bus mémoire rien que pour elle. Cela peut se faire en envoyantconfigurant un signalbit sur ledu bus mémoire, ou paspar d'autres mécanismes de synchronisation entre processeurs. Quoi qu’il en soit, leLe cout de ce blocage de la mémoire est assez lourd : cela peut prendre un sacré bout de temps, ce qui faitrend que nosles instructions atomiques sontassez lentes. Du moins, c'est le cas si la donnée est en mémoire et que le processeur est un peu stupide. En effet, sur certains processeurs,Mais on peut optimiser le tout dans le cas où la donnée est dans le cache. Dans ce cas, pas besoin de bloquer la mémoire. : leLe processeur a juste à écrire dans la mémoire cache, et les mécanismes de cohérence des caches se contenteront de mettre à jour la donnée de façon atomique automatiquement. Le cout des instructions atomiques est alors fortement amorti.
===InstructionsLes instructions LL/SC===
Une autre technique de synchronisation est basée sur deuxles instructions : '''Load-Link''' et '''Store-Conditional'''. L'instruction Load-Link va lirelit une donnée depuis la mémoire de façon atomique. L'instruction Store-Conditional écrit une donnée chargée avec Load-Link, mais uniquement à condition que la copie en mémoire n'aie pas été modifiée entre temps. : siSi ce n'est pas le cas, Store-conditional échoue. Pour indiquer un échec, il y a plusieurs solutions : soit elle met un bit du registre d'état à 1, soit elle écrit une valeur de retour dans un registre. Sur certains processeurs, l’exécution d'interruptions ou d'exceptions matérielles après un Load-Link fait échouer un Store-conditional ultérieur. Implémenter ces deux instructions est assez simple, et peut se faire en utilisant les techniques de bus-snopping vues dans le chapitre sur la cohérence des caches. Pour implémenter l'instruction SC, il suffit de mémoriser si la donnée lue par l'instruction LL a été invalidée depuis la dernière instruction LL. Pour cela, on utilise un registre qui mémorise l'adresse lue par l'instruction LL, à laquelle on ajoute un bit d'invalidation qui dit si cette adresse a été invalidée. L'instruction LL va initialiser le registre d'adresse avec l'adresse lue, et le bit est mis à zéro. Une écriture a lieu sur le bus, des circuits vérifient si l'adresse écrite est identique à celle contenue dans le registre d'adresse et mettent à jour le bit d'invalidation. L'instruction SC doit vérifier ce bit avant d'autoriser l'écriture.
Implémenter ces deux instructions est assez simple, et peut se faire en utilisant les techniques de bus-snopping vues dans le chapitre sur la cohérence des caches. Pour implémenter l'instruction SC, il suffit de mémoriser si la donnée lue par l'instruction LL a été invalidée depuis la dernière instruction LL. Pour cela, on utilise un registre qui mémorise l'adresse lue par l'instruction LL, à laquelle on ajoute un bit d'invalidation qui dit si cette adresse a été invalidée. L'instruction LL va initialiser le registre d'adresse avec l'adresse lue, et le bit est mis à zéro. Une écriture a lieu sur le bus, des circuits vérifient si l'adresse écrite est identique à celle contenue dans le registre d'adresse et mettent à jour le bit d'invalidation. L'instruction SC doit vérifier ce bit avant d'autoriser l'écriture.
===Mémoire Transactionnelle Matérielle=== ▼
▲=== MémoireLa mémoire Transactionnelle Matérielle===
Pour résoudre les différents problèmes posés par les verrous d'exclusion mutuelle, les chercheurs ont inventé la '''mémoire transactionnelle'''. La mémoire transactionnelle permet de rendre atomiques des morceaux de programmes complets, que l'on appelle des transactions. Pendant qu'une transaction s’exécute, tout se passe comme si la transaction ne modifiait pas notre donnée et reste plus ou moins "invisible" des autres processeurs. Dans le cas où la donnée partagée n'a pas été modifiée par un autre processeur durant l’exécution d'une transaction, celle-ci peut alors écrire son résultat en mémoire. Mais dans le cas contraire, la transaction échoue et doit rependre depuis le début : les changements effectués par la transaction ne seront pas pris en compte.
Ces techniques ont un défaut : la quantité de données manipulées par la transaction est limitée à la taille du cache. Pour éviter ce petit problème, certains chercheurs travaillent sur une mémoire transactionnelle capable de gérer des transactions de taille arbitraires. Ces techniques mémorisent les données modifiées par la transaction en mémoire RAM, dans des enregistrements que l'on appelle des logs.
===SpeculativeLe ''speculative Lock Elision''===
Les instructions atomiques sont lentes, sans compter qu'elles sont utilisées de façon pessimistes : l'atomicité est garantie même si aucun autre thread n'accède à la donnée lue/écrite. Aussi, pour accélérer l'exécution des instructions atomiques, des chercheurs se sont penchés sur ce problème de réservations inutiles et ont trouvé une solution assez sympathique, basée sur la mémoire transactionnelle. Au lieu de devoir mettre un verrou et de réserver notre donnée juste au cas où, on peut agir d'une façon un peu plus optimiste. Rien n’empêche de transformer nos instructions atomiques servant pour les réservations en instructions permettant de démarrer des transactions. Bien évidemment, les instructions atomiques servant à libérer la donnée partagée vont marquer la fin de notre transaction. Ce mécanisme tente donc de se passer des instructions atomiques en les transformant en transaction une première fois, puis revient à la normale en cas d'échec. Il s'appelle le '''Speculative Lock Elision'''.
|
