Le nid de dodo

Un article de bredelet    Pas de commentaires

Le concept de transaction est bien connu des utilisateurs de base de données, où il sert à grouper des opérations pour permettre l’accès concurrent et consistant aux données de la base.

La programmation parallèle peut faire appel à la notion de transaction pour manipuler les variables partagées. Le principal intérêt de ce modèle est la simplicité d’utilisation et une efficacité meilleure que d’autres modèles comparables.

1. Les transactions

   Une transaction en dodo est délimitée par un bloc sync qui contient les instructions qui font partie de la transaction. Ces instructions sont exécutées comme si il n’y avait pas de parallélisme et nulle autre tâche n’interfère avec son exécution.

   En réalité ce n’est pas tout à fait vrai, par défaut dodo triche pour éviter le rollback des transactions. En effet si le système détecte qu’une transaction ne peut pas être complétée « comme si nulle autre tâche n’interfère », pour bien faire il faut annuler tout ce que la transaction a fait jusqu’ici et recommencer du début! C’est ce qu’on appelle un rollback.

   Nous verrons plus tard comment changer les options pour autoriser à nouveau les rollbacks et se conformer au principe d’isolation. Voyons maintenant un exemple de bloc sync:

   sync
   {
      .a = a + b
   }
   

   Pourquoi veut-on créer une transaction juste pour ajouter deux variables?

   Eh bien si on y pense, il se pourrait qu’une autre tâche intervienne entre le moment où les variables sont lues et le moment où a est mise à jour, ce qui fait que la valeur finale ne sera pas vraiment a + b. L’utilisation d’une transaction permet de protéger le bloc de code des influences extérieures.

   Pour prendre en compte la possibilité de rollback, il convient d’indiquer à dodo comment annuler les changements déjà faits. Si par exemple f(a) cause un rollback on peut écrire:

   sync
   {
      .a = a + b ...> __undo .a = a - b
      f(a)
   }
   

   Note: Les instructions précédées de __undo sont aussi exécutées en cas d’exception, sauf si le gestionnaire d’événements convertit l’exception en return. Un bloc sync définit son propre gestionnaire d’événements.

2. Les variables versionnées

   Les variables partagées ordinaires ne sont pas de grande utilité dans le cadre des transactions, car leurs modifications sont généralement problématiques à annuler en cas de rollback. C’est pourquoi on fait appel aux variables versionnées. Les modifications d’une variable versionnée sont automatiquement annulées en cas de rollback.

   Une variable versionnée a une partie commune, partagée entre toutes les tâches, et une partie locale qui est utilisée dans le cadre d’une transaction. Quand la variable est lue dans une transaction, la partie partagée est copiée dans la partie locale ainsi que son numéro de version. C’est ce qui permet à sa valeur de rester consistante tout au long de la transaction, même si une autre tâche intervient.

   Quand la transaction a copié la valeur partagée de la variable dans sa partie locale, la variable est dans l’état synchronized.

