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 dune 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.
Publicité
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
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 dun ensemble de transaction est dite s rialisable si elle donne pour chaque
transaction participante, le m me r sultat que lex 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 deffectuer une op ration de
s lection ou de mise jour.
En th orie, une transaction ne peut rel cher de verrous avant davoir 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
Publicité
wli(x) : verrou en criture (write lock)
rli(x) : verrou en lecture (real lock)
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
Publicité
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 dautoriser des interblocages: Deux
transactions concurrentes demandent chacune un verrou sur une ressource d tenue par lautre.
Voici lexemple 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 dun
verrouillage deux phases:
Publicité
rl1(x) r1(x) rl2(y) r2(y) wl1(y) T1 en attente wl2(x) T2 en attente
T1 et T2 sont en attente lune de lautre: Il y a interblocage (deadlock).
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 dattente des transactions et teste lexistence de cycles dans ce
graphe. Si cest le cas, cest quil y a interblocage et une des transactions doit tre annul e et
r -ex cut e. Autre solution: tester le temps dattente et annuler les transactions qui d passent
le temps limite. Notons que le probl me vient dun acc s aux m mes ressources, mais dans un
ordre diff rent : il est donc bon, au moment o lon crit des programmes, dessayer de
normaliser lordre dacc s aux donn es.
2. Cest une m thode beaucoup plus simple qui consiste fixer, a priori, lordre de
s rialisabilit des transactions soumises au scheduler. Pour cela, on affecte chaque
transaction une estampille. Chaque valeur destampille 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 laction aj de la transaction Tj et TS(Ti) > TS (Tj) alors Ti est abandonn e.
3. Sur lexemple suivant : r1(s) w2(x) r3(x) r2(x) w1(x)
en admettant que lestampille 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