Cours de Bases de données








télécharger 391.04 Kb.
titreCours de Bases de données
page13/14
date de publication23.12.2016
taille391.04 Kb.
typeCours
ar.21-bal.com > droit > Cours
1   ...   6   7   8   9   10   11   12   13   14

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 transformé 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 ordonnancement 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 analyser 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 cohé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 implicitement.
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)

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 concurrence 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 gestionnaire 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 donné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 verrouillage qui correspond au moment où elle pose son dernier verrou (la fin de la première phase). On montre alors que les ordonnancements sont équivalents a l'exécution en série selon l'ordre des points de verrouillage 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
1   ...   6   7   8   9   10   11   12   13   14

similaire:

Cours de Bases de données iconAdministrateur(trice) de bases de données / Intégrateur(trice) d’applications
«Accompagner les transitions agro-écologiques des systèmes et territoire d’élevage») et sur le pôle basmati («Bases de données, modèles...

Cours de Bases de données iconI ] Les différents modèles de bases de données

Cours de Bases de données iconUniversité Sidi Mohamed Ben Abdellah
«pose» sur le IaaS. IL permet d’externaliser l’infrastructure matérielle, mais également des applications middleware : bases de données,...

Cours de Bases de données iconC onsultant(e) système spécialiste O. S. et bases de données / Grenoble...

Cours de Bases de données iconProtection des logiciels et des bases de données

Cours de Bases de données iconM. Bilodeau est un professionnel dynamique, versé dans plusieurs...

Cours de Bases de données iconPour les projets de logiciels et/ou de bases de données, cette déclaration...

Cours de Bases de données iconCours : mat-4172-2 Collecte de données en contexte fondamental

Cours de Bases de données iconAccès sécurisés aux données partout dans le monde avec aprol
«parlantes» sont transférées à la base de données du cloud. Cette méthode basée sur les concepts du fog computing (informatique géodistribuée)...

Cours de Bases de données iconAu risque de refroidir les ardeurs de quelques dsi, le temps semble...
«humeur» des internautes. A nous les connexions vers les sites métiers pour remplir nos bases de données des informations professionnels...








Tous droits réservés. Copyright © 2016
contacts
ar.21-bal.com