Cours 9

Question 1

Definir la coherence.

Answer 1

Coherence (consistency): refleter sur la copie d’une donnee les modifications intervenues sur d’autre copies de cette donnee.
En anglais:
• Coherence, en cas de plusieurs modifications concurrentes sur une donnee, la meme valeur finale rejoindra eventuellement toutes les copies.
• Consistency, l’ordre entre plusieurs modifications concurrentes sur differentes donnees sera vu de maniere coherente (plus ou moins stricte selon le modele) par les clients de toutes les copies

Les modeles de coherence sont utilises pour les donnees reparties ou repliquees: bases de donnees, systemes de fichiers, cache…

Question 2

Definir les modeles de coherence.

Answer 2

• Coherence stricte: la mise a jour est vue en meme temps sur toutes les copies (e.g. invalider la valeur actuelle sur toutes les copies, propager la nouvelle valeur sur toutes les copies).
• Coerence sequentielle: l’ordre des modifications est le meme sur toutes les copies.
• Coherence causale: l’ordre des modifications reliees
causalement (e.g. meme origine) est le meme sur toutes les copies.

Question 3

Definir le concept de transaction.

Answer 3

• Dans la plupart des cas, on doit s’assurer de la coherence d’un groupe de modifications (transaction) plutot qu’une modification seule (e.g. transactions dans les bases de donnees, operations sur les donnees et metadonnees pour ecrire dans un fichier).
• La coherence sera donc etudiee principalement sous l’angle des transactions.
• Transaction: sequence d’operations que le serveur execute d’une maniere atomique, meme en presence d’acces simultanes par plusieurs clients et de pannes.
• Assurer le partage securitaire et coherent des donnees des serveurs par plusieurs clients.

Question 4

Definir la synchronisation simple (sans transaction).

Answer 4

• Operations atomiques au niveau du serveur.
• Utilisation de plusieurs fils d’execution au niveau du serveur.
• Les operations des clients peuvent s’executer simultanement.
• Un verrou assure qu’un seul thread accede a un objet a un instant donne.

Question 5

Definir les proprietes des transactions.

Answer 5

