Fonctionnement d'un ordinateur/Les sections critiques et le modèle mémoire

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 quant à l'interaction avec la mémoire RAM. La première contrainte garantit 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 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 utilisé 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. Ce qui fait que l'on peut se retrouver dans la situation illustrée ci-dessous, où un processeur n'a pas eu le temps de finir son incrémentation qu'un autre en a démarré une nouvelle.

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 pas encore modifiée par le premier processeur. Dans notre exemple, un seul thread doit pouvoir manipuler notre compteur à la fois. Et bien sûr, cette réponse se généralise à presque toutes les autres situations impliquant une donnée partagé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 la certitude qu'aucun autre thread ne peut modifier la donnée partagé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.

L'exclusion mutuelle permet à un thread de réserver la donnée partagée. Un thread qui veut manipuler une donnée réserve celle-ci, et la libère une fois qu'il en a fini avec elle. Si la donnée est réservée, tous les autres threads attendent leur tour. Pour mettre en œuvre cette réservation/dé-réservation, on ajoute 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. Ce compteur ce qu'on appelle un verrou d'exclusion mutuelle, aussi appelé mutex (raccourci du terme anglais mutual exclusion).

Mutex.

Les 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...

Idéalement, il faudrait que lecture et é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. Elles peuvent lire le 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, comme des sémaphores, des verrous (Locks), etc. Généralement, un programmeur n'a pas à manipuler des instructions atomiques lui-même, mais manipule 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 :

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.

Lors de l’exécution de l'instruction atomique, aucun processeur ne peut aller manipuler la mémoire. L'instruction atomique réserve l'accès au bus en configurant un bit du bus mémoire, ou par d'autres mécanismes de synchronisation entre processeurs. Le cout de ce blocage de la mémoire est assez lourd, ce qui rend les instructions atomiques assez lentes.

Mais on peut optimiser le cas où la donnée est dans le cache, en état Modified ou Exclusive. Dans ce cas, 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 automatiquement. Le coût des instructions atomiques est alors fortement amorti.

Sur un processeur avec désambiguïsation mémoire de type x86, il faut attendre que la file d'écriture soit vidée avant de démarrer une instruction atomique. La raison est que les instructions atomiques font une lecture, une opération, et une écriture, dans cet ordre. En théorie, la lecture peut passer avant une écriture précédente, à une adresse différente. Mais dans ce cas, cela signifierait que l'écriture aussi serait déplacée avant, car la lecture est liée à l'écriture les deux se font de manière atomique. Et faire passer une écriture avant une autre n'est pas compatible avec les règles du total store ordering.

Les instructions LL/SC

Une autre technique de synchronisation est basée sur les instructions Load-Link et Store-Conditional. L'instruction Load-Link lit 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. Si 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.

La mémoire Transactionnelle Matérielle

La mémoire transactionnelle permet de rendre atomiques des morceaux de programmes complets. Les morceaux de programmes rendus atomiques sont appelés des transactions. Pendant qu'une transaction s'exécute, tout se passe comme si la transaction ne modifiait pas de données et restait plus ou moins "invisible" des autres processeurs. Une fois terminée, le processeur vérifie s'il y a eu un conflit d'accès avec les autres processeurs. Si c'est le cas, la transaction échoue et doit reprendre depuis le début : les changements effectués par la transaction ne seront pas pris en compte. Mais s'il n'y a pas eu conflit d'accès, alors la transaction a réussi et elle peut écrire son résultat en mémoire.

Définir une transaction demande d'ajouter plusieurs instructions : une pour démarrer une transaction, une autre pour la terminer, éventuellement une troisième pour annuler précocement une transaction. Lorsqu'une transaction échoue, elle laisse la main au logiciel. Précisément, elle fait un branchement vers une fonction qui gère l'échec de la transaction. La fonction décide s'il faut ré-exécuter la transaction, attendre un peu avant de la re-démarrer, ou faire autre chose.

Un autre point est que quand une transaction échoue, les registres doivent être remis à leur valeur initiale, celle d'avant la transaction. Et cette restauration est déléguée au code de gestion d'échec de transaction. Il est aussi possible de gérer la sauvegarde des registres en matériel, avec un système de checkpoints, déjà abordé dans le chapitre sur les processeurs à émission dans l'ordre, dans la section sur les interruptions et le pipeline. Reste à détecter les conflits d'accès.

La mémoire transactionnelle explicite : la réservation des lignes de cache

