close

Se connecter

Se connecter avec OpenID

Accès simultané

IntégréTéléchargement
Contrôle de l’Accès Simultané
Chapitre 17
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
1
Plans Sérialisables par Rapport aux Conflits

Deux actions sont en conflit si
 elles opèrent sur le même élément de la BD,
 elles appartiennent à différentes transactions,
 une d’elles au moins est une action d’écriture.

Deux plans sont équivalents par rapport aux conflits si:




Ils contiennent les mêmes actions des mêmes transactions.
Chaque pair d’actions conflictuelles est ordonnée de la même
manière dans les deux plans.
Un plan S est sérialisable par rapport aux conflits ssi S est
équivalent par rapport aux conflits à un (quelconque) plan
séquentiel (sériel).
Rappel:
 plan sérialisable
 plan recouvrable
 plan évitant les abandons en cascade
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
2
Exemple

Le plan suivant n’est pas sérialisable p.r. conflits:
T1:
T2:
R(A), W(A),
R(A), W(A), R(B), W(B)
R(B), W(B)
A
T1
T2
Graphe de dépendance
B

Le cycle dans ce graphe révèle le problème. Le
résultat de T1 dépend de T2 et vice-versa.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
3
Graphe de Dépendance

Graphe de dépendance (précédence): contient
 un nœud par Xact;
 une arête de Ti à Tj si une action de Ti précède et
entre en conflit avec une action de Tj.

Théorème: Un plan est sérialisable p.r. conflits si
et seulement si son graphe de dépendance est
acyclique.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
4
2PL Strict: Rappel

Protocole ‘’Strict Two-phase Locking’’ (‘’Strict 2PL’’):




Chaque Xact doit obtenir un verrou (partagé) du genre S
sur un objet avant de le lire, et un verrou (exclusif) du
genre X sur un objet avant de le lire.
Tous les verrous sont retenus par une Xact jusqu’à sa fin
complète.
Si une Xact retient un verrou X sur objet, aucune autre
Xact ne peut obtenir un verrou sur cet objet.
2PL strict ne permet que des plans dont le graphe
de dépendance est acyclique.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
5
2PL

Protocole ‘’Two-phase Locking’’ (‘’2PL’’):




Chaque Xact doit obtenir un verrou (partagé) du genre S
sur un objet avant de le lire, et un verrou (exclusif) du
genre X sur un objet avant de le lire.
Aucune Xact ne peut obtenir de verrous supplémentaires
après qu’elle ait relâché un verrou.
Si une Xact retient un verrou X sur objet, aucune autre
Xact ne peut obtenir un verrou sur cet objet.
2PL permet des plans non recouvrables.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
6
Gestion des Verrous



Les requêtes pour verrouiller/déverrouiller sont traitées
par le ‘’lock manager’’.
Le lock manager maintient une table des verrous, i.e. une
table de hachage avec l’identité de l’objet de la base de
données comme clé.
Une entrée dans la table des verrous contient au moins:






# de Xacts présentement verrouillant un objet
Type de verrous (S ou X)
Pointeur vers la queue des requêtes des verrous
Verrouiller et déverrouiller doivent être des opérations
atomiques.
Promouvoir un verrou: transformer un verrou S en un
verrou X.
Rétrograder un verrou: transformer un verrou X en un
verrou S. Cette approche est la plus répandue dans les
systèmes commerciaux.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
7
Interblockages (‘’Deadlocks’’)
Interblockage: Cycle des transactions
attendant que d’autres transactions leur
passent des verrous sur un objet donnée.
 Deux voies de solutions classiques pour
traiter les interblockages sont:



prévention
détection
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
8
Prévention des Interblockages


Assigner des priorités basées sur des estampilles
(‘’timestamps’’); l’estampille la plus petite a la plus
grande priorité: i.e. les vieilles Xacts ont priorité sur les
plus jeunes.
Supposez que Ti veut un verrou retenu par Tj. Deux
polices sont possibles à ce sujet:




‘’Wait-Die’’: Si Ti a une plus grande priorité, Ti attend que Tj
finisse; sinon Ti est abandonnée et recommencée
‘’Wound-wait’’: Si Ti a une plus grande priorité, Tj est
abandonnée et recommencée; sinon Ti attend
Si une transaction recommence, elle doit reprendre son
estampille initiale.
La prévention est aussi possible en utilisant un 2PL
conservateur: chaque Xact obtient à l’avance tous les
verrous dont elle pourrait avoir besoin.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
9
Détection des Interblockages

Créer un graphe ‘’waits-for’’:



Les nœuds sont des transactions
Il y a une arête allant de Ti à Tj si Ti est entrain
d’attendre que Tj relâche un verrou
Ensuite vérifier périodiquement s’il n’y a pas
de cycles dans le graphe ‘’waits-for’’.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
10
Détection des Interblockages (Suite)
Exemple:
T1: S(A), R(A),
S(B)
T2:
X(B),W(B)
X(C)
T3:
S(C), R(C)
X(A)
T4:
X(B)
T1
T2
T1
T2
T4
T3
T3
T3
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
11
Contrôle d’Accès Simultané Optimiste


