Cours de Bases de données

Si ~ a un verrou sur D Alors

Lire(D)

Sinon

Tant que il y a un transaction avec un verrou

X sur D Faire

Attendre

Fournir un verrous S a ~ sur D Lire(D)

Protocole avec estampillage~

j Acquisition des verrousi

Pour l'opération d'écriture

Si ~ a un verrou X sur D Alors Ecrire(D)

Sinon

Tant que il y a une transaction avec

un verrou sur D Faire

Si T'~ a déja un verrou S sur D Alors

Transformer S en X

Sinon

Fournir un verrou X sur D a ~ Ecrire(D)

Le but est d'avoir des ordonnancements sérialisables équivalents à l'ordre chronologique des transactions
e A chaque transaction est associée une estampille relative au moment où elle "arrive", i.e T'~ avant T, ~ ST'~) < ST(T,) (l'heure système ou bien un simpIe compteur)
e A chaque objet D de la base sont associées 2 estampilles

On ne dit pas quand est-ce que les verrous sont libérés !!

1. E~ST'(D) : la plus grande des estampilles des transactions qui ont écrit D avec succès

2. L~sT(D) : la plus grande des estampilles des transactions qui ont lu D avec succès
Protocole avec estampillage~

j Protocole avec estampillagel

Supposons que ~ veuille lire D

Si ST(T) > E~sT(D), alors la lecture est autorisée et

L~ST(D) l max{L~ST'(D),ST~)}

Supposons que ~ veuille écrire D
e Si TS~) < L~sT(D) : dans ce cas, cela veut dire qu'il y a une transaction qui est arrivée après T et qui a lu D. T est annulée
e Si TS(T) < E~sT'(D) si on laisse faire cette écriture, alors elle va "écraser" celle faite par une transaction arrivée après T T est annulée

 Si ST(T) < E~ST(D), alors T est "annulée" et relancée avec une nouvelle estampille
e Sinon,

- l'écriture est réalisée

- E~sT(D) ' ST(T)

j Protocole avec estampillage~

Soient les transactions T₁,T₂,T₃,T₄ et T₅ avec les estampilles resp. 1, 2, 3, 4 et 5.

L'ordonnancement suivant représente une situation où T₂ et T₄ sont annulées

T₁ T₂ T₃ T₄ T₅

Lire(X)

Lire(Y)

Lire(Y)

Lire(Y)

Ecrire(Y)

Lire(Z)

Ecrire(Z)

Lire(Z)

Lire(Z)

abort

Lire(X)

Ecrire(Z)

abort

Ecrire(X)
y____

___________________ Ecrire(Z)

j Protocole avec estampiIlage~

e L'estampillage permet d'éviter les blocages (les transactions sont exécutées ou bien annulées)

e Il garantit la c-sérialisabilité puisque tous les arcs sont de la forme T " T, avec ST(T)
e Par contre, le problème de récupérabilité persiste. Si T est annulée alors que T, a lu une valeur écrite par T~ alors T, doit aussi être annulée. Si T, a déja validé, alors l'ordonnancement n'est pas récupérable.
jProtocole basé sur la validationî
L'exécution d'une transaction T se fait en 3 phases

Lecture : Les écritures se font dur des "variables

locales"

Protocole basé sur la validationi

Pour faire le test de validité, nous avons besoin de savoir a quels moments ont lieu les différents phases. D'où l'utilisation d'estampilles

1. Début(T~): Le moment où T a débuté

Validation : Tester la validité des écritures (ne violent elles pas la sérialisabilité ?)
Ecriture : Si la validation réussit, alors les écritures sont retranscrites sur la base

Protocole basé sur la validationi

2. Validation(T~): Le moment où T a terminé sa phase précédente
3. Fin(T~): Le moment où T termine la phase d'écriture

La sérialisabilité est testée en se basant sur un estampillage des transactions correspondant a leur estampille de validation, i.e ST(T) = Validation(T).
Exemple d'ordonnancementl
La validation de T, réussit Si pour chaque T t.q

ST(T) ₁

Lire(B)
b Fin(T) < Débat(T,), ou bien
 Débat(T~) < Fin(T~ < validation(T,) et l'ensemble des données écrites par T est distinct de celui des données lues par T,
Pour le 2ème point:
 Les écritures de T n'ont pas d'effet sur les lectures de T~ (elles ont lieu après la fin des lectures de T)
 les écritures de T n'ont pas d'effet sur les lectures de T, (T, ne lit aucun objet écrit par T)

Lire(A)



Affieher(A + B)

T₂
Lire(E)

B := B - 50

Lire(A)

A := A + 50


Ecrire(E)

Ecrire(A)

Note: La méthode de validation permet d'éviter les cascades de Poli back puisque les lectures ne se font que sur des données persistantes.
Granularité du verrouiIIage~ Granulanté du verrouiIIage~

Nous considérons la hiérarchie suivante

 Nous sommes en présence d'une structure d'arbre de

la forme
Base

Table Table4 Table n

Page

{

Tuple
Permettre aux transactions de verrouiller n'importe quel niveau mais en respectant un nouveau protocole

Avant de verrouiller un objet D, T doit avoir un verrou intentionnel sur tous les ancêtres de D
___'[IPIXI P ]IX[PIXI

IP ~ oui oui oui ~f oui

IX ~ oui f oui ___ ~f ___

P oui __ oui ~

X ~_~_ _ __ PIX oui __ __ 113

49

Page Il Page tm

Tuptelti TupleII2
e Un noeud D peut être verrouillé en P ou IP Si le parent est déja verrouillé en IX ou

 D peut être verrouillé en X, PIX ou~ Si le parent de d est verrouillé en IX ou PIX

T peut libérer un verrou sur D si elle ne possède plus de verrous sur les descendants de D

La aussi, on utilise le verrouillage en deux phases

Gestion des bIocages~

Granularité du verrouiIIage~
Exemples

Prévenir vs guérir

1) Prévenir
T₁ parcourt R et met a jour quelques tuples

 T₁ obtient un verrou PIX sur R, a chaque lecture d'un tuple, elle pose d'abord un verrou P, et Si elle a besoin de le modifier, elle transforme le P en X

T₂ utilise un index pour lire une partie de R

 T₂ pose un verrou IP sur R, ensuite elle obtient des verrous P pour chaque tuple qu'elle veut lire

T₃ lit la table R en entier

Soit T qui demande un verrou en conflit avec celui déja détenu par T,
e Privilégier les plus anciennes transactions (estampillage):
- ST(T) < ST(T,) ~ T peut attendre T,

- ST(T) > ST(T,) ~ T est annulée
- Si T est relancée avec une nouvelle estampille, alors elle risque d'attendre longtemps!! La relancer avec la même estampille.
- Noter qu'ici, seules les transactions demandeuses sont annulés

e Privilégier la transaction qui détient le verrou

 T₃ demande un verrou sur R ou bien

- ST(T) est annulée

-ST(T) > ST(T,) alors T attend
Gestion des blocages

Prévenir vs guérir
1) Guérir

Gestion des blocages

Ici, il faut détecter le blocage. Le système maintient un graphe G (N, A) avec

Prévenir vs guérir

Que faire Si un blocage est détecté ?

N les transactions
 T ' T, 55 T attend que T, libère un verrou
 Quand T demande un verrou détenu par T,, alors l'arc T ' T, est r ajouté au graphe
Il faut annuler une transaction participant au cycle.
Choisir celle qui permet de réduire au maximum le nombre de cycles

 T ' T, est supprimé quand T, ne détient plus le verrou demandé par T

Choisir celle qui est la moins proche de son état de validation

 Le système est bloqué ssi G contient un cycle

 Un algorithme est lancé périodiquement pour tester 'acyclicité
Le problème
La suppression d'ùn tuple ne peut se faire que Si T détient un verrou X sur ce tuple

L'insertion d'un tuple par T, implique la détention d'un verrou X par T, sur ce tuple

T veut supprimer tous les comptes dont le solde est

> 300. Elle verrouille donc tous ces tuples.

T, insère un compte avec un solde > 400. Noter qu'il n'y a pas conflit.

 Ensuite, T affiche les comptes dont le solde est > 200. Le nouveau tuple est affiché.

Noter que cette exécution n'est pas équivalente a une exécution en série pourtant l'ordonnancement est c-sérialisable!!

Choisir une transaction qui n'a pas été annulée plusieurs fois