La mémoire transactionnelle se décline en deux versions principales, que nous allons qualifier d'explicite et d'implicite. La mémoire transactionnelle implicite est la plus simple conceptuellement : les lectures et écritures utilisées dans la transaction sont des instructions d'accès mémoire normales, mais sont gérées de manière transactionnelle lors de la transaction. Une autre solution utilise des accès mémoires transactionnels explicites, qui ajoute des instructions d'accès mémoire spécialisées pour les transactions. Il est possible d'exécuter des instructions mémoire normale dans une transaction, qui s'exécutent même si la transaction échoue. Les instructions LOAD/STORE transactionnelles sont les seules à être annulées si la transaction échoue.

L'instruction de lecture transactionnelle réserve une ligne de cache pour le processeur. Par réserver, on veut dire que le processeur est le seul à avoir accès en écriture à cette ligne de cache. Si un autre processeur tente d'écrire dans cette ligne de cache, la transaction fautive est annulée. Il est aussi possible de libérer une ligne de cache réservée avec une instruction RELEASE, complémentaire des instructions de lecture/réservation. Pour résumer, il y a donc trois instructions mémoire transactionnelles : READ/RESERVE, WRITE-IF-RESERVED, et RELEASE.

Vous aurez peut-être fait le lien avec les instructions LINK-LOAD et STORE-CONDITIONNAL, et il faut avouer que les instructions mémoire transactionnelles ressemblent un petit peu. Disons que ce sont des variantes adaptées au fait qu'elles s'exécutent dans des transactions. De plus, LINK-LOAD et STORE-CONDITIONNAL ne réservent pas des lignes de cache, elles se contentent de vérifier qu'une écriture n'a pas eu lieu entre la lecture et l'écriture.

Pour gérer les réservations, le processeur incorpore un registre de réservation par ligne de cache réservée. Le registre mémorise la donnée lue ou écrite. Les écritures se font dans ce registre, elles ne sont pas propagées dans le cache. Par contre, il est possible que ces registres soient pris en compte par les mécanismes de cohérence des caches, afin de gérer la détection des conflits.

Les transactions explicites sont plus flexibles, mais posent plus de problèmes d'implémentation que les transactions implicites. La réservation des lignes de cache est compliquée à implémenter. En comparaison, les méthodes implicites sont plus simples à comprendre et à implémenter. Nous allons nous concentrer sur les méthodes implicites dans le reste du chapitre.

La mémoire transactionnelle implicite : les ensembles de lecture et d'écriture

Toute transaction lit un ensemble de données appelé lensemble de lecture, et écrit/modifie des données qui forment lensemble d'écriture. Le processeur doit identifier l'ensemble de lecture et d'écriture quelque part pour détecter les conflits. Deux conditions font qu'une transaction peut échouer. La première est quand un autre processeur a écrit une donnée dans l'ensemble de lecture. La seconde est quand un autre processeur a lu ou écrit une donnée dans l'ensemble d'écriture. Par contre, il n'y a pas de problème si une donnée est lue par un autre processeur dans l'ensemble de lecture.

Mémoriser l'ensemble de lecture est assez simple : il suffit d'ajouter un bit READ à chaque ligne de cache, qui indique qu'elle a été lue par une transaction. Par contre, la gestion de l'ensemble d'écriture est plus complexe. Il y a deux méthodes : une qui autorise les écritures dans le cache, une autre qui met en attente les écritures.

L'implémentation avec un ensemble d'écritures dans la Store Queue

Une première méthode met en attente les écritures, qui ne sont propagées dans le cache qu'une fois que la transaction est terminée. Elle mémorise l'ensemble de lecture dans le cache, mais l'ensemble d'écriture reste dans la Store Queue, la Load-Store Queue ou autre. La technique en question a été implémentée pour la première fois sur les processeurs Transmetta Crusoe et Efficeon, sous le nom de gated store buffer.

Avec cette technique, les données sont bel et bien lues depuis le cache, mais les écritures ne sont pas propagées dans le cache, elles restent dans le pipeline. A la fin de la transaction, le processeur vérifie s'il n'y a pas eu de conflits et si la transaction est validée. Si ce n'est pas le cas, la Store Queue/Load-Store Queue est vidée, ce qui annule les changements effectués par la transaction (ROB ou autre méthode capable de gérer les interruptions précises). Si c'est le cas, les écritures sont propagées dans le cache.

Si la transaction réussit, le processeur doit vider la Store Queue dedans. Les écritures se font une par une, ce qui peut prendre un peu de temps, surtout si la transaction a fait beaucoup d'écritures. Et pendant le temps, les données écrites peuvent en théorie être écrasées par une écriture provenant d'un autre cœur. Pour éviter cela, le processeur peut interdire les écritures dans tout le cache partagé pour éviter qu'un autre cœur y accède. Mais la méthode entrainerait des performances assez mauvaises. Une autre solution, systématiquement utilisée, est de seulement bloquer les lignes de cache concernées par les écritures en attente. La dernière méthode peut se mettre en œuvre en utilisant judicieusement le protocole de cohérence des caches, en exposant la Store Queue aux mécanismes de cohérence des caches.

