Chapitre 4

Gestion des Transactions et de de la

concurrence d’accès

2022/2023
 Introduction aux transactions
• En BD 2 problèmes :
– De multiples utilisateurs doivent pouvoir accéder à
la base de donnée en même temps  problème
d’accès concurrents

– De nombreuses et diverses pannes peuvent

apparaître. Il ne faut pourtant pas perdre les
données…,

La Gestion de transactions répond à ces problèmes

Notion de transaction

• Une transaction est une suite d'opérations interrogeant et/ou modiant la

BD, pour laquelle l'ensemble des opérations doit être soit validé, soit
annulé.
• Toute la transaction est réalisée ou rien ne l’est
– Validation : toute la transaction est prise en compte
– Avortement ou annulation : la transaction n’a aucun effet

• Sous oracle
– Début d’une transaction : ordre SQL ou fin de la précédente
– Fin d’une transaction : validation(Commit) ou annulation (Rollback)
• L'exécution d’une transaction provoque le passage d'un état
cohérent de la BD à un nouvel état cohérent
• Une transaction est constituée de trois primitives

Ouverture d’une transaction Begin transaction

Travail sur les données Travail sur les données

clôture avec conf…

irm
. ation àà COMMIT
clôture avec annulationàà ROLLBACK
 Propriété d’une transaction

• Atomicité

– Soit toutes les modifications effectuées par une transaction sont enregistrées dans la
BD, soit aucune ne l’est.
• Cohérence
– Une transaction fait passer une BD d’un état cohérent à un autre état cohérent. Un
état cohérent est un état dans lequel les contraintes d’intégrité sont vérifiées.
• Isolation

– Une transaction se déroule sans être perturbée par les transactions

concurrentes : tout se passe comme si elle se déroulait seule.
• Durabilité
– Une fois qu’une transaction a été confirmée le SGBD garantit qu’aucune
modification qu’elle a effectuée ne sera perdue même en cas :
interruption, pannes du système d’exploitation, « crash » de disque, etc.
 Vies possibles d’une transcation

• Vie sans histoire

– La transaction arrive sur la fin
– Point de confirmation : commit
• Un assassinat
– Arrêt par un événement extérieur
– Arrêt par le sgbd lui même (dead lock)
– Le système fait marche arrière (rollback) et annule les
actions déjà effectuées
• Un suicide
– Arrêt et annulation par la transaction elle même (rollback)
 Utilisation des transactions: Accès concurrents

• Accès concurrent

– Il y a un accès concurrent lorsque plusieurs utilisateurs

(transactions) accèdent en même temps à la même donnée
dans une base de données.
• Gestion des accès concurrents (contrôle de concurrence)

– S’assurer que l’exécution simultanée des transactions produit le

même résultat que leur exécution séquentielle (l’une puis l’autre)
• Problèmes posés par les accès concurrents
– Perte de mise à jour
– Lecture impropre
– Lecture non reproductible
– Objets fantômes
 Perte de mise à jour

T1 et T2 modifient simultanèment A. Les modifications effectuées par T1 sont perdues

T1 T2 BD
A = 10
read A(10)
read A(10)
A = A + 10
write A A = 20
A = A + 50
write A A = 60
 Lecture impropre
T1 T2 BD
A + B = 200
A = 120
T2 lit une valeur de A non validée,
B = 80
read A affiche une valeur incohérence
A = A - 50
write A (si A n’est pas A = 70
validé, donc A a pris une
valeur non validé à T2)

read A
read B
display A + B
(150 est affiché)
read B
B = B + 50
write B B = 130
 Lecture impropre (donnée non
confirmée)

T1 T2 BD
A = 50
A = 70
write A A = 70
read A
(70 est lu)
traitement rollback A = 50
(La valeur initiale de A est restaurée
avec A A=50)

T1 lit une valeur de A non confirmée

SGBD resoud le problème avec commit pour éviter les problèmes
Lecture non reproductible
T1 T2 BD
A = 10
read A
(10 est lu)
A = 20
write A A = 20
read A
(20 est lu)

T2 lit deux valeurs de A différentes

SGBD resoud le probleme avec commit ou rollback
 Objet fantôme

T1 T2 BD

E = {1, 2, 3}

display card(E)
3 est affiché

insert 4 into E E = {1, 2, 3, 4}

display card(E)
4 est affiché

SGBD resoud le problème d’objet fantôme

