Mémoire Transactionnelle Logicielle

Mémoire Transactionnelle Logicielle

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 implanté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 implantations concrètes se multiplient.

Sommaire

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 a cause de changements conflictueux, 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éficies 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'implantation. 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 désavantages 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 verrouilage 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 limitent 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'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.

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

Un problème avec l'implantation de la memoire 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) { }
}

Transaction A

atomic {
    x++;
    y++;
}

Transaction B

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.

Implantations

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

  • (en) La bibliothèque STM décrite dans « Composable Memory Transactions », fait partie de la distribution du Glasgow Haskell Compiler standard.
  • (en) SXM, une implantation des transactions par Microsoft Research. Documentation, Download page.
  • (en) Several implementations by Tim Harris&Keir Fraser, fondê sur les idêes de se papier « Language Support for Lightweight Transactions », « Practical Lock Freedom », un travail non encore publié.
  • (en) The Lightweight Transaction Library (LibLTX), une implantation 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 implantation open source en C de Duilio Protti fondée sur « Composable Memory Transactions ». L'implantation 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 implantation 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é implanté dans Pugs via la bibliothèque STM de Glasgow Haskell Compiler. Dans Parrot, une STM a été implanté en C et est accessible via des opcodes de l'assembleur imcc.
  • (en) jstm est une implantation open source en java, avec des extensions spéciales comme la réplication d'objets entre machines Documentation

Références

Liens externes

Voir aussi

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « M%C3%A9moire transactionnelle logicielle ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Mémoire Transactionnelle Logicielle de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Memoire transactionnelle logicielle — 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 …   Wikipédia en Français

  • 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 …   Wikipédia en Français

  • Parallélisme (informatique) — Pour les articles homonymes, voir parallèle. Blue Gene L cabinet., un des ordinateurs massivement parallèle les plus rapides des années 2000 En informatiqu …   Wikipédia en Français

  • Synchronisation (multitâches) — Pour les articles homonymes, voir Synchronisation. Dans le contexte de la programmation concurrente, le terme de synchronisation se réfère à deux concepts distincts mais liés : la synchronisation de processus et la synchronisation de données …   Wikipédia en Français

  • Programmation concurrente — La programmation concurrente est un style de programmation tenant compte, dans un programme, de l existence de plusieurs piles sémantiques. Ces piles peuvent être appelées threads, processus ou tâches. Elles sont matérialisées en machine par une… …   Wikipédia en Français

  • Pugs — est une mise en œuvre expérimentale de Perl 6 en langage Haskell, et utilisant les spécificités les plus avancée de GHC. Selon le dorsal de génération et d exécution de code, Pugs peut être considéré soit comme un compilateur, soit comme un… …   Wikipédia en Français

  • STM — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres > Sigles de trois lettres   Sigles de quatre lettres …   Wikipédia en Français

  • INTERNET — est un réseau («net») de réseaux disséminés dans le monde entier et dont certains services sont accessibles librement. Internet représente également une communauté d’utilisateurs qui dialoguent ou échangent du courrier électronique. Internet est… …   Encyclopédie Universelle

  • Test de Charge — Test de performance Un test de performance ou benchmark est un test dont l objectif est de déterminer la performance d un système informatique. L acception la plus courante de ce terme est celle dans laquelle ces tests logiciels vont avoir pour… …   Wikipédia en Français

  • Test de performance — Un test de performance est un test dont l objectif est de déterminer la performance d un système informatique. L acception la plus courante de ce terme est celle dans laquelle ces tests logiciels vont avoir pour objectif de mesurer les temps de… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”