Cours 9 Flashcards
(39 cards)
Definir la coherence.
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…
Definir les modeles de coherence.
• 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.
Definir le concept de transaction.
- 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.
Definir la synchronisation simple (sans transaction).
- 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.
Definir les proprietes des transactions.
- 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
Qu’est-ce que le concept de “Panne inevitable mais objets recuperables”?
- 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.
Definir un coordonateur de transaction et comment il fonctionne.
- 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.
Que se passe-t-il en cas de panne du client.
- 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).
Que se passe-t-il en cas de panne du serveur.
• 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.
Definir ce qu’est la serialisation des transactions.
- 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.
Quelles sont les contraintes pour serialiser les transactions?
- 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.
Definir des transactions serialisables.
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.
Definir les approches de controle de la concurrence.
- 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.
Definir le recouvrement apres l’abandon d’une transaction.
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)
Comment se premunir contre les problemes d’ecriture prematurees?
• 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.
Definir les transactions imbriquees.
• 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
Definir le verrouillage.
- 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.
Definir les differentes granularite des verrous.
- 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).
Definir des protocoles de verrouillage.
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.
Definir le gestionnaire de verrous.
- 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
Definir ce que sont les interblocages.
- Implique au moins deux transactions.
* Chaque transaction est bloquee et ne peut etre debloquee que par une autre transaction de l’ensemble.
Definir des solutions pour la prevention d’interblocages.
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.
Definir les mecanismes de detection d’interblocages.
- 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).
Definir la resolution d’interblocage.
- 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.
