Mémoire transactionnelle logicielle

En informatique, la mémoire transactionnelle logicielle, en anglais software transactional memory (STM), est un mécanisme de contrôle de concurrence analogue aux transactions de base de données pour contrôler l'accès à la mémoire partagée dans la programmation concurrente. Elle fonctionne comme une alternative à la synchronisation fondée sur les verrous, et est typiquement implémentée sans verrous. Dans ce contexte, une transaction est une portion de code qui exécute une série de lectures et d'écriture en mémoire partagée. Ces lectures et ces écritures ont lieu de manière virtuellement indivisible, les états intermédiaires ne sont pas visibles pour les autres transactions qui réussissent. En 1993, Herlihy et Moss ont eu l'idée de fournir du support matériel pour les transactions. En 1995, Mur Shavit et Dan Touitou ont adapté cette idée en supprimant la nécessité d'un matériel spécifique, d'où le nom de mémoire transactionnel logicielle. La STM a été récemment l'objet d'intenses recherches et les implémentations concrètes se multiplient.

Performances

Contrairement aux techniques de verrou utilisées dans des applications multithread, la STM est optimiste : chaque thread effectue des modifications dans la mémoire partagée sans se soucier de ce que les autres threads font, enregistrant chacune de ses lectures et chacune de ses écritures dans un log. Au lieu de donner la responsabilité aux threads qui écrivent en mémoire afin de s'assurer qu'ils n'affectent pas indûment des opérations en cours, cette responsabilité est donnée aux threads lecteurs, qui après avoir terminé une transaction complète, vérifient que les autres threads n'ont pas fait des changements concurrents à la mémoire. On appelle commit l'opération finale, dans laquelle les changements d'une transaction sont validés et, si la validation réussit, sont rendus permanents. Une transaction peut aussi avorter à tout moment. Tous les changements qui la concernent sont « défaits » (rolled back en anglais) ou annulés. Si une transaction ne peut être commise à cause de changements conflictuels, elle est typiquement avortée et ré-exécutée à partir du début jusqu'à ce qu'elle réussisse.

Le bénéfice d'une approche optimiste est la concurrence accrue : aucun thread ne doit attendre pour accéder à une ressource, et différents threads peuvent modifier de manière sûre et simultanée des parties disjointes des structures de données qui seraient normalement protégées sous le même verrou. Malgré le surcoût de réessayer des transactions qui échouent, dans la plupart des programmes réalistes, les conflits sont suffisamment rares pour qu'il y ait un gain de performance immense par rapport aux protocoles à base de verrous sur un grand nombre de processeurs.

