Précédent Remonter

Chapitre 10  Concurrence

10.1  Sérialisabilité et recouvrabilité

10.1.1  Graphe de sérialisation et équivalence des exécutions

Construisez les graphes de sérialisation pour les exécutions (histoires) suivantes. Indiquez les exécutions sérialisables et vérifiez s'il y a des exécutions équivalentes.
  1. H1:w2[x] w3[z] w2[y] c2 r1[x] w1[z] c1 r3[y] c3

  2. H2:r1[x] w2[y] r3[y] w3[z] c3 w1[z] c1 w2[x] c2

  3. H3:w3[z] w1[z] w2[y] w2[x] c2 r3[y] c3 r1[x] c1
  1. H1: les conflits
    sur x: w2[x] r1[x];  sur y: w2[y] r3[y];  sur z: w3[z] w1[z]

    le graphe de sérialisation
    (50,15) (0,10)T1 (20,10)T2 (40,10)T3 (18,11)(-1,0)13 (25,11)(1,0)13 (42,8)(0,-1)6 (42,2)(-1,0)40 (2,2)(0,1)6

  2. H2: les conflits
    sur x: r1[x] w2[x];  sur y: w2[y] r3[y];  sur z: w3[z] w1[z]

    le graphe de sérialisation
    (50,15) (0,10)T1 (20,10)T2 (40,10)T3 (5,11)(1,0)13 (25,11)(1,0)13 (42,8)(0,-1)6 (42,2)(-1,0)40 (2,2)(0,1)6

  3. H3: les conflits
    sur x: w2[x] r1[x];  sur y: w2[y] r3[y];  sur z: w3[z] w1[z]

    le graphe de sérialisation
    (50,15) (0,10)T1 (20,10)T2 (40,10)T3 (18,11)(-1,0)13 (25,11)(1,0)13 (42,8)(0,-1)6 (42,2)(-1,0)40 (2,2)(0,1)6
Conclusion: H1¬ identique àH3,  H1 et H3 sérialisables,

Les histoires H1 et H3 ne sont pas équivalentes. Pour avoir équivalence, deux conditions sont nécessaires: (i) avoir les mêmes transactions et les mêmes operations, et (ii) avoir le meme ordre des operations conflictuelles.

Ici la seconde condition est remplie, mais pas la premiere! En effet, si on extrait la transaction T1 de ces histoires, on remarque que pour H1 on a T1 = r1[x] w1[z] c1, tandis que pour H3, T1 = w1[z] r1[x] c1. Et c'est pareil pour T2.

10.1.2  Recouvrabilité

Parmi les exécutions (histoires) suivantes, lesquelles sont recouvrables, lesquelles évitent les annulations en cascade et lesquelles sont strictes? Indiquez s'il y a des exécutions sérialisables.
  1. H1:r1[x] w2[y] r1[y] w1[x] c1 r2[x] w2[x] c2

    T1 lit y de T2 (r1[y] après w2[y]), mais T1 se termine avant T2 ==> H1 non-recouvrable

    H1 n'est pas sérialisable (les conflits w2[y] - r1[y] et w1[x] - r2[x] forment un cycle)
  2. H2:r1[x] w1[y] r2[y] c1 w2[x] c2

    T2 lit y de T1 (r2[y] après w1[y]) avant que T1 se termine ==> H2 recouvrable, mais n'évite pas les avortements en cascade

    H2 est sérialisable (les seuls conflits sont r1[x] - w2[x] et w1[y] - r2[y])
  3. H3:r1[y] w2[x] r2[y] w1[x] c2 r1[x] c1

    T1 lit x de T2 (r1[x] après w2[x]) après la fin de T2, mais écrit x (w1[x] après w2[x]) avant la fin de T2 ==> H3 évite les annulations en cascade, mais n'est pas stricte

    H3 est sérialisable (les seuls conflits sont w2[x] - w1[x] et w2[x] - r1[x])

10.2  Contrôle de concurrence

10.2.1  Verrouillage à 2 phases

Un scheduler avec verrouillage à 2 phases reçoit la séquence d'opérations ci-dessous.

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

Indiquez l'ordre d'exécution établi par le scheduler, en considérant qu'une opération bloquée en attente d'un verrou est exécutée en priorité dès que le verrou devient disponible. On suppose que les verrous d'une transaction sont relâchés au moment du Commit.

¤ r1[x], r2[y] exécutées

¤ w3[x] bloquée à cause de r1[x]

¤ w1[y] bloquée à cause de r2[y]

L'opération w1[y] qui est bloquée va aussi bloquer tout le reste de la transaction T1! Donc w1[x] ne peut pas s'exécuter, même si cette opération n'a pas de problème de verrou :

