Comment implémentez-vous la mémoire transactionnelle logicielle?

Question

En ce qui concerne les instructions atomiques de bas niveau et les barrières de mémoire (je suppose qu’elles sont utilisées), comment implémentez-vous STM?

Ce qui est mystérieux pour moi, c’est que, dans la mesure où un morceau de code est arbitraire, vous avez besoin d’un moyen de revenir en arrière et de déterminer si les valeurs utilisées à chaque étape étaient valides. Comment faites-vous cela et comment le faites-vous efficacement? Cela semblerait également suggérer que, comme toute autre solution «verrouillante», vous voulez garder vos sections critiques aussi petites que possible (pour réduire la probabilité d'un conflit), ai-je raison?

De même, STM peut-il simplement détecter "un autre thread est entré dans cette zone pendant l'exécution du calcul; le calcul n'est donc pas valide" ou peut-il réellement détecter si des valeurs obstruées ont été utilisées (et donc par chance, parfois deux threads peuvent exécuter la même section critique simultanément sans avoir besoin de revenir en arrière)?

Answer 1

La réponse la plus simple est "ça dépend". Il existe des tonnes d’implémentations radicalement différentes qui fonctionnent de toutes les manières imaginables.

  

Ce qui est mystérieux pour moi, c’est qu’étant donné une partie arbitraire du code, vous avez besoin d’un moyen de revenir en arrière et de déterminer si les valeurs utilisées à chaque étape sont valides. Comment faites-vous cela et comment le faites-vous efficacement?

Une solution consiste à utiliser le versioning. Chaque fois qu'un objet est modifié, son numéro de version est mis à jour. Pendant que la transaction est en cours d'exécution, vous validez la version de chaque objet auquel vous avez accédé et, lorsque la transaction est validée, vous vérifiez que les objets sont toujours valides . . Cette validation peut être une simple comparaison d’entiers (si version_start_ transaction> = version_objet , l’objet est valide), il peut donc être effectué assez efficacement.

  

Cela semblerait également suggérer que, comme pour toute autre solution "verrouillable", vous souhaitez que vos sections critiques soient aussi petites que possible (pour réduire la probabilité d'un conflit), ai-je raison?

Très probable. Je pense que quelques implémentations sont allées dans le sens de supposer / obliger tout à être une transaction, mais oui, dans la plupart des implémentations, les transactions sont des morceaux de code spécialement marqués, risque de conflit pouvant entraîner l'annulation des transactions.

  

De même, STM peut-il simplement détecter "un autre thread est entré dans cette zone pendant l'exécution du calcul; le calcul n'est donc pas valide" ou peut-il réellement détecter si des valeurs obstruées ont été utilisées (et donc par chance, parfois deux threads peuvent exécuter la même section critique simultanément sans avoir besoin de revenir en arrière)?

Ce dernier. Rappelez-vous que l’idée dans TM est de protéger les données , plutôt que le code .

Différents chemins de code peuvent accéder à la même variable dans différentes transactions. Cela doit être détecté par le système de MT. Il n'y a pas de réelle notion de "cette zone", car cela fait référence à du code plutôt qu'à des données. Le système de MT ne se soucie pas du code en cours d’exécution, il contrôle les données en cours de modification. En ce sens, il diffère entièrement des sections critiques (qui protègent le code plutôt que les données)

Answer 2

Certains articles peuvent être très difficiles à lire, mais deux très clairs et concis sont:

Verrouillage transactionnel II, Dave Dice, Ori Shalev, Nir Shavit qui décrit le " TL2 " Algorithme STM en termes de toute langue.

Deuce: Mémoire transactionnelle logicielle non invasive en Java, Guy Korland, Nir Shavit, Pascal Felber , qui explique un transformateur de classes de temps de chargement qui transforme les classes java classiques en classes en mémoire comportant un bytecode supplémentaire permettant d'effectuer STM. Ceci est pertinent pour la question car le document explique comment le code sans STM peut être transformé mécaniquement en un code exécutant STM dans n’importe quel langage OO.

Le framework Deuce vous permet de greffer l’algorithme que vous souhaitez utiliser; y compris l'algorithme TL2. Comme le framework Deuce est en Java, la discussion suivante utilise la terminologie java mais suppose seulement que vous écrivez dans un langage OO.

Vous trouverez ci-dessous une description de l’approche TL2. Les articles ont des liens vers des approches alternatives mais étudier un algorithme répond à beaucoup de questions.

  

comment implémentez-vous STM? Ce qui est mystérieux pour moi, c’est qu’étant donné un morceau de code arbitraire, vous avez besoin d’un moyen de revenir en arrière et de déterminer si les valeurs utilisées à chaque étape étaient valides.

Une brève réponse sur la façon dont TL2 gère STM est "comptabilité". et alors uniquement en utilisant des verrous en écriture au moment de la validation. Lisez le papier pour les détails les plus fins, mais voici le contour d’une brosse en carton. Chaque propriété que vous pouvez utiliser dans le code d'origine aurait un getter et un setter. Dans le code transformé, un numéro de version de la propriété et un code supplémentaire sont également ajoutés au getter et au setter. Vous devez enregistrer la version de chaque attribut lu dans la transaction en tant que transaction "read-set". Vous pouvez le faire en demandant à chaque getter d’ajouter la version de l’attribut vue dans une liste liée de threadlocal. Vous devez également mettre les écritures en mémoire tampon en tant que " write-set " dans un threadlocal jusqu'à ce que vous vous engagiez. Notez que les méthodes de lecture doivent vérifier et renvoyer une valeur de groupe d'écriture threadlocal pour un champ donné, le cas échéant. De cette façon, vous voyez vos écritures non validées dans vos lectures, mais aucun autre fil ne les verra jusqu'à ce que vous les validiez.

Au moment de la validation, vous verrouillez en écriture tous les attributs que vous êtes sur le point d'écrire. Lorsque vous avez les verrous, vous vérifiez à nouveau que votre ensemble de lectures est toujours valide. que les attributs que vous avez lus dans votre transaction n'ont pas été mis à jour vers une version supérieure par une autre transaction. Si tel est le cas, votre logique métier risque de ne pas être valide, car vos lectures peuvent être incohérentes. Vous devez donc annuler toute la transaction. Si les dernières vérifications sont satisfaisantes, vous vous engagez à vider votre ensemble d'écriture, à modifier les versions de ces attributs, à libérer les verrous en écriture et à effacer les listes de threadlocal des ensembles d'écriture et de lecture.

Le document explique que l’algorithme peut abandonner plus tôt s’il détecte qu’un attribut en cours de lecture a été écrit depuis le début de la transmission. Le document contient quelques astuces pour accélérer les transactions en lecture seule. Il a même une astuce pour déterminer quels blocs sont en lecture seule et lesquels sont en lecture / écriture. Quiconque s’intéresse à ce genre de choses devrait vraiment apprécier les deux journaux.

Le cadre Deuce présenté dans l’article ci-dessus montre comment modifier tous vos getters et setters en injectant un nouveau bytecode java dans vos classes au moment du chargement. D'autres langages pourraient avoir un compilateur ou un préprocesseur spécial qui effectue la même transformation mécanique du code normal en code activé par STM. Plus précisément, avec Deuce, vos objets de code source peuvent avoir de simples paires d'accesseurs getter, mais les classes transformées à l'exécution ont enrichi les outils getter qui effectuent le travail de livre.

Transformer du code standard en code STM (en particulier au moment de l’exécution) est intéressant, mais si vous devez réellement écrire une structure de données compatible STM, vous n’avez besoin d’aucune sauce magique. Créez plutôt une classe Ref avec un get () et un set (x) et créez chaque relation entre vos objets de structure de données des références . Dans le get et le set de votre classe Ref , vous pouvez effectuer le travail de rédaction threadlocal. Vous pouvez ensuite implémenter une version simple de " TL2 " ou tout autre algorithme qui fonctionne bien pour vos structures de données et votre concurrence entre lecture et écriture.

  

Cela semblerait également suggérer que, comme tout autre "verrouillage"   solution que vous voulez garder vos sections critiques aussi petit que possible   (pour diminuer la probabilité d'un conflit), ai-je raison?

TL2 a une période critique dans la conservation des verrous en écriture, puis dans les vérifications finales et les écritures, faciles à comprendre et à optimiser sans aucune compréhension de la logique applicative de l’application. Si vous attribuez à chaque numéro une propriété unique, vous pouvez éviter le blocage en prenant des verrous par ordre croissant. Il est important de noter que toute votre logique métier est spéculative, en supposant que les vérifications de validation passent. Vous ne gardez pas les verrous lorsque vous utilisez une logique métier lente et arbitraire. Vous pouvez effectuer plusieurs recherches sur le service Web ou des appels de base de données lents. Vous ne verrouillez aucun verrou avant la validation. Il est clair que les professionnels vont régler le diable de la section critique générique.

Le document indique clairement que l'algorithme peut abandonner plus souvent que la logique métier spécifique l'exige. L'algorithme générique ne sait pas si des lectures modifiées spécifiques n'affecteront pas le résultat réel de l'écriture. Une logique manuscrite qui comprend la logique métier réelle peut connaître des cas particuliers dans lesquels une annulation n'est pas nécessaire pour un ensemble donné de lectures non conformes. Si toutefois vous avez beaucoup de code à écrire et une application où la probabilité de restauration est très faible, une approche STM mécanique générique peut entraîner moins de bogues et de bonnes performances.

  

De même, STM peut-il simplement détecter " un autre thread est entré dans cette zone   le calcul était en cours d'exécution, le calcul n'est donc pas valide "   ou peut-il réellement détecter si des valeurs obstruées ont été utilisées (et donc   par chance, parfois deux threads peuvent exécuter la même section critique   simultanément sans avoir besoin de revenir en arrière)?

L’approche TL2 s’applique uniquement aux données lues ou écrites et non au code qui les fait. C'est ce que vous obtenez et définissez et qui compte; et si un autre fil a marché sur vos orteils avant de vider toutes les écritures. Tout ce qui est requis du code est que vous ayez un begin () , commit () et rollback () dans la logique applicative pour démarrer , terminez et annulez la transaction. Même cela peut être généré du code. Avec Java, vous pouvez marquer vos méthodes avec l'annotation @Transactional sur les méthodes, puis générer du code qui encapsule vos appels de méthodes dans un try / catch / finally qui effectue le début / la validation / l'annulation en tant que java idiomique. Deuce injecte une telle logique au moment du chargement de la classe.

Encore une fois, vous n’avez pas besoin d’une telle sauce magique pour commencer / commettre / annuler dans vos propres structures de données activées par STM. Vous pouvez être explicite et insérer tout cela dans votre code logique de structure de données pour créer vos propres classes explicitement activées par STM dans n’importe quel langage OO.

Answer 3

La implémentation de STM de GHC est décrite dans la section six de:

Transactions sur la mémoire composable . Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy. PPoPP'05: Symposium ACM SIGPLAN sur les principes et la pratique de la programmation parallèle, Chicago, Illinois, juin 2005

Et la cinquième section de:

Mémoire transactionnelle avec invariants de données . Tim Harris, Simon Peyton-Jones. Mars 2006 TRANSACT '06

Answer 4

Je vous suggère de regarder cette présentation: http: // www. infoq.com/presentations/Value-Identity-State-Rich-Hickey

Dans la seconde moitié, il explique comment mettre à jour des valeurs sans les laisser dans un état non défini. Par exemple, si vous souhaitez mettre à jour un arbre dans le style STM, vous ne modifiez pas du tout la version précédente. Disons que tree est un pointeur sur la racine de l’arbre. Les seuls nœuds que vous créez sont les nœuds qui ont changé (mais ils peuvent faire référence aux nœuds de l'instantané d'origine de l'arborescence.

Ensuite, vous effectuez une comparaison-échange sur le pointeur arborescence . Si cela réussit, tout le monde va maintenant voir votre nouvel arbre et l'ancien peut être ramassé. Si ce n’est pas le cas, répétez le processus et l’arbre que vous venez de construire est nettoyé.

La grande idée est qu'il n'est pas nécessaire de détecter si quelqu'un d'autre a modifié l'arborescence de l'arbre jusqu'à ce que vous échangiez les anciennes et les nouvelles valeurs. Il n'y a donc pas de "conflits". ou " valeurs écrasées " de la programmation typique multithread.

Answer 5

Si vous utilisez le framework .NET,

Vous pouvez consulter cette expérience

• .NET 4.0 STM.Net
  
• Le podcast .NET sur STM.Net: Dana Groff et Yossi Levanoni Parlez STM