1-CI2-TEMPS-ETATS.pdf

Architectures Réparties Gestion du temps et des états dans les systèmes distribués Khaled Barbaria [email protected] Faculté des Sciences de Bizerte CI2...

Architectures Réparties Gestion du temps et des états dans les systèmes distribués Khaled Barbaria [email protected] Faculté des Sciences de Bizerte CI2 2023-2024 Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 1/1  Résumé Plan Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 2/1  Introduction Introduction Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 3/1  Introduction Introduction La latence caractérise les systèmes distribués. Les délais sont dûs au moyen de communications. Ces délais sont significatifs et variables À cause des variations des délais, il est possible d’avoir, pour un même protocole : des exécutions différentes des résultats différents. Exemple : un chef envoie un premier message pour demander l’ouverture d’une vanne. Quelques minutes après, il envoie un second message pour demander la fermeture. Selon les délais de transfert, on peut avoir une quantité de liquide variable. Que se passe t’il si les message se dédoublent dans le canal de transmission ? ! Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 4/1  Introduction Évènements dans un système distribué I Évènement On appelle évènement tout changement (significatif) dans l’état d’un système. L’ordre sur les évènements est important, par exemple pour mettre en place une exclusion mutuelle. Cet ordre doit être le même pour tous les processus (sinon il y aura des mal entendus). Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 5/1  Introduction Évènements dans un système distribué II Ordre physique C’est l’ordre établi par un observateur réel, externe au système Deux évènements ne peuvent avoir lieu exactement en même temps. La probabilité que deux évènments aient lieu dans le même instant peut (à prioti) être rendue aussi petite que possible. Il est toujours possible pour un observateur externe suffisamment précis de dire quel évènement précède l’autre. Problème : les processus n’ont pas accès à temps global. Ils disposent uniquement d’horloges locales. La synchronisation des horloges est très difficile voire impossible dans la majorité des cas. Conclusion 1 : les processus n’ont pas accès à l’ordre physique des évènements. Conclusion 2 : les évènements du système distribués peuvent être perçus différement par les processus. D’où le problème de décicions Khaled cohérentes. Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 6/1  Relation de causalité Relation de causalité Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 7/1  Relation de causalité Relation de causalité I Causalité (Wikipedia) "En physique, le principe de causalité affirme que si un phénomène (nommé cause) produit un autre phénomène (nommé effet), alors l’effet ne peut précéder la cause. À ce jour, il n’a pas été mis en défaut par l’expérience" Dans la grande majorité des cas, il n’est pas nécessaire d’avoir une forte synchronisation des horloges. Il faut surtout mettre en évidence la dépendance causale entre les évènements. Il ne jamais contredire le principe de causalité, au risque d’incohérences graves au niveau du SD. Par exemple : l’envoi d’un message au niveau d’un site précède forcément sa réception au niveau d’un autre site. Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 8/1  Relation de causalité Relation de causalité II Relation de précédente causale Trois lois basiques définissent une relation d’ordre (précède) sur les évènements d’un système distribué. Cette relation est notée "→" 1 Ordre local : a→b si a et b sont générés dans cet ordre au niveau d’un même site. 2 Propriété de causalité élémentaire : a→b si a et b sont respectivement les évènements d’envoi et de réception d’un même message. 3 Transitivité : si a→b et b→c alors a→c Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 9/1  Relation de causalité Relation de causalité III Remarques L’ordre local est facilement établi en utilisant un compteur. A l’occurrence d’un évènement, le compteur est incrémenté et sa valeur définit la date de l’évènement. La relation de précédence causale est une relation d’ordre partiel : il est possible d’avoir deux évènements impossibles à classer par cette relation d’ordre : évènements concurrents. Exemple Classer causalement les différents évènements ayant lieu sur les sites S1, S2 et S3. Quels sont les évènements concurrents ? Distinguer la concurrence physique de la concurrence causale. Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 10 / 1  Relation de causalité Relation de causalité IV Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 11 / 1  Relation de causalité Relation de causalité V Si deux évènements se précèdent causalement alors ils se précèdent physiquement. L’inverse n’est pas vrai : deux évènements qui se précèdent réellement peuvent ne pas être classés par la relation d’ordre causal (évènements concurrents). Concurrence logique : pas de causalité Concurrence physique : occurrence en même temps physique. Remarque 1 : Deux évènements peuvent être concurrents logiquement même s’ils ne sont pas concurrents physiquement. Remarque 2 : Si deux évènements sont en concurrence logique, l’ordre de leurs exécutions (avant, après, en même temps) ne change pas le résultat des interactions entre les processus. Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 12 / 1  Relation de causalité Ordonnancement des évènements distribués Horloges Pour établir un ordre sur les évènements, on leurs associe des dates en utilisant des horloges. Les horloges permettront aux processus d’avoir le même ordre sur les évênements. Ceci permettra d’éviter les “malentendus”. Il On souhaite établir un tel ordre en se basant uniquement sur des informations consultables localement. Propriétés des horloges : Monotonie : l’horloge doit toujours avancer (s’il y a des corrections, il faut les appliquer en incrémentant l’horloge. Deux évènements différents ne doivent pas avoir la même date. Cohérence : Si a→ b alors H(a) < H(b) Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 13 / 1  Horloges logiques Horloges logiques Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 14 / 1  Horloges logiques Algorithme de l’horloge logique (de Lamport) I Horloges logiques Objectif : Réaliser une datation des évènements compatible avec la causalité et définissant un ordre total sur les évènements. Un ordre est total s’il permet de décider, pour toute paire d’évènements, quel événement précède l’autre. Algorithme : chaque site Si maintient une variable Hi. Initialisation : Hi ← 0 ∀i Evènement local sur Si : Hi ← Hi + 1 ; Émission d’un message : évènement local, cause une incrémentation de Hi. Le message est estampillé par la date de son émission. ∀m message : H(m) ← H(émission(m)) Réception d’un message m : Hi ← max (Hi ,H(m)) +1 ; Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 15 / 1  Horloges logiques Algorithme de l’horloge logique (de Lamport) II Khaled Barbaria (FSB) Gestion du temps et des états dans les systèmes distribués 2023-2024 16 / 1  Horloges logiques Algorithme de l’horloge logique (de Lamport) III Ordre (total) défini par les horloges logiques Soient deux évènements a et b, H(a) et H(b) désignent leurs dates respectives. L’ordre défini par les horloges de Lamport est noté "«". a«b si : H(a)