3  Concurrence (4 points)

1. (1 point) Trouvez les conflits dans H et montrez que H n'est pas sérialisable.
   
   Solution Conflits r₁[x]-w₃[x], w₃[x]-r₂[x], r₂[y]-w₁[y]
   Le graphe de sérialisation contient un cycle T₁ -> T₃ -> T₂ -> T₁, donc H n'est pas sérialisable.
   
   
2. (1 point) Trouvez l'exécution obtenue à partir de H par verrouillage à deux phases. On considère que les verrous d'une transaction sont relâchés au Commit et qu'à ce moment les opérations bloquées en attente de verrou sont exécutées en priorité (si elles peuvent recevoir le verrou attendu).
   
   Solution r₁[x] et r₂[y] s'exécutent
   r₃[x] s'exécute (pas de conflit avec r₁[x])
   w₃[x] est bloquée par r₁[x]
   w₁[y] est bloquée par r₂[y]
   r₂[x] s'exécute (pas de conflit avec r₁[x] ou avec r₃[x])
   c₁ est bloquée, car T₁ est bloquée (w₁[y] bloquée)
   c₂ s'exécute et relâche les verrous de r₂[y] et r₂[x]
   => w₁[y] et c₁ sont débloquées et exécutées
   => c₁ relâche les verrous de T₁
   => w₃[x] est débloquée et exécutée
   c₃ est exécutée Résultat: r₁[x] r₂[y] r₃[x] r₂[x] c₂ w₁[y] c₁ w₃[x] c₃
   
   
3. (1 point) Le raisonnement suivant mène à une conclusion paradoxale. Considérons une histoire quelconque H non-sérialisable, traitée par verrouillage à deux phases. H contient donc un cycle dans son graphe de sérialisation. Chaque arc T_i -> T_j de ce cycle provient d'une paire d'opérations conflictuelles de type a_i[x] avant b_j[x]. Quand a_i[x] s'exécute, elle prend le verrou sur x, ce qui bloquera b_j[x]. Donc T_i bloque T_j, mais comme les arcs forment un cycle, il y aura un blocage circulaire, donc un interblocage. Conclusion: toute histoire non-sérialisable traitée par verrouillage à deux phases produit un interblocage! Cependant, l'exemple précedent montre que cette conclusion est fausse, car H n'est pas sérialisable et elle ne produit pas d'interblocage. Expliquez pourquoi il n'y a pas d'interblocage et pourquoi le raisonnement ci-dessus est faux. Solution Parmi les 3 conflits, r₁[x] bloque w₃[x], r₂[y] bloque w₁[y], mais w₃[x] ne bloque pas r₂[x], car w₃[x] est elle-même bloquée (et donc ne prend pas de verrou).
   Donc dans le couple a_i[x]-b_j[x], a_i[x] peut ne pas bloquer b_j[x] si elle-même est déjà bloquée.
   
   
4. (1 point) Montrez que H n'évite pas les annulations en cascade. Montrez qu'avec un autre placement des Commit, H peut éviter les annulations en cascade.
   
   Solution r₂[x] a lieu après w₃[x] (T₂ lit x de T₃) avant que T₃ se termine, donc H n'évite pas les annulations en cascade. On peut éviter les annulations en cascade en plaçant c₃ avant r₂[x], ce qui est possible, car la dernière opération de T₃ est avant r₂[x].