Atomicité

7c.1 URD L2 2005Systèmes d’exploitation

AtomicitéAtomicité

Transactions Atomiques Recouvrement à Base de Journal Checkpoints Transactions Concurrentes Serialisabilité Protocoles à Verrous


Transactions AtomiquesTransactions Atomiques Assure que les opérations s’exécutent en 1 seul bloc logique,

totalement, ou pas du tout Liées au domaine des bases de données Le challenge est d’assurer l’atomicité en dépit des pannes de

système Transaction - collection d’instructions ou d’opérations qui

exécute une fonction logique unique On est concerné par des changements persistents – sur disque Une transaction est une série d’opérations read et write Terminés par un commit (transaction réussie) ou abort

(transaction non réussie) Les transactions non réussies doivent faire un rollback pour défaire

tous les changements faits


Types de Média de StockageTypes de Média de Stockage Stockage Volatile – information stockée ne survit pas après un

crash système Exemple: mémoire centrale, cache

Stockage Non Volatile – Information normallement survit après un crash système Exemple: disque et cassette

Stockage Stable – Information jamais perdue Pas facilement atteignable, alors approximation via la réplication ou

RAID sur des périphériques distincts

Le but est d’assurer l’atomicité d’une transaction où les pannes provoquent des pertes d’information sur du stockage volatile


Recouvrement à Base de JournalRecouvrement à Base de Journal Enregistrer sur un média stable les informations de modifications

effectuées par une transaction Plus commun : write-ahead logging

Ecrire sur un média stable, chaque entrée décrivant une seule opération d’écriture liée à une transaction Nom de la transaction Nom de l’item de donnée Ancienne valeur Nouvelle valeur

<Ti starts> écrit dans le journal au début de la transaction <Ti commits> écrit quand la transaction réussit et ainsi se termine

Une entrée du journal doit être écrite sur le média stable avant l’occurrence des opérations sur les données


Algorithme de Recouvrement Basé sur un Algorithme de Recouvrement Basé sur un JournalJournal

Utilisant le journal, le système peut traîter toutes les erreurs en mémoire volatile Undo(Ti) restore la valeur de toutes les données modifiées par Ti

Redo(Ti) affecte les nouvelles valeurs à toutes les données dans la transaction Ti

Undo(Ti) and redo(Ti) doivent être idempotents Plusieurs exécutions doivent avoir le même résultat qu’une seule

exécution Si le système tombe en panne, on restore les états de toutes les

données modifiées via le journal Si le journal contient <Ti starts> sans <Ti commits>, on fait undo(Ti)

Si le journal contient <Ti starts> et <Ti commits>, on fait redo(Ti)


CheckpointsCheckpoints Le journal peut devenir très long, et le recouvrement peut alors

prendre beaucoup de temps Les checkpoints raccourcissent le journal et le temps de

recouvrement. Schéma de Checkpoint:

1. Ecrire toutes les entrées de journal actuellement en mémoire volatile sur un média stable

2. Ecrire toutes les données modifiées de la mémoire volatile sur le média stable

3. Ecrire une entrée <checkpoint> dans le journal Maintenant, un recouvrement inclut uniquement les Ti, tel que Ti

a commencé l’exécution avant le dernier checkpoint , et toutes les transactions après Ti


Transactions ConcurrentesTransactions Concurrentes Doivent être équivalentes à une exécution de transactions en

série – serialissabilité On pourrait exécuter toutes les transactions dans une section

critique Pas efficace, très restrictive

Algorithmes de contrôle de concurrence assurent la sérialisabilité


SerialisabilitéSerialisabilité Considérez deux données A et B Considérez les transactions T0 et T1

Exécuter T0, T1 atomiquement

Une séquence d’exécution est appelée schedule Un ordre d’exécutions atomiques de transactions est appelé

schedule en série Pour N transactions, il y a N! schedules en séries valides


Schedule 1: TSchedule 1: T00 puis T puis T11