3. Les options de synchronisation

   Par défaut, dodo garantit que la transaction a une vue cohérente des données: il existe un moment dans le temps où toutes les variables de la transaction ont la valeur que la transaction a lue. C’est la seule garantie des options par défaut (use: newest). Pour l’exemple précédent, si a vaut 0 et b vaut 3 au départ, et il y a trois tâches qui exécutent la transaction en parallèle, la valeur finale de a peut être 9, 6 ou bien 3. Il se peut même qu’elle aille de 6 à 3 (inversion temporelle).

   Exemples d’exécution
   Valeur lue par la troisième tâche en vert, valeur écrite par la troisième tâche en gras
   
   temps —–>
   a: 0 , 3 , 6 , 9
   temps —–>
   a: 0 , 3 , 6 , 6
   temps —–>
   a: 0 , 3 , 6 , 3

   Si l’on veut assurer la consistence temporelle, et s’assurer que la variable a des valeurs qui se suivent de façon logique dans le temps, on peut choisir l’option suivante:

   __handle (use: first)
   

   Cela indique à dodo que la valeur ne devrait pas être remplacée si la version utilisée par la transaction n’est plus celle que contient la variable partagée. Une fois encore, cette option ne cause pas de rollbacks.

   Cependant, avec ceci il se peut qu’une variable soit mise à jour alors qu’une autre ne l’est pas — la transaction n’assure pas vraiment la cohérence des données mises à jour. C’est pourquoi dodo ne garantit pas une vue cohérente des données avec cette option.

   Effet de l’option use: first sur les conflits de version avec une transaction parallèle (en vert)

   sync
   {
      .a *= b
      ++.b
   }
   
   Val. lue/écrite     a  b  |  a  b  |  a  b
   -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
   Début transaction   3  2  |  3  2  |  3  2  
   Fin transaction     5  2  |  3  4  |  3  2
   Valeur locale       6  3  |  6  3  |  6  3
   -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
   Valeur partagée     5  3  |  6  4  |  6  3
   -  -  -  -  -  -  -  -  -  -  -  -  -  -  -
   

   Pour obtenir davantage de garanties il faut autoriser les rollbacks. Le premier exemple de transaction avec rollback est avec les options:

   __handle (use: newest, action: fail)
   

   Ces options sont similaires aux options par défaut, mais si dodo détecte une inversion temporelle les opérations sont annulées et la transaction s’exécute à nouveau. Dans les exemples d’exécution précédents le dernier ne serait pas possible.

   Finalement, ces options apportent toutes les garanties que l’on peut attendre d’une transaction:

   __handle (use: first, action: fail)
   

   Cela indique à dodo que la transaction doit être réexécutée si la version utilisée par la transaction n’est plus celle que contient la variable partagée quand elle est mise à jour. De plus ces options assurent une vue cohérente des données. Dès lors la seule exécution possible est:

   a: 0 3 6 9

   Les options de synchronisation peuvent s’appliquer à une variable particulière avec la notation __handle variable.

4. Bloc sync conditionnel

   Le bloc sync conditionnel s’écrit:

   sync select
   {
      condition1 =>
         ...transaction1...
      condition2 =>
         ...transaction2...
      ...
   }
   

   Les variables utilisées dans la condition font partie de la transaction. Si les conditions sont réunies mais par la suite, la transaction sélectionnée fait un rollback, alors dodo teste les conditions de la transaction suivante. Si nulle transaction n’a de succès, alors le bloc sync entier fait un rollback. Une erreur est signalée si aucune transaction n’a été tentée dans un bloc sync conditionnel.

   La condition spéciale default indique qu’aucune autre condition n’est remplie; de fait, la condition default n’est pas remplie si l’exécution d’une autre transaction a été tentée mais s’est soldée par un rollback. L’utilisation de default permet d’assurer qu’au moins une transaction est tentée.

5. Transaction à l’intérieur d’une transaction

   Si le bloc sync se trouve à l’intérieur d’un autre bloc sync, cela définit une sous-transaction. Les changements faits dans la sous-transaction ne sont effectifs que quand la transaction englobante termine avec succès. En cas de rollback de la sous-transaction, la transaction englobante fait aussi l’objet d’un rollback. Le reste dépend des options de synchronisation.

   Avec les options de synchronisation par défaut (use: newest), dodo assure une vue cohérente des données de la sous-transaction à un moment dans le temps. Mais celle-ci peut différer de la vue de la transaction englobante.

   Avec l’option de consistance temporelle (use: first), la vue de la transaction englobante est réutilisée.

   Si les rollbacks sont autorisés en cas d’inversion temporelle (use: first, action: fail), l’inversion temporelle est détectée quand une variable est lue ou mise à jour dans la sous-transaction.

   Finalement avec toutes les garanties en place (use: first, action: fail), la vue de la transaction englobante est réutilisée. La version des variables de la sous-transaction est testée quand elles sont mises à jour.

   Note: Une variable versionnée est synchronisée avant d’être passée en paramètre à une fonction contenant potentiellement une transaction.

Les blocs sync conditionnels et emboîtés permettent la composition de transactions.

Partie 1 – Présentation
Partie 2 – Le passage de messages
Partie 3 – Les tâches et les variables partagées