Faculté des Sciences de Bizerte SI3 AU:2015-2016
Correction de TD7
Gestion des données et transactions réparties
Exercice1 : Propriétés des exécutions concurrentes
Le principe de recouvrabilité consiste à ne jamais annuler une transaction validée. Une solution aux annulations en cascade est de ne permettre la lecture de valeurs écrites que par des transactions déjà validées. Ceci assure aussi la recouvrabilité d’une exécution.
1. Une exécution recouvrable est une exécution qui évite l'annulation des transactions validées (respecte la règle de durabilité) Exemple: w1(x) r2(x) w2(x) C2 R1 L'annulation de T1 (R1) oblige l'annulation de T2 après que T2 soit validé (C2): Cette exécution est non recouvrable. Par contre l'exécution de w1(x) R1 r2(x) w2(x) C2 est recouvrable.
2. r1(s) r1(c1) w1(s) r2(s) r2(c2) w2(s) w2(c2) w1(c1) R1 Ici le Rollback de T1 intervient sans que T2 n'ait validé. Il faut alors impérativement que le système effectue également un Rollback de T2 pour assurer la cohérence de la base: On parle d'annulation en cascade.
ã Ì
3. r1(s) r1(c1)w1(s) r2(s) r2(c2) w2(s) w2(c2) w1(c1) R1 Ici il y'a y une " écriture sale" (dirty write). En effet T1 a validé après que T1 ait écrit dans s. Donc la validation de T1 enregistre la mise-à-jour de T2 alors que celle-ci s'apprête à annuler ses mises-à-jour par la suite. Au moment où T2 va annuler, le gestionnaire de transaction doit remettre la valeur du tuple s connue au début de la transaction: ce qui revient à annuler la mise-à-jour de T1
Publicité
Exercice 2 : Sérialisabilité et verrouillage à deux phases
1. Sérialisabilité: Critère permettant de dire que l'exécution d'un ensemble de transactions (schedule) est correcte. Une exécution d’un ensemble de transaction est dite sérialisable si elle donne pour chaque transaction participante, le même résultat que l’exécution en série de ces mêmes transactions. Une exécution sérialisable de transactions nous offre les bénéfices d'une exécution multitâche sans les inconvénients d'incohérence de données engendrés par ce type de traitement.
2. Le verrouillage à deux phases est une technique de prévention des conflits basée sur le blocage des objets par des verrous en lecture ou écriture avant d’effectuer une opération de sélection ou de mise à jour. En théorie, une transaction ne peut relâcher de verrous avant d’avoir obtenu tous ceux qui lui sont nécessaires, afin de garantir la correction du mécanisme.
3. Non-respect de la règle de relâchement des verrous: Soit les deux transactions suivantes: T1: r1(x) w1(y) C1 T2: w2(x) w2(y) C2
1 Wiem BEN ROMDHANE
Faculté des Sciences de Bizerte SI3 AU:2015-2016
et l'ordre d'exécution suivant: r1(x) w2(x) w2(y) C2 w1(y) C1. Supposons que l'exécution avec pose et relâchement de verrous soit la suivante:
rl1(x) r1(x) ru1(x) wl2(x) w2(x) wl2(y) w2(y) wu2(x) wu2(y) C2 wl1(y) w1(y) wu1(y) C1
wli(x) : verrou en écriture (write lock) rli(x) : verrou en lecture (real lock)
Publicité
T1 a relaché le verrou sur x puis en a repris un sur y. un "fenêtre" s'est ouverte qui a permis à T2 de poser des verrous sur x et y. Conséquence: l'exécution n'est plus sérialisable car T2 a écrit sur T1 pour x, et T1 a écrit sur T2 pour y (r1(x)< w2(x) et w2(y)< w1(y)). 3. i. w1(x) r2(x) w1(y) w2(y) w3(x) C3 w1(x) w1(x) w1(x) C1 C2: existence de cycle: exécution non sérialisable. ii. r1(x) w2(x) C2 w3(y) C3 r1(y) w1(z) C1: sans cycle: exécution sérialisable.
4. H1: r1(x) w2(x) C2 w3(y) C3 r1(y) w1(z) C1
r1(x) s'exécute w2(x) bloquée en attente de verrou sur x C2 bloqué, car T2 bloquée w3(y)et C3 s'exécutent r1(y) s'exécute w1(z) s'exécute C1 s'exécute et relâche les verrous sur T2 w2(x) C2 s'exécutent
H2: r1(x) r2(y) r3(x) r1(z) r1(u) w3(x) r1(y) r3(u) w2(y) C2 C1 w3(u) C3 r1(x) r2(y) s'exécutent en prenant des verrous de lecture r3(x) partage le verrou de lecture sur x avec r1(x) et s'exécute r1(z) r1(u) s'exécutent en prenant des verrous de lecture w3(x) bloquée par r1(x), donc T3 bloquée r1(y) partage le verrou de lecture sur y avec r2(y) et s'exécute r3(u)bloqué car T3 bloquée w2(y) bloquée par r1(y), donc T2 bloquée C2 bloquée car T2 bloquée C1 s'exécute et relâche les verrous de T1 w3(x) s'exécute r3(u) s'exécute w2(y) s'exécute C2 et relâche les verrous de T2 w3(u) et C3 s'exécutent
Exercice 3 : Estampillage
1. Le principal défaut du verrouillage à deux phases est d’autoriser des interblocages: Deux transactions concurrentes demandent chacune un verrou sur une ressource détenue par l’autre. Voici l’exemple type: Les deux transactions sont les suivantes : T1: r1(x) w1(y) C1 T2: r2(y) w2(x) C2
2 Wiem BEN ROMDHANE
Faculté des Sciences de Bizerte SI3 AU:2015-2016
Considérons maintenant que T1et T2 s'exécutent en concurrence dans le cadre d’un verrouillage à deux phases: rl1(x) r1(x) rl2(y) r2(y) wl1(y) T1 en attente wl2(x) T2 en attente T1 et T2 sont en attente l’une de l’autre: Il y a interblocage (deadlock).
Publicité
Cette situation ne peut pas être évitée et doit donc être gérée par le SGBD: En général ce dernier maintient un graphe d’attente des transactions et teste l’existence de cycles dans ce graphe. Si c’est le cas, c’est qu’il y a interblocage et une des transactions doit être annulée et ré-exécutée. Autre solution: tester le temps d’attente et annuler les transactions qui dépassent le temps limite. Notons que le problème vient d’un accès aux mêmes ressources, mais dans un ordre différent : il est donc bon, au moment où l’on écrit des programmes, d’essayer de normaliser l’ordre d’accès aux données.
2. C’est une méthode beaucoup plus simple qui consiste à fixer, a priori, l’ordre de sérialisabilité des transactions soumises au scheduler. Pour cela, on affecte à chaque transaction une estampille. Chaque valeur d’estampille est unique et les valeurs sont croissantes: on garantit ainsi un ordre total entre les transactions.
Chaque transaction reçoit une date de début (estampillage): Si une action ai de la transaction Ti est en conflit avec l’action aj de la transaction Tj et TS(Ti) > TS (Tj) alors Ti est abandonnée.
3. Sur l’exemple suivant : r1(s) w2(x) r3(x) r2(x) w1(x) en admettant que l’estampille est le numéro de la transaction, on rejette la transation T1, au moment de w1(x).
4. Méthode peu utilisée car elle entraîne des abandons inutiles de transactions, et le risque de privation : une transaction est toujours rejetée.
3 Wiem BEN ROMDHANE