La mémoire transactionnelle implicite implémentée dans le cache

Dans cette section, nous allons étudier les techniques qui utilisent le cache pour mémoriser à la fois l'ensemble de lecture et d'écriture. Avant toute chose, précisons 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, mais passons.

Les premières propositions utilisent un cache dédié aux transactions : le cache transactionnel. À cela, il faut ajouter des instructions pour manipuler le cache transactionnel. Les données dans le cache transactionnel utilisent un protocole légèrement différent des autres caches, avec des états et des transitions en plus. Mais le cout en transistors d'un cache séparé fait que cette méthode n'a jamais été utilisée dans un processeur commercial.

Une méthode moins couteuse en circuit réutilise les caches existants dans le processeur. Les écritures se font dans le cache, mais le processeur dispose d'un moyen de les annuler en cas de problème. Mais cela demande de résoudre plusieurs problèmes. Le première est la gestion des ensembles d'écritures/lecture, le second est qu'il faut annuler les écritures si une transaction échoue. Mais un point très intéressant est que la détection des conflits réutilise les mécanismes de cohérence des caches. Si un conflit est détecté pour une ligne de cache, elle est marquée comme invalide pour le protocole de cohérence des caches, et l'invalidation est propagée aux autres cœurs grâce à la liste d'adresse précédente. La détection des conflits se fait donc pendant que la transaction s'exécute, les transactions sont annulées dès qu'un conflit est détecté.

Commençons par le premier problème, à savoir la détermination des ensembles de lecture/écriture. Pour cela, chaque ligne de cache possède un bit WRITE qui indique qu'elle a été écrite par une transaction. Les bits READ et WRITE sont mis à 0 au début de chaque transaction. La première écriture dans une ligne de cache met le bit WRITE à 1. Les bits READ et WRITE sont utilisés pour détecter les conflits, la détection des conflits étant prise en charge par les mécanismes de cohérence des caches.

Hardware Transaction

Le second problème à résoudre est que les écritures réalisées lors d'une transaction écrasent une ligne de cache, elles en modifient le contenu. Mais si la transaction est annulée, alors il faut retrouver la ligne de cache originelle, il faut la remettre dans son état d'avant la transaction. Pour cela, la solution la plus simple est que les lignes de cache modifiées ne sont pas écrasées : leur contenu est envoyé en mémoire RAM, elles sont évincées du cache. Il faut juste configurer le cache pour qu'il sauvegarde les lignes de cache modifiées avant de faire les écritures, et ce uniquement lors des transactions.

Une autre solution n'envoie pas les données en mémoire RAM, mais profite de la présence d'une hiérarchie de cache, avec la présence d'un cache partagé. Typiquement, les transactions modifient les données dans le cache L1, mais une copie de la donnée originelle est présente dans le cache L2 partagé. Sur les processeur avec un cache L3, c'est ce dernier qui est utilisé pour conserver les données non-modifiées. La raison est que ce dernier est partagé entre tous les cœurs. L'idée est que les transactions modifient les données dans les caches L1/L2 non partagés, mais propagent les écritures dans le cache partagé si la transaction réussit. Si elle échoue, les lignes de caches fautives sont marquées comme invalides par la cohérence des caches. En somme, on utilise des caches inclusifs, mais on débranche l'inclusivité du cache pendant les transactions, avant de les rétablir si la transaction réussit. Les lignes de cache marquées comme lues ou écrites par une transaction (bit READ WRITE) doivent rester dans le cache non-partagé et sont ignorées par l'algorithme de remplacement des lignes de cache.

Une autre solution, utilisée sur le processeur Blue gene d'IBM, consiste à avoir plusieurs exemplaires d'une donnée dans le cache, chacun venant d'un processeur/cœur différent. Si un seul processeur a manipulé la donnée partagée, celle-ci ne sera présente qu'en une seule version dans les caches des autres processeurs. Mais si la transaction échoue, alors cela veut dire que plusieurs processeurs ont modifié cette donnée : plusieurs versions d'une même donnée différente sera présente dans le cache

Voyons maintenant ce qu'il en est pour la détection des conflits. Plusieurs cas peuvent mener à un conflit et à l'abandon d'une transaction. Les cas en question surviennent quand un processeur veut écrire une donnée utilisée par une autre transaction.