Schedule Non SérieSchedule Non Série Schedule Non Série permet des exécutions entrelacées

L’exécution résultante pas nécessairement incorrecte

Considérez le schedule S, opérations Oi, Oj

Conflit s’il y a accès aux mêmes données, avec au moins une écriture

Si Oi, Oj sont consécutifs et les opérations de différentes transactions & Oi and Oj ne sont pas en conflit Alors S’ avec un ordre Oj Oi équivalent à S

Si S devient S’ en échangeant les ordres des opérations non conflictuelles S est conflict serializable


Schedule 2: Concurrent SerializableSchedule 2: Concurrent Serializable


Protocole à VerrousProtocole à Verrous Assurer la sérialisabilité en associant un verrou à chaque

donnée Suivre un protocole à verrous pour le contrôle d’accès

Verrou Partagé – Ti a un verrou en mode partagé (S) sur l’item Q, Ti peut

lire Q mais pas écrire Q Exclusif – Ti a un verrou en mode exclusif (X) sur Q, Ti peut lire et

écrire Q Exige que chaque transaction sur un item Q acquière un verrou

approprié Si le verrou est déjà pris, une nouvelle requête doit attendre

Similaire aux algorithmes de lecteurs-écrivains


Protocole à Verrous à Deux PhasesProtocole à Verrous à Deux Phases Générallement assure le conflit de serialisabilité Chaque transaction fait des requêtes de lock et unlock en deux

phases Grandissant – acquérir les verrous Rétrécissant – relâcher les verrous

Possibilité de deadlocks


Protocoles à Base d’EstampillesProtocoles à Base d’Estampilles Selectionne l’ordre parmi les transactions en avance –

Ordonnancement à base d’estampilles Transaction Ti associée avec l’estampille TS(Ti) avant que Ti

commence TS(Ti) < TS(Tj) si Ti entre dans le système avant Tj

TS peut être généré à partir de l’horloge système ou un compteur logique incrémenté à chaque transaction

Les estampilles déterminent l’ordre de la sérialisabilité Si TS(Ti) < TS(Tj), un système doit assurer que l’ordre produit est

équivalent a l’ordre série où Ti apparaît avant Tj


Implémentation des Protocoles à base Implémentation des Protocoles à base d’Estampillesd’Estampilles

Une donnée Q reçoit deux estampilles W-timestamp(Q) – plus grande estampille de la transaction qui a

exécuté write(Q) avec succès R-timestamp(Q) – plus grande estampille d’un read(Q) Mise à jour dès qu’un read(Q) ou write(Q) sont exécutés

Protocole d’ordonnancement à base d’estampilles assure que tous les read et write sont exécutés dans l’ordre de leurs timestamps

Supposez que Ti exécute read(Q) Si TS(Ti) < W-timestamp(Q), Ti a besoin de lire la valeur de Q qui a

été réécrite operation read rejetée et Ti défaite (rolled back)

Si TS(Ti) ≥ W-timestamp(Q) read exécuté, R-timestamp(Q) mis à max(R-timestamp(Q), TS(T i))


Protocole d’Ordonnancement à Base Protocole d’Ordonnancement à Base d’Estampillesd’Estampilles

Supposez Ti exécute write(Q) Si TS(Ti) < R-timestamp(Q), La valeur de Q produite par Ti était

requise avant et Ti a assumé qu’elle ne pourra pas être produite

Opération Write rejetée, Ti défaite (rolled back)

Si TS(Ti) < W-timestamp(Q), Ti essaye d’écrire une valeur obsolète de Q Opération Write rejetée et Ti défaite (rolled back)

Sinon, write exécuté

Toute transaction Ti défaite est assignée une nouvelle estampille et relancée

L’algorithm assure la conflict serialisabilité et supprime les deadlocks


Schedule Possible sous Protocole à Schedule Possible sous Protocole à EstampilleEstampille

Documents

Atomicité