Ces problèmes sont rencontrées si on n’a pas le
mécanisme de commit et rollback
 contrôle des accès(solution)
• Verrouillage :
– Le verrouillage est la technique la plus classique pour résoudre les problèmes
dus à la concurrence :

• Avant de lire ou écrire une donnée une transaction peut demander un

verrou(partagé possibilité de lecture seulement) sur cette donnée pour interdire
aux autres transactions d’y accéder.

• Si ce verrou ne peut être obtenu, parce qu’une autre transaction en possède

un, la transaction demandeuse est mise en attente.
– Afin de limiter les temps d’attente, on peut jouer sur :
• la granularité du verrouillage : pour restreindre la taille de la donnée verrouillée
(n-uplet, une table)

• le mode de verrouillage: pour restreindre les opérations interdites sur la donnée

verrouillée
Verrouillage : Exemple

T1 T2 Résultat A=10

Read A avec verrou

A=A+10 Read A avec verrou
attente A=20
Write A A=20
Commit;
Read A avec verrou 20
A=A+50 50
Write A A=70
commit
L’impasse générée par deux transactions (ou plus) qui attendent,
l’une, que des verrous se libèrent, alors qu’ils sont détenus par l’autre
 Contrôle de la concurrence
OBJECTIFS
• Produire une exécution correcte, en respectant les propriétés ACID
• Assurer l’Isolation des transactions tout en
• Permettant l’ex´ecution simultan´ee d’un grand nombre de transactions
• Gardant de tr`es bonne performance
• E´vitant les blocages
• Les autres propri´et´es sont assur´es par la reprise apr`es les pannes
• L’ex´ecution doit ˆetre ´equivalente `a une exécution en série des transactions
• Ex´ecution s´erialisable = ex´ecution ´equivalente `a une ex´ecution en s´erie quelconque des transactions
• Plusieurs ex´ecutions en s´erie sont possibles (n ! pour n transactions)
• Objectif contrôle de concurrence = produire des ex´ecutions s´erialisables en modifiant l’entrelacement des
transactions
Le SGBD doit mémoriser les phases d’exécution d’une transaction :

• BEGIN TRANSACTION

• READ ou WRITE

• END TRANSACTION

• COMMIT TRANSACTION

• ROLLBACK (ou ABORT)

OPÉRATIONS COMMUTABLES/ OPERATIONS

CONFLICTUELLES
Opérations conflictuelles

Deux op´erations a et b, ex´ecut´ees respectivement par deux transactions diff´erentes

T et T’ sont dites conflictuelles si l’ex´ecution des deux s´equences a ;b (a puis b) et b
;a (b puis a) est susceptible de conduire `a des r´esultats diff´erents et ne sont pas
commutables.
[Link] opérations d’une même transaction ne peuvent pas changer de position relative
[Link] opérations sur des articles différents sont toujours commutables
3- Seules les lectures (Lire-Lire) sont commutables → s’il y a au moins une écriture alors il y a conflit.

Conflit équivalence

Deux exécutions sont conflit équivalentes s’ils ont le même ordre relatif de chaque

paire d’opérations conflictuelles.

Notations :
• Transaction Ti : Séquence d’opérations terminée par commit ou bien rollback

• Op´erations : Lire, ´Ecrire, Commit, Rollback

• li [x ] : lecture de l’article x dans la transaction Ti

• ei [x ] : ´ecriture de l’article x dans la transaction Ti
• ci : validation (commit) de la transaction Ti
• ri : annulation (rollback) de la transaction Ti
 • Exemple :

• T1 : l1[x ]e1[x ]c1; T2 : l2[y ]e2[y ]c2

• H1 : l1[x ]e1[x ]c1l2[x ]e2[y ]c2 (une ex´ecution s´erie de T1 puis T2)
• H2 : l1[x ]l2[y ]e1[x ]e2[y ]c2c1 (une ex´ecution concurrente de T1 et T2 équiavalent `a H1)

Sérialisabilité:

Un ordonnancement de n transactions est sérialisable ou conflit sérialisable s’il

est conflit équivalent à un ordonnancement série des mêmes transactions
• Vérification de s´erialisabilit´e :

1- Transformations par commutation des opérations non conflictuelles