¤ w1[x] bloquée à cause de w1[y]

¤ w2[y] exécutée

¤ c2 relâche les verrous sur y => w1[y], w1[x] peuvent s'exécuter

¤ r3[y] bloquée car T3 bloquée à cause de w3[x]

¤ r1[y] exécutée

¤ c1 relâche les verrous sur x, y => w3[x], r3[y] peuvent s'exécuter

¤ w3[y], c3 exécutées

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

10.2.2  Estampillage et la règle de Thomas

Etant donée la séquence d'opérations suivante, comparez les exécutions établies par un scheduler avec estampillage simple et un scheduler intégré pur utilisant la règle de Thomas. Le scheduler avec estampillage n'utilise que le test des estampilles, sans retarder ensuite l'exécution des opérations. Considérez qu'une transaction rejetée est relancée tout de suite avec une nouvelle estampille et que ses opérations déjà exécutées sont traitées avec priorité.

H:r1[x] r2[y] w3[x] w1[x] w3[y] w2[y]

Estampillage:

¤ r1[x], r2[y], w3[x] exécutées

¤ w1[x] rejetée à cause de w3[x] => T1 rejetée et relancée en tant que T4 => r4[x], w4[x] exécutées

¤ w3[y] exécutée

¤ w2[y] rejetée à cause de w3[y] => T2 rejetée et relancée en tant que T5 => r5[y], w5[y] exécutées

Résultat: r1[x] r2[y] w3[x] a1 r4[x] w4[x] w3[y] a2 r5[y] w5[y]

Scheduler intégré avec la règle de Thomas:

¤ r1[x], r2[y], w3[x] exécutées

¤ w1[x] ignorée à cause de w3[x] (règle de Thomas)

¤ w3[y] exécutée

¤ w2[y] ignorée à cause de w3[y] (règle de Thomas)

Résultat: r1[x] r2[y] w3[x] w3[y]

10.2.3  Comparaison des méthodes de contrôle de concurrence

Parmi les exécutions suivantes, lesquelles ne peuvent pas être obtenues par verrouillage à 2 phases et lesquelles ne peuvent pas être obtenues par estampillage simple?

H1:r1[x] r2[y] w2[x] c2 r1[y] c1 verrouillage: impossible, car pour exécuter w2[x],T1 doit relâcher le verrou obtenu par r1[x], donc ne pourra plus obtenir le verrou pour r1[y]

estampillage: possible

H2:r1[x] w2[y] r2[x] c2 w1[y] c1 verrouillage: possible

estampillage: impossible, car w1[y] rejetée à cause de w2[y]

10.3  Reprise après panne

10.3.1  Journalisation

Soit le journal physique ci-dessous, dans lequel on a marqué les opérations Commit et Abort réalisées:

[T1,x,3], [T2,y,1], [T1,z,2], c1, [T2,z,4], [T3,x,2], a2, [T4,y,3], c3, [T5,x,5]
  1. Indiquez le contenu de liste_commit, liste_abort, liste_active.

    liste_commit = {T1, T3}; liste_abort = {T2}; liste_active = {T4, T5};

  2. En supposant qu'une nouvelle écriture vient de s'ajouter au journal, lesquelles des écritures suivantes sont compatibles avec une exécution stricte: [T5,y,4], [T4,z,3] ou [T6,x,1]?

    [T5,y,4] écrit y; y déjà écrit par T4 (encore active) => exécution non-stricte

    [T4,z,3] écrit z; z déjà écrit par T1 et T2, déjà terminées => exécution stricte

    [T6,x,1] écrit x; x déjà écrit par T5 (encore active) => exécution non-stricte

  3. Quelles sont les entrées récupérables par l'algorithme de ramasse-miettes?

    [T2,y,1], [T2,z,4] récupérables, car T2 rejetée

    [T1,x,3] récupérable, car T3 validée a écrit ensuite x

  4. Si les valeurs initiales des enregistrements étaient x=1, y=2,z=3, et si une panne survenait à ce moment, quelles seraient les valeurs restaurées pour x, y et z après la reprise?

    T3 est la dernière transaction validée à avoir écrit dans x ([T3,x,2]), donc la valeur restaurée est x=2.

    Aucune transaction validée n'a écrit dans y, donc la valeur restaurée est y=2, valeur initiale.

    T1 est la dernière transaction validée à avoir écrit dans z ([T1,z,2]), donc la valeur restaurée est z=2.

10.4  Concurrence: Gestion Bancaire

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. É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.

    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: 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. 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?

    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. Quelle est l'exécution H' obtenue à partir de H par verrouillage à deux phases? 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]?

    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 Remonter