Le verrouillage est une approche conservatrice et
pessimiste dans laquelle on prévient les conflits.
Desavantages:
 Coût de la gestion des verrous
 Détection/résolution des interblockages
 Congestion pour les objets très utilisés
Si les conflits sont plutôt rares, on pourrait gagner en
accès simultané en évitant de verrouiller les objets, mais
plutôt en vérifiant la présence des conflits avant que les
Xacts ne soient validées.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
12
Le Modèle de Kung-Robinson

Dans un protocole optimiste, les Xacts ont trois
phases:
 LECTURE: Les Xacts lisent les données de la
base de données, mais procèdent aux
changements sur des copies privées des
données lues.
 VALIDATION: Chercher les conflits.
 ECRITURE: Les copies locales modifiées par les
Xacts validées sont rendues publiques.
ROOT
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
13
Accès Simultané à Base d’Estampilles

Idée: Donner à chaque objet une estampille
de lecture (RTS), une estampille d’écriture
(WTS), ainsi qu’une estampille de base (TS)
au moment où elle commence:
 Si l’action ai d’une Xact Ti est en conflit
avec une action aj d’une autre Xact Tj, et
TS(Ti) < TS(Tj), alors ai doit être exécutée
avant aj. Sinon, recommencer toute Xact
qui violerait cet ordre.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
14
Lorsque une Xact T veut Lire un Objet O

Si TS(T) < WTS(O), cela viole l’ordre des estampilles
par rapport à la Xact qui a écrit O.
 Ainsi if faut abandonner T et la recommencer avec une
nouvelle et plus grande estampille TS. (Si T est
recommencé avec la même TS, T échouera à nouveau!)
Si TS(T) > WTS(O):
 Permettre à T de lire O.
 RTS(O) devient max(RTS(O), TS(T))
 Les changements faits sur RTS(O) lors des lectures
doivent être écrits sur disque! Cela entraîne des
coûts (de même que les incessants
recommencements des Xacts).

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
15
Lorsqu’une Xact T veut Écrire un Objet O


Si TS(T) < RTS(O), cela viole l’ordre des estampilles par
rapport à la Xact qui a écrit O. D’où T est abandonnée
puis recommencée.
Si TS(T) < WTS(O), cela viole l’ordre des estampilles par
rapport à la Xact qui a écrit O. (Abandonner T ou
appliquer la règle de Thomas)
 Règle d’écriture de Thomas: On peut ignorer de telles
modifications périmées ; pas besoin de recommencer T! (la
modification faite par T est effectivement suivie par une autre
sans lectures intercalées.) Ceci permet quelques plans
sérialisables mais pas sérialisables par rapport aux conflits:

Sinon, permettre à T d’écrire O
et WST(O) prend la même
valeur que TS(T).
T1
R(A)
T2
W(A)
Commit
W(A)
Commit
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
16
Estampilles vs.Recouvrabilité

Malheureusement, les estampilles
permettent des plans nonrecouvrables:

La méthode des estampilles peut être
modifiée afin de permettre seulement
des plans recouvrables; 2 stratégies sont possibles:
 Stocker toute écriture en tampon jusqu’à la validation
de la Xact qui écrit (Mais mettre à jour la WTS(O)
lorsque l’écriture est permise.)
 Bloquer toute Xact T qui lit (où TS(T) > WTS(O)) jusqu’à
ce que la Xact qui écrit O soit validée.
Similitude avec 2PL: les Xacts qui lisent ne relâchent les
verrous qu’après validation.

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
17
Résumé
Plusieurs méthodes de contrôle d’accès
simultané basées sur le verrouillage existent
(Strict 2PL, 2PL). Le graphe de dépendance
permet de détecter les conflits entre Xacts.
 Le lock manager gère les verrous sur les
objets. Les interblockages peuvent soit être
prévenus ou détectés.

Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
18
Résumé (Suite)




Le contrôle d’accès simultané optimiste vise à minimaliser
les coûts d’un tels accès dans un environnement dit
optimiste dans lequel les lectures sont répandues et les
écritures plutôt rares.
Le contrôle optimiste engendre cependant d’autres coûts;
beaucoup de systèmes commerciaux utilisent le
verrouillage.
Les estampilles sont une autre alternative à 2PL; elles
permettent certains plans sérialisables que 2PL ne
permettent pas.
La recouvrabilité avec les estampilles est similaire au
traitement des écritures dans 2PL.
Database Management Systems 3ed, R. Ramakrishnan and J. Gehrke
19
Auteur
Документ
Catégorie
Без категории
Affichages
5
Taille du fichier
150 Кб
Étiquettes
1/--Pages
signaler