En Bretagne pdf free - PDF eBooks Free | Page 1

Les accès
concurrents
IV -
IV
Transaction
33
Problèmes liés aux accès concurrents
34
Gestionnaire des transactions
37
Notion d'ordonnancement
38
Plan d'exécution de transactions (Schedule)
39
Opérations permutables/ Opérations conflictuelles
42
Technique de contrôle d'accès concurrents basée sur le
verrouillage
44
A. Transaction
Une transaction est un ensemble d'actions permettant de prendre une base donnée
dans un état cohérent et de la rendre dans un état cohérent.
Il s'agit d'éviter par exemple qu'un utilisateur x puisse lire ou mettre à jour une
donnée qui est en train d'être modifiée par un utilisateur y.
Exemple
Dans un système de réservation de places d'avions, le risque de vendre le même
numéro de siège deux fois peut facilement se produire si les réservations sont
effectuées en même temps depuis plusieurs points de vente sans contrôle de
conflit.
Définition
Une transaction est une unité de traitement séquentiel exécutée pour le compte
d'un utilisateur. C'est une suite finie d'actions (opérations) portant sur des objets
de la BD
Exemple
On considère l'opération de transfert d'une somme d'argent X d'un compte bancaire
C1 à un compte C2. Cette transaction peut se définir au moyen des actions
suivantes :
Début-transaction T1
Lire (C1)
C1 : = C1- X
Nadia Abdat & Nazih Selmoune
33
Les accès concurrents
Ecrire (C1)
Lire (C2)
C2 : = C2 + X
Ecrire (C2)
Fin-transaction
1. Les opérations d'une transaction
Début
Initialiser une nouvelle transaction.
Une transaction débute à la connexion d'un outil ou à la fin de la transaction
précédente
Fin
Terminer une transaction.
Une transaction se termine par un ordre de validation (COMMIT), d'annulation
(ROLLBACK) de déconnexion (DISCONNECT) ou de fin normale de session.
Lire
Lecture de la valeur d'un objet à partir de la BD et stockage de cette valeur dans
l'espace de travail de la transaction (variables locales)
Écrire
A partir d'une valeur stockée dans l'espace de travail de la transaction, écrire cette
valeur dans la BD pour l'objet désigné
Annuler (ROLLBACK)
Défaire toutes les mises à jour effectuées par la transaction depuis son début.
Valider (COMMIT)
Confirmer toutes les mises à jour effectuées par la transaction depuis son début.
2. Les objets manipulés dans une transaction
En ce qui concerne les objets que manipule une transaction, il peut s'agir de
relation, de tuple ou même d'attribut.
B. Problèmes liés aux accès concurrents
L'environnement bancaire fournit un exemple qui permet de bien illustrer les
problèmes posés par la gestion des transactions dans le cas des accès concurrents.
1. Problème 1 : Panne
On considère l'opération de transfert d'une somme d'argent S d'un compte C1 à un
compte C2 (transaction T1). Pour simplifier, nous supposons que la seule contrainte
à vérifier est que la somme de tous les comptes est constante. Le programme de
transfert est le même que celui de Exemple 1.
34
Nadia Abdat & Nazih Selmoune
Les accès concurrents
Exemple
Exemple 1
S'il y a un arrêt brutal de T1 : supposons qu'une panne vienne interrompre
l'exécution de T1 juste après l'action 4 : C1 a été débité mais C2 n'a pas été crédité
donc risque d'incohérence.
2. Problème 2 : Perte de mise à jour
Exemple
Soit T2 une autre exécution des actions précédentes qui agit sur les mêmes
comptes C1 et C2.
Si T1 est exécutée totalement, puis T2, on aura retiré "2 fois S" de C1 pour les
ajouter à C2 et la BD sera toujours cohérente. Mais si on exécute en parallèle T1 et
T2 le mélange de leurs actions respectives peut causer des incohérences comme
dans l'exemple suivant :
Exemple 2
Dans cet exemple, la mise à jour effectuée par T1 sur C1 et C2 est perdue. On dit
qu'il y a recouvrement de T1 par T2.
Nadia Abdat & Nazih Selmoune
35
Les accès concurrents
3. Problème 3 : Inconsistance des mises à jour ou
contrainte d'intégrité non vérifiée
Exemple
Considérons une base de données contenant les éléments A et B avec la contrainte
A = B, et soient les deux transactions suivantes
T1 : A = A + 1 ; B = B + 1 ;
T2 : A = A * 2 ; B = B * 2 ;
Une exécution concurrente de T1 et T2 peut être schématisée comme suit .
Exemple 3
Si l'état initial est : A = 10; B = 10 l'état final sera : A = 22, B = 11.
Cette exécution concurrente est incohérente. T2 met à jour un état transitoire
incohérent.
4. Problème 4 : Mise à jour non validée
Ce problème apparaît quand une transaction T1 lit une donnée qui a été mise à jour
par une autre transaction T2 sans que cette mise à jour ne soit validée par T2. Car
si cette mise à jour est annulée, T1 aura lu une donnée qui n'existe plus (et qui,
dans un sens, n'a jamais existé).
Exemple
Exemple 4
36
Nadia Abdat & Nazih Selmoune
Les accès concurrents
5. Propriétés d'une transaction
Un des objectifs des SGBD est d'assurer des accès concurrents aux données sans
problèmes. Pour cela une transaction doit vérifier certaines propriétés appelées
(ACID).
Une transaction est caractérisée par quatre propriétés ACID: Atomicité, Cohérence,
Isolation, Durabilité.
Atomicité.
La séquence d'actions d'une transaction est indivisible, i.e., si toutes les actions
sont effectuées alors validation de la transaction sinon annulation. (ie Tout ou rien)
Cohérence
L'exécution d'une transaction dans un environnement sans panne préserve la
cohérence de la base de données (ie une transaction appliquée à une base de
donnée cohérente restitue une base de donnée cohérente).
Isolation
Les actions d'une transaction sont isolées. Ses résultats intermédiaires (état
temporairement incohérent) sont masqués aux autres transactions.
Durabilité
Il est impossible d'annuler les résultats d'une transaction qui s'est bien terminée.
Remarque
Ainsi,
 dans problème 1, la propriété d'atomicité n'est pas respectée,
 dans problème 2, la propriété d'isolation n'est pas respectée
 dans problème 3, les propriétés d'isolation et de cohérence ne sont pas