• 2- Le graphe de précédence est acyclique.
Graphe de pr´ec´edence ou graphe de s´erialisation :
• Nœuds : Les transaction Ti
• Arcs : Pour toute paire d’op´erations conflictuelle Ai pr´ec`ede Bj un arc orient´e de Ti
vers Tj
• (a) et (d) s´erialisables et ´equivalents `a T1; T2

• (b) s´erialisable et ´equivalent `a T2; T1

• (c) non s´erialisable

 Non s´erialisable : 2 cycles
• T1 → T2 → T1
• T1 → T2 → T3 → T1

S´erialisable et ´equivalent `a
• T3 → T1 → T2

S´erialisable et ´equivalent `a
• T3 → T1 → T2
• T3 → T2 → T1
 Algorithmes de contrˆole de la concurrence
• Le th´eor`eme de s´erialisabilit´e est un moyen de v´erification : il ne permet pas de g´en´erer des
ex´ecutions s´erialisables
• Ordonnanceur (Scheduler) :
• Un module du SGBD qui applique le protocole de contrˆole de concurrence
• R´eordonne les op´erations pour garantir la s´erialisaibilit´e
• Deux familles d’approches :
• Optimistes :
• Supposent que le concurrence est rare
• Agissent suite `a la détection d’un cycle pour rejeter une transaction
• Pessimistes :
• Préviennent l’apparition de cycles en évitant l’acc`es concurrent
 VERROUILLAGE
Verrou (Lock)

• Une variable associée `a chaque objet de la BD (enregistrement)

• Objectif : bloquer les autres transactions qui veulent accéder `a un enregistrement en cours de
mise `a jour par une transaction

Principe : Chaque transaction qui va modifier une donnée X

• Vérifie si X n’est pas verrouillé (sinon attendre)

• Poser un verrou
• Modifier X
Enlever le verrou : libérer X → servir une transaction bloquée
Verrouillage `a 2 phase (2PL) : 2 Phase Lock

Deux types de verrou :

1- Verrou partag´e S (Shared Lock) : il est possible de poser d’autres verrou de

type partag´e (pour lecture)
2- Verrou exclusif X (Exclusive Lock) : il est impossible de poser un autre verrou
partag´e ou exclusif (lecture et ´ecriture)

Règle :
Une transaction qui lib`ere un verrou n’a plus le droit d’en poser.
Deux Phases :

1- Poser des verrous

2- Lib´erer des verrous (`a la fin de la transaction)
 Problème de verrouillage
1- Interblocage (Deadlock) :
• T1 a un verrou sur x et veut accédera y qui est verrouillé par T2 et T2 veut accéder `a x.
• Solutions :
• Timeout : Au bout d’un temps d’attente la transaction bloquée et annulée
• Autres : Wait-Die, Wound-Wait, Victim Selection, ...
2- Performance :
• Verrouillage d’enregistrement coûteux
• Verrouillage de table = temps d’attente important
3- Famine (Starvation) :
• Une transaction attend indéfiniment et les autres continuent leurs exécutions
• Solution : FIFO
 Exemple :
Prenons l’exécution concurrente : l1[x ]l2[y ]e1[y ]C1e2[y ]C2 Conflits : l2[y ] < e1[y ] et e1[y ] <
e2[y ] → Un cycle Par application du verrouillage :

1- l1[x ] : verrou S sur x donné `a T1

2- l2[y ] : verrou S sur y donné `a T2 T2
3- e1[y ] : T1 est bloquée car elle demande un verrou X sur y sur lequel il y a un verrou S par T2
4- C1 : T1 est bloquée
5- e2[y ] : verrou X sur y donné `a T2 (Upgrade du verrou S)
6- C2 : validation de T2 et libération de ses verrous 7.
7- Reprise de T1 : exécution de e1[y ] et C1
Exécution obtenue : l1[x ]l2[y ]e2[y ]C2e1[y ]C1
Conflits : l2[y ] < e1[y ] et e2[y ] < e1[y ] → Pas de cycle
 ESTAMPILLAGE

Estampille (Timestamp)

• Un numéro distinct attribué `a chaque transaction croissant avec la date de début noté E (Ti )
• Donnée par un compteur ou horloge
• Mémoriser les estampilles des transactions les plus jeunes effectuant une lecture/´écriture
notées resp. El (x ) et Ee (x )

Principe :

• Les opérations en conflits passent selon l’ordre des estampilles

• En cas de problème annuler la transaction la plus récente
• Pas de verrouillage (et donc d’interblocage)