Précédent Index

3   Concurrence (6 points)

Soit l'exécution concurrente suivante de trois transactions dans le SGBD d'un système bancaire.

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

  1. (1,5 pt) Parmi les opérations programmées dans le système, il y a les deux suivantes:
    O1: calcul de la somme entre le solde du compte courant et celui du CODEVI d'un client et enregistrement du résultat dans la base de données.
    O2: crédit du compte d'un client et enregistrement de l'opération dans la base de données.

    Montrez que parmi les transactions de H, il y en a qui peuvent correspondre à O1 et O2. Peut-on dire que dans H apparaît une exécution concurrente des deux opérations?

    Solution: O1: lecture compte courant, lecture CODEVI, écriture somme
    O2: lecture et écriture compte, écriture opération

    T    1 : r1[x] w1[y] w1[x] c1
    T    2 : r2[y] w2[z] c2
    T    3 : r3[y] r3[x] w3[z] c3

    T1 est compatible avec O2 et T3 avec O1. Par contre, on ne peut pas dire que H contient une exécution concurrente de O1 et O2, car y dans T1 correspond à un enregistrement d'opération bancaire, tandis que dans T3 il est un compte client.

  2. (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: w1[x] - r3[x]
    sur     y: r2[y] - w1[y], w1[y] - r3[y]
    sur     z: w2[z] - w3[z]

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

    Pas de cycle, donc H est sérialisable.

  3. (1 pt) L'exécution H évite-t-elle les annulations en cascade? Sinon, est-il possible de modifier juste l'emplacement des Commit afin que H évite les annulations en cascade?

    Solution: H n'évite pas les annulations en cascade, car T3 lit y de T1 avant que T1 soit validée. L'autre lecture (T3 lit x de T1) se fait après la validation de T1.

    Il suffirrait, pour éviter les annulations en cascade, de placer le     Commit de T1 avant la lecture r3[y]. Mais cela n'est pas possible, car T1 a d'autres opérations après r3[y]. Donc, il n'est pas possible de déplacer juste les Commit pour éviter les annulations en cascade.

  4. (1 pt) On sait que la position des Commit dans une exécution n'a pas d'influence sur sa sérialisabilité, car seuls les conflits comptent dans ce cas. Est-ce que l'algorithme de verrouillage à deux phases est-il également insensible à la position des Commit dans l'exécution? Justifiez votre réponse.

    Solution: Non, l'algorithme de verrouillage à deux phases est sensible à la position des Commit, car le relâchement de verrous se fait à ce moment-là seulement. Donc trop retarder le Commit produira probablement des interblocages.

  5. (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], r2[y] s'exécutent
    w    1[y] bloquée par r2[y]
    r    3[y] s'exécute, car le verrou de lecture sur y peut être partagé
    w    2[z] s'exécute
    w    1[x] bloquée, car T1 bloquée
    c    1 bloquée, car T1 bloquée
    r    3[x] s'exécute, car le verrou de lecture sur x peut être partagé
    c    2 s'exécute et les verrous de T2 sont relâchés. Par contre, w1[y] ne peut pas être débloquée, car le verrou de lecture sur y et detenu par T3
    w    3[z] s'exécute, car le verrou sur z a été relâché par T2
    c    3 s'exécute et tous les verrous de T3 sont relâchés ® toutes les opérations bloquées peuvent s'exécuter
    w    1[y], w1[x], c1 s'exécutent

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