respectées
 dans problème 4, la propriété d'isolation n'est pas respectée.
C. Gestionnaire des transactions
Le module du SGBD chargé de contrôler les accès concurrents aux données est le
contrôleur (ou scheduleur)
Une demande de transaction arrive au SGBD pour exécuter un programme
d'application donné. Lorsque ce programme émet l'action Début-transaction, ceci a
pour effet de créer au niveau du SGBD une nouvelle occurrence ou instance de
transaction à laquelle est associé :
1. un identificateur interne
2. un espace de travail
3. un contexte d'exécution formé d'une série de blocs de contrôle.
Une transaction peut avoir après cela trois vies différentes
Nadia Abdat & Nazih Selmoune
37
Les accès concurrents
Vie sans histoire :
La transaction exécute normalement toutes les actions prévues. On dit qu'elle a
atteint son point de confirmation ou de validation (COMMIT). Il s'agit en quelque
sorte d'un point de non retour à partir duquel toutes modifications faites sur la base
par cette transaction sont considérées comme définitives.
Assassinat
Un événement externe peut interrompre l'exécution d'une transaction d'une façon
irrémédiable. C'est le cas d'une panne ou action délibérée du SGBD (conflit entre
transactions). Afin de respecter l'atomicité (tout ou rien), il faut faire faire à cette
transaction une marche arrière et effacer de la BD toute trace de son passage.
Nous dirons que la transaction a été annulée (Rollback).
Suicide
Si au cours de son exécution la transaction découvre une anomalie elle peut
s'annuler elle-même. Dans ce cas on doit pouvoir programmer l'opération annuler
En résumé le gestionnaire des transactions d'un SGBD doit
 Initialiser chaque transaction T et en contrôler l'exécution. Si celle-ci se
passe bien, il doit confirmer la transaction. Dans le cas d'une exécution
anormale, il doit l'annuler en défaisant ce qu'elle a fait.
 Contrôler les accès concurrents en synchronisant les transactions en conflit
 Assurer la reprise après panne (Recovery) et donc être capable de refaire le
