Cours 8 Flashcards
Definir la problematique du temps dans les systemes repartis.
• Le temps est tres important dans les systemes repartis. On veut savoir avec precision quand un evenement est arrive.
• Il n’y a pas d’horloge globale pour mesurer le temps a travers le systeme reparti, etant donne le delai pour envoyer par reseau une lecture de temps.
• Algorithmes de synchronisation servent a maintenir la
coherence des donnees reparties, eliminer les mises a jour redondantes, verifier l’authenticite des requetes envoyees au serveur, coordonner certaines operations, tracer l’execution du systeme…
Definir comment les horloges fonctionnent dans les ordinateurs.
• Horloge d’ordinateur: cristal au quartz qui vibre a une
frequence precise (e.g. `a plus ou moins 10−6), avec une
interruption apres un certain nombre d’oscillations, ce qui genere un tic.
• L’horloge est obtenue par un calcul d’un temps initial (heure lue du circuit RTC memorise avec une pile): temps lu au demarrage + nombre de tics depuis ce temps initial x duree d’un tic.
• Les cristaux different d’un ordinateur a l’autre, ce qui cause une desynchronisation entre les systemes multi-ordinateurs, appelee derive des horloges (clock skew).
Definir la problematique de la synchronisation.
- Le temps de propagation est limite par la vitesse de la lumiere.
- Delais lies a la preemption et au traitement des interruptions pour recevoir un message de synchronisation.
- Le GPS (Global Positionning System) donne l’heure juste a 1us pres a travers le monde. La difference d’heure recue entre les satellites est causee par la distance et donne la position par triangulation.
- Plusieurs ordinateurs (20 a 30) sont connectes a des horloges atomiques ou GPS et agissent comme serveurs de temps primaires. On compte quelques milliers de serveurs de temps secondaires qui prennent l’heure des serveurs primaires via l’Internet. La precision est typiquement de 30ms ou mieux 99% du temps.
- Avec une horloge calibrable, il est possible d’obtenir une precision de 1ms sur plusieurs heures.
Definir la synchronisation par la methode de Christian.
• Methode basee sur la synchronisation externe ;
• Elle utilise un serveur central de temps (Time server) qui est connecte a un peripherique recevant des signaux d’une source UTC ;
• Le processus P peut mesurer le temps de reponse a sa
requete, Tr, et affecte a son horloge t + Tr / 2.
Definir la synchronisation par l’algorithme de Berkeley.
- Un coordonnateur (maıtre) interroge les autres ordinateurs (esclaves) dont les horloges sont a synchroniser.
- Les esclaves envoient la valeur de leur horloge au maıtre.
- Le maıtre estime leur temp local en observant le delai d’un aller-retour.
- Il calcule la moyenne des valeurs recues et de sa propre valeur.
- Le maıtre renvoie les ajustements necessaires aux esclaves.
- Si le maıtre tombe en panne, un autre est elu comme maıtre.
Definir le network time protocol (NTP).
- Defini en 1995 dans le RFC 958.
- Le service NTP est fourni par un reseau de serveurs localises a travers l’Internet.
- Serveurs primaires connectes directement a une source de temps UTC.
- Serveurs secondaires synchronises avec les serveurs primaires.
Definir le modele de synchronisation des serveurs (j’imagine que c’est relie a NTP?).
Diffusion selective - multicast:
• Utilise dans des LANs a haut debit.
• Un ou plusieurs serveurs diffusent le temps aux demons s’executant sur d’autres ordinateurs connectes au LAN.
• Les demons qui recoivent les messages affectent a leur horloge les valeurs recues en considerant un faible delai.
Appel de procedure:
• Un serveur accepte les requetes des autres ordinateurs ;
• Renvoie une reponse contenant une estampille (valeur de l’horloge locale).
• Offre une meilleure precision.
Definir le concept d’evenement dans un systeme reparti.
• Un evenement e est l’occurrence d’une seule action.
• Un evenement modifie l’etat d’un processus : L’ordre total unique des ´ev`enements est not´e : • e → e’
si l’evenement e est survenu avant e’ dans Pi
• L’historique de Pi est une s´erie d’evenements survenus dans Pi et ordonnes par la relation :
History(Pi) = hi = … CHECKER LES NOTES
Definir le concept d’horloges logiques.
- Souvent, seul l’ordre entre les evenements importe.
- Dans un meme processus, les evenements sont numerotes avec un compteur.
- Lors d’un envoi de message, la correspondance est faite entre le decompte de l’envoyeur et celui du receveur (Te < Tr).
- En l’absence de messages, on ne peut rien dire sur l’ordre reel entre deux evenements dans des processus differents. On les considere concurrents.
Definir les vecteurs de compteurs d’evenements.
• Vecteur de N entiers initialises a 0 dans chacun des N
processus.
• A chaque evenement dans le processus i, Vi[i] est incremente.
• A chaque message envoye par le processus i, Vi est inclus.
• Lorsque le processus i recoit un vecteur dans un message, il prend pour chaque entree de son vecteur le maximum entre l’entree presente et celle recue (fusion des vecteurs).
• Chaque entree dans le vecteur du processus i indique le dernier evenement dans un autre processus qui peut avoir influence le processus i (lien de causalite).
Definir l’etat global d’un systeme reparti et a quoi il sert.
• Pour verifier si une des proprietes particulieres est verifiee ou non durant son execution.
• Ramasse-miettes (garbage collection), un objet doit etre supprime s’il n’est plus rejoignable.
• Interblocage reparti s’il y a un cycle dans le graphe d’attente de plusieurs processus.
• L’´etat global est important mais difficile a obtenir sans tout figer.
• Une propriete est stable si une fois atteinte elle demeure vraie (e.g. interblocage).
• Un systeme est securitaire pour une propriete si cette
propriete reste verifiee independamment de l’ordre dans lequel les evenements non relies causalement surviennent (e.g. jamais d’interblocage).
• Un systeme est vivace pour une certaine propriete si elle devient eventuellement vraie, independamment de l’ordre dans lequel les evenements non relies causalement surviennent (e.g. une demande de verrou doit etre satisfaite).
Definir ce qu’est un cliche coherent de l’etat global.
- Une coupe (cut) est un sous-ensemble de l’etat global.
- Une coupe C est coherente si pour chaque evenement e qu’elle inclut, tous les evenements qui sont survenus avant la coupe sont inclus
- ∀e ∈ C, f → e ⇒ f ∈ C
Definir l’algorithme pour l’obtention d’une coupe coherente.
• Un processus memorise son etat, envoie un message
demandant la memorisation aux autres processus connectes en sortie, et enregistre tous les messages recus d’autres processus qui n’ont pas encore memorise leur etat.
• Un processus qui re¸coit l’ordre de memorisation fait de meme.
• A la fin, l’etat global est l’etat de chaque processus plus les messages memorises (deja envoyes avant que le processus d’origine n’ait memorise son etat mais recus apres que le processus courant ait memorise son etat).
Definir le calcul d’un cliche coherent possible.
• Il est possible d’enregistrer les evenements (changements d’etat) de tous les processus. Chaque processus envoie une trace a un moniteur central avec pour chaque evenement un vecteur de compteurs d’evenements.
• Un etat global est defini par un numero de dernier evenement pour chaque processus implique. Cet etat est coherent si pour chaque dernier evenement les entrees des vecteurs de compteurs d’evenements sont inferieures ou egales au dernier evenement inclus pour le processus correspondant.
• Dans un systeme synchrone, un etat est coherent si les
differences entre les temps des evenements sont inferieures a l’imprecision des horloges.
Definir les proprietes d’un cliche coherent possible.
- Construire un treillis d’etats globaux possibles (coherents).
- Traverser le treillis un niveau a la fois.
- Si un des etats globaux possibles rejoint a une propriete, cette propriete est possible.
- Si on arrete a chaque etat global possible pour lequel la propriete est vraie et qu’on ne puisse ainsi arriver a l’etat final, cette propriete est necessairement vraie.
