Systèmes Répartis - Chapitre 4 - PDF

# Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD # Chapitre 4 ## État global dans les Systèmes Répartis # Plan 1. État Global: Problématique 2. État Global: Applications 3. État Global: Coupure 4. État Global: Caractéristique 5. État Global: Coh...

# Systèmes Répartis ## H. Mansouri ## Laboratoire des Réseaux et des Systèmes Distribués ## LRSD # Chapitre 4 ## État global dans les Systèmes Répartis # Plan 1. État Global: Problématique 2. État Global: Applications 3. État Global: Coupure 4. État Global: Caractéristique 5. État Global: Cohérence 6. Sauvegarde non coordonnée 7. Sauvegarde coordonnée 8. Datation de Coupure 9. Algoritme de Chandy-Lamport 10. Algoritme de Chandy-Lamport: Exemple ## État Global: Problématique Dans un systèmes réparti, un processus a besoin de connaître les états de tous ces partenaires pour pouvoir prendre une décision locale impactant l'état global du système. ### Problème : - L'absence de mémoire partagé résulte une connaissance incorrecte ou approximative de la valeur des objets distribués. - L'absence d'horloge globale (commune) induit l'absence d'une notion de temps cohérent. - Temps de transfert des messages est non borné. ### Comment donc collecter un état global cohérent ? ## État Global: Problématique Soit un système bancaire distribué gérant deux comptes C1 et C2 reliés chacun par un canal d'entrée et un canal de sortie. Le transfert d'argent est représenté sur le schéma suivant: | C1 | Canal | C2 | Etat global | |--------------|-------------|--------------|---------------------| | 900 $ vide | Vide | 500 $ vide | Cohérent | | 900 $ vide | 200 $ vide | 500 $ vide | Incohérent | | 900 $ Ack | Vide | 700 $ vide | Incohérent | | 700 $ vide | Ack | 700 $ vide | Cohérent | ## État Global: Applications - Détecter des propriétés caractérisant l'exécution (terminaison, inter-blocage, vérification d'assertions, etc.) ⇒ - Effectuer des mesures de performances - Trouver des états cohérents à partir desquels on peut reprendre un calcul distribué en cas de faute ou défaillance. ## État Global: Coupure - Calcul distribué = ensemble E d'événements - Coupure C est un sous-ensemble fini de E tel que: si a et b deux événements du même processus alors : - a ∈ Cet ba⇒bEC - Etat associé à une coupure: l'événement le plus récent pour chaque processus. ## État Global: Coupure The image shows a diagram with three processes P1, P2, P3 and a set of events e11, e12, e13, e14, e15, e21, e22, e23, e24, e31, e32, e33, e34, e35 - State = { e11, e12, e13, e21, e22, e23, e31, e32, e33, e34 } - Coupure = (e13, e23, e34) ## État Global: Caractéristique Chaque processus et chaque canal possède à tout moment un état local : - L'état local d'un processus Pi résulte de son état initial et de la séquence d'événements sur ce processus: - Événement locale - Événement d'émission de message - Événement de réception de message - L'état d'un canal de communication entre deux processus Pi et Pj est l'ensemble des messages en transit sur ce canal, c'est à dire qui ont été émis par le processus Pi et n'ont pas encore été reçus par le processus Pj. ## État Global: Caractéristique - Un état global est l'ensemble des états locaux des processus plus les états des canaux de communication. - GS={C12 + C23 + C33 + m1} The image shows a diagram with three processes P1, P2, P3 and three channels C12, C23, C33. ## État Global: Cohérence - ∀m: Send (m) ∈ GS ^ Receive (m) ∈ GS - ∀m: Receive (m) ∈ GS → Send (m) ∈ GS The image shows two diagrams with three processes P1, P2, P3, one with three messages m1, m2, m3, the second with three messages m1, m2, m3, m4. - The first diagram has a coherent global state. - The second diagram has an incoherent global state. ## État Global: Cohérence - Dans un état global incohérent, il existe au moins un message m dont l'évènement de réception est enregistré mais l'évènement d'émission associé ne l'est pas. Ce message est appelé message orphelin. - Un état global est cohérent si et seulement si pour tout message m, si l'événement de réception de mest enregistrer alors l'évènement d'émission correspondant est enregistré dans l'état global. - Un état global is dit fortement cohérent si tout message émis est reçu. - Un état global est dit cohérent transitaire si au moins un message m dont l'évènement d'émission est enregistré mais l'évènement de réception associé ne l'est pas. ## État Global: Cohérence The image shows a diagram with processes P1, P2, P3 and channel C11, C12, C21, C22, C23, C31, C32, C33. - GS1={C11, C21, C31} est fortement cohérent. - GS2={C11, C22, C32} est incohérent. - GS3={C12, C23, C33} est cohérent transitaire. ## Sauvegarde non coordonnée - Chaque processus sauvegarde son état local sans coordination : - Pas de messages de coordination supplémentaires. - Donner aux processus une autonomie maximale. - ✓ La sauvegarde d'un point de reprise au moment opportun. - X Produire des points de reprise inutiles. - X Possibilité de l'effet domino: The image shows a diagram with processes P1, P2, P3. ## Sauvegarde coordonnée - Les processus se coordonnent avant de sauvegarder leurs états. - ✓ Garantir la cohérence de l'état enregistré. - ✓ Recouvrement simple. - ✓ L'effet domino n'est pas possible. - ✓ Réduire le coûts de stockage. - X Échange de messages de coordination supplémentaires. The image shows a diagram with processes P1, P2, P3. ## Datation de Coupure Horloge de Mattern: permet de dater une coupure - Soit un système réparti de N processus, - C = {e1,..., eN} une coupure, ei l'événement le plus récent pour le processus Pi, - V(ei) la datation de ei et V(C) la datation de la coupure : - V(C) = (max V(e1), ..., max V(en)) - Cest cohérent si : - V(C) = (V(e1)[1], ..., V(ei)[i], ..., V(en)[n]) ## Datation de Coupure - Coupure C1 = (e13, e22, e33) : - V(e13) = (3,0,0), V(e22) = (1,2,1), V(e33) = (0,0,3) - V(C) = (max(3,1,0), max(0,2,0), max(0,1,3)) = (3,2,3) - V(C)[1] = V(e13)[1], V(C)[2] = V(e22)[2], V(C)[3] = V(e33)[3] cohérent The image shows a diagram with three processes P1, P2, P3 and a set of events e11, e12, e13, e14, e15, e21, e22, e23, e24, e31, e32, e33, e34, e35. ## Datation de Coupure - Coupure C2 = (e13, e23, e34): - V(e13) = (3,0,0), V(e23) = (1,3,5), V(e34) = (2,0,4) - V(C) = (max(3,1,2), max(0,3,0), max(0,5,4)) = (3,3,5) - V(C)[1] = V(e13)[1], V(C)[2] = V(e23)[2], V(C)[3] ≠ V(e34)[3] incohérente The image shows a diagram with three processes P1, P2, P3 and a set of events e11, e12, e13, e14, e15, e21, e22, e23, e24, e31, e32, e33, e34, e35. ## Algoritme de Chandy-Lamport L'idée principale : - si nous savons que tous les messages qui ont été envoyés par chaque processus ont été reçus par un autre, nous pouvons alors enregistrer l'état global du système. ### Hypothèses de l'algorithme : - Sur un canal de communication entre chaque deux processus, les messages sont reçus dans le même ordre qu'ils sont envoyés (FIFO). ## Algoritme de Chandy-Lamport ### Fonctionnement: - Tout processus du système distribué peut initier cet algorithme d'enregistrement d'état global (Checkpointing) à l'aide d'un message spécial appelé MARKER. - Ce marqueur traverse le système distribué sur tous les canaux de communication et amène chaque processus à enregistrer son propre état. - À la fin, l'état de l'ensemble du système (état global) est enregistré. - L'algorithme n'interfère pas avec l'exécution normale des processus. ## Algoritme de Chandy-Lamport À l'initialisation de l'algorithme par un processus Pi : - Pi enregistre son propre état local. - Envoi un marqueur sur chaque canal sortant avant d'envoyer tout autre message. - Commencer l'enregistrement de l'état de chaque canal entrant. À la réception d'un marqueur par un processus Pj provenant de Pi : - Si le processus Pj n'a pas encore enregistré son propre état local alors: - Exécuter les Règles d'envoi de marqueur par un processus Pj. - Si le processus Pj a déjà enregistré son état : - Arrêter l'enregistrement de l'état des canaux d'entrée du Pi. À la réception de tous les marqueurs parr un processus Pj : - Valider l'état local de Pj. ## Algoritme de Chandy-Lamport The image shows a detailed implementation of the algorithm. ## Algoritme de Chandy-Lamport: Exemple The image shows a diagram with three processes P1, P2, P3 and a set of events e11, e12, e13, e14, e15, e16, e17, e18, e19, e110, e111, e21, e22, e23, e24, e25, e26, e27, e28, e29, e210, e31, e32, e33, e34, e35, e36, e37, e38, e39, e310, e311. - Un état global est l'ensemble des états locaux des processus plus les états des canaux de communication. ## Algoritme de Chandy-Lamport The image shows a table of local states for each process and channels between them. - L'état global GS={e11, e12, e13, e14, e21, e22, e23, e24, e25, e26, e31, e32, e33, e34, e35, m1, m2, m4, m5, m6}