travail des transactions ayant atteint leur point de confirmation avant la
panne mais aussi défaire le travail de celles qui n'avaient pas atteint ce point
au moment de la panne.
D. Notion d'ordonnancement
• Un ordonnancement représente l'ordre dans lequel les opérations des transactions
dans un environnement concurrent sont exécutées.
Un ordonnancement série de deux transactions T1 et T2 consiste à exécuter en
séquence toutes les opérations de T1, puis celles de T2 (pas de parallélisme).
Un ordonnancement série est correct.
Exécution concurrente correcte
Une exécution concurrente sera correcte si elle produit les mêmes résultats et a les
mêmes effets sur la BD qu'une exécution série de mêmes transactions.
Ordonnancement sérialisable
Le principe de sérialisabilité consiste à ne laisser s'exécuter les transactions en
parallèle que celles provoquant les mêmes effets sur les données qu'une exécution
en séquence de ces mêmes transactions.
Définition
Un ordonnancement est sérialisable ssi il est équivalent à un ordonnancement série
formé des mêmes transactions.
38
Nadia Abdat & Nazih Selmoune
Les accès concurrents
E. Plan d'exécution de transactions (Schedule)
Une exécution de transactions (T1, T2, ..., Tn) est une séquence d'actions obtenue
en intercalant les diverses actions des transactions T1, T2, ..., Tn tout en
respectant l'ordre interne des actions de chaque transaction.
Exemple
Considérons deux transactions T1 et T2 qui réalisent des transferts entre trois
comptes bancaires C1, C2, C3. T1 transfert 1000 DA de C1 à C2, T2 transfert 2000
DA de C2 à C3.
On suppose qu'à l'état initial : C1= 10.000 DA C2=8.000 DA C3=9.000 DA
Plan d'exécution
Nadia Abdat & Nazih Selmoune
39
Les accès concurrents
Exemple
Exécution de (a)
40
Nadia Abdat & Nazih Selmoune
Les accès concurrents
Exemple
Exécution de (b)
Nadia Abdat & Nazih Selmoune
41
Les accès concurrents
Exemple
Exécution de (c)
(a) et (b) sont équivalents.
Le problème provient de l'ordre dans lequel sont exécutées les actions lire et écrire
des différentes transactions lorsque ces actions concernent les mêmes objets et
sont donc en conflit.
F. Opérations permutables/ Opérations
conflictuelles
Nous définissons dans ce qui suit les opérations permutables et les opérations
conflictuelles
1. Opérations permutables
Définition
Deux opérations Oi et Oj sont permutables si et seulement si toute exécution de Oi
suivie de Oj donne le même résultat que celle de Oj suivi de Oi.
42
Nadia Abdat & Nazih Selmoune
Les accès concurrents
Exemple
Soient O1 et O2 tq :
Image 6 Opérations permutables
Pour la valeur initiale de A=10,
L'exécution O1, O2 donne A = 11 puis A = 21
L'exécution O2, O1 donne A = 20 puis A = 21
En fait, O1,O2 et O2,O1 donneront toujours le même résultat car les deux sont des
opérations d'addition qui est elle-même commutative. Donc O1 et O2 sont
permutables
Exemple
Soient O3 et O4 tq :
Image 7 Opérations non permutables
Pour la valeur initiale de A=10,
L'exécution O3, O4 donne (A = 20 puis A = 21)
L'exécution O4, O3 donne (A = 11 puis A = 22)
Donc O3 et O4 sont non permutables.
Remarque
Deux opérations travaillant sur 2 granules différents sont permutables.
2. Opérations conflictuelles
Définition
Deux opérations issues de deux transactions différentes sont en conflit si elles
opèrent sur le même élément de données (granule) et au moins l'une d'entre elles
est une action d'écriture.
Cas 1 : Ti : Lire(X) Tj : Ecrire(X)
Cas 2 : Ti : Ecrire (X) Tj : Ecrire (X)
Cas 3 : Ti : Ecrire (X) Tj : Lire (X)
Ainsi, dans ces cas il y a obligation de précédence de Ti par rapport à Tj.
Définition
: Il y a précédence de Ti par Tj (Ti précède Tj, notée Ti < Tj) dans une exécution E
si et seulement si, il existe deux opérations non permutables Oi et Oj telle que Oi
est exécutée par Ti avant Oj par Tj.
Remarque
Si une exécution de transactions est transformable par permutations successives en
une exécution en série, alors elle est sérialisable.
Nadia Abdat & Nazih Selmoune
43
Les accès concurrents
Exemple
Soit l'ordonnancement O suivant :
Image 8 Exemple
Remarquons
Image 9 Exemple
L'ordonnancement
sérialisable?
O
est-il
Image 10 Exemple
O est transformé par permutations d'opérations en une exécution en série T1T2,
donc O est sérialisable
G. Technique de contrôle d'accès concurrents basée
sur le verrouillage
L'idée de base du verrouillage est très simple : lorsqu'une transaction Ti veut
s'assurer que l'objet A dont elle dispose ne soit modifié de façon imprévisible, elle
pose un verrou sur A. Verrouiller l'accès à l'objet A par les autres transactions et
ainsi de les empêcher en particulier de le modifier. Ti est par conséquent capable de
mener à bien son calcul avec l'assurance que l'objet A restera dans un état stable
aussi longtemps que Ti le souhaite.
1. Verrous exclusifs et Verrous partagés
Le système gère deux types de verrous : les verrous exclusifs (ou d'écriture)
"Xlocks" et les verrous partagés (ou de lecture) "Slocks".
Si la transaction Ti détient un verrou exclusif (X) sur l'objet A, alors la demande
d'un verrou de n'importe quel type sur A faite par une autre transaction Tj sera
refusée.
Si la transaction Ti détient un verrou partagé (S) sur l'objet A alors
 Une demande d'un verrou de type X faite par une transaction distincte Tj
sera refusée.
 Une demande d'un verrou de type S faite par une transaction distincte Tj
pourra être accordée: Tj aura dans ce cas elle aussi posée un verrou (S) sur
A.
Si une demande de verrou émise par la transaction Tj est refusée car elle entre en
conflit avec un verrou déjà détenu par la transaction Ti, la transaction Tj est mise
en attente. Tj devra attendre jusqu'à ce que Ti abandonne (libère) le verrou.
44
Nadia Abdat & Nazih Selmoune
Les accès concurrents
Remarque
Le système doit garantir que Tj ne soit pas être mise en attente indéfiniment.
Il existe plusieurs techniques de verrouillage. Dans ce qui suit, nous présentons la
technique de verrouillage à deux phases notée (V2P).
2. Verrouillage à deux phases (V2P)
Avant d'agir sur un objet, une transaction Ti doit obtenir un verrou sur cet objet.
Après l'abandon d'un verrou, la transaction Ti ne doit plus jamais pouvoir obtenir de
verrous.
Une transaction qui obéit à ce protocole a ainsi deux phases: une phase
d'acquisition de verrous et une phase d'abandon de verrou.
Dans la pratique, la seconde phase est souvent condensée en une seule opération
de Commit (ou Rollback) à la fin de la transaction.
Exemple
: Reprise du problème 3
Reprise du problème 3
3. Interblocage (dead lock)
Le verrouillage règle donc certains problèmes
problèmes : l'inter-blocage ou dead lock.
mais
génère
de
nouveaux
L'inter-blocage est une situation dans laquelle deux transactions ou plus sont
Nadia Abdat & Nazih Selmoune
45
Les accès concurrents
simultanément en attente, chaque transaction étant en attente que l'une des autres
transactions abandonne un verrou pour poursuivre son exécution.
Exemple
: Reprise du problème 2
Interblocage
Détection du blocage
Si un blocage se produit, il est souhaitable que le système le détecte et le
supprime.
Pour cela, on construit au fur et à mesure le graphe des attentes (graphe indiquant
"qui est en attente de qui").
Dans le graphe des attentes, chaque nœud correspond à une transaction. Une
flèche de Ti vers Tj signifie que la transaction Ti attend de verrouiller une donnée
actuellement verrouillée pat Tj.
Détecter le blocage implique de détecter un cycle (circuit) dans le graphe des
attentes.
Supprimer le blocage implique de choisir une des transactions bloquées (dans le
circuit) et l'annuler, ce qui libère ses verrous et permet aux autres transactions de
poursuivre leur exécution.
Graphe d'attente
Timeout
Dans la pratique, tous les systèmes ne détectent pas les blocages. Certains utilisent
un mécanisme de délai (timeout) et considèrent qu'une transaction qui n'a rien fait
pendant ce délai est bloquée et donc sera annulée.
Certains systèmes relancent automatiquement l'exécution d'une transaction
annulée.
46
Nadia Abdat & Nazih Selmoune

Download Report