Mais, en pratique, la STM souffre de performance moindre comparé aux systèmes à fine granularité avec un petit nombre de processeurs (1 à 4 selon l'application). Cela est dû principalement au surcoût associé à la maintenance du log et au temps consommé lors d'un commit de multiples transactions. Mais même dans ce cas, typiquement. les performances ne sont que deux fois moindres, les avocats de la STM croient que les bénéfices conceptuels de la STM compensent cette pénalité.

Théoriquement, dans le pire des cas, quand il y a n transactions concurrentes en même temps, cela pourrait nécessiter O(n) de consommation mémoire et processeurs. Les besoins réels dépendent de détails d'implémentation. Par exemple, on peut faire qu'une transaction échoue suffisamment tôt pour minimiser le surcoût. Mais il y aura toujours des cas, certes rares, où des algorithmes à base de verrous auront un meilleur temps théorique que la mémoire transactionnelle logicielle.

Avantages et inconvénients conceptuels

En plus des bénéfices en performance, la STM simplifie grandement la compréhension des programmes multithreads et aide donc à rendre les programmes plus maintenables car travaillant en harmonie avec les abstractions de haut niveau comme les objets et les modules. La programmation à base de verrous comporte nombre de problèmes connus qui surgissent fréquemment en pratique :

• Elle demande de penser en termes de chevauchement d'opérations et d'opérations partielles dans des sections de code grandement séparées et apparemment sans rapport, ce qui est une tâche difficile et source d'erreurs pour les programmeurs.
• Elle demande au programmeur d'adopter une politique de verrouillage pour éviter les deadlocks, les livelocks et les autres cas d'échec afin de progresser. De telles politiques sont souvent appliquées de manière informelle et sont faillibles, et quand ces problèmes surviennent, ils sont insidieux et difficiles à reproduire et à déboguer.
• Elle peut aboutir à une inversion de priorité, un cas ou un fil de haute priorité est forcé d'attendre à cause d'un fil de de basse priorité ayant un accès exclusif à une ressource dont le fil de haute priorité a besoin.

Par contraste, le concept de transaction de mémoire est beaucoup plus simple car on peut voir isolément chaque transaction dans un calcul unifilaire. Les deadlocks et les livelocks sont, soit évités entièrement, ou gérés par un gestionnaire externe de transactions. Le programmeur n'a jamais à s'en soucier. Les inversions de priorités peuvent encore être un problème, mais les transactions de haute priorité peuvent faire avorter des transactions de priorité moindre qui n'ont pas été commises.

D'autre part, le besoin de faire avorter des transactions qui échouent limite le comportement possible des transactions : elles ne peuvent pas effectuer les actions qui ne peuvent pas être défaites, comme la plupart des entrées/sorties. En pratique, on peut typiquement surmonter de telles limitations en créant des tampons qui accumulent les opérations irréversibles et les exécutent plus tard en dehors de toute transaction.

Opérations composables

En 2005, Tim Harris, Simon Marlow, Simon Peyton Jones, et Maurice Herlihy ont décrit un système de STM construit pour Concurrent Haskell. Il autorise la composition d'opérations atomiques en des opérations atomiques plus large, un concept utile qui est impossible avec la programmation à base de verrous. Citons les auteurs :

Peut-être l'objection la plus fondamentale [...] est que les programmes à base de verrous ne se composent pas : des fragments corrects peuvent échouer quand ils sont combinés. Par exemple, considérons une table de hachage avec des opérations insertion et d'effacement sûres relativement aux threads. Maintenant, supposons que nous voulions effacer un item A de la table t1, et l'insérer dans la table t2. Mais l'état intermédiaire (dans lequel aucune table ne contient l'item) ne doit pas être visible des autres threads. A moins que l'implanteur de la table de hachage anticipe ce besoin, il n'y a pas de moyen simple de satisfaire cette condition. [...]. En bref, les opérations qui sont correctes individuellement (insert, delete) ne peuvent pas être composées en des opérations plus larges et encore correctes.
—Tim Harris et al, « Composable Memory Transactions », Section 2: Background, pg.2

Avec la STM, résoudre le problème est simple : envelopper les opérations dans une transaction rend leur combinaison atomique. Le seul point délicat est qu'il n'est pas clair pour l'appelant, qui ne connait pas les détails d'implémentation des méthodes composantes. quand elles doivent essayer de réexecuter la transaction si elle échoue. En réponse à ce problème, les auteurs ont proposé une commande retry qui utilise le log de la transaction qui a échoué pour déterminer quelle cellule mémoire est lue, et de réessayer automatiquement la transaction quand l'une de ces cellules est modifiée. La logique est que la transaction ne se comportera pas différemment tant qu'aucune de ces valeurs n'est changée. Les auteurs ont aussi proposé un mécanisme pour la composition d'alternatives, le mot-clé orElse. Il exécute une transaction et si cette transaction fait un retry, en exécute une seconde. Si les deux font un retry, il les essaie tous deux encore aussitôt qu'un changement approprié est fait. Ce service, comparable aux fonctionnalités réseau de POSIX de l'appel système select(), permet à l'appelant de choisir d'attendre simultanément plusieurs évènements, Cela simplifie aussi les interfaces programmatiques, par exemple en fournissant un mécanisme simple pour convertir entre des opérations bloquantes et non bloquantes.

Support proposé par le langage

La simplicité conceptuelle de la STM permet d'exposer ce mécanisme au programmeur avec une syntaxe relativement simple. Language Support for Lightweight Transactions (support par le langage de transactions poids-plume) de Tim Harris et Keir Fraser propose d'utiliser une région critique conditionnelle pour représenter les transactions. Dans sa forme la plus simple, c'est juste un « bloc atomique », c’est-à-dire un bloc de code qui n'est pas interruptible :

 // 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;
 }

Lorsque la fin du bloc est atteinte, la transaction est commise si possible, sinon elle est avortée et réessayée. CCRsQu'est-ce que CCRs ?! permet aussi une ´condition de garde, qui permet a une transaction d'attendre jusqu'à ce qu'elle ait du travail à faire :

 atomic (queueSize > 0) {
     enlève un item de la queue et l'utilise
 }

Si la condition n'est pas satisfaite, le gestionnaire de la transaction attendra jusqu'à ce qu'une autre transaction ait été commise qui affecte la condition avant de réessayer. Ce couplage lâche entre producteurs et consommateurs améliore la modularité comparé à l'usage de signaux explicites entre les threads. « Composable Memory Transactions » (transactions mémoire composables) va un pas plus loin avec sa commande retry discutée ci-dessus, qui peut, à tout moment, faire avorter la transaction et attendre qu'une valeur lue avant la transaction soit modifiée avant de réessayer. Par exemple :

 atomic {
     if (queueSize > 0) {
         enlève l'item de la queue et l'utilise
     } else {
         retry
     }
 }

Cette faculté de réessayer dynamiquement plus tard la transaction simplifie le modèle de programmation et ouvre d'autres possibilités. Un problème est comment les exceptions se comportent quand elles se propagent en dehors des transactions. Dans « Composable Memory Transactions », les auteurs ont décidé qu'elle causerait l'avortement de la transaction puisque les transactions indiquent normalement des erreurs inattendues dans Concurrent Haskell, mais que les exceptions pourraient retenir de l'information allouées et lues durant la transaction à fins de diagnostic. Ils insistent sur le fait que d'autre conceptions peuvent être raisonnables dans d'autres cas.

Problème d'implémentation

Un problème avec l'implémentation de la mémoire transactionnelle logicielle est qu'il est possible qu'une transaction lise un état inconsistant, c’est-à-dire qu'elle lise un mélange d'anciennes et de nouvelles valeurs écrites par une autre transaction. Une telle transaction est condamnée à avorter si elle tente un commit, mais il est possible qu'un état inconsistant fait qu'une transaction déclenche une condition fatale exceptionnelle telle qu'une erreur de segmentation ou même entre une boucle sans fin, comme dans l'exemple suivant artificiel de la figure 4 de « Language Support for Lightweight Transactions » (support au niveau du langage des transactions poids-plume) :

atomic {
    if (x != y) 
        while (true) { }
}

atomic {
    x++;
    y++;
}

Si initialement x=y , aucune des deux transactions ci-dessus n'altère l'invariant, mais il est possible qu'une transaction A lise x avant qu'une transaction B ne le modifie, provoquant l'entrée dans une boucle infinie. La stratégie habituelle pour gérer cela est d'intercepter toute exception fatale et de vérifier périodiquement si chaque transaction est valide. Sinon, on peut provoquer son avortement immédiat, puisqu'elle échouera quoi qu'il arrive.

Implémentations

Nombre d'implémentations de STM ont été publiées (avec de grandes variations de qualité et de stabilité), beaucoup sous des licences libres :

• (en) La bibliothèque STM décrite dans « Composable Memory Transactions », fait partie de la distribution du Glasgow Haskell Compiler standard.
• (en) SXM, une implémentation des transactions par Microsoft Research. Documentation, Download page.
• (en) Several implementations by Tim Harris&Keir Fraser, fondé sur les idées des papiers « Language Support for Lightweight Transactions », « Practical Lock Freedom », un travail non encore publié.
• (en) The Lightweight Transaction Library (LibLTX), une implémentation en C par Robert Ennals se concentrant sur l'efficacité et basée sur ses papiers « Software Transactional Memory Should Not Be Obstruction-Free » et « Cache Sensitive Software Transactional Memory ».
• (en) LibCMT, une implémentation open source en C de Duilio Protti fondée sur « Composable Memory Transactions ». L'implémentation inclut aussi un binding C#.
• (en) RSTM Une équipe dirigée par Michael Scott a écrit cette STM. Mike Spear, Virendra Marathe, et Chris Heriot ont écrit le code, avec des contributions de Athul Acharya, David Eisenstat, Bill Scherer, Arrvindh Shriraman, et Vinod Sivasankaran.
• (en) Une implémentation de AtomJava par le groupe de recherche SCAT.
• (en) TARIFA est un prototype qui ajoute le mot-clef « atomic » au C/C++ en instrumentant l'assembleur généré par le compilateur.
• Une STM pour Perl 6 a été implémentée dans Pugs via la bibliothèque STM de Glasgow Haskell Compiler. Dans Parrot, une STM a été implémentée en C et est accessible via des opcodes de l'assembleur imcc.
• (en) jstm est une implémentation open source en java, avec des extensions spéciales comme la réplication d'objets entre machines Documentation

Références

• (en) Nir Shavit and Dan Touitou. Software Transactional Memory. Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, pp.204–213. August 1995. Le papier à l'origine de la STM.
• (en) Maurice Herlihy, Victor Luchangco, Mark Moir, and William N. Scherer III. Software Transactional Memory for Dynamic-Sized Data Structures. Proceedings of the Twenty-Second Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), 92–101. July 2003.
• (en) Tim Harris and Keir Fraser. Language Support for Lightweight Transactions. Object-Oriented Programming, Systems, Languages, and Applications, pp.388–402. October 2003.
• (en) Tim Harris, Simon Marlow, Simon Peyton Jones, and Maurice Herlihy. Composable Memory Transactions. ACM Conference on Principles and Practice of Parallel Programming 2005 (PPoPP'05). 2005.
• (en) Robert Ennals. Software Transactional Memory Should Not Be Obstruction-Free.
• (en) Michael L. Scott et al. Lowering the Overhead of Nonblocking Software Transactional Memory propose une introduction non seulement sur la RSTM mais aussi sur les approches courantes concernant la STM.

Liens externes

• (en) Cambridge lock-free group
• (en) Robert Ennals' Fast STM site
• (en) Software transactional memory Description; Derrick Coetzee
• (en) Transactional Memory Bibliography

Voir aussi

• Transaction informatique
• Transaction (base de données)

• Portail de l’informatique