Mémoire transactionnelle logicielle - Définition

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'implantation 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.

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.