• Atomicite: Les effets d’une transaction ne sont rendus visibles que si toutes ses operations peuvent etre realisees. Sinon, aucun effet n’est produit par la transaction
• Coherence: les effets d’une transaction doivent satisfaire les contraintes de coherences de l’application (la transaction transforme l’etat coherent du systeme en un autre etat coherent)
• Isolation: les effets d’une transaction sont identiques `a ceux qu’elle pourrait produire si elle s’executait seule dans le systeme
• Durabilite: les effets d’une transaction terminee ne peuvent etre detruits ulterieurement par une quelconque defaillance

Question 6

Qu’est-ce que le concept de “Panne inevitable mais objets recuperables”?

Answer 6

• Objets pouvant etre recuperes suite a une panne de serveur. Le serveur doit stocker suffisamment d’information en memoire stable (disque), possiblement redondante.
• Un journal sur disque permet de lister les elements d’une transaction avant de commettre ou d’annuler, et permet en cas de panne de savoir ce qui etait en train d’etre fait.
• La synchronisation des transactions pour les serialiser est une methode permettant l’isolation.

Question 7

Definir un coordonateur de transaction et comment il fonctionne.

Answer 7

• Creation: le coordonnateur cree la transaction et lui affecte un identificateur unique qui sera associe a toutes les operations de cette transaction.
• Operations: le coordonnateur maintient la liste des objets ou processeurs impliques dans les differentes operations de la transaction.
• Fin: la transaction est confirmee (commit) ou annulee (abort) par le client, le coordonnateur accepte ou annule une transaction confirmee et annule une transaction annulee.
• Une transaction est completee suite a la cooperation entre le programme du client, les objets recuperables et le coordonnateur.

Question 8

Que se passe-t-il en cas de panne du client.

Answer 8

• Le client redemarre et a oublie toute transaction qu’il avait initiee et qui etait en cours.
• Si le serveur n’a plus de nouvelles d’un client apres un cetain delai (timeout) il annule la transaction.
• Si le client n’etait pas en panne mais son reseau etait trop lent et le delai expire, le serveur lui refusera la transaction puisqu’elle est annulee (ou repondra que la transaction n’existe plus).

Question 9

Que se passe-t-il en cas de panne du serveur.

Answer 9

• Le serveur redemarre et a oublie toutes les transactions en cours (non completees) qui sont consequemment annulees.
• Une procedure de recouvrement (e.g. lecture du journal des transactions) permet au serveur de revenir a un etat coherent des objets (valeurs produites par les plus recentes transactions completees).
• Un client ne recevant plus de reponse du serveur apres un certain delai abandonne sa requete.
• Si le serveur a redemarre, le client se fera repondre que la transaction n’existe plus.
• Si le serveur plante avant d’avoir repondu au client si la
transaction est acceptee, le client reste dans l’incertitude. Il demandera le statut de la transaction apres le redemarrage et se fera confirmer qu’elle est acceptee ou repondre que la transaction n’existe plus.

Question 10

Definir ce qu’est la serialisation des transactions.

Answer 10

• Une transaction executee seule ne presente pas de probleme.
• L’execution serialisee des transactions, une par une, permet aussi d’assurer les proprietes requises, T1, T2, . . . , Tn .
• Entrelacement des transactions equivalent a une execution en serie, pour un ordre des transactions quelconque, est aussi acceptable.

Question 11

Quelles sont les contraintes pour serialiser les transactions?

Answer 11

• Deux operations sont en conflit si leur effet combine depend de l’ordre dans lequel elles sont executees.
• Lecture-Lecture, pas de conflit.
• Lecture-Ecriture, conflit, le resultat de la lecture est affecte par l’ecriture de la variable a lire.
• Ecriture-Ecriture, conflit, le resultat des lectures subsequentes depend de l’ordre des deux ecritures sur une meme variable.

Question 12

Definir des transactions serialisables.

Answer 12

Deux transactions sont serialisables si toutes les paires

d’operations en conflit des deux transactions sont executees dans le meme ordre sur tous les objets qu’elles accedent.

Question 13

Definir les approches de controle de la concurrence.

Answer 13

• Le protocole doit produire un ordonnancement equivalent a une execution en serie.
• Le verrouillage:
  • Utilise par la plupart des systemes.
  • Chaque objet est verrouille par la premiere operation qui y accede.
  • L’objet est deverrouille au commit ou abort.
• Controle optimiste de la concurrence:
  • On suppose l’absence de conflit.
  • Chaque transaction est executee jusqu’a la fin sans bloquer.
  • Avant d’etre completee, le serveur verifie si elle n’a pas execute des operations sur des objets qui sont en conflit avec les autres operations des autres transactions simultanees.
  • Si de tels conflits existent, le serveur abandonne la transaction et le client peut la redemarrer.

Question 14

Definir le recouvrement apres l’abandon d’une transaction.

Answer 14

Le serveur doit:
• Sauvegarder les effets des transactions completees
• Assurer qu’aucun effet des transactions abandonnees ne soit stocke

Problemes associes a l’abandon de transactions, si mal gere:
• Probleme de lectures contaminees (dirty reads)
• Probleme d’ecritures prematurees (premature writes)

Question 15

Comment se premunir contre les problemes d’ecriture prematurees?

Answer 15

• Chaque transaction possede ses propres versions
provisoires (tentative) des objets qu’elle met a jour.
• Les ecritures sont faites sur les versions provisoires.
• Les lectures d’autres transactions sont faites a partir des versions provisoires (correct si finit apres), ou a partir des versions permanentes (correct si finit avant ou est annule).
• Les versions provisoires sont transferees dans les versions permanentes des objets seulement lorsque la transaction est completee, en une seule etape.
• Pendant le transfert, les autres transactions n’ont pas acces aux objets modifies.
• Si les objets modifies ne sont pas verrouilles (controle
optimiste), il faut verifier la coherence des transactions
concurrentes.

Question 16

Definir les transactions imbriquees.

Answer 16

• Transaction contenue dans une autre et qui peut elle-meme contenir des transactions imbriquees
• Une transaction imbriquee a un niveau de la hierarchie n’est completee que si son parent complete son execution
• Accroit le niveau de concurrence en permettant aux
transactions imbriquees d’un meme niveau dans la hierarchie d’etre executees simultanement
• Permet aux transactions imbriquees d’ˆetre completees ou abandonnees independamment les unes des autres

Question 17

Definir le verrouillage.

Answer 17

• Un verrou permet de reserver l’acces unique a un objet (ressource).
• Si un client demande l’acces a un objet deja verrouille par une autre transaction, il doit attendre son deverrouillage.
• Verrou de lecture: avant une operation de lecture d’un objet, le serveur pose un verrou (non exclusif) de lecture sur l’objet.
• Verrou d’´ecriture: avant une operation d’ecriture d’un objet, le serveur pose un verrou (exclusif) d’ecriture sur l’objet.

Question 18

Definir les differentes granularite des verrous.

Answer 18

• Verrou complet ou separe lecture et ecriture.
• Verrou sur un seul objet.
• Verrou sur un groupe d’objets (e.g. page sur disque).
• Verrou global (serialiser completement les transactions).

Question 19

Definir des protocoles de verrouillage.

Answer 19

Verrouillage a 2 phases:
• 1ere phase (growing phase): la transaction acquiert de
nouveaux verrous.
• 2eme phase (shrinking phase): la transaction libere ses verrous.
• Aucun verrou ne peut etre pose si un verrou a ete leve.

Verrouillage strict a 2 phases:
• Verrouillage a 2 phases dans lequel les verrous sont liberes seulement lorsque la transaction est completee ou abandonnee.
• Previent les lectures contaminees et les ecritures prematurees
• Il faut attendre le commit ou abort mais pas necessairement la fin de la transaction pour liberer les verrous de lecture.

Question 20

Definir le gestionnaire de verrous.

Answer 20

• Maintient la table de verrous pour les objets d’un serveur.
• Entree pour chaque verrou:
  • objet associe au verrou;
  • type de verrou (ecriture ou lecture);
  • identificateurs des transactions detenant le verrou (un seul pour ecriture);
  • liste des transactions en attente du verrou

Question 21

Definir ce que sont les interblocages.

Answer 21

• Implique au moins deux transactions.

* Chaque transaction est bloquee et ne peut etre debloquee que par une autre transaction de l’ensemble.

Question 22

Definir des solutions pour la prevention d’interblocages.

Answer 22

Solution 1: verrouiller tous les objets utilises par la transaction des le debut.
• Genere un verrouillage premature, reduit la concurrence.
• Parfois, il est impossible de predire des le debut quels objets seront utilises (cas d’applications interactives).

Solution 2: verrouiller les objets dans un ordre predefini.
• Pour ordonner, il faut aussi predire les objets utilises.

Question 23

Definir les mecanismes de detection d’interblocages.

Answer 23

• Detecter les cycles dans le graphe de dependance.
• Abandonner une transaction appartenant a chacun des cycles.
• Le module responsable de la d´etection peut faire partie du gestionnaire de verrous:
  • Maintient une representation du graphe de dependance.
  • Arcs ajoutes ou supprimes dans le graphe lors des operations sur les verrous.
  • Verification periodique de l’existence de cycle.
  • Lorsqu’un cycle est detecte, une des transactions est
  abandonnee (choisie selon son age, le nombre de cycles dans lesquels elle apparaıt).

Question 24

Definir la resolution d’interblocage.

Answer 24

• Chaque verrou pris a une periode durant laquelle il est non vulnerable.
• A la fin de cette periode, si une autre transaction attend apres le verrou, la transaction qui le possede est annulee et le verrou libere.
• La transaction qui attendait peut maintenant acquerir le verrou et poursuivre son travail.

Question 25

Definir le controle optimiste de la concurrence COC.

Answer 25

• Approche developpee par Kung et Robinson (1981) pour pallier les inconvenients du verrouillage.
• Chaque transaction a une version provisoire des objets qu’elle met a jour (Il est aise d’abandonner une transaction).
• Les lectures sont executees sur la version reelle (pas de lectures contaminees). Il serait possible mais plus difficile de lire dans les versions provisoires.
• Les ecritures sont executees sur la version provisoire.
• Deux ensembles sont associes avec chaque transaction, les objets lus et les objets mis a jour.
• La validation est une phase atomique, on verifie si les
operations ont produit des conflits ou pas. Si la transaction est validee, tous les changements seront rendus permanents. Sinon, les versions provisoires sont simplement abandonnees.

Question 26

Definir les mecanismes de validation des transactions.

Answer 26

• Methode vers l’arriere, verifier qu’aucune transaction
concurrente terminee n’ait ecrit une variable lue par la
transaction a valider.
• Methode vers l’avant, verifier que la transaction courante n’ait pas ecrit une variable deja lue par une transaction concurrente non terminee.
• La phase de validation et d’ecriture doit etre atomique par rapport aux operations des autres transactions. Tout le reste est bloque lorsqu’on valide et termine une transaction.

Question 27

Definir la validation des transactions par estampille de temps.

Answer 27

• Un numero d’ordre (temps) est affecte a chaque transaction au moment du debut de la transaction. Ti precede Tj si i < j.
• A chaque lecture, ou ecriture d’une variable, on note le temps de la transaction.
• Pour une ecriture d’une variable, si la transaction est avant la derniere lecture ou avant la derniere ecriture commise, la transaction est annulee, autrement l’ecriture est acceptee.
• Pour la lecture d’une variable, si la transaction est avant la derniere ecriture commise, la transaction est annulee, autrement la lecture est acceptee.
• Des versions plus elaborees de l’algorithme peuvent lire des anciennes valeurs ou des nouvelles valeurs tentatives et ainsi eviter plusieurs conflits et augmenter la concurrence possible.

Question 28

Que fait un gestionnaire de recuperation en cas de panne?

Answer 28

• Sauver les items de donnees sur support de stockage
permanent.
• Recuperer les donnees apres une panne du processeur.
• Optimiser la performance de la recuperation.
• Liberer l’espace de stockage des donnees intermediaires.

Question 29

Qu’est-ce qu’un stockage permanent?

Answer 29

• Memoire non volatile avec ecriture atomique.
• Disque.
• Disque et cache + pile.
• Disques redondants.
• Disque + ruban.
• Rubans ou disques redondants a distance.

Question 30

Definir le principe de recuperation en cas de panne.

Answer 30

• Toutes les nouvelles valeurs a commettre doivent etre
memorisees pour les appliquer si la transaction est acceptee.
• Toutes les anciennes valeurs doivent etre conservees au cas ou la transaction sera annulee.
• Il faut eventuellement se debarrasser des nouvelles valeurs de transactions annulees, ou des anciennes valeurs de transactions acceptees.

Question 31

Definir la methode du journal (recuperation en cas de panne).

Answer 31

• Ajouter a la fin du journal les nouvelles valeurs pour une transaction, et les marques pour le debut, la fin ou
l’annulation d’une transaction.
• Lorsqu’une transaction est acceptee, une marque est ecrite dans le journal et les nouvelles valeurs sont propagees eventuellement a la base de donnee.
• Pour recuperer: initialiser les donnees, lire a l’envers le
journal, et ajouter toutes les valeurs provenant de transactions acceptees pour les elements de donnees qui n’ont pas encore ete lus du journal.
• Si la recuperation est arretee et recommencee, le resultat n’est pas modifie.
• Lorsque le journal devient trop long, une copie de toutes les valeurs acceptees mais non propagees est ecrite dans un nouveau journal, puis les entrees de transactions en cours sont ajoutees, et le nouveau journal remplace l’ancien.

Question 32

Definir la methode des doubles versions.

Answer 32

• Un espace de donnee suffisant pour les valeurs acceptees et les valeurs tentatives de toutes les transactions en cours est utilise.
• Une carte dit pour chaque variable ou se trouve la valeur acceptee.
• Pour preparer une transaction, les nouvelles valeurs sont stockees et une carte qui y refere est creee.
• Pour accepter une transaction, la nouvelle carte remplace l’ancienne.

Question 33

Qu’est-ce qu’une transaction repartie?

Answer 33

• Une transaction repartie peut faire des requetes a plusieurs serveurs.
• Un serveur peut faire appel a d’autres serveurs pour traiter une requete
• A la fin de la transaction, tous les serveurs doivent soit
completer, soit abandonner (prennent conjointement la meme decision).

Question 34

Quels sont les defis des transactions reparties?

Answer 34

CONTROLE DE LA CONCCURENCE :
• Les transactions doivent etre serialisees globalement sachant que chaque serveur serialise localement les transactions.
• Des interblocages repartis peuvent survenir suite a des cycles de dependances entre differents serveurs.

RECOUVREMENT D’ABANDON DE TRANSACTIONS:
• Chaque serveur doit assurer que ses objets soient recuperables
• Garantir que le contenu des objets reflete bien tous les effets des transactions completees et aucun de celles abandonnees

RECOUVREMENT DE PANNES:
• Un serveur est designe comme coordonnateur, il determine si la transaction est approuvee ou non.
• Chaque serveur doit finaliser les transactions approuvees, meme en cas de panne.

Question 35

Qu’est-ce qu’une transaction repartie simple?

Answer 35

• Contient des operations qui s’adressent a plusieurs serveurs, mais un seul a la fois.
• Les requetes sont envoyees et traitees sequentiellement

Question 36

Que sont des transactions reparties imbriquees?

Answer 36

• Consiste en une hierarchie de sous-transactions
• Les sous-transactions du meme niveau s’executent
simultanement, s’adressent a plusieurs serveurs et sont
elles-memes des transactions imbriquees

Question 37

Definir les protocoles de fin de transactions.

Answer 37

• Assurer l’atomicite d’une transaction repartie: toutes les operations sont executees correctement, ou aucune operation n’est executee (elle est abandonnee).
• Protocole de fin de transaction a une phase: le coordonnateur envoie d’une facon repetitive un message de fin de transaction aux participants jusqu’a ce que tous les participants repondent par un accuse de reception. Ne fonctionne que si tous acceptent (ou tous refusent).
• Protocole de fin de transaction a deux phases: premier tour pour verifier si tous les participants peuvent accepter la transaction, deuxieme tour pour donner le verdict.

Question 38

Definir le fonctionnement du protocole de fin de transaction a deux phases.

Answer 38

Phase de vote:
• Chaque serveur (coordonnateur et participants) vote pour compl´eter ou abandonner la transaction.
Phase de d´ecision:
• Si au moins un des serveurs a vot´e pour abandonner, la
d´ecision sera d’abandonner la transaction.
• Les serveurs ex´ecutent la d´ecision prise par le coordonnateur.

Question 39

Definir le controle de la concurrence pour les transactions reparties.

Answer 39

• Les serveurs qui traitent des transactions reparties doivent s’assurer que leur execution est equivalente a une execution en serie. Si une transaction T est avant U selon un des serveurs, alors elle doit etre dans cet ordre pour tous les serveurs dont les objets sont accedes a la fois par T et U.
• Le controle optimiste de la concurrence avec sa phase de verification atomique ne se prete pas bien aux transactions reparties.
• Le verrouillage fonctionne bien en reparti, chaque serveur controle la concurrence de ses propres objets avec des verrous poses localement et leves seulement a la fin de la transaction.