Systèmes Répartis - Chapitre 2 - PDF

# Systèmes Répartis H. Mansouri Laboratoire des Réseaux et des Systèmes Distribués LRSD ## Chapitre 2 Gestion du Temps dans les Systèmes Répartis ## Plan 1. Système distribué: Architecture 2. Système distribué: Processus 3. Système distribué: Canal de communication 4. Système Synchrone / Asyn...

# Systèmes Répartis H. Mansouri Laboratoire des Réseaux et des Systèmes Distribués LRSD ## Chapitre 2 Gestion du Temps dans les Systèmes Répartis ## Plan 1. Système distribué: Architecture 2. Système distribué: Processus 3. Système distribué: Canal de communication 4. Système Synchrone / Asynchrone 5. Etat global d'un système distribué 6. Temps physique 7. Temps physique: Algorithme de Cristian 8. Temps physique: Algorithme de Berkeley 9. Temps physique: Solution distribuée 10. Temps logique 11. Temps logique: chronogramme 12. Temps logique: dépendance causale 13. Graphe de dépendance causale 14. Délivrance FIFO vs Délivrance causale ## Système distribué: Architecture ## Système distribué: Processus Élément logiciel effectuant une tâche, un calcul par exemple, en exécutant un ensemble d'instructions, une instruction correspond à un événement local : * Événements interne * Événements d'émission de message * Événements de réception de message Chaque processus : * Possède un identifiant unique * Possède une mémoire et horloge locales * Pas de connaissance de l'état des autres processus * Les processus du système s'exécutent en parallèle ## Système distribué: Canal de communication **Caractéristiques :** * Uni/Bidirectionnel: sens unique ou dans les deux sens. * Fiable/Non : perd/modifie ou pas des messages. * FIFO/Non: Ordre de réception par rapport à l'émission. * Synchrone/Asynchrone : l'émetteur et le récepteur se synchronisent pour réaliser l'émission et/ou la réception, **Modèle de communication dans les systèmes distribués :** * Bidirectionnel, non Fiable, non FIFO, asynchrone * Bidirectionnel, Fiable, FIFO, synchrone ## Etat global d'un système distribué Un état est la situation dans laquelle se trouve un processus à un instant donné (valeurs des variables, ensembles de données de la mémoire, ensemble de données circulant sur un canal de communication). * État local: propre à un processus * État global: propre au système **Problématique:** Un état global est lié aux valeurs des variables à un temps (instant t), or chaque processus possède une mémoire et horloge physique locales et pas de mémoire et d'horloge globales dans un système distribué. ## Etat global d'un système distribué **Solutions:** * Synchronisation des horloges : * Synchronisation interne * Synchronisation externe * Utilisation de temps logique : * Horloge de Lamport * Horloge Vectorielle de Mattern * Horloge Matricielle ## Temps physique Une convention internationale définit le temps physique ou réel : * UTC: temps universel coordonné * Utilise une horloge atomique (dérive d'une microseconde tous les 3 ans environ) * L'heure universelle est diffusée par radio et satellites * Un ordinateur muni d'un récepteur peut donc synchroniser périodiquement son horloge interne, et fonctionner comme serveur de temps sur un réseau local. ## Temps physique Le temps et l'état global sont difficiles à réaliser dans les SDs : * Les processus sont distribués géographiquement * Le taux d'occurrence des événements est élevé * Les durées d'exécution des événements est très courtes * Le délai de transfère des messages n'est pas négligeable **On ne peut qu'approximer la vision globale en :** * Simulant un temps global via des horloges logiques * Simulant un état global via des Snapshots ## Temps physique * Les horloges physiques des sites dérivent constamment. ## Temps physique: Algorithme de Cristian **Utiliser le temps d'un serveur comme référentiel de temps:** * Un client demande, via un message, le temps à un serveur. * Le serveur répond en envoyant un message contenant le temps courant T. * Le client utilise la valeur T reçue pour mettre à jour son horloge. ## Temps physique: Algorithme de Cristian * (T1-T0)/2 est l'estimation du coût dans chaque direction. * Le client doit donc ajuster son horloge à: Tclient = Tserveur + (T1-T0)/2 * La précision du résultat est donc: ± (T1-T0)/2 - Tmin ## Temps physique: Algorithme de Cristian **Exemple :** * Un client envoie sa requête à 10:10:15.100 (T0) * Il reçoit la réponse du serveur à 10:10:15.900 (T1) * La réponse contient: 10:11:25.300 (Tserveur) * Temps écoulé est: 10:10:15.900 - 10:10:15.100 = 800 ms * Meilleure estimation: Le temps à été généré il y a 400 ms * Ajuster le temps client à: 10:11:25.300 + 400 = 10:11:25.700 * Si le temps min de transit d'un message est 200 ms alors la précision est : (T1-T0)/2-Tmin = 400-200 = ± 200 ms ## Temps physique: Algorithme de Berkeley * Un processus Pi est élu comme un serveur reference de temps. * Pi demande périodiquement le temps des autres processus. * Une fois Pi reçus tous les temps, il élimine les temps des horloges trop déviantes, et calcule la moyenne. * Pi diffuse le temps moyen aux autres processus pour ajuster leurs horloges. ## Temps physique: Solution distribué * Christian et Berkeley sont des algorithmes centralisés. * Chaque processus diffuse son heure au début d'une période de temps. * Chaque processus collecte tous les messages arrivés durant un intervalle. * Chaque processus exécute un même algorithme à partir des n données reçues pour l'obtention d'une heure moyenne. ## Temps logique * Créer un temps qui n'est pas lié au temps physique * Créer un ordonnancement logique en fonction des événements locaux des processus et des messages envoyés et reçus. **Trois approches principales :** * Horloge scalaire (Lamport) * Horloge vectorielle (Mattern) * Horloge matricielle ## Temps logique: chronogramme * Décrit l'ordonnancement temporel des événements des processus et des échanges de messages. * Chaque processus est représenté par une ligne. **Trois types d'événements signalés sur une ligne :** * Émission d'un message à destination d'un autre processus. * Réception d'un message venant d'un autre processus. * Événement interne dans l'évolution du processus ## Temps logique: chronogramme * exy avec x le numéro du processus et y le numéro de l'événement pour le processus, dans l'ordre croissant. ## Temps logique: dépendance causale * Il y a une dépendance causale entre 2 événements si un événement doit avoir lieu avant l'autre. **Notation: ee'** * e→ e', alors une des trois conditions suivantes doit être vérifié: * e précède localement e' sur le même processus. * e est l'émission d'un message, e' est la réception de ce message. * il existe un événement f tel que efet fe' * Evénements concurrents: e || e' = non((e → e') et (e' → e)) ## Temps logique: dépendance causale e11 → e12 e12 → e34 e11 → e35 e12 || e32 ## Graphe de dépendance causale ## Délivrance FIFO vs Délivrance causale * Délivrance FIFO: si 2 messages sont envoyés successivement de Pi vers Pj alors le premier sera délivré avant le deuxième. * Délivrance causale: si l'envoi d'un message m1 par Pi à destination Pn précède (causalement) l'envoi de m2 par Pj à destination Pn alors le m1 sera délivré avant m2 à Pn.