• Le premier cas est celui où la donnée n'a pas encore été écrite, elle est dans l'ensemble de lecture. Le premier processeur qui la modifie gagne la course, si on peut dire. Il exécute son écriture, le protocole de cohérence des caches lance une demande d'invalidation des autres copies dans les autres caches, qui fait alors automatiquement échouer les transactions sur les autres processeurs.
• Le second cas est celui où la donnée a déjà été modifiée par un processeur dans son cache, mais n'est pas présente dans les autres caches non-partagés. Dans ce cas, si un second processeur veut modifier la donnée, il va aller la chercher dans le cache partagé L2/L3. Mais le protocole de cohérence des caches va remarquer que la donnée est dans le cache L1/L2 d'un autre cœur, avec le bit W mis à 1. Un conflit a alors lieu.

Le speculative Lock Elision

Les instructions atomiques 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 ont trouvé une solution à ce problème de réservations inutiles, basée sur la mémoire transactionnelle. L'idée est de générer des transactions en partant des instructions atomiques présentes dans le programme. Une instruction d'acquisition d'un LOCK démarre une transaction, alors qu'une instruction atomique qui le libère termine la transaction. L'optimisation porte le nom de Speculative Lock Elision, abrévié en SLE. Il s'agit d'une méthode que l'on classe à part de la mémoire transactionnelle explicite ou implicite, c'est une troisième possibilité.

Pour rappel, une instruction atomique est typiquement une opération de type READ-MODIFY-WRITE : elle lit une donnée, la modifie, et écrit le résultat en mémoire. Tel est le cas de l'instruction FETCH-AND-ADD, ou de ses dérivés. Le SLE n’exécute pas l'instruction atomique permettant d'effectuer un LOCK. À la place, elle exécute une lecture normale, une opération, et l'écriture du résultat. L'écriture n'est pas propagée dans le cache, mais est mise en attente dans la Store Queue. Puis, le processeur exécute les instructions qui suivent de manière transactionnelle. Quand le processeur rencontre une instruction atomique pour libérer le LOCK, il termine la transaction et vérifie si elle s'est bien passée ou doit être annulée. Les écritures en attente dans la store queue sont alors soit annulées, soit envoyées au cache et disponibles pour le mécanisme de cohérence des caches.

Dans sa version non-optimisée, le SLE exécute la transaction une seule fois. Si elle échoue, l'instruction atomique est exécutée pour de vrai. Pour plus d'efficacité, certains processeurs cherchent à éviter ce genre de situation en estimant la probabilité que le premier essai (la transaction) échoue. Pour cela, ils incorporent un circuit permettant d'évaluer les chances que le premier essai marche en tant que transaction : le Transaction Predictor. Une fois cette situation connue, le processeur décide ou non d’exécuter ce premier essai en tant que transaction.

L'exemple avec le x86

Dans cette section, nous allons étudier les premiers processeurs grand public qui ont supporté la mémoire transactionnelle matérielle : les processeurs Intel basés sur l’architecture Haswell, sortis aux alentours de mars 2013. Sur ces processeurs, deux modes sont disponibles pour la mémoire transactionnelle matérielle : le mode TSX, et le mode HLE.

Le mode TSX fournit quelques instructions supplémentaires pour gérer la mémoire transactionnelle matérielle. On trouve ainsi trois nouvelles instructions : XBEGIN, XEND et XABORT. XBEGIN démarre une transaction, XEND la termine, XABOUT la fait échouer immédiatement. L'instruction XBEGIN fournit une adresse qui pointe sur un morceau de code permettant de gérer l'échec de la transaction. Les registres modifiés par une transaction échouée sont remis dans leur état initial, à une exception près : le registre EAX est utilisé pour retourner un code d'erreur qui indique les raisons de l'échec d'une transaction.

Le mode HLE est celui de Speculative Lock Elision. Les instructions atomiques peuvent être transformées en transaction à une condition : qu'on leur rajoute un préfixe. Le préfixe d'une instruction x86 est un octet optionnel, placé au début de l'instruction, qui permet de modifier le comportement de l'instruction. Le préfixe LOCK rend certaines instructions atomiques, REPNZE répète certaines instructions tant qu'une condition est requise, etc. Le fait est que certains préfixes n'ont pas de signification pour certaines instructions et étaient totalement ignorés par le processeur. Pour supporter le Lock Elision, ces préfixes sans significations sont réutilisés pour indiquer qu'une instruction atomique doit subir la Lock Elision. De plus, deux "nouveaux" préfixes font leur apparition : XAQUIRE qui sert à indiquer que l'instruction atomique doit être tentée en tant que transaction ; et XRELEASE qui dit que la transaction spéculative est terminée. Ainsi, un programme peut être conçu pour utiliser la Lock Elision, tout en fonctionnant sur des processeurs plus anciens, qui ne la supportent pas ! Belle tentative de garder la rétrocompatibilité.