Précédent Index

3  Concurrence et reprise sur pannes (6 points)

Les trois programmes suivants peuvent s'exécuter dans un système de gestion bancaire. Débit diminue le solde d'un compte (c) avec un montant donné (m). Pour simplifier, tout débit est permis (on accepte des découverts). Crédit augmente le solde d'un compte (c) avec un montant donné (m). Transfert transfère un montant (m) à partir d'un compte source (s) vers un compte destination (d). L'exécution de chaque programme démarre par un Start et se termine par un Commit (non montrés ci-dessous). 
Débit (c:Compte;     |    Crédit (c:Compte;     |    Transfert (s,d:Compte;
       m:Montant)    |            m:Montant)    |               m:Montant)
begin                |    begin                 |    begin
  t := Read(c);      |      t = Read(c);        |      Débit(s,m);
  Write(c,t-m);      |      Write(c,t+m);       |      Crédit(d,m);
end                  |    end                   |    end
Le système exécute en même temps les trois opérations suivantes: (1) un transfert de montant 100 du compte A vers le compte B, (2) un crédit de 200 pour le compte A, (3) un débit de 50 pour le compte B.

  1. (1 point) Écrire les transactions T1, T2 et T3 qui correspondent à ces opérations. Montrer que l'histoire H: r1[A] r3[B] w1[A] r2[A] w3[B] r1[B] c3 w2[A] c2 w1[B] c1 est une exécution concurrente de T1, T2 et T3.
    Solution:
    1 point: 0,5 points pour avoir écrit les transactions; 0,5 points pour avoir justifié que H est une exécution concurrente de T1, T2 et T3 Débit et Crédit sont constitués chacun d'une lecture, suivie d'une écriture. Dans ce cas, les transactions T1, T2 et T3 seront: T1: r1[A] w1[A] r1[B] w1[B] c1
    T2: r2[A] w2[A] c2
    T3: r3[B] w3[B] c3 L'histoire H contient toutes les opérations de T1, T2 et T3 et respecte l'ordre des opérations dans chaque transaction. Donc H est une exécution concurrente de T1, T2 et T3.

  2. (2 points) Mettre en évidence les conflits dans H et construire le graphe de sérialisation de cette histoire. H est-elle sérialisable? H est-elle recouvrable?
    Solution:
    2 points: 0,5 points pour les conflits; 0,5 points pour le graphe; 0,5 points pour justifier que H est sérialisable; 0,5 pour montrer que H n'est pas recouvrable Les conflits sur A: r1[A]-w2[A];w1[A]-r2[A]; w1[A]-w2[A]
    Les conflits sur B: r3[B]-w1[B]; w3[B]-r1[B]; w3[B]-w1[B] Le graphe de sérialisation SG(H): T3-> T1-> T2 H est sérialisable, car le graphe ne contient pas de cycle. H n'est pas recouvrable, car T2 lit A de T1 (après w1[A] on a r2[A]), mais T2 se termine avant T1. La même conclusion est obtenue en considérant la suite w3[B] r1[B].
  3. (3 points) Quelle est l'exécution H' obtenue à partir de H par verrouillage à deux phases (2 points)? On suppose que les verrous d'une transaction sont relâchés après le Commit de celle-ci. Une opération bloquée en attente d'un verrou bloque le reste de sa transaction. Au moment du relâchement des verrous, les opérations en attente sont exécutées en priorité.
    Si au début le compte A avait un solde de 100 et B de 50, quel sera le solde des deux comptes après la reprise si une panne intervient après l'exécution de w1[B] (1 point)?

    Solution:
    2 points: 1,5 points pour le verrouillage à deux phases; 0,5 points pour la reprise



    r1[A], r3[B] reçoivent les verrous de lecture et s'exécutent
    w1[A] obtient le verrou d'écriture sur A (déjà obtenu en lecture par T1) et s'exécute
    r2[A] bloquée en attente de verrou sur A => T2 bloquée
    w3[B] obtient le verrou d'écriture sur B (déjà obtenu en lecture par T3) et s'exécute
    r1[B] bloquée en attente de verrou sur B => T1 bloquée
    c3 s'exécute et relâche les verrous sur B => r1[B] débloquée, obtient le verrou et s'exécute (T1 débloquée)
    w2[A] et c2 bloquées car T2 bloquée
    w1[B] obtient le verrou et s'exécute
    c1 s'exécute et relâche les verrous sur A => r2[A], w2[A] et c2 s'exécutent Le résultat est H': r1[A] r3[B] w1[A] w3[B] c3 r1[B] w1[B] c1 r2[A] w2[A] c2 Si une panne intervient après l'exécution de w1[B], seule la transaction T3 (le débit de 50 sur B) est validée à ce moment. Après la reprise, seul l'effet de T3 sera retrouvé, donc le compte A aura un solde de 100 et B de 0.
Précédent Index