Mémoire transactionnelle logicielle

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. L'opération finale est appelée commit, 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 performances moindres 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.

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 où un fil de haute priorité est forcé d'attendre à cause d'un fil 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.

En 2005, Tim Harris, Simon Marlow, Simon Peyton Jones, et Maurice Herlihy ont décrit un système de STM construit pour Concurrent Haskell (en). Il autorise la composition d'opérations atomiques en des opérations atomiques plus larges, 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 d'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. À 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.

La simplicité conceptuelle de la STM permet d'exposer ce mécanisme au programmeur avec une syntaxe relativement simple. Language Support for Lightweight Transactions (prise en charge par le langage de transactions légères) de Tim Harris et Keir Fraser propose d'utiliser la notion de région critique conditionnelle (« Conditional Critical Region ») pour représenter les transactions. Dans sa forme la plus simple, il s'agit simplement d'un « bloc atomique », c’est-à-dire d'un bloc de code qui ne peut s'exécuter qu'entièrement ou pas du tout :

 // Insère, de manière atomique, un nœud dans une liste doublement chaîné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 validée si possible, sinon elle est avortée et réessayée.

Les régions critiques conditionnelles rendent également possibles les conditions de garde, qui permettent de faire attendre une transaction jusqu'à ce qu'elle ait du travail à faire :

 atomic (queueSize > 0) {
     // Retire un élément de la file d'attente avant de l'utiliser
 }

Si la condition n'est pas satisfaite, le gestionnaire de la transaction attendra avant de réessayer la transaction qu'une autre transaction soit validée après avoir modifié la condition. Ce couplage lâche entre producteurs et consommateurs rend le code plus modulaire qu'une utilisation de signaux explicites entre threads.

Les transactions mémoire composables (« Composable Memory Transactions ») permettent d'aller encore plus loin grâce à la commande retry (cf. ci-dessus) qui peut, à tout moment, faire avorter la transaction et attendre, avant de la réessayer, qu'une quelconque valeur lue avant la transaction soit modifiée. Par exemple :

 atomic {
     if (queueSize > 0) {
         // Retire un élément de la file d'attente avant de l'utiliser
     } else {
         retry
     }
 }

Cette capacité à réessayer dynamiquement plus tard la transaction simplifie le modèle de programmation et ouvre d'autres possibilités.

L'un des problèmes qui se posent est la manière dont une exception qui se propage en dehors d'une transaction interagit avec cette dernière. Dans le cadre des transactions mémoire composables, Tim Harris et Keir Fraser ont choisi de faire avorter la transaction quand une exception est propagée, dans la mesure où, dans Concurrent Haskell, une exception indique normalement une erreur inattendue, mais ils ont aussi décidé qu'à des fins de diagnostic, les exceptions puissent conserver de l'information allouée et lue durant la transaction. Cependant, Tim Harris et Keir Fraser insistent sur le fait que ce choix n'est pas le seul possible, et que d'autres implémentations peuvent faire d'autres choix raisonnables.

Un problème avec l'implémentation de la mémoire transactionnelle logicielle est qu'il est possible qu'une transaction lise un état incohérent, 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 incohérent fasse qu'une transaction déclenche une condition fatale exceptionnelle telle qu'une erreur de segmentation ou même entre dans une boucle sans fin, comme dans l'exemple suivant artificiel de la figure 4 de « Language Support for Lightweight Transactions » (prise en charge par le 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.

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

• La bibliothèque STM décrite dans « Composable Memory Transactions », fait partie de la distribution du Glasgow Haskell Compiler standard.
• SXM, une implémentation des transactions par Microsoft Research.
• 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é.
• 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 ».
• 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#.
• 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.
• Une implémentation de AtomJava par le groupe de recherche SCAT.
• 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.
• jstm est une implémentation open source en java, avec des extensions spéciales comme la réplication d'objets entre machines

• (en) Nir Shavit and Dan Touitou. Software Transactional Memory. Proceedings of the 14th ACM Symposium on Principles of Distributed Computing, p. 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, p. 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.