XVIII.EXECUTIONS CONCURRENTES
Plusieurs transactions peuvent être exécutées en concurrence pour :
une meilleure utilisation du processeur (une transaction peut utiliser le processeur pendant qu'une autre accède au disque)
la réduction du temps de réponse aux transactions (une transaction courte n'a pas à attendre la fin d'une longue transaction)
Le contrôle de la concurrence est un mécanisme permettant l'interaction entre transactions tout en assurant l'intégrité de la base.
3.1) Ordonnancement
En anglais : Schedule. En fait, c’est une séquence chronologique spécifiant l'ordre d'exécution d'opérations de plusieurs transactions.
Exemple
T1
|
T2
|
Lire(A)
|
|
A := A - 1000
|
|
Ecrire(A)
|
|
Lire(B)
|
|
B := B + 1000
|
|
Ecrire(B)
|
|
|
Lire(A)
|
|
Temp := A * 0,1
|
|
Ecrire(A)
|
|
A := A - Temp
|
|
Ecrire(A)
|
|
Lire(B)
|
|
B := B + Temp
|
|
Ecrire(B)
|
C'est un ordonnancement "en série" de T1 et T2. On l'appellera O1.
L' ordonnancement 03 représente une exécution "entrelacée" de T1 et T2. Il est équivalent a 1,T2>.
j Sérialisabilité I
Dans la suite, on ne va considérer que les opéra-
L'ordonnancement suivant (04) ne préserve pas la valeur de A + B.
T1
T2
tions de lecture et d'écriture.
e Hypothèse Chaque transaction prise a part préserve la cohérence de la base.
LireÇA)
A := A - 1000
Ecrire(A)
Lire(B)
B := B + 1000
Ecrire(B)
Lire (A)
Temp A * 0, 1
A := A - Temp
Ecrire(A)
Lire(B)
e Ainsi, l'exécution en série préserve la cohérence.
Un ordonnancement entrelacé est sérialisable s'il est équivalent a un ordonnancement en série.
Difrérentes définitions d'équivalence
B := B + Temp - c-sérialisabilité (Sérialisabilité de conflit)
Ecrire(B)
- v-sérialisabilité (Sérialisabilité de vue)
I c-sérialisabilité I
Les instructions f~ et des transactions T~ et Tj sont en conflit s'il existe un objet Q accédé par t~ et et l'une d'elles écrit Q. Si t~ Lire(Q) et = Lire(Q) alors il n'y a pas de conflit.
Si un ordonnancement O peut être transformé en 0' par une série de remplacements (swaps) d'instructions non conflictuelles, alors O et 0' sont c-équivalents.
I c-sérialisabîlité I
L'ordonnancement 03 ci-dessous peut être trans formé en O~. Il est donc c-sérialisable.
T1 T2
Lire(A)
O est c-sérialisable s'il est c-équivalent a un ordon Ecrire(A)
nancement en série. Lire(A)
Eerire(A)
lire(B)
b L'ordonnancement ci-dessous n'est pas Ecrire(B)
lire(B)
c-séria lisable
Bcrire(B)
T3 1T4
Lire(Q)
Ecrire(Q)
Bcrire(Q)
j v-sérialisabilité
j v-sérialisabilité I
O et O' sont "v-équivalents en vue" Si
Pour chaque objet Q, Si dans O, ~ lit la valeur initiale de Q alors ~ lit la valeur initiale de Q dans O'.
Pour chaque Q, Si dans O, ~ lit une valeur de Q
produite par ~, alors dans O', cette lecture doit aussi
correspondre a une valeur produite par ~.
Pour chaque Q, Si dans O, ~ est la dernière a exé cuter Ecrire(Q), alors elle est aussi la dernière a l'exécuter dans O'.
e O est v-sérialisable s'il est v-équivalent â un ordon nancement en série
e Chaque ordonnancement c-sérialisable est v-sérialisable
L'ordonnancement suivant est v-sérialisable
T5 jT6 jT7
Lire(Q)
Ecrire(Q)
Ecrire(Q)
Ecrire(Q)
Il est v-équivalent a 6,T7>
e Si O est v-sérialisable et non c-sérialisable, alors il contient des mises a jour sans ef~t
j Autres notions de sérialisabilité i
L'ordonnancement ci-dessous est équivalent a pourtant il n'est ni v-sérialisable ni c-sérialisable
T1
Lire(A>
A := A - 1000
Ecrire(A)
Lire(B)
B := B + 1000
Ecrire(B)
T
Lire(B)
B := B - 10
Ecrire(B)
Lire(A)
A A + 10
Ecrire(A)
Reprise sur panne. Récupérabilitél
e Ordonnancement récupérable Si T~ lit un objet précédemment écrit par Tj alors la validation de T, a lieu avant la validation de T'~
L'ordonnancement suivant n'est pas récupérable Si T9 valide tout de suite après la lecture
T8 jT9
Lire(A)
Eerire(A)
Lire(A)
Ecrire(B)
Si T8 doit être avortée, alors T9 aura lu une valeur qui peut être "incohérente"
Pour déterminer ce type d'équivalence, il faut anal yser des opérations autres que Lire et Ecrire.
Le SGBD doit s'assurer que les ordonnancements soient récupérables.
Récupérabilité (suite)
L'echec d'une transaction peut conduire a l'avortement de plusieurs transactions
T,.
T10 T11 T12
Lire(A)
Lire(B)
Ecrire(A)
Lire(A)
Ecrire(A)
Lire(A)
Si T10 échoue, alors T11 et T12 doivent être avortées.
Récupéra bilité (suite) I
e Ordonnancement sans cascade : Si pour chaque paire ~ T, t q T, lit une donnée précédemment écrite par ~, alors la validation de T~ a lieu avant celle de
e Un ordonnancement sans cascade de roîl back est récupérable.
e Il est souhaitable de restreindre les ordonnancements a ce ceux qui sont sans cascade
Implémentation de l'isolationI
Les ordonnancements devraient être
v- ou c-sérialisables, récupérables pour garder la co hérence de la base et de préférence sans cascade.
Si l'on autorise que les ordonnancements en série, alors toutes les propriétés sont garanties.
Faire la balance entre le taux de concurrence et le traitement en plus qui s'y greffe.
Définition des transactions en SQLI
Dans SQL, une transaction commence implicite ment.
Une transaction se termine soit par l'exécution d'unE commande COMMIT (ou COMMIT WORK) soit par ROLL BACK (ou ROLL BACK WORK)
Exemple de testi
T1 T2 T3 T4 T5
Tester la sérialisabilitél Li~e(X)
Considérer un ordonnancement O des transactions T1,. . .T'~. Le graphe de précédence de O est un graphe (N, A) où
Lire(Y)
Li~c(Z)
Lir~(U)
Lsre(Y)
Liee(V)
Lire(W)
ECTire(W)
Ecrire(Z)
N est l'ensemble des transactions
Il y a un arc (~O est c-sérialisable 55 son graphe de précédence est acyclique.
Lire(U)
Ecrsre(U)
Le r~(Y) Fcrer£(Y)
Lira(Z)
Ecrire(Z)
Test de la v-sérialisabilitéî
Il a été montré que le test de la v-sérialisabilité est un problème NP-complet. Il est donc très peu probable que l'on trouve un algorithme efficace (polynômial) qui puisse faire ce test.
Exemple de test
T1 j T2 Lire(A)
Lire(A)
Ecrire(A)
Ecrire(A)
Dans la pratique, on se contente de la c-sérialisabilit<
conclusion
Tester Si un ordonnancement est sérialisable après son exécution (ou bien sur son graphe de précédence) est inefficace.
Contrôle de concurrencel
e Protocoles basés sur les verrous
e Protocoles basés sur les estampilles
But Développer des stratégies de contrôle de con currence qui puissent garantir la c-sérialisabilité. Ces protocoles n'auront pas besoin de faire le test sur le graphe de précédence (utilisation de techniques de verrouillage, cf prochain cours)
Pourquoi ce cours ? Pouvoir décider Si un protocole est correct par rapport â une notion de sérialisabilité.
e Protocoles basés sur la validation
e Différentes granularités
e Gestion des deadlock (verrous mortels)
30
Notion de verrouiIlage~
Les transactions posent des verrous sur les données auxquelles elles veulent accéder.
Les données peuvent être verrouillées de deux manières
Notion de verrouillage (suite)
e Matrice de compatibilité de verrous
Verrou exclusif Dans ce cas, la donnée peut être lue et écrite. Le verrou VX est attribué lors de l'exécution de l'opération Lock~X(donnée)
Verrou partagé : Dans ce cas, la donnée ne peut
être que lue. Le verrou VP est attribué suite a
l'exécution de Lock~P(donnée)
Les demandes de verrous sont adressées au ges tionnaire de la concurrence.
Une transaction ne peut avancer tant que le verrou qu'elle demande ne lui est pas attribué.
jipI x
½frfrP oui non
fififix non non
Une transaction ne peut poser un verrou sur une don née que Si ce verroù est compatible avec les verrous qui y sont dèja posés.
Lors de son exécution, une transaction peut libérer certains verrous. Utilisation de la commande Unlock((
Notion de verrouillage (suite)
e Considérer l'ordonnancement suivant
Notion de verrouillage (suite)
T1
T2
T1 : Lock~P(A)
Lire(A)
Unlock(A)
Lock~P(B)
Lire(B)
Unlock(B)
Afficlîer(A + B)
Un protocole de verrouillage est une discipline qui dicte aux transactions comment elles demandent et comment elles libèrent les verrous
Lock~X(B)
Lire(B)
B := B - 1000 Ecrire(B)
Lock~X(A)
Ecrire(A)
LOck~P(A)
Lire(A)
Lock~P(B)
Lire(B)
T1 et T2 seront bloqués. Nous sommes en situation de deadlock. Pour résoudre ce problème, une des deux transactions doit étre avortée et ses verrous libérés
e La possibilité de deadlock existe dans presque tous les protocoles
Verrouillage a deux phasesi
verrouillage 2PL
b Ce protocole garantit la c-sérialisabilité Phase 1:
Verrouillage a deux phasesI
- La transaction peut poser des verrous
- Elle ne peut pas en libérer
Phase 2:e Le 2PL ne garantit pas l'absence de deadlocks e Le 2PL ne garantit pas l'absence de cascades
- La transaction peut libérer des verrous
- Elle ne peut plus en poser
On associe a chaque transaction un point de ver rouillage qui correspond au moment où elle pose son dernier verrou (la fin de la première phase). On mon tre alors que les ordonnancements sont équivalents a l'exécution en série selon l'ordre des points de ver rouillage des transactions.
Extension : "2PL stricte" et "2PL rigoureux"
Acquisition des verrousi
Extension du 2PLI
Dans le 2PL stricte, les transactions gardent leurs verrous exclusifs jusqu'au commit.
Dans le 2PL rigoureux, les transactions gardent tous leurs verrous jusqu'au commit.
La différence : T~, qui vient après T,, peut écrire un objet A après que T, l'ait lu et avant que T, ne soit validée.
Alors que dans le 2ème cas, ~ ne peut pas modifier un objet accédé par tant que celle-ci n'a pas validé.
C'est généralement par â l'utilisateur d'inclure dans son code les demandes de verrous.
Si une transaction T~ veut lire/écrire un objet D sans demander explicitement un verrou, alors l'algo suivant est utilisé
Pour l'opération de lecture
|
