Précédent Index

3   Concurrence (4 points)

Soit l'exécution concurrente suivante de trois transactions dans un SGBD.

H: r1[x] r2[x] r3[y] w1[x] w1[z] r3[z] c1 w2[z] c2 w3[y] c3

  1. (1 pt) Vérifiez si H est sérialisable, en trouvant les conflits et en construisant son graphe de sérialisation.

    Solution: Conflits :

    sur     x: r2[x] - w1[x]
    sur     y: rien
    sur     z: w1[z] - r3[z], w1[z] - w2[z], r3[z] - w2[z]

    Graphe de sérialisation: T    1 ¾® T3 ¾® T2 ¬¾ T1

    Il y a deux cycles, donc H n'est pas sérialisable.

  2. (1 pt) L'exécution H est-elle stricte? Sinon, est-il possible de modifier juste l'emplacement des Commit afin que H devienne stricte?

    Solution: L'exécution n'est pas stricte, car elle n'évite pas les annulations en cascade (T3 lit z de T1 avant que T1 soit validée). Si on déplace c1 juste après w1[z], alors les annulations en cascade sont évités et en plus l'écriture w2[z] se fait après la validation de T1 qui écrit aussi z. Donc, dans ce cas, H devient stricte.

  3. (1,5 pt) Quelle est l'exécution obtenue par verrouillage à deux phases à partir de H?
    On considère que le relâchement des verrous d'une transaction se fait au Commit et qu'à ce moment on exécute en priorité les opérations bloquées en attente de verrou, dans l'ordre de leur blocage.

    Solution: r1[x] s'exécute
    r    2[x] s'exécute aussi, car on peut partager le verrou de lecture
    r    3[y] s'exécute
    w    1[x] est bloquée par r2[x]
    w    1[z] est bloquée, car T1 est bloquée
    r    3[z] s'exécute
    c    1 est bloquée, car T1 est bloquée
    w    2[z] est bloquée par r3[z]
    c    2 est bloquée, car T2 est bloquée
    w    3[y] s'exécute
    c    3 s'exécute et relâche les verrous de T3 Þ w2[z] peut s'exécuter et c2 aussi, qui relâche les verrous de T2 Þ w1[x], w1[z] et c1 s'exécutent

    Résultat: r    1[x] r2[x] r3[y] r3[z] w3[y] c3 w2[z] c2 w1[x] w1[z] c1

  4. (0,5 pt) L'exécution H produit-elle des annulations quand elle est traitée par un contrôleur intégré avec estampillage et la règle de Thomas? Justifiez votre réponse, mais sans produire tout le résultat donné par le contrôleur intégré.

    Solution: Oui, H produit des annulations, car on retrouve r2[x] suivi de w1[x], donc un conflit lecture-écriture avec arrivée en retard de w1[x] Þ rejet de w1[x] même par un contrôleur intégré.
Précédent Index